Local Search Solver, une bibliothèque de recherche locale pour des applications industrielles
Florian Fontan  1@  , Luc Libralesso  2@  
1 : Artelys France
Artelys France
2 : Laboratoire dÍnformatique, de Modélisation et dÓptimisation des Systèmes
Ecole Nationale Supérieure des Mines de St Etienne : UMR6158, Centre National de la Recherche Scientifique : UMR6158, Université Clermont Auvergne : UMR6158, Institut national polytechnique Clermont Auvergne : UMR6158, Université Clermont Auvergne

La recherche locale fait partie des principales méthodes de résolution de problèmes d'optimisation combinatoire. Toutefois, résoudre un problème avec cette technique demande en général un temps de développement supérieur au temps nécessaire à l'écriture d'un modèle en Programmation Linéaire en Nombres Entiers ou d'un modèle en Programmation Par Contrainte. Ceci rend son utilisation difficile en pratique pour des problèmes complexes dont le modèle évolue rapidement. Nous cherchons donc à développer des méthodes et outils basés sur la recherche locale présentant un bon compromis entre le temps nécessaire au développement et la qualité des solutions renvoyées.

Nous présentons une bibliothèque écrite en C++ publiée sous licence MIT, dont l'objectif est de permettre l'implémentation rapide d'algorithmes performants basés sur la recherche locale. L'utilisateur n'a besoin d'écrire que les composants spécifiques au problème considéré. Nous avons notamment utilisé cette bibliothèque lors du challenge ROADEF/EURO 2020 portant sur un problème industriel complexe de planification de maintenances. Bien que cette approche n'aie pas été la meilleure, elle a quand même permis de trouver 3 meilleures solutions sur 30, et se classe 4e sur 13 lors de la phase finale.


Personnes connectées : 1 Vie privée
Chargement...