Implémentation du Chinese Postman Problem au sein du moteur de routage Valhalla

Dans la continuité de l'article précédent sur le routage Kadas, nous voulons maintenant calculer la route la plus courte pour patrouiller toutes les routes d'une région sélectionnée, avec la possibilité d'inclure les zones à éviter.

Ce problème est connu sous le nom de Chinese Postman (“facteur chinois”) Problem ou Route Inspection Problem en théorie des graphes, où le but est de trouver le chemin le plus court tout en visitant chaque arête du graphe.

Il peut être résolu en un temps polynomial pour les graphes dirigés et non dirigés. Pour un graphe mixte, le problème devient un problème NP-Complet.

Nous avons dû implémenter le solveur du “facteur chinois” sur Valhalla car il n'existait pas auparavant.

Dans cette implémentation, nous travaillons avec un graphe dirigé car il correspond à la représentation graphique dans Valhalla pour les données OpenStreetMap. L'algorithme Chinese Postman a déjà été développe dans des domaines théoriques et académiques. Par exemple, il est possible de l'explorer avec cette visualisation de la Technische Universität München (TUM). À l’heure actuelle, 3 algorithmes sont nécessaires pour résoudre le problème : Floyd-Warshall algorithm, Hungarian Method, et Hierholzer Method. Pour Floyd-Warshall, nous utilisons un algorithme de matrice de coûts existant et inhérent à Valhalla.

Le plus grand défi consiste à intégrer l'algorithme à Valhalla et à traiter certains cas réels. L'algorithme ou l'implémentation existante ne traite qu'une situation idéale (c'est-à-dire que le graphe est fortement connecté). Ce n'est pas le cas dans les données du monde réel, nous avons donc dû apporter plusieurs améliorations et ajouts à l'algorithme théorique, qui inclut par exemple de quitter la zone d'intérêt pour visiter des parties du réseau qui ne peuvent être atteintes de l'intérieur.

Finalement, nous avons réussi à créer un prototype fonctionnel d'un solveur de facteur chinois dans Valhalla. L'utilisateur peut dessiner la zone qu'il souhaite visiter, une zone qui ne doit pas être visitée et le type de véhicules utilisés. Il renverra un itinéraire avec une navigation virage par virage, tout comme un algorithme de routage standard. Cela signifie que l'itinéraire traité peut également être utilisé pour la navigation.

Le prochain plan est de fusionner cette fonctionnalité avec la branche principale afin qu'elle puisse être utilisée et testée par la communauté. Nous tenons à remercier le client et financeur de ce projet Armasuisse.