KIT | KIT-Bibliothek | Impressum | Datenschutz

Fast Detour Computation for Ride Sharing

Geisberger, Robert; Luxen, Dennis; Neubauer, Sabine; Sanders, Peter; Volker, Lars

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.

Open Access Logo


Verlagsausgabe §
DOI: 10.5445/IR/1000097651
Veröffentlicht am 20.08.2019
Originalveröffentlichung
DOI: 10.4230/OASIcs.ATMOS.2010.88
Scopus
Zitationen: 26
Coverbild
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Proceedingsbeitrag
Jahr 2010
Sprache Englisch
Identifikator ISBN: 978-3-939897-20-0
ISSN: 2190-6807
KITopen-ID: 1000097651
Erschienen in 10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS’10), Liverpool, GB, September 9, 2010. Ed.: T. Erlebach
Verlag Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl
Seiten 88-99
Serie OpenAccess Series in Informatics ; 14
Nachgewiesen in Scopus
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page