- Forward


Real-Time Routing
An Introduction


Prof. David Bernstein
James Madison University

Computer Science Department
bernstdh@jmu.edu

Print

Motivation
Back Forward
  • Personal Navigation Systems:
    • Provide maps, real-time location, and a suggested route
  • Users of Personal Navigation Systems:
    • Either by choice or as a result of "driver error" do not always follow the suggested route
  • The Implication:
    • Personal navigation systems need to be able to determine that the user has gone "off route" and determine a new suggested route in real time
What's the Big Deal?
Back Forward
  • We Know...
    • How to calculate "shortest" paths
  • But...
    • "City" street segments are often only 0.1 miles long and at 30mph this distance is covered in 12 seconds
    • In that amount of time we must: determine that the user is "off route", calculate a new route, and present it to the user (perhaps on a map, in text, and as "spoken" directions)
Using the "All Pairs" Problem
Back Forward
  • The Idea:
    • Find the "shortest" path between every pair of nodes (which can be done in \(O(n^{3})\) time)
  • Different Implementations:
    • Solve this problem up front and use the results when the user goes "off route"
    • Order the nodes (based on their proximity to the origin) and use idle processor time
Using the Suggested Route
Back Forward
  • The Idea:
    • When the user goes "off route" calculate the shortest path back to the suggested route (i.e., to any node in the route)
  • An Observation:
    • The resulting route is not necessarily optimal
Using the Suggested Route (cont.)
Back Forward

Getting back to the Suggested Route

images/back-to-path.gif
There's Always More to Learn
Back -