Proceedings of the International Symposium on Combinatorial Search · 2021 · 39 citations · 12 references
ComputingTransportation PlanningDistributed SystemsTransportationTransportation EngineeringShortest Path AlgorithmsTransportation NetworksDijkstra's Algorithm
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.
12
A note on two problems in connexion with graphs
E. Dijkstra · Numerische Mathematik · 1959 · 23.8K citations
Computing the shortest path: A search meets graph theory
Andrew V. Goldberg, Chris Harrelson · 2005 · 728 citations
Exact Routing in Large Road Networks Using Contraction Hierarchies
Robert Geisberger, Peter Sanders, Dominik Schultes et al. · Transportation Science · 2012 · 319 citations · Full text