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

Technology No. 20130008
IP Status: Issued US Patent; Application #: 13/974,777


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


Researchers
Shashi Shekar, PhD
Professor, Computer Science and Engineering
External Link (experts.umn.edu)

Publications
Intelligent Shelter Allotment for Emergency Evacuation Planning: A Case Study of Makkah
IEEE Intelligent Systems, Volume: 30, Issue: 5 , Sept.-Oct. 2015
Experiences with evacuation route planning algorithms
International Journal of Geographical Information Science, 26:12, 2253-2265

Interested in Licensing?
The University relies on industry partners to scale up technologies to large enough production capacity for commercial purposes. The license is available for this technology and would be for the sale, manufacture or use of products claimed by the issued patents. Please contact us to share your business needs and technical interest in this technology and if you are interested in licensing the technology for further research and development.
  • swap_vertical_circlecloud_downloadSupporting documents (0)
Questions about this technology?