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

Abstract

Dans 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ésoudre