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?
Punk Rock Operations Research 
August 27th, 2012 at 12:21 pm
I agree that their manifesto is a bold one, and I am sorry that my opinion is that their “then” conjecture simply is not true.
Traffic flow is an interesting area, and while we can make improvements for users by improving infrastructure and information, the nature of demand is such that congestion is unlikely to ever disappear. So, even if travel time savings of 5% were possible for all users (the “then” conjecture), it seems likely that demand would adjust so that (on average) people were enabled to live such that their trips were about 5% more distant.
Research on the network game of traffic control is interesting, but pragmatic application is extremely challenging. I wonder what level of market penetration and user compliance to routing directions will be required to make a significant impact?
August 28th, 2012 at 2:13 am
That was very interesting, Laura. We have just spent the last two weeks driving around Melbourne Australia using our TomTom. I noticed that when we were in slow traffic the time to destination seemed only to increase additively, while I would have thought a multiplicative model, using the current (very slow) speed might have been better. But then, how would it know how long the slow speed would last?
They are wonderful machines though, and meant that I didn’t get carsick while navigating, and our domestic disputes were kept to a minimum. My son, who has autism, doesn’t like it if we don’t follow the instructions. However he is also blind, so we just turn off the sound when we are going to be disobedient.
August 28th, 2012 at 4:30 am
Thanks for the article! t is great that people can have this information to navigate congested public infrastructure. I bet this model could apply to any circumstance where there is a queue!
August 29th, 2012 at 11:14 am
Did he say what type of crowdsourcing data they collect and how they collect it? (Are they receiving data from TomTom devices in customers’ cars?)
August 29th, 2012 at 11:19 am
“Michigan U”-turns are a type of intersection that doesn’t have direct left turns; to turn left, one goes beyond the intersection to a U-turn and then returns to make a right turn at the intersection. Or, one turns right initially and then goes down to the U-turn. Either way, it is equivalent to a left turn.
We just had an intersection here turned into one with the added complication that going straight is no longer possible for the (smaller) road: one first turns right from the smaller road onto the larger one, then does the U-turn, then turns right to continue on the smaller road.
August 30th, 2012 at 7:50 am
@Jeffrey, Yes, the crowdsourcing data comes from the GPS devices in the customers’ cars.
September 4th, 2012 at 9:26 am
My favorite GPS-related U-turn story: Several years ago a car-rental GPS told me, “Make a U-turn. Then, make another U-turn.”
September 9th, 2012 at 1:56 pm
[…] how do GPS devices find the best route? (punkrockor.wordpress.com) […]