Large neighborhoods with implicit customer selection for vehicle routing problems with profits.
No Thumbnail Available
Date
2015
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
We consider several vehicle routing problems (VRP) with profits, which seek to select a subset of customers,
each one being associated with a profit, and to design service itineraries. When the sum of profits is maximized
under distance constraints, the problem is usually called the team orienteering problem. The capacitated
profitable tour problem seeks to maximize profits minus travel costs under capacity constraints. Finally, in the
VRP with a private fleet and common carrier, some customers can be delegated to an external carrier subject to
a cost. Three families of combined decisions must be taken: customer’s selection, assignment to vehicles, and
sequencing of deliveries for each route.
We propose a new neighborhood search for these problems, which explores an exponential number of solutions
in pseudo-polynomial time. The search is conducted with standard VRP neighborhoods on an exhaustive
solution representation, visiting all customers. Since visiting all customers is usually infeasible or suboptimal,
an efficient select algorithm, based on resource constrained shortest paths, is repeatedly used on any new route
to find the optimal subsequence of visits to customers. The good performance of these neighborhood structures
is demonstrated by extensive computational experiments with a local search, an iterated local search, and
a hybrid genetic algorithm. Intriguingly, even a local-improvement method to the first local optimum of this
neighborhood achieves an average gap of 0.09% on classic team orienteering benchmark instances, rivaling with
the current state-of-the-art metaheuristics. Promising research avenues on hybridizations with more standard
routing neighborhoods are also open.
Description
Keywords
Vehicle routing, Team orienteering, Local search, Large neighborhoods
Citation
VIDAL, T. V. G. et al. Large neighborhoods with implicit customer selection for vehicle routing problems with profits. Transportation Science, v. 50, p. 150319104929005-734, 2015. Disponível em: <https://pubsonline.informs.org/doi/10.1287/trsc.2015.0584#>. Acesso em: 16 jan. 2018.