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é.

Abstract

In the last ten years, postal services had to adapt to a changing market, due to vigorous growth in online shopping, combined with a significant decline in transaction mailing. Indeed, traditional mail and parcel delivery are not handled similarly. For the first one, postmen are generally assigned to geographical areas and must visit every address on every street within their assigned territories. For the latter one, only a few residents or businesses have to be visited. Also, truck usage is mandatory because of the bulkiness of the parcels. Time constraints, called time windows are assigned to some of the clients, restricting the visiting time to a predefined period. Those constraints most of the time originate from agreements between the postal service and its clients, generally companies. In recent years, contracts such as 24H or 48H-delivery may also lead to time windows. The parcel delivery problem has some special characteristics in the postal context. The number of customers per tour is relatively high (50 to 150 customers per route) and the truck capacity is not considered. However, route duration is a key component in this problem, as the postmen shifts depend on it. Furthermore, the service time counts for a substantial part of the route duration. It includes parking time and parcel handling at the customers among other little tasks and is, by definition, incompressible. In the last years, postal companies also tended to assign more compact routes to their employees for several reasons. It helps to increase the postman's knowledge of the neighborhood (road works, rush-hour congestion, etc.) and thus improve his performance. In some companies where rewards are granted for every parcel effectively delivered, it may enable a faster return to absent clients. In this thesis, we present tools to optimize spatio-temporal characteristics of the routes in a postal context. The latter is very dynamic, as customers potentially change every day. We intend to develop methods able to generate good quality solutions in a reasonable amount of time, despite the large size of instances. Giro Inc., the Montreal-based company that develops GeoRoute, a software optimizing routes of several postal services worldwide, has supported us during the three different projects presented in the following document. In the first part of this thesis, we illustrate how dealing with route duration may be beneficial from a strategic point of view as well as for economical considerations. Working on the traveling salesman problem with time windows, we define solution methods that find the best balance between travel time and route duration, deliverers' time being a precious and limited resource. Besides, we develop a method to solve large postal instances (up to about 500 customers) with very few time windows by mixing customer clustering, constraints programming and mixed-integer programming. Finally, we show that when some time windows are set, the shortest path is not necessarily the most cost-effective, as some potential waiting time may occur. In the second project, we focus on compactness. We first define the exact compactness of a route as the area of the convex hull of the clients belonging to this route. Then, we propose two different approximations of this measure. The two latter approximations are tested on academic benchmarks and on instances derived from industrial instances by adjusting an algorithm combining large neighborhood search and heuristic column generation. In this project, the size of the tested instances is limited to 500 customers, which is not as large as real world-instances in the postal context. We observe that with academic instances, where many time windows are imposed, compactness may be largely improved, but generating more compact routes is costly as longer travel times are required. However, when there are fewer time windows as in real-world instances, considering compactness may even work as a good guide for our method. Indeed, in a limited amount of time, both compactness and travel time may be reduced for the different routes. The third part of the thesis may be seen as an extension of the previous one, applied to large industrial instances (up to more than 3000 customers). Dealing with such large instances brings new challenges. Therefore, we present several techniques to obtain good-quality solutions in a reasonable amount of time. First, we limit the search space dynamically around the current solution to help to generate improving routes. Then, we use an iterative problem decomposition, with variable size to limit side effects, in order to intensify the search in every geographical zone of the instance. We show that our heuristic generates more compact routes without degrading travel time, compared to other solutions not considering compactness.