Large Neighborhoods with Implicit Customer Selection for Vehicle Routing Problems with Profits
Thibaut Vidal (),
Nelson Maculan (),
Luiz Satoru Ochi () and
Puca Huachi Vaz Penna ()
Additional contact information
Thibaut Vidal: Departamento de Informática – Pontifícia Universidade Católica do Rio de Janeiro, Rio de Janeiro 22451-900, Brazil
Nelson Maculan: Universidade Federal do Rio de Janeiro, Rio de Janeiro 21941-972, Brazil
Luiz Satoru Ochi: Instituto de Computação – Universidade Federal Fluminense, Niterói 24210-240, Brazil
Puca Huachi Vaz Penna: Instituto de Computação – Universidade Federal Fluminense, Niterói 24210-240, Brazil
Transportation Science, 2016, vol. 50, issue 2, 720-734
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.
Keywords: vehicle routing; team orienteering; prize collecting VRP; local search; large neighborhoods; dynamic programming (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (12)
Downloads: (external link)
http://dx.doi.org/10.1287/trsc.2015.0584 (application/pdf)
Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.
Export reference: BibTeX
RIS (EndNote, ProCite, RefMan)
HTML/Text
Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:50:y:2016:i:2:p:720-734
Access Statistics for this article
More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().