DROPS

Document

DOI: 10.4230/OASIcs.ATMOS.2013.123

Result Diversity for Multi-Modal Route Planning

Authors: Hannah Bast, Mirko Brodesser, and Sabine Storandt

Published in: OASIcs, Volume 33, 13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (2013)

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.

Cite as

Hannah Bast, Mirko Brodesser, and Sabine Storandt. Result Diversity for Multi-Modal Route Planning. In 13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 33, pp. 123-136, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{bast_et_al:OASIcs.ATMOS.2013.123,
  author =	{Bast, Hannah and Brodesser, Mirko and Storandt, Sabine},
  title =	{{Result Diversity for Multi-Modal Route Planning}},
  booktitle =	{13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  pages =	{123--136},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-58-3},
  ISSN =	{2190-6807},
  year =	{2013},
  volume =	{33},
  editor =	{Frigioni, Daniele and Stiller, Sebastian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2013.123},
  URN =		{urn:nbn:de:0030-drops-42494},
  doi =		{10.4230/OASIcs.ATMOS.2013.123},
  annote =	{Keywords: Route Planning, Multi-Modal, Result Diversity}
}

Search Results

Documents authored by Brodesser, Mirko

Result Diversity for Multi-Modal Route Planning

Abstract

Cite as

Thanks for your feedback!

Could not send message