Models and Algorithms for Last Mile Delivery Problems with Multiple Shipping Options

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 itDans cette thèse, nous étudions les problèmes de tournées de véhicules dans le contexte de la livraison du dernier kilomètre lorsque plusieurs options de livraisons sont proposées aux clients. Le mode de livraison le plus commun est la livraison à domicile ou au travail. La livraison peut également être effectuée dans des points de collecte tels que des consignes ou des magasins. Ces dernières années, un nouveau concept appelé livraison dans le coffre / dans la voiture a été proposé. Avec ce mode de livraison, les colis des clients peuvent être livrés directement dans les coffres des voitures. Notre objectif est de modéliser et de développer des approches de résolution efficaces pour les problèmes de routage dans ce contexte, dans lequel chaque client peut disposer de plusieurs lieux potentiels de livraison. Premièrement, nous proposons un état de l'art sur les problèmes de routage non-Hamiltoniens. Ensuite, nous étudions le cas avec un seul véhicule, qui est modélisé comme un problème du voyageur de commerce généralisé avec fenêtres de temps (GTSPTW). Quatre formulations en programme linéaire à variables mixtes et un algorithme efficace de branch-and-cut sont proposés. Ensuite, nous étudions le cas multi-véhicules, dénommé problème de tournées de véhicules généralisé avec fenêtres de temps (GVRPTW). Une heuristique efficace basée sur la génération de colonnes est proposée pour le résoudr