Customised Shortest Paths Using a Distributed Reverse Oracle

Authors

  • Arthur Mahéo Monash University, Faculty of IT, Melbourne, Australia
  • Shizhe Zhao Monash University, Faculty of IT, Melbourne, Australia
  • Afzaal Hassan Swinburne University of Technology, Melbourne, Australia
  • Daniel D. Harabor Monash University, Faculty of IT, Melbourne, Australia
  • Peter J. Stuckey Monash University, Faculty of IT, Melbourne, Australia
  • Mark Wallace Monash University, Faculty of IT, Melbourne, Australia

Keywords:

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

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.

Downloads

Published

2021-07-21