Optimisation de tournées de véhicules en viabilité hivernale

Cette thèse développe des outils mathématiques et informatiques pour améliorer les opérations de viabilité hivernale. En particulier, la confection des tournées de déneigement est traitée comme un problème de tournées sur les arcs avec plusieurs contraintes. Une métaheuristique est d'abord développée pour la confection de ces tournées. Par la suite, des modifications majeures sont apportées à cet algorithme pour tenir compte des caractéristiques spécifiques aux problèmes de tournées sur les arcs (arc routing problem) (ARP) sur des réseaux routiers réels. Finalement, un second problème combinant les tournées de déneigement et d'épandage avec la mise en commun de certains véhicules pour les opérations est traité. La solution développée permet de tirer parti des caractéristiques de chaque véhicule. Tout au long de la thèse, un accent particulier est porté sur l'utilisation des données réelles ainsi que sur le développement de méthodes pour faciliter l'importation et l'exportation de ces données. Les travaux entourant cette thèse débutent avec la confection de tournées de déneigement pour une ville au Québec, soit Dolbeau-Mistassini (DM). De nombreux problèmes ont été rencontrés avec l'utilisation d'une méthode tirée de la littérature. Parmi ceux-ci, on compte : — de nombreux demi-tours difficiles à exécuter par les véhicules ; — le faible respect des priorités accordées aux rues à l'échelle du réseau ; — de nombreux véhicules parcourent de longues distances pour se rendre dans les coins reculés du réseau ; — le déséquilibre des tâches de travail en raison des différentes vitesses d'opération des véhicules ; — le fait que la méthode ne tient pas compte des ruelles qui peuvent être traitées dans une direction ou dans l'autre en un seul passage. À la suite de nombreux ajustements manuels pour corriger les tournées obtenues, force a été de constater que des améliorations pouvaient être apportées à ce type de méthode. Les travaux concernant la première contribution de cette thèse ont donc porté sur le développement d'une méthode de création de tournées de déneigement. En raison du grand nombre de variables et de contraintes considérées dans le problème, le choix s'est porté sur une méthode heuristique. Ce type de méthode offre un bon équilibre entre le temps de traitement et la qualité des solutions obtenues. Plus précisément, le choix s'est arrêté sur une métaheuristique de type algorithme de recherche à voisinage adaptatif large (adaptive large neighborhood search) (ALNS), en raison du succès remporté récemment par ce type de méthode. Le premier article a permis de constater que l'algorithme développé permet de créer des tournées pour les véhicules de déneigement. Les contraintes suivantes sont respectées : équilibrage des tournées, couverture partielle du réseau, vitesses hétérogènes, restrictions de virages, restrictions rue/véhicule et hiérarchie du réseau. Pour la deuxième contribution de thèse, le problème a d'abord été formalisé par l'intermédiaire d'un programme linéaire en nombres entiers (mixed integer programming) (MIP). Le problème a été formulé comme un problème des k-postiers ruraux avec objectif minmax (min-max k-vehicles rural postman problem) (MM K-RPP) avec hiérarchies, pénalités sur virages, vitesses d'opération hétérogènes et tournées ouvertes sur un graphe mixte. Tel qu'anticipé, la résolution devient rapidement impossible à traiter avec un solveur commercial en utilisant seulement 20 segments de rue. Il a été décidé de poursuivre l'approfondissement de l'algorithme développé en première partie. Cette décision a été prise notamment en raison du très long temps de traitement qui réduit l'utilité du premier algorithme. Cette décision repose aussi sur le fait que visuellement, on constate que les tournées obtenues peuvent être améliorées. Dans cette optique, une collaboration a été initiée avec messieurs Fabien Lehuédé et Olivier Péton du laboratoire des sciences du numérique de Nantes (LS2N) à IMT Atlantique. Leur expertise avec la méthode ALNS a effectivement permis d'améliorer grandement les résultats obtenus. Parmi les améliorations apportées, on note une transformation du réseau permettant de tenir compte des pénalités sur virages lors du calcul des plus courts chemins. Cette transformation permet également de mieux prendre en compte les ruelles qui requièrent un seul passage dans une direction ou dans l'autre. De plus, la possibilité d'appliquer plusieurs fois un opérateur de destruction avant de passer à la construction est ajoutée. Cette contribution a également été l'occasion de développer et tester de nouveaux opérateurs de voisinage, développer une méthode de groupement des arcs et revoir et simplifier le code de la métaheuristique. L'algorithme a été appliqué à la première étude de cas ainsi qu'a deux nouvelles études de cas, Baie-Comeau (BC) et Plateau-Mont-Royal (PMR). Des tests ont également été exécutés en comparant les nouvelles tournées obtenues à des tournées conçues quelques années plus tôt ainsi qu'aux résultats obtenus par un solveur commercial. Les résultats obtenus démontrent que la méthodologie améliore les tournées conçues précédemment. Il est aussi possible de conclure que la méthode de groupage des arcs améliore la qualité des solutions obtenues et l'efficacité des nouveaux opérateurs développés varie selon le réseau utilisé. Pour la troisième contribution, nous sommes revenus sur le cas d'étude initial tel que décrit par les intervenants de la première étude de cas. Il a été dit que les charges de travail doivent être équilibrées, mais que certains véhicules doivent également épandre des fondants ou des abrasifs en plus de déneiger. Pour tenir compte de cette contrainte, certaines tournées avaient délibérément été gardées plus courtes dans les premières solutions. Pour le troisième article, il a été décidé de traiter cette problématique de front. Ce qu'il faut savoir est que certains véhicules sont équipés pour l'épandage et le déneigement alors que d'autres sont équipés pour le déneigement seulement. Lorsque les premiers traitent un segment de rue, ils exécutent les deux opérations simultanément. Lorsque les deuxièmes traitent un segment de rue, il faut planifier un second passage par les premiers véhicules pour qu'ils puissent épandre des fondants ou des abrasifs. L'algorithme développé précédemment a donc été modifié dans cette optique. En plus, la considération des contraintes de restrictions rue/véhicule a été ajoutée dans l'algorithme. Les résultats démontrent que l'algorithme permet effectivement de concevoir des tournées qui respectent les contraintes de la nouvelle étude de cas. Cet outil permet donc de tirer profit de l'interaction entre les divers types de véhicules. La contribution souligne également l'utilité d'un tel outil pour supporter l'analyse des besoins justifiant l'achat de nouveaux véhicules. En parallèle aux développements algorithmiques, des méthodes d'importation et d'exportation des données provenant des cas d'étude réels sont aussi développées. Dès le départ, il a été choisi d'utiliser des fichiers de type Shapefile comme source de données en raison de sa grande disponibilité et de la compatibilité avec les système d'information géographique (SIG). Une méthode pour passer du réseau géographique vers un réseau mathématique a donc été améliorée au cours des travaux. Alors qu'au début des travaux de la thèse, il fallait passer par un chiffrier Microsoft ExcelTM pour ensuite importer les données dans le code, à la fin, une méthode automatisée permet l'importation directe à partir des fichiers Shapefiles vers le code de la métaheuristique. Quant aux résultats obtenus, ils furent obtenus dans les premières étapes sous forment de représentations géographiques dans un SIG ainsi que des feuilles d'instructions indiquant les étapes, coin de rue par coin de rue, aux opérateurs de véhicules. De ce côté, les développements ont permis d'obtenir des fichiers de type KML. Ce type de fichier est compatible avec plusieurs logiciels et applications, dont Google EarthviewTM et des applications de guidage routier sur des appareils mobiles.

