Customised Shortest Paths using a Distributed Reverse Oracle - SoCS 2021
Channel: Shortest Path Lab @ Monash University
Date: 2024-02-08

Mahéo, A., Zhao, S., Hassan, A., Harabor, D.D., Stuckey, P.J. and Wallace, M., 2021, July. Customised shortest paths using a distributed reverse oracle. In Proceedings of the International Symposium on Combinatorial Search (Vol. 12, No. 1, pp. 79-87).

Speaker: Arthur Maheó

Abstract:
We consider the design and implementation of a centralised oracle that provides commuters with customised and congestion-aware driving directions. Computing directions for a single journey is straightforward, but doing so at city-scale, in real-time, and under changing conditions is extremely challenging. In this work we describe a new type of centralised oracle which combines fast database-driven path planning with a query management system that distributes work across a small commodity cluster of networked machines. Our system allows large-scale changes to the underlying graph metric, from one query to the next, and it supports a variety of query types including optimal, bounded suboptimal, time-budgeted and k-prefix. Simulated experiments show strong results: we can provide real-time routing for all peak-hour commuter trips in the city of Melbourne, Australia. 

Paper source (PDF): 
https://doi.org/10.1609/socs.v12i1.18554

Citations:
https://dblp.org/rec/conf/socs/MaheoZAHS021.html?view=bibtex