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

1 Citation (Scopus)

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.

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)
Pages79-87
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
https://ojs.aaai.org/index.php/SOCS (Proceedings)

Publication series

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

Conference

ConferenceInternational Symposium on Combinatorial Search 2021
Abbreviated titleSoCS 2021
Country/TerritoryChina
CityGuangzhou
Period26/07/2130/07/21
Internet address

Keywords

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

Cite this