MUSE : une planification d'itinéraires inspirée de Séparateurs Multimodaux
(2020) ALGOTEL 2020 – 22èmes Rencontres Fran- cophones sur les Aspects Algorithmiques des Télécommunications — Location: Lyon
Files
Pelsser_ICTM22.pdf
Open Access - Adobe PDF
- 431.22 KB
Details
- Authors
- Abstract
- Le domaine des algorithmes de calcul de plus courts chemins connait un essor important avec le développement du cloud. Quelques solutions, dites ultimodales, 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.
- Affiliations
Université de Strasbourg
Citations
Falek, A. M., Pelsser, C., Julien, S., & Theoleyre, F. (2020). MUSE : une planification d’itinéraires inspirée de Séparateurs Multimodaux. ALGOTEL 2020 – 22èmes Rencontres Fran- cophones sur les Aspects Algorithmiques des Télécommunications, Lyon. https://hdl.handle.net/2078.5/256393