Optimisation spatio-temporelle des routes pour les problèmes de livraison de colis par services postaux

En raison d'une forte croissance du commerce en ligne, combinée à un recul significatif du courrier transactionnel, les services postaux ont dû, au cours des dix dernières années, s'adapter à un marché en métamorphose. En effet, le courrier traditionnel et la livraison de colis ne se gèrent pas de la même façon. Pour le courrier postal, les facteurs sont généralement assignés à des zones géographiques dans lesquelles ils doivent visiter toutes les adresses sur toutes les rues au cours de leur tournée. En ce qui concerne les colis, seulement quelques résidents ou commerçants doivent être visités, et l'encombrement des divers colis oblige les livraisons à s'effectuer par camion. Parmi les clients à visiter, certains présentent des contraintes horaires, appelées fenêtres de temps, période durant laquelle leur colis doit être livré. Cette contrainte provient généralement d'accords entre les services postaux et leurs clients (généralement des entreprises). Depuis quelques années, des contrats de livraison en moins de 24H ou 48H peuvent aussi être à l'origine de ces fenêtres de temps. Le problème de livraison de colis dans le milieu postal possède quelques caractéristiques qui lui sont propres. Le nombre de clients par route est relativement conséquent (traditionnellement entre 50 et 150 clients par route) et la capacité des camions n'est généralement pas limitante. En revanche, la durée des tournées est une mesure essentielle dans ce genre de problème, la durée des journées de travail des livreurs en dépendent. Il est bon de noter que le temps de service, comprenant entre autres stationnement du véhicule, récupération du colis dans le camion et livraison en mains propres, compte pour une part conséquente de la durée des routes et que ce temps est incompressible. Au cours des dernières années, les compagnies postales ont cherché à assigner à leurs livreurs des routes plus compactes pour diverses raisons. Cela permet notamment d'augmenter la connaissance du quartier des livreurs (travaux, embouteillages réguliers aux heures de pointe, etc.) et ainsi améliorer leurs performances. Dans certaines compagnies pour lesquelles les livreurs reçoivent une récompense pour chaque colis livré, cela peut aussi permettre un retour plus rapide chez un client absent. Dans cette thèse, nous présentons les outils mis en place pour optimiser les caractéristiques spatio-temporelles des routes dans ce contexte postal. Ce dernier étant très dynamique, puisque les clients peuvent changer d'un jour à l'autre, nous cherchons à développer des méthodes donnant les meilleurs résultats possibles en peu de temps, et ce malgré la taille conséquente des instances. L'intégralité des projets présentés par la suite a été réalisée en collaboration avec Giro Inc., la compagnie montréalaise ayant développé GeoRoute, un logiciel d'optimisation utilisé par de nombreuses compagnies postales à travers le monde. Dans la première partie de cette thèse, nous expliquons en quoi la durée des routes peut être un avantage aussi bien stratégique que purement économique. En effet, en nous intéressant au problème de voyageur de commerce avec fenêtres de temps, nous mettons en place des méthodes pour essayer de trouver le meilleur équilibre économique entre temps de parcours et durée de la tournée, le temps des livreurs étant une ressource précieuse et limitée. En plus de ceci, nous développons une méthode permettant de résoudre des instances postales de très grande taille (jusqu'à près de 500 clients) avec très peu de fenêtres de temps en mélangeant agrégations de clients, programmation par contraintes et programmation en nombres entiers. Nous observons que, dans un contexte où il existe des fenêtres de temps, le chemin le plus court n'est pas forcément le moins coûteux, car il faut prendre en considération les éventuels temps d'attente. Dans le deuxième projet, nous nous intéressons particulièrement à la notion de compacité. À partir d'une compacité géographique considérée comme exacte et calculée comme étant l'aire de l'enveloppe convexe des clients d'une route, nous proposons deux approximations de cette mesure. Par la suite, nous les testons, aussi bien sur des instances académiques que sur des instances dérivées de données du monde industriel, en ajustant un algorithme combinant recherche à voisinage large et génération de colonnes heuristique. Dans ce projet, nous nous limitons à des instances de taille moyenne, relativement à la nature du problème, c'est-à-dire ne dépassant pas les 500 clients. Nous pouvons analyser à travers les résultats obtenus sur les instances académiques que, lorsqu'il existe de nombreuses fenêtres de temps, la compacité des routes ne peut être améliorée qu'au détriment d'un temps de parcours plus long. En revanche, quand les fenêtres de temps sont moins nombreuses comme c'est le cas avec les données réelles, la prise en compte de la compacité peut avoir l'effet d'un guide pour notre méthode, permettant ainsi, en un temps limité, d'améliorer à la fois la compacité et le temps de parcours de chacune des routes. La troisième partie de cette thèse est une extension du projet précédent, appliqué à des instances industrielles de très grande taille (jusqu'à plus de 3000 clients). Gérer de telles instances amène de nouveaux défis. Nous présentons donc plusieurs techniques pour rendre les temps de calcul raisonnables sans impacter la qualité des solutions. Tout d'abord, nous limitons l'espace de recherche de façon dynamique autour de la solution courante afin de favoriser l'obtention de routes améliorantes. Ensuite, nous utilisons une méthode de décompositions successives du problème, à taille variable pour limiter les effets de bord, pour intensifier la recherche dans toutes les zones géographiques de l'instance. Nous montrons alors que notre heuristique permet d'obtenir des routes plus compactes sans dégrader la qualité de la solution par rapport à d'autres méthodes négligeant l'aspect compacité.