Abstract
Le domaine des algorithmes de calcul de plus courts chemins connait un essor important avec le développement du cloud. Quelques solutions, dites multimodales, sont conçues pour combiner divers modes de transports, 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 découpons tout d’abord le graphe en partitions indépendantes (ou cellules), chacune découpée en modes de transport afin de pouvoir plus tard répondreà n’importe quelle requête,. Ensuite, nous précalculons toutes les plus courtes routes, sur ce petit nombre de cellules, en tenant compte des labels (modes) de chaque arête. Nous pouvons ainsi répondreà une requête très rapidement dans la phase online : l’utilisateur spécifie les séquences de mode qu’il autorise, et exploite les plus courtes routes pré-calculées.