Arc Routing Problems for Road Network Maintenance

Cette thèse présente deux problèmes rencontrés dans l'entretien des réseaux routiers, soit la surveillance des réseaux routiers pour la détection de verglas sur la chaussée et la reprogrammation des itinéraires pour les activités de déneigement et d'épandage de sel. Nous représentons ces problèmes par des modèles de tournées sur les arcs. La dépendance aux moments et la nature dynamique sont des caractéristiques propres de ces problèmes, par conséquence le cas de surveillance des réseaux routiers est modélisé comme un problème de postier rural avec fenêtres-horaires (RPPTW), tandis que le cas de la reprogrammation utilise des modèles obtenus à partir des formulations de problèmes de tournées sur les arcs avec capacité. Dans le cas du problème de surveillance, une patrouille vérifie l'état des chemins et des autoroutes, elle doit principalement détecter le verglas sur la chaussée dans le but d'assurer de bonnes conditions aux chauffeurs et aux piétons. Étant donné un réseau routier et des prévisions météo, le problème consiste à créer une tournée qui permette de détecter opportunément le verglas sur les rues et les routes. L'objectif poursuivi consiste à minimiser le coût de cette opération. En premier, on présente trois formulations basées sur la programmation linéaire en nombres entiers pour le problème de surveillance des réseaux qui dépend du moment et deux méthodes de résolution: un algorithme de coupes et un algorithme heuristique appelé adaptive large neighborhood search (ALNS). La méthode exacte inclut des inéquations valides tirées du problème du voyageur de commerce avec fenêtres-horaires et aussi du problème de voyageur du commerce avec contraintes de précédence. La méthode heuristique considère deux phases: en premier, on trouve une solution initiale et après dans la deuxième phase, l'algorithme essaie d'améliorer la solution initiale en utilisant sept heuristiques de destruction et deux heuristiques de réparation choisies au hasard. La performance des heuristiques est évaluée pendant les itérations. Une meilleure performance correspond à une plus grande probabilité de choisir une heuristique. Plusieurs tests ont été faits sur deux ensembles d'exemplaires de problèmes. Les résultats obtenus montrent que l'algorithme de coupes est capable de résoudre des réseaux avec 104 arêtes requises et des fenêtres-horaires structurées par tranches horaires ; l'algorithme peut aussi résoudre des réseaux avec 45 arêtes requises et des fenêtres-horaires structurées pour chaque arête requise. Pour l'algorithme ALNS, différentes versions de l'algorithme sont comparées. Les résultats montrent que cette méthode est efficace parce qu'elle est capable de résoudre à l'optimalité 224 des 232 exemplaires et de réduire le temps de calcul significativement pour les exemplaires les plus difficiles. La dernière partie de la thèse introduit le problème de la reprogrammation de tournées sur les arcs avec capacité (RCARP), lequel permet de modéliser la reprogrammation des itinéraires après une panne d'un véhicule lors de la phase d'exécution d'un plan initial des activités de déneigement ou d'épandage de sel. Le planificateur doit alors modifier le plan initial rapidement et reprogrammer les véhicules qui restent pour finir les activités. Dans ce cas, l'objectif poursuivi consiste à minimiser le coût d'opération et le coût de perturbation. La distance couverte par les véhicules correspond au coût d'opération, cependant une nouvelle métrique est développée pour mesurer le coût de perturbation. Les coûts considérés sont des objectifs en conflit. On analyse quatre politiques à la phase de re-routage en utilisant des formulations de programmation linéaire en nombres entiers. On propose une solution heuristique comme méthode pour résoudre le RCARP quand les coûts d'opération et de perturbation sont minimisés en même temps et quand une réponse rapide est nécessaire. La méthode consiste à fixer une partie de l'itinéraire initial et après à modifier seulement les itinéraires des véhicules les plus proches de la zone de l'interruption de la tournée du véhicule défaillant. La méthode a été testée sur des exemplaires obtenus d'un réseau réel. Nos tests indiquent que la méthode peut résoudre rapidement des exemplaires avec 88 arêtes requises et 10 véhicules actifs après la panne d'un véhicule. En conclusion, la principale contribution de cette thèse est de présenter des modèles de tournées sur les arcs et de proposer des méthodes de résolution d'optimisation qui incluent la dépendance aux temps et l'aspect dynamique. On propose des modèles et des méthodes pour résoudre le RPPTW, et on présente des résultats pour ce problème. On introduit pour la première fois le RCARP. Trois articles correspondant aux trois principaux chapitres ont été acceptés ou soumis à des revues avec comité de Lecture: “The rural postman problem with time windows” accepté dans Networks, “ALNS for the rural postman problem with time windows” soumis à Networks, and “The rescheduling capacitated arc routing problem” soumis à International Transactions in Operational Research.