Exact method for bi-objective vehicle routing problems
Estèle Glize  1@  , Nicolas Jozefowiez  2@  , Sandra Ulrich Ngueveu  1@  
1 : Laboratoire d'analyse et d'architecture des systèmes [Toulouse]  (LAAS)  -  Website
Centre National de la Recherche Scientifique : UPR8001, Institut National des Sciences Appliquées - Toulouse, Institut National Polytechnique [Toulouse]
7 Av du colonel Roche 31077 TOULOUSE CEDEX 4 -  France
2 : Laboratoire de Conception, Optimisation et Modélisation des Systèmes  (LCOMS)  -  Website
Université de Lorraine : EA7306
LCOMS EA7306, Université de Lorraine, Metz 57000, France -  France

This paper presents an original and generic column generation-based exact method to solve bi-objective vehicle routing problems.The talk will first provide a quick overview of exact methods on bi-objective problems and in particular on vehicle routing problems. Then mathematical formulations for these problems will be introduced, either with two explicit objectives or with ε-constraint linearization. Theorems on the structure of bi-objective vehicle routing problems will be presented, and based on them, new rules to explore the solution space will be introduced. The resulting exact method takes advantages of different techniques to discard some insignificant columns and save the current state of column generation. Numerical results on the two following case-studies show the efficiency of the approach with regards to the state-of-the art: bi-objective vehicle routing with time windows and with two integer costs and on bi-objective team-orienteering problem with time windows

Online user: 1 RSS Feed