Customised shortest paths using a distributed reverse oracle

Arthur Maheo, Shizhe Zhao, Afzaal Hassan, Daniel Harabor, Peter Stuckey, Mark Wallace

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

3 Citations (Scopus)


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.

Original languageEnglish
Title of host publicationProceedings of the Fourteenth International Symposium on Combinatorial Search (SoCS 2021)
EditorsHang Ma, Ivan Serina
Place of PublicationPalo Alto CA USA
PublisherAssociation for the Advancement of Artificial Intelligence (AAAI)
Number of pages9
ISBN (Electronic)9781577358701, 9781713834557
Publication statusPublished - 2021
EventInternational Symposium on Combinatorial Search 2021 - Online, Guangzhou, China
Duration: 26 Jul 202130 Jul 2021
Conference number: 14th (Proceedings)

Publication series

Name14th International Symposium on Combinatorial Search, SoCS 2021
PublisherAssociation for the Advancement of Artificial Intelligence (AAAI)


ConferenceInternational Symposium on Combinatorial Search 2021
Abbreviated titleSoCS 2021
Internet address


  • Real-time Search
  • Real-life Applications
  • Time, Memory
  • And Solution Quality Trade-offs

Cite this