Branch-and-price algorithms for the bi-objective vehicle routing problem

Nicolas Jozefowiez (1) , Sandra Ulrich Ngueveu (2, 3) , Estèle Glize (3)

1 LCOMS - Laboratoire de Conception, Optimisation et Modélisation des Systèmes
2 Toulouse INP - Institut National Polytechnique (Toulouse)
3 LAAS-ROC - Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes

This paper presents an exact method for the bi-objective Vehicle Routing Problem (BOVRP) where the objectives are to minimize two different lengths on the routes like the travel distance and the cost of the journey. These two objectives can be conflictive: in motor vehicle, the travel time differs from the fuel consumption. Many industrials are interested in finding a good compromise. So the BOVRP presenting two different costs c 1 and c 2 on each route is a relevant challenge. The multi-objective VRP (MOVRP) is more and more studied. But due to its complexity and the possibility of objective functions (number of vehicles, fairness...), this particular case has not been explored yet. A complete survey of MOVRP can be found in Jozefowiez et al. [1]. Reiter and Gutjahr [2] has solved exactly the BOVRP minimizing the distance and the length of the longest route using an adaptive-constraint method. In the larger scope of multi-objective integer programming, exact methods are divided into two classes: methods working on the feasible solutions space [3] and those working on the objective functions space [4]. These last methods solve a sequence of mono-objective problem and so, lean on their efficiency on single-objective integer programming solver. The-constraint method is one of the most effective objective space search algorithm [2, 5]. The main idea of this paper is to propose a competitive method for finding the complete and exact Pareto front of BOVRP where the objectives are to minimize the total lengths of the journey, mainly in clustered graph.

Domaines: Recherche opérationnelle [math.OC]; Combinatoire [math.CO]

Nicolas Jozefowiez, Sandra Ulrich Ngueveu, Estèle Glize. Branch-and-price algorithms for the bi-objective vehicle routing problem. Odysseus 2018 Seventh International Workshop on Freight Transportation and Logistics, Jun 2018, Cagliari, Italy. ⟨hal-01880521⟩