Cette thèse porte sur deux problèmes de tournées de véhicules avec collecte et livraison, transferts et horizon temporel. Elle fournit des modèles, des résultats théoriques et des méthodes pour les gérer.

Le premier problème est un problème de repositionnement d'objets avec transferts et horizon temporel. Un modèle multiflot dans un réseau étendu dans le temps est introduit et on propose une approche de « projection et remontage » pour gérer ce modèle. Tout d'abord, on dérive un « modèle projeté » qui gère les contraintes de temps de manière implicite et qui fournit une borne inférieure pour le coût d'une solution optimale du problème. Le modèle projeté est renforcé en ajoutant des contraintes spécifiques et on le résout par séparation et coupe. Le problème du « remontage » consiste à calculer des solutions de bonne qualité à partir de solutions du modèle projeté.

Le deuxième problème est un problème classique de tournées de véhicules avec collecte et livraison, transferts et un horizon temporel. On introduit le « problème du chemin virtuel » qui consiste en la modification d'un graphe dirigé acyclique avec un système de contraintes sous-jacent. L'objectif est de construire un chemin dirigé reliant deux sommets donnés, tout en minimisant une fonction de coût et en maintenant un système de contraintes réalisable. On propose un algorithme de type A* pour résoudre ce problème de manière exacte. Alors, on montre que le problème de l’insertion exacte d’une requête dans un planning de tournées de véhicules avec collecte et de livraison et transferts est un cas particulier de ce problème, et on propose également une heuristique basée sur l'algorithme de Dijkstra. Enfin, on combine ces algorithmes avec des métaheuristiques classiques pour gérer l'insertion de plusieurs requêtes.

Jury :

Maurício CARDOSO DE SOUZA - Universidade Federal de Minas Gerais - Rapporteur et examinateur

Pierre FOUILHOUX - Université Sorbonne Paris Nord - Rapporteur et examinateur

Alain QUILLIOT - Université Clermont Auvergne - Directeur de thèse

Eric SANLAVILLE - Université du Havre - Examinateur

Hélène TOUSSAINT - Université Clermont Auvergne - Codirectrice de thèse

Annegret WAGLER - Université Clermont Auvergne - Codirectrice de thèse.