Application du branch-and-price au problème de tournées de techniciens chez ERDF

Session : GTSS1 / GTSS1 : Exact methods for scheduling problems
Mercredi 10 février 15:00 - 15:40 Salle : CI2-04
Etienne de Saint Germain, Bayram Kaddour et Pascal Benchimol

1 Contexte, problème métier et objectifs La planification des tournées d’interventions des agents ERDF implique chaque année quelques milliers d’agents et de véhicules pour réaliser une dizaine de millions d’interventions en parcourant plus de 200 millions de kilomètres dans la France métropolitaine. Le modèle retenu est déterministe : l’ensemble des interventions de la journée (caractérisées par leurs localisations, leurs durées, leurs fenêtres de temps...) et l’ensemble des techniciens sont connus. Il s’agit précisément du Vehicle Routing Problem with Time Windows (VRPTW) avec plusieurs techniciens. L’objectif est de développer une méthode permettant d’évaluer la qualité de solutions à ce problème trouvées par d’autres approches (heuristiques, PPC, etc). L’ensemble de ce travail est décrit précisément dans le rapport du stage du projet [1]. 2 Méthode employée La modélisation choisie s’inspire de travaux classiques sur le sujet [2, 3] et fait intervenir un problème linéaire en nombres entiers de très grande taille. Afin de le décomposer, une approche de type branch-and-price a été mise en place. Chaque noeud de l’arbre de recherche est résolu par un algorithme de génération de colonnes s’appuyant sur des problèmes de plus courts chemins avec contraintes de ressources [5] pour générer ses variables. Afin de permettre le passage à l’échelle de l’approche, nous avons utilisé des techniques de dominance qui permettent de réduire l’espace des solutions des sous-problèmes sans perte de l’optimalité telles une réduction des fenêtres de temps des interventions [3] ou une interdiction des cycles de longueur k dans les tournées générées [1]. Nous avons démontré une nouvelle borne inférieure théorique pour quantifier l’erreur commise lors d’une résolution incomplète des noeuds [1] et montré expérimentalement son intérêt par rapport aux bornes précédentes [4, 6]. Enfin, nous avons expérimenté diverses stratégies de branchement et d’exploration de l’arbre de décision. 3 Conclusions et perspectives L’implémentation a été réalisée en C++ et donne de très bons résultats sur des instances « jouets » (pour 9 interventions et 3 techniciens, la méthode donne une solution optimale en quelques secondes). En revanche, sur une grande partie des instances réelles, le passage à l’échelle pose encore problème. Quelques résultats sont regroupés dans le tableau 1. ------------------------------------------------------------------------------------- | inter- | tech- | borne | meilleure | écart rela- | | temps par | | ventions | niciens | inférieure | solution | tif (en %) | noeuds | noeud (en s) | ------------------------------------------------------------------------------------- | 54 | 12 | 1666.23 | 1731.59 | 3.8 | 1863 | 3.9 | | 79 | 12 | 1498.88 | 1682.86 | 10.9 | 70 | 102.9 | | 103 | 12 | 1468.12 | 2085.66 | 29.6 | 13 | 553.8 | | 118 | 9 | 3113.72 | 3791.43 | 17.9 | 744 | 9.7 | ------------------------------------------------------------------------------------- TAB. 1 – Résultats du branch-and-price après deux heures de calculs Le point critique de la méthode est la résolution de sous-problèmes qui représentent plus de 90% du temps de calcul. De premiers travaux pourraient être menés sur ce sujet en envisageant par exemple des résolutions heuristiques. Probablement moins impactant sur l’efficacité, d’autres travaux pourraient être envisagés sur la stratégie de branchement, sur une implémentation parallélisée de l’arbre de décision ou sur une modélisation du problème maître en Set-Partioning plutôt qu’en Set-Covering. Références [1] E. de Saint Germain, Etude de méthodes de décomposition pour la planification de tournées de techniciens, projet de fin d’étude, Ecole Nationale des Ponts et Chaussées, Cité Descartes, 6-8 Avenue Blaise Pascal, 77455 Champs-sur-Marne, France, 2015. [En ligne : https://drive.google.com/file/d/0BydRX2AmX1H5U0pETXRTeWc4aEU/view?usp=sharing]. [2] G. Desaulniers, J. Desrosiers, Y. Dumas, M. M. Solomon, and F. Soumis, Daily aircraft routing and scheduling, Cahiers du GERAD, 21 (1994). Révisé : Août 1995. [3] M. Desrochers, J. Desrosiers, and M. Solomon, A new optimization algorithm for the vehicle routing problem with time windows, Operations Research, 40 (1992), pp. 342–354. [4] A. A. Farley, A note on bounding a class of linear programming problems, including cutting stock problems, Operations Research, 38 (1990), pp. 922–923. [5] S. Irnich and G. Desaulniers, Shortest path problems with resource constraints, in Column Generation, G. Desaulniers, J. Desrosiers, and M. M. Solomon, eds., Springer US, 2005, pp. 33–65. [6] M. E. Lübbecke and J. Desrosiers, Selected topics in column generation, Operations Research, 53 (2005), pp. 1007–1023.

Mots clés : Vehicle Routing Problem with Time Windows (VRPTW), Programmation Linéaire en Nombres Entiers (PLNE), branch-and-price, génération de colonnes, Shortest Path Problem with Resource Constraints (SPPRC)