Abstract

In this thesis, we develop mathematical and computerized tools to improve winter viability operations. More precisely, the snow routing design problem is treated as an problème de tournée sur les arcs (arc routing problem) (ARP). In a first effort to solve the problem, a metaheuristic procedure is designed. Then, some major modifications are made to the algorithm to improve the consideration of specific characteristics of real road networks. Finally, a second problem combining the routing of the snowplow and the spreading vehicles are addressed. The objective is to fully take advantage of the characteristics of the different type of vehicles. In parallel with the algorithmic development, this thesis also develops some methodologies to facilitate the importation and exportation of the real world data. Works concerning this thesis were initiated with a mandate to design snowplow routes for a city in the province of Québec, namely DM. The problem was addressed by using a methodology found in the literature, however, several difficulties were encountered. Among others: — the routes contained several U-turns which are difficult to perform by the snow plowing vehicles; — little consideration of the priorities at the network level; — several vehicles have to travel to some remote streets in the same sector of the city where we would expect only one vehicle to go; — unbalanced sectors due to the different speeds of operation of the vehicles; — no consideration for back alleys that needs to be serviced only once in either direction. In respond to these problems, several manual modifications of the routes were undertaken to make them feasible. It was found that the methodology fails to solve the problem as it is encountered. Therefore, works concerning the first contribution of this thesis focused on the development of a methodology to design snowplow routing. Due to numerous variables and constraints, it was decided to develop a metaheuristic algorithm. This type of methodology offers a good balance between runtime and the quality of the solution obtained. In particular, an ALNS is selected because of its recent success cited in the literature. Thus, the first article concludes that the algorithm can design snowplow routing. The following constraints are considered: workload balance, partial area coverage, heterogeneous vehicle speeds, road/vehicle dependencies, network hierarchies and turn restrictions. In the second contribution of this thesis, the problem was modeled as a mixed integer program. It is formulated as a min-max k-rural postmen problem with hierarchies, turn penalties, open tours and heterogeneous speed on a mixed graph. As expected, the formulation is intractable even for a number of arcs as low as 20. It was then decided to pursue the development of the ALNS algorithm. This decision was taken considering the long runtime of the first algorithm and the fact that the routes obtained can be visually improved. A collaboration with Fabien Lehuédé and Olivier Péton from the Laboratoire des Sciences du Numérique de Nantes (LS2N), IMT Atlantique was undertaken. Their expertise with ALNS greatly helped to improve the results obtained. Among other improvements brought to the algorithm, one can cite the transformation of the graph which allows to better take into account turn penalties during the computation of the shortest paths. This transformation also allows to better take into account the back alleys which only need one service in either direction. This contribution also allowed to develop and test new neighborhood operators and an arc grouping methodology. Both of these innovations improve the quality of the solutions obtained. However the efficiency of the new operators varies with the network. For the third contribution, we took back the case study as it was described by the collaborator in DM. It was said that the workload needs to be balanced among the vehicles. However some vehicles must also perform winter spreading in addition to plowing. For the first set of routes produced, some of the routes were deliberately left with a lower workload to allow them to perform winter spreading. For the third article, it was decided to consider the spreading and the plowing directly during the construction and the improvement steps. Thus this problem was tackled more directly in the third article. It must be noted that some vehicles are equipped to perform both winter spreading and snow plowing and some others can only perform plowing. When the former service a street, they can perform both plowing and spreading at the same time. When the latter service a street, a second passage is required to spread salt or abrasives. The algorithm developed for the second contribution was then adapted for this new problem. Moreover, the street/vehicle restriction constraints were also added. The result shows that the algorithm can produce a set of routes respecting the constraints of the new problem. It can take advantage of the interaction between the various types of vehicles. The article also shows that such tool can be beneficial in analyzing the requirements for new vehicles. In parallel with the development of the algorithms, data importation and exportation techniques from real road networks are also developed. It was chosen to use Shapefiles because of its good relative availability and because of its compatibility with Geographic Information System (GIS). A method to transfer from a geographical to a mathematical network is improved during the thesis. At the beginning, a Microsoft ExcelTM datasheet is used to transfer the data from the GIS to the metaheuristic. At the end, it is possible to fetch the data directly from the Shapefiles to the metaheuristic. As for the results obtained, at the beginning, they were provided in the form of a Shapefile for visualization and indications on sheets of paper for the operators. At the end, the results can be exported to the KML format. This type of file is compatible with several software such as Google EarthviewTM and application Global Positioning System (GPS) applications on mobile devices.