Column Generation for Bi-Objective Vehicle Routing Problems with a Min-Max Objective

Boadu Mensah Sarpong 1 Christian Artigues 1 Nicolas Jozefowiez 1
1 LAAS-MOGISA
LAAS - Laboratoire d'analyse et d'architecture des systèmes [Toulouse]
Abstract : Column generation has been very useful in solving single objective vehicle routing problems (VRPs). Its role in a branch-and-price algorithm is to compute a lower bound which is then used in a branch-and-bound framework to guide the search for integer solutions. In spite of the success of the method, only a few papers treat its application to multi-objective problems and this paper seeks to contribute in this respect. We study how good lower bounds for bi-objective VRPs in which one objective is a min-max function can be computed by column generation. A way to model these problems as well as a strategy to effectively search for columns are presented. We apply the ideas to two VRPs and our results show that strong lower bounds for this class of problems can be obtained in "reasonable" times if columns are intelligently managed. Moreover, the quality of the bounds obtained from the proposed model are significantly better than those obtained from the corresponding "standard" approach.
Type de document :
Communication dans un congrès
Daniele Frigioni and Sebastian Stiller. ATMOS - 13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems - 2013, Sep 2013, Sophia Antipolis, France. Schloss Dagstuhl―Leibniz-Zentrum fuer Informatik, 33, pp.137--149, 2013, OpenAccess Series in Informatics (OASIcs). 〈10.4230/OASIcs.ATMOS.2013.137〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00871741
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : jeudi 10 octobre 2013 - 11:59:41
Dernière modification le : mercredi 28 février 2018 - 10:23:11
Document(s) archivé(s) le : vendredi 7 avril 2017 - 08:58:46

Fichier

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

Identifiants

Citation

Boadu Mensah Sarpong, Christian Artigues, Nicolas Jozefowiez. Column Generation for Bi-Objective Vehicle Routing Problems with a Min-Max Objective. Daniele Frigioni and Sebastian Stiller. ATMOS - 13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems - 2013, Sep 2013, Sophia Antipolis, France. Schloss Dagstuhl―Leibniz-Zentrum fuer Informatik, 33, pp.137--149, 2013, OpenAccess Series in Informatics (OASIcs). 〈10.4230/OASIcs.ATMOS.2013.137〉. 〈hal-00871741〉

Partager

Métriques

Consultations de la notice

200

Téléchargements de fichiers

247