Méthodes de modélisation et d’optimisation par recherche à voisinagesvariables pour le problème de collecte et de livraison avec transbordement

The thesis is conducted under the ANR project PRODIGE andit is focused on seeking strategies allowing the optimization of transportin general and road freight transport in particular. The transportation problemsupport for this study is the pickup and delivery problem with transshipment.This problem generalizes several classical transportation problems.Transshipment is used as optimization and flexibility leverage. Tostudy and solve this problem, analyzes are performed along three axes :the first objective concerns the development of an analytical model, moreaccurately a mathematical model with mixed variables. This model allowsproviding optimal solution to the decision maker, but has the disadvantageof requiring a time resolution that grows exponentially with the sizeof the problem. This limitation is overcome by the second line of the studythat solves the transportation problem studied by an approximate optimizationmethod while ensuring satisfactory solutions. The method usedis a mataheuristic broadly followed the variables neighborhoods researchprinciples. In the third objective, the overall results obtained in the thesisare tested in real transport situation via the PRODIGE project.La présente thèse se déroule dans le cadre du projet ANR PRODIGEet est axée sur la recherche de stratégies permettant l’optimisationdu transport en général et du transport routier de marchandises en particulier.Le problème de transport support de cette étude est le problèmede collecte et livraison avec transbordement. Ce problème généralise plusieursproblèmes de transports classiques. Le transbordement y est utilisécomme levier de flexibilité et d’optimisation. Pour analyser et résoudre ceproblème, les analyses sont effectuées suivant trois axes : le premier axeconcerne l’élaboration d’un modèle analytique plus précisément d’un modèlemathématique en variables mixtes. Ce modèle permet de fournir dessolutions optimales au décisionnaire du transport mais présente l’inconvénientde nécessiter un temps de résolution qui croit exponentiellementavec la taille du problème. Cette limitation est levée par le deuxième axed’étude qui permet de résoudre le problème de transport étudié par uneméthode d’optimisation approchée tout en garantissant des solutions satisfaisantes.La méthode utilisée est une métaheuristique inspirée de larecherche à voisinages variables (VNS). Dans le troisième axe, l’ensembledes résultats obtenus dans la thèse sont testés en situation de transportsréels via le projet PRODIGE