Algorithme mathématique : La problématique

Les problèmes de tournées de véhicules sont à la fois simples – à énoncer et à comprendre (« Je dois me rendre à tel endroit, à telle heure, puis à tel autre endroit, à telle heure ») – et très complexes à résoudre.

La variante la plus « facile », où il n’y a aucune contrainte et un seul véhicule à gérer est connue sous le nom de Travelling salesman problem (problème du voyageur de commerce).

Très étudié depuis des dizaines d’années, c’est un problème d’optimisation combinatoire qui est NP-complet.

Concrètement, cela signifie que le nombre de solutions possibles est tel que tous les algorithmes mathématiques connus permettant d’obtenir la solution optimale ont des temps d’exécution qui augmentent de façon exponentielle avec la taille du problème.

Cela les rend généralement inexploitables en pratique, y compris sur des exemples de taille modeste.

A titre d’exemple et comme le montre l’image plus haut, pour trois interventions avec un seul véhicule, il y a théoriquement 6 tournées différentes possibles.

La formule mathématique s’appelle « factorielle n » ou « n! ». Ici c’est factorielle 3 ou plus simplement 3 x 2 x 1 = 6

Pour 10 interventions  il est possible de créer 3.628.800 tournées différentes (10 x 9 x 8 ….. x 2 x 1).

Pour analyser ces tournées, un ordinateur capable d’étudier 10.000 tournées à la seconde, aurait besoin de 6 minutes.

Mais en ajoutant une seule intervention, le nombre de tournée différentes qu’il est possible de créer approche déjà les 40.000.000 ….

Pour 15 interventions, ce même ordinateur aurait besoin de 49 mois et pour 20 interventions plus de 7,5 millions d’années.

Et pour couronner le tout, avec 50 interventions le nombre de tournées différentes possibles dépasse le nombre d’atomes de l’univers…

La solution

Face à la difficulté du problème, et pour fournir efficacement des solutions aussi proches que possibles de l’optimal, Biosolver utilise une approche heuristique et méta-heuristique.

Cela permet de construire et de raffiner des solutions, tout en garantissant leur validité vis-à-vis de l’ensemble des contraintes.

Les choix algorithmiques sont guidés par les besoins :

• de performance (obtenir la meilleure solution possible en un temps rapide) et
• de pertinence (fournir une solution utilisable immédiatement et répondant précisément au besoin).

Par conséquent, et avant de démarrer un développement interne d’un algorithme spécifique, forcément long et coûteux, nous avons analysé les algorithmes mathématiques existants sur le marché.

Certains sont open source et équipent plusieurs solutions existantes sur le marché.

Mais aucun ne permettait de prendre en charge des contraintes que nous souhaitions respecter.

Aussi, nous avons développé dans un premier temps un algorithme mathématique spécifique avec plusieurs laboratoires de recherche du CNRS.

Le développement de ce premier algorithme et le logiciel BIOSOLVER a nécessité près d’un an de recherche & développement.

Mais pour répondre à de nouvelles contraintes exprimées par nos clients, nous avons crée et implémenté un nouvel et deuxième algorithme mathématique et une nouvelle matrice.

Aussi, il est désormais possible de disposer de deux versions de BIOSOLVER.

En fonction des contraintes et des objectifs poursuivis par le client et dans certains cas il est également possible de disposer d’une version dotée des deux algorithmes.

Cette version est mise à disposition des clients souhaitant, à partir de leurs propres cas, générer des tournées optimisées avec l’un et/ou l’autre algorithme.