In this thesis, we study routing problems that arise in the context of last mile delivery when multiple delivery options are proposed to the customers. The most common option to deliver packages is home/workplace delivery. Besides, the delivery can be made to pick-up points such as dedicated lockers or stores. In recent years, a new concept called trunk/in-car delivery has been proposed. Here, customers' packages can be delivered to the trunks of cars. Our goal is to model and develop efficient solution approaches for routing problems in this context, in which each customer can have multiple shipping locations. First, we survey non-Hamiltonian routing problems. Then, we study the single-vehicle case in the considered context, which is modeled as a Generalized Traveling Salesman Problem with Time Windows (GTSPTW). Four mixed integer linear programming formulations and an efficient branch-and-cut algorithm are proposed. Finally, we study the multi-vehicle case which is denoted Generalized Vehicle Routing Problem with Time Windows (GVRPTW). An efficient column generation based heuristic is proposed to solve it.
Rapporteurs : M. Yves Crama, Professeur, HEC Liège M. Guido Perboli, Professeur associé, Politecnico di Torino Membres : Mme Claudia Archetti, Professeur associée, ESSEC Paris M. Dominique Feillet, Professeur, Ecole des Mines de Saint-Etienne Mme Martine Labbé, Professeur, Université Libre de Bruxelles Mme Caroline Prodhon, Maître de conférences HDR, Université de Technologie de Troyes Directeur de thèse : M. Frédéric Semet, Professeur, Centrale Lille Invités ： M. Diego Cattaruzza, Maître de conférences, Centrale Lille M. Maxime Ogier, Maître de conférences, Centrale Lille
Thesis of the team INOCS defended on 14/10/2019
français
English