 |
Introduction
Eurodecision utilise depuis de nombreuses années des méthodes d'optimisation se basant sur une génération de colonnes par résolution d'un plus court chemin contraint. Pour faciliter la mise en œuvre de cette méthode, LP-TaskPlanner a été créé. Ce framework permet à l'utilisateur de modéliser son problème grâce à des graphes, des ressources et des expressions mathématiques. Le moteur, ayant la connaissance mathématique complète du problème, peut alors le résoudre grâce à différents algorithmes.
Les avantages pour l'utilisateur sont multiples. Tout d'abord, la modélisation est décorrélée de la résolution. Ensuite, l'utilisateur a à sa disposition un ensemble d'outils de modélisation flexibles et connus : réels, listes, valeurs discrètes, expressions mathématiques et booléennes, ainsi qu'un formalisme de programmation linéaire. Ces outils nous ont permis de modéliser des problèmes industriels complexes de manière formelle, ce qui était impensable avant.
Du point de vue du moteur de résolution, cette modélisation apporte également son lot d'avantages. Comme le modèle est formel, le moteur peut automatiser toutes les briques nécessaires à la résolution du problème : calcul du coût réduit, anticipation de violation de contrainte, filtrage des arcs des graphes, génération de la fonction de dominance, gestion des règles de branchement...
LP-TaskPlanner est actuellement utilisé dans les nouvelles versions de LP-EasyDriver, notre composant d'habillage et graphicage en transport en commun, et de LP-ShiftPlanner, notre composant de planification nominative.
De la théorie à la pratique
Si, en théorie, LP-TaskPlanner peut résoudre de manière exacte la plupart des problèmes que l'on peut modéliser avec ce dernier, en pratique, les problèmes industriels réels que nous lui soumettons sont beaucoup trop complexes ou volumineux. Les temps de calcul peuvent exploser, la dominance être totalement inefficace, la consommation mémoire peut s'envoler, etc. Autant de problèmes auxquels nous avons dû faire face en faisant preuve d'astuce et en sacrifiant l'exactitude des méthodes de résolution pour des approches heuristiques. Nous vous proposons lors de cette présentation de dévoiler une partie des mécaniques permettant aujourd'hui à LP-TaskPlanner de générer en des temps de calcul raisonnables des plannings pour de très gros réseaux de transport public, ou pour des équipes de plus d'une centaine de personnes.
