Optimization of pick up and delivery problems with transfers

Cette thèse étudie des variantes de problèmes de planification de tournées rencontrées en milieu urbain. Elle les situe par rapport aux travaux antérieurs dans le domaine en vue d’une modélisation pertinente s’appliquant aux problèmes de transport de personnes et de marchandises. Elle relève de la littérature consacrée à la résolution de problèmes de type collecte et livraison (Pickup and Delivery-PDP) et transport à la demande (Dial-A-Ride-DARP). Dans ces travaux, nous nous intéressons aux tournées autorisant les transferts de demandes entre véhicules, et en particulier à la présence de synchronisations entre véhicules (ou modes de transport) à la fois spatiale et temporelle, dans un contexte déjà fortement contraint par des fenêtres temporelles associées aux différents types d’acteurs (fournisseurs, clients, transporteurs), avec une flotte de véhicules hétérogène de capacités limitées, et plusieurs visites possibles par site. Ce type de variantes est abordé ici en version statique, lorsque l’on résout un problème dans lequel toutes les demandes sont connues à l’avance, mais dans une perspective d’utilisation dynamique des algorithmes au sein d'une plate-forme de services contextualisés.La thèse propose tout d’abord une formulation exacte mono-objectif (en Programmation Linéaire en Nombres Mixtes) dans laquelle on minimise classiquement la distance totale parcourue. La complexité importante de ce modèle, compte tenu du problème traité, nous a conduit dans un deuxième temps au développement d'algorithmes basés sur des heuristiques ou sur une métaheuristique hybridée avec des méthodes exacte et approchées, dans le but de permettre un passage à l'échelle. Ces algorithmes sont conçus comme une version relaxée du problème de tournées initial avec transferts, qui devient alors multi-objectifs, la seconde catégorie de critères traduisant le fait d'autoriser des retards sur les demandes et les sites visités, tout en cherchant à les minimiser. Les différentes contributions sont éprouvées par des tests sur des instances générées ou issues de la littérature. L’analyse des résultats obtenus ouvre la voie vers d’intéressantes perspectives de recherche dans le domaine considéré.This thesis studies variants of tour planning problems encountered in urban areas. It situates them in relation to previous work in the field with a view to relevant modelling for passenger and freight transport problems. It is based on the literature devoted to the resolution of Pickup and Delivery-PDP (Pickup and Delivery-PDP) and Dial-A-Ride-DARP (Dial-A-Ride-DARP) problems. In this work, we are interested in routes allowing demand transfers between vehicles, and in particular in the presence of synchronisation between vehicles (or modes of transport) both spatially and temporally, in a context already strongly constrained by time windows associated with different types of actors (suppliers, customers, transporters), with a heterogeneous fleet of vehicles of limited capacity, and several possible visits per site. This type of variant is addressed here in a static version, when solving a problem in which all the requests are known in advance, but in a perspective of dynamic use of the algorithms within a platform of contextualized services. The thesis first proposes an exact mono-objective formulation (in Linear Programming in Mixed Numbers) in which the total distance travelled is classically minimized. The important complexity of this model, taking into account the problem treated, led us in a second step to the development of algorithms based on heuristics or metaheuristics hybridized with exact and approximate methods, in order to allow a scaling. These algorithms are designed as a relaxed version of the initial tour problem with transfers, which then becomes multi-objective, the second category of criteria reflecting the fact of allowing delays on requests and sites visited, while seeking to minimize them. The various contributions are tested by means of tests on instances generated or taken from the literature. The analysis of the results obtained opens the way to interesting research perspectives in the field under consideration