A New Exact Algorithm to Solve the Multi-Trip Vehicle Routing Problem with Time Windows and Limited Duration

Abstract : This article tackles the multi-trip vehicule routing problem with time windows and limited duration. A trip is a timed route such that a succession of trips can be assigned to one vehicle. We provide a two-phase exact algorithm to solve it. The first phase enumerates possible ordered lists of client matching trip maximum duration criterion. The second phase uses a Branch and Price scheme to generate and choose best set of trips to visit all customers. We propose a set covering formulation as the column generation master problem, where columns (variables) represent trips. The sub-problem selects appropriate timing for trips and has a pseudo-polynomial complexity. Computional results on Solomon's benchmarks are presented. The computional times obtained with our new algorithm are much lower than the ones obtained in the sole exact algorithm previously published on this problem.
Type de document :
Rapport
RR-11023, 2011
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00616667
Contributeur : Isabelle Gouat <>
Soumis le : vendredi 4 mai 2012 - 11:00:22
Dernière modification le : jeudi 11 janvier 2018 - 06:26:15
Document(s) archivé(s) le : dimanche 5 août 2012 - 02:27:24

Fichier

LimitedHernandez2011WorkingPap...
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : lirmm-00616667, version 2

Citation

Rodolphe Giroudeau, Oliver Naud, Florent Hernandez, Dominique Feillet. A New Exact Algorithm to Solve the Multi-Trip Vehicle Routing Problem with Time Windows and Limited Duration. RR-11023, 2011. 〈lirmm-00616667v2〉

Partager

Métriques

Consultations de la notice

278

Téléchargements de fichiers

184