A relax-and-repair heuristic for the Swap-Body Vehicle Routing Problem

Nabil Absi 1 Diego Cattaruzza 1, 2 Dominique Feillet 1 Sylvain Housseman 1
2 INOCS - Integrated Optimization with Complex Structure
ULB - Université Libre de Bruxelles [Bruxelles], Inria Lille - Nord Europe, CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189
Abstract : In this paper we address the Swap-Body Vehicle Routing Problem, a variant of the Truck and Trailer Routing Problem. It was introduced in the VeRoLog Challenge 2014. We develop a solution approach that we coin Relax-and-Repair. It consists in solving a relaxed version of the SB-VRP and deriving a feasible solution by repairing the relaxed one. We embed this approach within a population-based heuristic. During computation we store all feasible routes in order to derive better solutions by solving a set-partitioning problem. In order to take advantages of nowadays multi-core machines, our algorithm is designed as a collaborative parallel population-based heuristic. Experimental results show that our relax-and-repair algorithm is very competitive and point the impact of each phase on the quality of the obtained solutions. The advantage of our approach is that it can be adapted to solve complex industrial routing problems.
Type de document :
Article dans une revue
Annals of Operations Research, Springer Verlag, 2017, 253 (2), pp.957-978
Liste complète des métadonnées

Littérature citée [23 références]  Voir  Masquer  Télécharger

https://hal-emse.ccsd.cnrs.fr/emse-01245335
Contributeur : Dominique Feillet <>
Soumis le : mercredi 3 février 2016 - 10:48:48
Dernière modification le : mardi 23 octobre 2018 - 14:36:10
Document(s) archivé(s) le : samedi 12 novembre 2016 - 04:26:05

Fichier

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

Identifiants

  • HAL Id : emse-01245335, version 1

Collections

Citation

Nabil Absi, Diego Cattaruzza, Dominique Feillet, Sylvain Housseman. A relax-and-repair heuristic for the Swap-Body Vehicle Routing Problem. Annals of Operations Research, Springer Verlag, 2017, 253 (2), pp.957-978. 〈emse-01245335〉

Partager

Métriques

Consultations de la notice

245

Téléchargements de fichiers

670