MUSE : planification d'itinéraires inspirée des séparateurs multimodaux

Cet article présente un algorithme multimodal du chemin le plus court basé sur des séparateurs de graphes. En divisant le réseau en partitions, le prétraitement peut être parallélisé, ce qui permet de calculer efficacement le chemin le plus court entre les différents modes de transport. Pendant la phase de requête, l'algorithme récupère rapidement l'itinéraire le plus court pour une séquence de modes donnée. Les travaux en cours se concentrent sur l'adaptation de l'approche à des graphes plus grands (France et Europe) et sur l'exploration de partitions à plusieurs niveaux avec une recherche bidirectionnelle afin d'améliorer encore les performances, ainsi que sur l'adaptation de la méthode pour les graphes dynamiques dont les temps de trajet dépendent du temps.

‍

Avec le développement du cloud, le domaine des algorithmes permettant de calculer des trajets plus courts est en plein essor. Certaines solutions, dites multimodales, sont conçues pour combiner différents modes de transport, mais au prix d'une augmentation significative de la complexité. Nous proposons ici MUSE, un algorithme basé sur des séparateurs de graphes, mais adapté au cas multimodal. Dans une phase de prétraitement, nous divisons d'abord le graphique en partitions indépendantes (ou cellules), chacune étant divisée en modes de transport, afin de pouvoir répondre ultérieurement à n'importe quelle requête. Nous pré-calculons ensuite tous les itinéraires les plus courts sur ce petit nombre de cellules, en tenant compte des étiquettes (modes) de chaque arête. Nous pouvons ainsi répondre très rapidement à une requête lors de la phase en ligne : l'utilisateur spécifie les séquences de modes qu'il autorise et utilise les itinéraires les plus courts pré-calculés.