KIT | KIT-Bibliothek | Impressum | Datenschutz

Fast Detour Computation for Ride Sharing

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

Todays ride sharing services still mimic a better billboard. They list the offers and allow to search for the source and target city, sometimes enriched with radial search. So finding a connection between big cities is quite easy. These places are on a list of designated origin and distination points. But when you want to go from a small town to another small town, even when they are next to a freeway, you run into problems. You can't find offers that would or could pass by the town easily with little or no detour. We solve this interesting problem by presenting a fast algorithm that computes the offers with the smallest detours \wrt a request. Our experiments show that the problem is efficiently solvable in times suitable for a web service implementation. For realistic database size we achieve lookup times of about 5ms and a matching rate of 90% instead of just 70% for the simple matching algorithms used today.

Open Access Logo

Volltext §
DOI: 10.5445/IR/1000012221
Cover der Publikation
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Forschungsbericht/Preprint
Publikationsjahr 2009
Sprache Englisch
Identifikator urn:nbn:de:swb:90-122210
KITopen-ID: 1000012221
Verlag Universität Karlsruhe
Umfang 5 S.
Bemerkung zur Veröffentlichung Technischer Bericht
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page