Multigraph Modeling and Adaptive Large Neighborhood Search for the Vehicle Routing Problem with Time Windows

Abstract : In this paper we propose a multigraph model and a heuristic for the Vehicle Routing Problem with Time Windows (VRPTW). In the classical VRPTW, travel information is commonly represented with a customer-based graph, where an arc is an abstraction of the best road-network path between two nodes. We consider the case when parallel arcs are added to this graph to introduce different compromises between travel time and cost. It has been shown in the literature that this multigraph modeling enables substantial gains in the solution quality, while highly complicating the problem. We develop an Adaptive Large Neighbourhood Search (ALNS) heuristic in which a special data structure and dynamic programming algorithms are used to efficiently address the multigraph setting. Computational experiments on several set of instances demonstrate the effectiveness of our solution method and the impact of alternative paths on the solution quality.
Type de document :
Article dans une revue
Computers & Operations Research, 2019, 104, pp.113-126. 〈10.1016/j.cor.2018.11.001〉
Liste complète des métadonnées

https://hal-emse.ccsd.cnrs.fr/emse-01915904
Contributeur : Dominique Feillet <>
Soumis le : mardi 22 janvier 2019 - 15:01:24
Dernière modification le : vendredi 15 mars 2019 - 01:14:53

Fichier

benticha2019.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Hamza Ben Ticha, Nabil Absi, Dominique Feillet, Alain Quilliot. Multigraph Modeling and Adaptive Large Neighborhood Search for the Vehicle Routing Problem with Time Windows. Computers & Operations Research, 2019, 104, pp.113-126. 〈10.1016/j.cor.2018.11.001〉. 〈emse-01915904〉

Partager

Métriques

Consultations de la notice

77

Téléchargements de fichiers

43