Titre de la Thèse :
" Unified matheuristic for solving rich vehicle routing problems"
Vendredi 13 juin 2014 - 14 h 00 - Grand Amphithéâtre - Ecole Centrale de Lille
Le jury est composé de :
Directeurs de Thèse :
Frédéric SEMET, Ecole Centrale de Lille
Mahdi KHEMAKHEM, Université de Sfax
Habib CHABCHOUB, Université de Sfax
Bernard GENDRON, Université de Montréal
Saoussen KRICHEN, Université de Jendouba
Jorge E. MENDOZA, Université Catholique de l’Ouest
Nenad MLADENOVIC, Brunel University
Saïd HANAFI, Université de Valenciennes
The purpose of this thesis is to develop a solution framework for Rich vehicle Routing Problems (RVRPs). We first provide a comprehensive survey of the RVRP literature as well as a taxonomy. Then we propose an elaborate definition of RVRPs. Selected papers addressing various variants are classified according to the proposed taxonomy. A cluster analysis based on two discriminating criteria is performed and leads to define RVRPs.
In the second part of this thesis, we described a unified column generation based matheuristic to solve RVRPs. The proposed method is able to deal with a broad range of constraints and is then used to solve a set of basic and rich VRPs. The RVRP studied in this thesis concerns industries where goods are inhomogeneous and should be segregated during transportation. This feature motivates the use of multi-compartment vehicles. Specifically, we are interested in solving a multi-depot multi-compartment multi-commodity vehicle routing problem with time windows (MDMCMCm-VRPTW). First, we introduce a three-index vehicle flow formulation for this problem and we apply the Dantzig-Wolfe (DW) decomposition on this formulation. This decomposition gives raise to a more tractable integer problem. We propose a unified column generation heuristic cooperating with an effective variable neighborhood search (VNS) matheuristic to solve the pricing problem. The VNS combines several removal and insertion routing heuristics as well as computationally efficient constraint checking procedures in order to solve the MDMCMCm-VRPTW for a single vehicle. The loading problem related to the use of a multi-compartment vehicle is addressed carefully. Two loading neighborhoods based on the solution of mathematical programs are proposed to intensify the search. They interact with the heuristic routing neighborhoods, as it is common in matheuristics. On a set of 191 instances of less complex routing problems, the unified matheuristic turns to be competitive. A sensitivity analysis, performed on more complex generated instances reveals the importance of some algorithmic features and of loading neighborhoods for reaching high quality solutions. The VNS based matheuristic is embedded in a column generation heuristic to solve the MDMCMCm-VRPTW. We propose a set of techniques to improve the solution quality as well as an exact post-processing method to optimize the assignment of customers to vehicle routes. While developing the unified matheuristic, we focus on the definition of a generic data structure which offers flexibility when it comes to extend or to specialize the proposed matheuristic.
Last, we tackle the real case study that motivated this work. We introduce, model and solve to optimality a rich multi-product, multi-period and multi-compartment vehicle routing problem with a required compartment cleaning activity. This real-life application arises in the oil collection process in Tunisia. We propose an exact branch-and-cut algorithm to solve the problem. We evaluate the performance of the algorithm on real data sets under different transportation scenarios to demonstrate to our industrial partner the advantages of using multi-compartment vehicles.