Open Street permet de trouver le plus court chemin passant par une liste de villes donnée. Ce problème d’optimisation est communément appelé « problème du voyageur de commerce » par les mathématiciens. Il est connu pour être un problème NP-complet, c’est à dire qu’il n’existe pas actuellement d’algorithme qui permettre une résolution exacte en un temps fini. Cela explique qu’au delà d’une dizaine de points, les algorithmes de type « force brute » sont incapables d’apporter une solution en un temps raisonnable.
A titre informatif, le tableau ci-dessous décrit le nombre d’itinéraires possibles en fonction du nombre de lieux de passages. Pour chacune de ces possibilités, un algorithme « force brute » devrait sommer la distance totale entre chacun des points. On se rend vite compte qu’un nombre de possibilités à 2568 zéros est bien trop grand pour être traité par des ordinateurs, même les plus puissants du monde comme on en utilise à la NASA où chez Météo France.
Lieux de passage | Possibilités |
20 | 2,43 1018 |
50 | 3,04 1064 |
100 | 9,33 10157 |
200 | 7,88 10375 |
1000 | 4,02 102567 |
Ainsi, nous n’utilisons pas d’algorithme qui tenterait de comparer tous les trajets possible, et notre logiciel de résolution a été développée par nos soins. En quelques secondes, Open Street peut trouver des solutions approchées de l’ordre de 99% pour des cas d’optimisation jusqu’à plusieurs centaines de points. Les solutions proposées permettront donc de générer des économies substantielles pour des acteurs de tous secteurs, dont l’activité nécessite des tournées par la route.
La vraie force d’Open Street est de réussir à donner rapidement des résultats fiables pour un problème mathématique complexe.