[ROADEF20] Modéliser un problème de Recherche Opérationnelle: retour sur expériences

Le résumé ci-dessous est issu d’une présentation réalisée par Guillaume Pinot (Ingénieur Recherche Opérationnelle chez Kardinal) et Aurélien Questel (Eurodécision) lors de la ROADEF 2020. Vous pouvez retrouver le support de la présentation à la fin de cet article.

Introduction

La plupart du temps, la résolution d’un problème de Recherche Opérationnelle est directement réalisée en se basant sur le modèle informatique du problème, venant directement du client. C’est souvent la manière la plus simple et la plus rapide.

Mais, pour pouvoir mutualiser les développements, il peut être judicieux de réaliser un modèle intermédiaire, entre la représentation purement mathématique et le modèle du client. Un tel modèle
intermédiaire permet aussi de simplifier et mutualiser la résolution du modèle de recherche opérationnelle.

Ce découpage est un problème complexe, avec différents compromis possibles. Nous donnons des préconisations pour réaliser ce modèle intermédiaire en s’appuyant sur plusieurs cas industriels.

Solutions Industrielles

Eurodécision propose le produit LP-EasyDriver pour répondre aux problèmes d’habillage et de graphicage (planification des chauffeurs de bus et des bus). Ce produit est utilisé par des  transporteurs de différents pays, aux réglementations diverses. Pour sa résolution, il repose sur le produit LP-TaskPlanner.

Kardinal propose un outil de planification de tournées de véhicules en SaaS. Cette solution est utilisée pour différents types de clients, allant du dernier kilomètre de la livraison de colis aux prélèvements sanguin à domicile. Pour faciliter l’évolution du produit, un modèle mathématique de tournées de véhicule a été réalisé.

Les différents niveaux d’abstraction

L’interface pour le client

Eurodécision propose le produit LP-EasyDriver pour répondre aux problèmes d’habillage et de graphicage (planification des chauffeurs de bus et des bus). Ce produit est utilisé par des transporteurs de différents pays, aux réglementations diverses. Pour sa résolution, il repose sur le produit LP-TaskPlanner.

Kardinal propose un outil de planification de tournées de véhicules en SaaS. Cette solution est utilisée pour différents types de clients, allant du dernier kilomètre de la livraison de colis aux  prélèvements sanguin à domicile. Pour faciliter l’évolution du produit, un modèle mathématique de tournées de véhicule a été réalisé.

Modèle mathématique intermédiaire

Créer un modèle mathématique intermédiaire entre le modèle métier et le modèle de résolution apporte plusieurs avantages.

Tout d’abord, cela permet de travailler sur un modèle plus générique sans gêner le client. Par exemple, le modèle mathématique peut permettre de mettre comme contrainte une borne sur un indicateur d’une ressource. Cela permet de n’avoir qu’une sorte de contrainte pour gérer la durée maximale de travail et le nombre maximal de tâches effectuées. Ainsi, l’interface métier peut faire des évolutions sans avoir à toucher la partie résolution. De plus, la résolution n’a à implémenter ce genre de contrainte qu’une seule fois.

D’autre part, développer la résolution sur un modèle plus générique apporte également des avantages: Le modèle étant plus explicite, il est plus facile de se concentrer uniquement sur la résolution et ne pas mélanger le métier avec les détails d’implémentation de la résolution.

Finalement, la méthode de résolution peut être changée plus facilement. Comme la couche transformant le modèle métier en modèle mathématique est commune, la création d’une nouvelle méthode de résolution est simplifiée.

La plus grande difficulté est de trouver le bon niveau d’abstraction pour ce modèle mathématique. En effet, plus ce modèle est proche du métier, et plus on garde de la sémantique du problème, permettant de s’abstraire de la méthode de résolution. Mais un modèle trop proche du métier le rendra peu réutilisable. D’un autre coté, avoir un modèle mathématique plus proche de la méthode de résolution permet de la réutiliser pour résoudre plus de problème différent. Mais il est alors plus restreint dans la méthode de résolution, et des informations peuvent être perdues dans la
transformation du modèle.

Modèle mathématique proche du métier: le cas du modèle de Kardinal

Le modèle mathématique de Kardinal reste proche du métier. Il propose de déclarer des ressources, des arrêts, des matrices de distances, des indicateurs et des contraintes. Les indicateurs et les contraintes peuvent être proche du métier (durée travaillée) ou des combinaisons génériques d’autres indicateurs (la somme pondérée de plusieurs indicateurs).

Ce modèle laisse une totale liberté sur la méthode de résolution, mais reste cloisonné à la résolution de problème de type tournées de véhicules.

Modèle mathématique proche de la méthode de résolution: le cas LP-TaskPlanner

LP-TaskPlanner expose un modèle de génération de colonnes avec comme sous-problème un plus court chemin sous contrainte de ressources.

Sa généricité lui permet d’être utilisé dans plusieurs produits métier comme LP-EasyDriver et LP-ShiftPlanner (planification de personnel). Par contre, son modèle proche de la méthode de résolution limite les méthodes de résolutions possibles.

Conclusions et perspectives

Il est important de créer des modèles intermédiaires entre le problème du client et la méthode de résolution. Cela permet, entre autre, de réutiliser les composants, de décorréler le travail des différentes équipes et de simplifier le développement de la méthode de résolution.

Le découpage peut être fait à différents niveaux, avec des avantages et des inconvénients. Il est également possible de réaliser plusieurs découpages: il est théoriquement possible d’utiliser LP-TaskPlanner pour résoudre le modèle mathématique de Kardinal.

 

Pour télécharger le support de la présentation réalisée par Guillaume Pinot, Ingénieur en RO chez Kardinal, lors de la ROADEF 2020, cliquez ici.