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

REMERCIEMENTSJe tiens à remercier en tout premier lieu André et Martin pour leur soutien, leur confiance et leurs précieux conseils.Ce fut très agréable de travailler avec vous.En espérant que cela se poursuive.Je remercie également Fabien et Olivier pour leur hospitalité et leur aide.Vous avez certainement contribué à améliorer les résultats obtenus et je vous en suis très reconnaissant.Merci à Nathalie et Alberto pour l'aide et le code qu'ils m'ont fournis.Merci aussi à Lydie pour le coup de pouce qu'elle m'a donné.Un merci tout spécial à mes parents, mes frères et ma chère tante pour leur soutien indéfectible.Ce n'est pas facile de comprendre ce qui se passe durant un doctorat, mais votre support est certainement apprécié.Je tiens aussi à remercier tous mes amis du bureau pour leur soutien Marcela, Chahid, Juan Pablo, Raheleh, Salah, Jacqueline, Anne-Sarah, Flavio, Anne-Sandrine, Sandra, Mathieu, ainsi que Benoit.Votre présence a rendu mon travail plus agréable.Merci au service des travaux publics de la ville de Dolbeau-Mistassini pour leur temps et les informations qu'ils nous ont fournies à propos de leurs pratiques.Finalement, je tiens également à remercier le Conseil de recherches en sciences naturelles du Canada, le Fonds de recherche du Québec -Nature et technologies, le ministère des Transports, de la Mobilité durable et Électrification des transports ainsi que Polytechnique Montréal pour leur financement.Ils ont fourni une aide essentielle à la réussite de ce projet et ce fut très apprécié.v 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 Keywords: Winter maintenance, Snow plowing, Rural post-men problem, ALNS metaheuristic.

Récupéré en direct depuis OpenAlex et désinversé. Les résumés ne sont pas conservés dans cette base de données : les index inversés représentent 8,6 Go des 9,3 Go de texte de la base, et le serveur dispose de 13 Go libres.