OscaR.cbls

Pourquoi la recherche locale ?

La recherche locale est une technique d’optimisation polyvalente et évolutive pour résoudre des problèmes de recherche opérationnelle. Elle est, par exemple, bien adaptée aux problèmes d’optimisation avec un grand espace de recherche, tels que les problèmes d’optimisation de routage.

Elle peut également intégrer facilement des algorithmes dédiés tels que les graphes ou la géométrie computationnelle.

La recherche locale englobe également des métaheuristiques telles que la recherche tabou, le redémarrage, le recuit simulé, la destruction et la reconstruction, la recherche locale généralisée, les chaînes d’éjection, le VLSN, etc.

Pourquoi OscarR.cbls ?

Développer une solution de recherche locale est souvent coûteux car :

• Développer des contraintes efficaces est complexe car cela repose sur une évaluation incrémentale des contraintes.
• Une procédure de recherche dédiée doit être élaborée, et elle doit prendre en compte la structure du problème.

OscaR.cbls est une librairie logicielle qui permet de largement réduire ces coûts de développement.

OscaR.cbls est un outil intelligent pour les ingénieurs en optimisation. Il est fourni sous forme de bibliothèque logicielle open source (LGPL). Programmer en Scala ou en Java est nécessaire pour développer une solution basée sur OscaR.cbls. Quelques exemples sont fournis.

Pour utiliser OscaR.cbls, il est nécessaire de connaître les préceptes de la recherche locale et des métaheuristiques, notamment, afin d’élaborer et paramétrer les modèles et les procédures de recherche dans des applications spécifiques.

Philosophie générale d’OscarR.cbls

OscaR.cbls repose sur la philosophie générale suivante :

• Se concentrer sur la complexité computationnelle et fournir une API bien pensée pour obtenir une bonne complexité computationnelle globale, quelle que soit l’application.
• Offrir un support maximal, à la fois pour la modélisation et la résolution. Il est donc nécessaire de programmer en Scala ou Java pour utiliser OscaR.cbls.
• OscaR.cbls pourrait se résumer à comment investir au mieux le temps de cerveau disponible. OscaR.cbls permet de se concentrer pour :
  • Élaborer un modèle approprié d’un problème métier complexe sans perdre de temps dans la mise en œuvre.
  • Rapidement concevoir et étudier diverses procédures de recherches et métaheuristiques pour identifier la combinaison la mieux adaptée au cas considéré et à ses contraintes.

Principales fonctionnalités d’OscarR.cbls

La recherche locale, c’est la modélisation (modeling) avec la procédure de recherche (searching).

OscaR.cbls offre un support avancé à la fois pour la modélisation et la procédure de recherche :

• Modélisation basée sur les contraintes (constraint-based modeling)
  • Intègre des algorithmes très efficaces pour évaluer les solutions basées sur l’évaluation incrémentale, les pré-calculs, les caches, etc.
• Procédure de recherche basée sur les combinateurs (combinator-based searching)
  • Une procédure de recherche locale doit être conçue pour chaque cas d’utilisation, nous avons donc facilité la définition de toute procédure de recherche locale et métaheuristique en l’assemblant à partir d’une bibliothèque d’éléments standard.

Origines d’OscarR.cbls

OscaR.cbls a débuté en 2011 et a évolué au fil de projets industriels et de recherche. L’objectif global était de structurer les résultats de recherche pertinents issus du milieu académique dans un solveur propre et bien structuré. Il a évolué au fil des années et divers aspects ont été ajoutés, notamment :

• Combinateurs de recherche
• Optimisation de routage basée sur des séquences
• Mécanismes pour développer de nouvelles contraintes globales basées sur des fonctions de transition
• Recherche distribuée
• Informations de profilage

En 2024, nous avons commencé une réécriture en profondeur d’OscaR.cbls. Celui-ci ayant été initialement développé comme prototype de recherche, divers modules reposaient sur des technologies obsolètes. Début 2025, nous avons présenté la première version prête pour la production d’OscaR.cbls. Elle comprend notamment une API de référence qui a été conçue pour être stable face aux évolutions futures d’OscaR.cbls.

Optimisation de routage

La recherche locale s’applique très bien aux problèmes d’optimisation de routage de véhicule.

OscaR.cbls a donc été étendu avec des structures de données, contraintes globales et voisinages spécifiques.

Comme OScaR.cbls en général, ce module a été pensé pour être facilement étendu à de nouvelles contraintes et (méta-)heuristiques.

Et ensuite ?

OscaR.cbls hérite d’un code datant de 2011. Nous sommes actuellement en train de refactoriser l’ensemble de cette base de code. Dans les mois à venir, nous publierons davantage de versions d’OscaR.cbls avec des fonctionnalités incroyables, notamment :

• L’incorporation de plus de fonctionnalités de notre version héritée, y compris :
  • Contraintes globales (100+)
  • Combinateurs de voisinage (recuit simulé, chaînes d’éjection, acceptation tardive, VLSN)
• Optimisation multi-thread et multi-nœuds

OscaR.cbls propose une API utilisateur. Cette API sera rétrocompatible, donc passer aux futures versions d’OscaR.cbls sera simple.

Restez informé sur Github !