Large neighborhoods with implicit customer selection for vehicle routing problems with profits.

Simple item page
dc.contributor.authorVidal, Thibaut Victor Gaston
dc.contributor.authorMaculan Filho, Nelson
dc.contributor.authorOchi, Luiz Satoru
dc.contributor.authorPenna, Puca Huachi Vaz
dc.date.accessioned2018-01-30T13:15:30Z
dc.date.available2018-01-30T13:15:30Z
dc.date.issued2015
dc.description.abstractWe 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.pt_BR
dc.identifier.citationVIDAL, 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.pt_BR
dc.identifier.doihttp://dx.doi.org/10.1287/trsc.2015.0584
dc.identifier.issn1526-5447
dc.identifier.urihttp://www.repositorio.ufop.br/handle/123456789/9377
dc.identifier.uri2https://pubsonline.informs.org/doi/10.1287/trsc.2015.0584#pt_BR
dc.language.isoen_USpt_BR
dc.rightsrestritopt_BR
dc.subjectVehicle routingpt_BR
dc.subjectTeam orienteeringpt_BR
dc.subjectLocal searchpt_BR
dc.subjectLarge neighborhoodspt_BR
dc.titleLarge neighborhoods with implicit customer selection for vehicle routing problems with profits.pt_BR
dc.typeArtigo publicado em periodicopt_BR
Files
Original bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
ARTIGO_LargeNeighborhoodsImplicit.pdf
Size:
713.71 KB
Format:
Adobe Portable Document Format
Download
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
924 B
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
DECOM - Artigos publicados em periódicos