A new exact algorithm to solve the multi-trip vehicle routing problem with time windows and limited duration - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Article Dans Une Revue 4OR: A Quarterly Journal of Operations Research Année : 2014

A new exact algorithm to solve the multi-trip vehicle routing problem with time windows and limited duration

Résumé

This article tackles the multi-trip vehicle 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 an exact two-phase algorithm to solve it. The first phase enumerates possible ordered lists of clients which match the maximum trip duration criterion. The second phase uses a Branch and Price scheme to generate and choose a best set of trips so that all customers are visited. 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. Computational results on Solomon's benchmarks are presented. The computational times obtained with our new algorithm are much lower than the ones recently obtained in the only two studies published on this problem to date.
Fichier principal
Vignette du fichier
pub00039780.pdf (755.51 Ko) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

lirmm-01056150 , version 1 (16-05-2020)

Identifiants

Citer

Rodolphe Giroudeau, Dominique Feillet, Florent Hernandez, Olivier Naud. A new exact algorithm to solve the multi-trip vehicle routing problem with time windows and limited duration. 4OR: A Quarterly Journal of Operations Research, 2014, 12 (3), pp.235-259. ⟨10.1007/s10288-013-0238-z⟩. ⟨lirmm-01056150⟩
512 Consultations
428 Téléchargements

Altmetric

Partager

More