Large neighborhood search for multi-trip vehicle routing

Véronique François, Yasemin Arda, Yves Crama and Gilbert Laporte

European Journal of Operational Research, 2016, vol. 255, issue 2, 422-441

Abstract: We consider the multi-trip vehicle routing problem, in which each vehicle can perform several routes during the same working shift to serve a set of customers. The problem arises when customers are close to each other or when their demands are large. A common approach consists of solving this problem by combining vehicle routing heuristics with bin packing routines in order to assign routes to vehicles. We compare this approach with a heuristic that makes use of specific operators designed to tackle the routing and the assignment aspects of the problem simultaneously. Two large neighborhood search heuristics are proposed to perform the comparison. We provide insights into the configuration of the proposed algorithms by analyzing the behavior of several of their components. In particular, we question the impact of the roulette wheel mechanism. We also observe that guiding the search with an objective function designed for the multi-trip case is crucial even when exploring the solution space of the vehicle routing problem. We provide several best known solutions for benchmark instances.

Keywords: Transportation; Vehicle routing; Multi-trip; Large neighborhood search; Automatic algorithm configuration (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (16)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221716303034
Full text for ScienceDirect subscribers only

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:eee:ejores:v:255:y:2016:i:2:p:422-441

DOI: 10.1016/j.ejor.2016.04.065

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().