Optimisation de tournées de service en temps réel

Les tournées de service concernent l'organisation de déplacement de personnels vers des clients afin d'effectuer différentes activités techniques ou commerciales. Ces tournées peuvent devoir répondre à des objectifs et faire face à des contraintes nombreuses et complexes. Lors de la planification et de l'exécution de tournées de service mono-période, les entreprises sont confrontées aux aléas des temps de service et de parcours. C'est pourquoi, dans cette thèse, nous nous intéressons à une variante du problème de tournées de service, dans laquelle les temps de parcours et de service sont stochastiques. Il s'agit du problème de tournées de service multi-dépôt, incluant fenêtres de temps, temps de service et de parcours stochastiques avec priorité entre les clients (distinction clients obligatoires / clients optionnels). Afin de résoudre cette problématique, nous proposons trois méthodes différentes. Dans la première méthode, nous construisons d'abord des routes contenant uniquement des clients obligatoires puis nous procédons à l'insertion des clients optionnels. La deuxième méthode est une méthode approchée basée sur la génération de colonnes consistant à générer un ensemble de routes de bonne qualité pour chaque véhicule puis à en sélectionner une par véhicule. La dernière méthode est un algorithme de branch and price basé sur la deuxième méthode. Le sous-problème consiste à générer des routes réalisables pour un véhicule donné, tandis que le problème maître permet de sélectionner des routes en s'assurant que la priorité des clients est respectée. Après chacune de ces méthodes, afin d'évaluer la qualité de ces solutions face aux aléas, nous utilisons un algorithme de programmation dynamique et procédons à un ensemble de simulations du déroulement des tournées en temps réel. Nous avons testé ces méthodes sur des problèmes dont les données sont issues du milieu industriel.Mots-clés : Tournées de véhicules, multi-dépôt, fenêtres de temps, temps de service stochastiques, temps de parcours stochastiques, priorité entre les clients.