1 Search Results for "Volker, Lars"


Document
Fast Detour Computation for Ride Sharing

Authors: Robert Geisberger, Dennis Luxen, Sabine Neubauer, Peter Sanders, and Lars Volker

Published in: OASIcs, Volume 14, 10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS'10) (2010)


Abstract
Ride sharing becomes more and more popular not least because internet services help matching offers and request. However, current systems use a rather simple-minded functionality allowing to search for the origin and destination city, sometimes enriched with radial search around the cities. We show that theses services can be substantially improved using innovative route planning algorithms. More concretely, we generalize previous static algorithms for many-to-many routing to a dynamic setting and develop an additional pruning strategy. With these measures it becomes possible to match each request to $n$ offers using $2n+1$ exact travel time computations in a large road network in a fraction of a microsecond per offer. For requests spread over Germany according to population density, we are able to reduce the number of failing entries substantially. We are able to find a reasonable match for more than 60% of the failing entries left by contemporary matching strategies. Additionally, we halve the average waste of resources in the matches found compared to radial search.

Cite as

Robert Geisberger, Dennis Luxen, Sabine Neubauer, Peter Sanders, and Lars Volker. Fast Detour Computation for Ride Sharing. In 10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS'10). Open Access Series in Informatics (OASIcs), Volume 14, pp. 88-99, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2010)


Copy BibTex To Clipboard

@InProceedings{geisberger_et_al:OASIcs.ATMOS.2010.88,
  author =	{Geisberger, Robert and Luxen, Dennis and Neubauer, Sabine and Sanders, Peter and Volker, Lars},
  title =	{{Fast Detour Computation for Ride Sharing}},
  booktitle =	{10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS'10)},
  pages =	{88--99},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-20-0},
  ISSN =	{2190-6807},
  year =	{2010},
  volume =	{14},
  editor =	{Erlebach, Thomas and L\"{u}bbecke, Marco},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2010.88},
  URN =		{urn:nbn:de:0030-drops-27525},
  doi =		{10.4230/OASIcs.ATMOS.2010.88},
  annote =	{Keywords: ride sharing, algorithm engineering, carpool}
}
  • Refine by Author
  • 1 Geisberger, Robert
  • 1 Luxen, Dennis
  • 1 Neubauer, Sabine
  • 1 Sanders, Peter
  • 1 Volker, Lars

  • Refine by Classification

  • Refine by Keyword
  • 1 algorithm engineering
  • 1 carpool
  • 1 ride sharing

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2010

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail