Reference : Large neighborhood search for multi-trip vehicle routing
Scientific journals : Article
Business & economic sciences : Production, distribution & supply chain management
Large neighborhood search for multi-trip vehicle routing
François, Véronique mailto [Université de Liège > HEC-Ecole de gestion : UER > UER Opérations : Supply Chain Management >]
Arda, Yasemin mailto [Université de Liège > HEC-Ecole de gestion : UER > UER Opérations : Supply Chain Management >]
Crama, Yves mailto [Université de Liège > HEC-Ecole de gestion : UER > Recherche opérationnelle et gestion de la production >]
Laporte, Gilbert mailto [HEC Montréal > Département de sciences de la décision > > >]
European Journal of Operational Research
Elsevier Science
Yes (verified by ORBi)
The Netherlands
[en] Vehicle routing ; Multi-trip ; Large neighborhood search ; Algorithm configuration
[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.
QuantOM - Centre for Quantitative Methods and Operations Management
CECI ; Politique Scientifique Fédérale (Belgique) = Belgian Federal Science Policy ; Canadian National Sciences and Engineering Research Council
Researchers ; Professionals ; Students
Available online :

File(s) associated to this reference

Fulltext file(s):

Open access
LNS for MTVRP - Preprint v2.pdfAuthor preprint524.38 kBView/Open

Bookmark and Share SFX Query

All documents in ORBi are protected by a user license.