Critical-Time-Based Approach to Route Planning (20130008, Dr. Shashi Shekar)

Faster, more accurate algorithm reduces calculation time and computational cost

A novel route-planning algorithm dynamically updates routes by incorporating real-time traffic data to accurately predict future travel times and traffic situations. The algorithm’s temporally detailed (TD) roadmaps contain travel time information about road segments at all times of the day and week at fine temporal resolutions (seconds or minutes). By using better modelling of the traveler's perspective through the Lagrangian frame of reference, it can predict the fastest route at start time (e.g., it can change route preferences during rush and non-rush hours). The algorithm uses a spatio-temporal network and critical-time-points—start times at which an optimal path may change—to compute the fastest path (instead of determining the fastest path for each start-time). This adaptation significantly reduces calculation time and computational cost, resulting in a faster and more accurate algorithm.

Accurately predicts future travel times based on future traffic situations

Current online map services usually plan routes without considering real-time traffic data. And while some providers do consider real-time traffic data (e.g., Google Maps), the data is based the time the service was requested, which assumes travelers will experience the same traffic conditions at the time the route was planned all the way until they reach their destination. And no services currently predict arrival times in future events. This new algorithm incorporates real-time traffic data to dynamically update routes accordingly. In addition, it can accurately predict future travel times based on future traffic situations. Furthermore, most current techniques assume road segments in a transportation network follow First-in-First-Out (FIFO) logic (where flow arrives at the destination in the same order as it starts at the source), but transportation networks usually exhibit non-FIFO behavior. This algorithm is suitable for both FIFO and non-FIFO networks.

Phase of Development

• Prototype developed

Benefits

• Accurately predicts future travel times based on future traffic situations
• Faster and higher quality route planning algorithm
• Reduces computational cost
• Significantly reduces calculation time
• Shorter travel time may mean lower fuel consumption and greenhouse emissions

Features

• Dynamically updates routes by incorporating real-time traffic data
• Temporally detailed (TD) roadmaps
• Critical-time-points (start times at which an optimal path may change)
• Suitable for both FIFO and non-FIFO networks

Applications

• Mapping services, map routing software
• Consumer facing mapping/navigation programs (e.g., Google Maps, Bing maps, MapQuest, TomTom, Garmin, Apple, etc.)
• GPS systems, in-car GPS devices (e.g., Garmin, GM Onstar, etc.)
• Real-time traffic information providers (e.g., NAVTEQ, Inrix)
• Logistic and delivery software and services (e.g., UPS, FedEx)
• Location-based service applications
• Mobile device (e.g., smart phone, tablet, custom GPS devices) based routing and navigation apps