Le voyageur de commerce se libère avec VROOM
Catégorie: A l'actu, Données, Logiciels, Mobilité, Open Data, Réseaux/Transports
Par Sukran Dal
Le problème du voyageur de commerce (travelling salesman problem ou TSP) continue à faire couler beaucoup de calculs. Julien Coupey, travaillant sur la mobilité à l’institut FEMTO-ST de Besançon, s’y attelle en s’appuyant sur Open Street Map et obtient un très bon niveau de performance. Explications techniques lors de sa présentation à State of the Map 2017 à Avignon.
« Dans ce TSP, l’itinéraire n’est pas en boucle. Les points de départ et d’arrivée peuvent être différents, le point d’arrivée peut ne pas être fixé ou vice-versa. Avec VROOM (Vehicle Routing Open source Optimization Machine), les points passent par OSRM ou un autre calculateur afin de produire une matrice des temps de trajet routier. Cette matrice est asymétrique car les temps de trajets entre deux villes ne sont pas les mêmes à l’aller et au retour du fait des contraintes de circulation (sens unique par exemple).
L’heuristique de Christofides, rapide dans les calculs de recherche d’itinéraire, définit une première série de solutions. Puis des opérateurs de recherche locale, par la suppression des contraintes de circulation, repèrent des itinéraires plus optimisés (modèle rendu symétrique). Enfin, les contraintes de circulation sont réintroduites afin de rendre le modèle réaliste. Enfin, une recherche locale donne un dernier ensemble de solutions. Un benchmark avec une librairie de TSP, nommée TSPLIB, montre que 75 % des solutions issues de VROOM se situent à moins de 3,56 % des résultats optimums trouvés par TSPLIB. »
L’itinéraire optimisé entre 93 lieux défini en 83 millisecondes grâce à VROOM
Déjà utilisé par des entreprises comme Mapotempo, Julien Coupey cherche partenaires et financements pour développer de nouvelles fonctionnalités.
Communiqués 
