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

Cet article présente un algorithme multimodal du plus court chemin 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 plus court chemin pour différents modes de transport. Pendant la phase d'interrogation, l'algorithme récupère rapidement l'itinéraire le plus court pour toute séquence donnée de modes de transport. Les travaux en cours se concentrent sur l'extension de l'approche à des graphes plus grands (France et Europe) et sur l'exploration de partitions à plusieurs niveaux avec une recherche bidirectionnelle pour améliorer encore les performances, ainsi que sur l'adaptation de la méthode à des graphes dynamiques avec des temps de trajet dépendant du temps.

‍

Avec le développement du cloud, le domaine des algorithmes de calcul de plus courts chemins 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 les séparateurs de graphes, mais adapté au cas multimodal. Dans une phase de prétraitement, nous divisons d'abord le graphe en partitions indépendantes (ou cellules), chacune partitionnée en modes de transport, afin de pouvoir répondre ultérieurement à toute 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. De cette manière, nous pouvons répondre à une requête très rapidement dans 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.