Real-Time Routing

Real-Time Routing
An Introduction

Prof. David Bernstein
James Madison University

Computer Science Department

bernstdh@jmu.edu

Motivation

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?

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

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

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.)

Getting back to the Suggested Route