Article (Scientific journals)
Large neighborhood search for multi-trip vehicle routing
François, Véronique; Arda, Yasemin; Crama, Yves et al.
2016In European Journal of Operational Research, 255 (2), p. 422-441
Peer Reviewed verified by ORBi
 

Files


Full Text
LNS for MTVRP - Preprint v2.pdf
Author preprint (536.97 kB)
Download

All documents in ORBi are protected by a user license.

Send to



Details



Keywords :
Vehicle routing; Multi-trip; Large neighborhood search; Algorithm configuration
Abstract :
[en] 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.
Research Center/Unit :
QuantOM - Centre for Quantitative Methods and Operations Management
Disciplines :
Production, distribution & supply chain management
Author, co-author :
François, Véronique ;  Université de Liège > HEC-Ecole de gestion : UER > UER Opérations : Supply Chain Management
Arda, Yasemin  ;  Université de Liège > HEC-Ecole de gestion : UER > UER Opérations : Supply Chain Management
Crama, Yves  ;  Université de Liège > HEC-Ecole de gestion : UER > Recherche opérationnelle et gestion de la production
Laporte, Gilbert;  HEC Montréal > Département de sciences de la décision
Language :
English
Title :
Large neighborhood search for multi-trip vehicle routing
Publication date :
01 December 2016
Journal title :
European Journal of Operational Research
ISSN :
0377-2217
eISSN :
1872-6860
Publisher :
Elsevier Science, Amsterdam, Netherlands
Volume :
255
Issue :
2
Pages :
422-441
Peer reviewed :
Peer Reviewed verified by ORBi
Tags :
CÉCI : Consortium des Équipements de Calcul Intensif
Funders :
BELSPO - Service Public Fédéral de Programmation Politique scientifique
NSERC - Natural Sciences and Engineering Research Council
Commentary :
Available online : http://www.sciencedirect.com/science/article/pii/S0377221716303034
Available on ORBi :
since 03 July 2016

Statistics


Number of views
227 (39 by ULiège)
Number of downloads
393 (8 by ULiège)

Scopus citations®
 
56
Scopus citations®
without self-citations
53
OpenCitations
 
32
OpenAlex citations
 
51

Bibliography


Similar publications



Contact ORBi