AAAI Publications, Sixth Annual Symposium on Combinatorial Search

Font Size: 
Multi-Hop Ride Sharing
Florian Drews, Dennis Luxen

Last modified: 2013-06-19


We study the problem of ride sharing in road networks. Current approaches to this problem focus on simple bulletin board like services or on algorithms that do not allow to transfer. In this work, we present a solution with an arbitrary number of transfers that respects personal preferences of the users. We engineer the ride sharing problem by searching a graph that represents a timetable network similar to those used for train networks. Our experimental analysis shows that our solution provides good performance and that it is significantly faster than a naive search. The algorithm achieves about an order of magnitude higher speedups over Dijkstra's algorithm than what could be expected from previous work.


Algorithm Engineerring, Ride Sharing, Shortest Paths

Full Text: PDF