Office for Technology Commercialization
http://www.research.umn.edu/techcomm
612-624-0550

Critical-Time-Based Approach to Route Planning

Technology #20130008

Questions about this technology? Ask a Technology Manager

Download Printable PDF

Image Gallery
Jamarat complex with multiple levels shown as 1, 2, 3, and 4 on associated ramps(a) the Jamarat complex with multiple levels shown as 1, 2, 3, and 4 on associated ramps; (b) crowd density and walking speed model; (c) experiment design; (d) effect of the number of evacuees (1 person/m2, n = 1,394); (e) effect of crowd density (150,000 evacuees, n = 1,394); (f) runtime comparison (1 person/m2, n = 1,394); (g) runtime comparison (150,000 evacuees, n = 1,394); (h) cumulative evacuees of 150,000 evacuees (1 person/m2, n = 1,394) ISA input and possible outputs: (a) input, (b) allotment 1 (invalid), (c) allotment 2, and (d) allotment 3.
Categories
Researchers
Shashi Shekar, PhD
Professor, Computer Science and Engineering
External Link (www-users.cs.umn.edu)
Managed By
Andrew Morrow
Technology Licensing Officer
Patent Protection
US Patent 9285218
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


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


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 Andrew Morrow 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.