Result Diversity for Multi-Modal Route Planning

Abstract : We study multi-modal route planning allowing arbitrary (meaningful) combinations of public transportation, walking, and taking a car / taxi. In the straightforward model, the number of Pareto-optimal solutions explodes. It turns out that many of them are similar to each other or unreasonable. We introduce a new filtering procedure, Types aNd Thresholds (TNT), which leads to a small yet representative subset of the reasonable paths. We consider metropolitan areas like New York, where a fast computation of the paths is difficult. To reduce the high computation times, optimality-preserving and heuristic approaches are introduced. We experimentally evaluate our approach with respect to result quality and query time. The experiments confirm that our result sets are indeed small (around 5 results per query) and representative (among the reasonable Pareto-optimal paths), and with average query times of about one second or less.
Type de document :
Communication dans un congrès
Daniele Frigioni and Sebastian Stiller. ATMOS - 13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems - 2013, Sep 2013, Sophia Antipolis, France. Schloss Dagstuhl―Leibniz-Zentrum fuer Informatik, 33, pp.123--136, 2013, OpenAccess Series in Informatics (OASIcs). 〈10.4230/OASIcs.ATMOS.2013.123〉
Liste complète des métadonnées

Littérature citée [12 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00871740
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : jeudi 10 octobre 2013 - 11:59:38
Dernière modification le : vendredi 11 octobre 2013 - 13:38:04
Document(s) archivé(s) le : vendredi 7 avril 2017 - 08:56:29

Fichier

11.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Hannah Bast, Mirko Brodesser, Sabine Storandt. Result Diversity for Multi-Modal Route Planning. Daniele Frigioni and Sebastian Stiller. ATMOS - 13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems - 2013, Sep 2013, Sophia Antipolis, France. Schloss Dagstuhl―Leibniz-Zentrum fuer Informatik, 33, pp.123--136, 2013, OpenAccess Series in Informatics (OASIcs). 〈10.4230/OASIcs.ATMOS.2013.123〉. 〈hal-00871740〉

Partager

Métriques

Consultations de la notice

155

Téléchargements de fichiers

292