vehicle routing; multiple trips; large neighborhood search
Abstract :
[en] We consider two large neighborhood search approaches for the multi-trip vehicle routing problem, where each vehicle can perform several routes during the working shift to serve a set of customers. The problem specifically arises when customers are close to each other and/or when the demands are large.
A common approach in the literature consists in solving this problem by mixing vehicle routing heuristics with bin packing routines to assign routes to vehicles. We compare this approach with the use of specific operators designed to tackle the routing and the assignment aspects of the problem simultaneously. We provide several best known solutions for benchmark instances.
At the end of the work, we give insights about the proposed algorithm configurations by analyzing the behavior of several method components.
Research Center/Unit :
QuantOM
Disciplines :
Quantitative methods in economics & 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