Branch-and-price algorithms for the solution of the Multi-Trip Vehicle Routing Problem with Time Windows

Abstract : We investigate the exact solution of the vehicle routing problem with time windows, where multiple trips are allowed for the vehicles. In contrast to previous works in the literature, we specifically consider the case in which it is mandatory to visit all customers and there is no limitation on duration. We develop two branch-and-price frameworks based on two set covering formulations: a traditional one where columns (variables) represent routes, that is, a sequence of consecutive trips, and a second one in which columns are single trips. One important difficulty related to the latter is the way mutual temporal exclusion of trips can be handled. It raises the issue of time discretization when solving the pricing problem. Our dynamic programming algorithm is based on concept of groups of labels and representative labels. We provide computational results on modified small-sized instances (25 customers) from Solomon’s benchmarks in order to evaluate and compare the two methods. Results show that some difficult instances are out of reach for the first branch-and-price implementation, while they are consistently solved with the second.
Type de document :
Article dans une revue
European Journal of Operational Research, Elsevier, 2016, 249 (2), pp.551-559. 〈10.1016/j.ejor.2015.08.040〉
Liste complète des métadonnées

https://hal-emse.ccsd.cnrs.fr/emse-01186966
Contributeur : Dominique Feillet <>
Soumis le : mardi 25 août 2015 - 17:12:40
Dernière modification le : mardi 23 octobre 2018 - 14:36:10

Identifiants

Citation

Florent Hernandez, Dominique Feillet, Rodolphe Giroudeau, Olivier Naud. Branch-and-price algorithms for the solution of the Multi-Trip Vehicle Routing Problem with Time Windows. European Journal of Operational Research, Elsevier, 2016, 249 (2), pp.551-559. 〈10.1016/j.ejor.2015.08.040〉. 〈emse-01186966〉

Partager

Métriques

Consultations de la notice

199