how do GPS devices find the best route?
Posted by Laura McLay on August 27, 2012
The GPS maker TomTom was one of the ISMP sponsors (I attended ISMP last week) and they organized a session about optimizing traffic with TomTom speakers.
TomTom’s bold Manifesto: When 10% of people drive with TomTom’s HD traffic, roads will flow more efficiently and journey times will be reduced by 5% for everyone.
Google Maps and every GPS uses some kind of shortest path algorithm to recommend routes. These models need road costs to find a shortest path. TomTom’s cost models allow for
- Line paths (traffic speeds)
- Turn costs (left turns, exit highway penalties)
- Path costs (complex manuveurs, U-turns)
The path to success involves getting estimates of these costs. TomTom has done quite a bit of crowd sourcing. TomTom’s data is stored in Amsterdam, and it grows by a factor of 2-3 per year. They captured almost 8M km this year just in Berlin. They capture >1B travel speeds per day across 50B km of roads. They do find that crowdsourcing cannot be used entirely for generating the road networks. However, all map parameters depend on crowdsourced data or are dynamic.
They used to have a constant “speed curve” – average travel speed on a road per hour of day. They now have day and time dependent speed curves that can reflect morning and evening rush hours. These speed curves no longer depend on speed limits. The speed frequencies result in bimodal distributions with one model reflecting typical speeds and the other reflecting speeds of < 4mph (traffic jams!) This is all reflected in a network, which is time-expanded (e.g., nodes are intersections AND times of day).
The shortest path is thus always changing, since the network changes during a trip. TomTom charges a monthly fee for getting real-time routes, which are mostly used by daily commuters. When there is traffic, TomTom is able to find a new route that is different than the route everyone else takes to get around the traffic jam. This, of course, makes less traffic for the drivers who wait it out in the traffic jam. Thus, drivers following the optimal real-time shortest path make shorter paths for their non-optimal peers (see TomTom’s manifesto above).
Coordinating road traffic on the roads (i.e., controlling all traffic rather than directing a single driver) by anticipating the behavior of many drivers is a challenging problem. The price of anarchy is the ratio of the cost of a worst equilibrium to the cost of an optimal solution. The optimal solution in congestion games on a network are optimal for the system, but they are not fair in the sense that some drivers have shorter paths than others. Here the drivers with the longer travel times have an inventive to switch to a shorter route that makes their travel time shorter but slows down the system. To coordinate fairness, they have added fairness constraints and used Stackelberg routing (with a traffic leader who routes a fraction of traffic first that anticipates the selfish behavior of the other drivers). TomTom has found that games with atomic and nonatomic players shows promise for combining coordinated and non-coordinated drivers.
Here is an interesting topic: U-turns are incredibly complex and could be a talk in themselves. U-turns could be forbidden (as they are in Malasia), P-shaped (as they are in Michigan?), and made via roundabout. Unfortunately, U-turns were not discussed much. Please leave your complex U-turn experiences in a comment.
Here is another interesting topic: one of the speakers gave an example of the single hour that traffic is the worst on the road outside the conference. It was Tuesdays from 5-6pm. I travel home from work during this hour in Richmond, Virginia (USA), and have noticed that the congestion at the main interstate exchange is worst on Tuesdays at this same time (measured in how long the line is for I-95 N coming from I-195). The speaker did not elaborate, but I am curious is Tuesdays from 5-6pm is a bad hour everywhere.
FYI, TomTom does academic work. They have a Navigation Research Toolkit for researchers and they sponsor PhD dissertations. They are also hiring (go to http://www.tomtom.jobs)
Do you use a GPS for your daily commute? How has it changed your routes?