A shortened version of this post was adapted for Symposium Magazine‘s article Understanding the Irrational Commuter, which appeared in the September 2013 issue.

When walking, riding, or driving to a destination, you need to figure out the route (sequence of road segments) you will take. When transportation analysts are solving this problem, they need to figure this out for you, and your two million closest friends, across your metropolitan area. Solving this problem was one of the early applications of mainframe computers in the 1950s, and is still a challenging problem, because the decision you or any traveler makes depends on the decision every other traveler makes.
In metropolitan transportation planning agencies across the world, computerized travel demand models are used daily to predict the effects of changes of networks (e.g. adding a lane), land uses (e.g. developing a surface parking lot), and policies (e.g. raising the price of gas $0.50) on levels of traffic and subsequent delays. One of the key components of these models is called alternately “route assignment” (where the model tells traffic which route to take) or “route choice” (if we imagine the model predicts which route users will choose to maximize their utility)

The principle underlying most applications of route choice is called Wardrop’s First Principle, or Principle of User Equilibrium, which says: the journey times on all routes actually used are equal and less than those which would be experienced by a single vehicle on any unused route.

John Glen Wardrop, a British transport analyst published this in 1952 implicitly combining two ideas.

The first is the principle of least effort, which is common for many scientific principles. It basically says that people, animals, or students will chose the path of least resistance to get from their origin to their objective. There is no shorter route available (since if there were, you would use it).

The second is what economists now call Nash Equilibrium. It is likely that Wardrop didn’t know about it at the time because Nash had published in 1950 and 1951 and didn’t get his doctorate until 1952. The now widely known Nash Equilibrium says that in a game between multiple players, equilibrium is achieved when no player benefits by changing his strategy while the others keep their’s unchanged. You are choosing the best decision for yourself subject to everybody else doing the same. It’s analogous to the Wardrop Equilibrium that we have in route choice. (John Nash later won the Economics Nobel Prize, his life is detailed in the Sylvia Nasar book and film A Beautiful Mind).

Wardrop’s First Principle has been the foundation of route choice models that have been used since that time but it hadn’t received much empirical testing. As a researcher, I like to look under-the-hood so to speak, so with students and colleagues at the University of Minnesota we ask the question:

Do people actually use the shortest path?

The data necessary to test this question haven’t been available until very recently. We need to know A) what the real shortest path is on a network, which requires travel time data on all road segments, and B) what paths people actually use. While people might tell you in a survey they’re going from A to B, in general we didn’t know what particular routes that they were using (and many people couldn’t accurately answer than anyway). With the advent of GPS systems and more pervasive traffic monitoring we are now able to get better data about what routes travelers are actually taking.

Colleagues and I at the University of Minnesota conducted a study examining the change in peoples travel behavior with the construction of the replacement I-35W Mississippi River Bridge. Recall in August of 2007 the bridge famously collapsed, and in September of 2008 a replacement bridge opened. We were able to get some funding to do a study to examine the impacts of the reopening, looking at the detailed travel behavior of individuals before and after reopening.

A few weeks prior to reopening, we instrumented about 200 vehicles with GPS units and told their drivers to drive as they normally would. We didn’t give them any other instructions except they had to come to the University or another particular location to get the GPS unit installed, and 8-13 weeks later had to return so we could remove the GPS unit from their vehicles. The people that were targeted in this study lived and worked near the University of Minnesota or in downtown Minneapolis because those were people who were likely to be affected by the change in the network associated with the I-35W Bridge. They lived throughout the region.

People drove for eight weeks, and we collected the data. We (to be clear, my very tireless graduate student, now George Mason University Assistant Professor, Shanjiang Zhu) spent a lot of time cleaning the Raw GPS data, which has all sorts of potential errors. We had to make sure that GPS points fell on the network, that people were driving on the right side of the road, and so on. We matched this data to routes, so for each individual trip we could track where it started, where it ended, and the specific road segments that were taken. We also used this very large data set to estimate the travel time on all of the relevant links in the network.

In addition to knowing what route that somebody actually took, we had measurements of the expected travel time on most of the alternative routes a traveler might consider, since other travelers used those roads.

We have long had data on the freeway system from loop detectors. Magnetic induction loops are cut into each lane on the Twin Cities freeway network every half-mile or so. These report to a traffic management center data from every tenth of second indicating whether they are under a large metallic object (disrupting the magnetic field).

Unfortunately, we never had very good real-time data on signalized surface streets. While data is sometimes collected for traffic light timing, it is not stored.

The new GPS data gives the speeds on the arterials at any given time. We compared the routes that travelers actually took with what we skimmed to be the shortest travel time on the network based on the average travel speed was on each of those links, and we compared them.

Recall that we asked, “Do people take the shortest path?” For work trips: 15% of the people take what we measured as the shortest path. A number of people take a path that while not, strictly speaking, the shortest, probably is very close to the shortest, which might deviate by one or two links or might deviate by a very short period of time, less than a minute difference than the shortest path. There are a significant number of people who take routes that are 2-5 minutes or 5-10 minutes longer than the shortest travel time path.

For non-commute trips, which tend to be a little bit shorter, we get a higher percentage of people taking the shortest path. But you would think for the people who make the same trip every day that they would know what the network looks like, and it turns out that if they do know what the network looks like they’re not choosing to not take the shortest time, or they don’t actually know.

To answer the question “do people take the shortest path”? We came to conclude, no.

This is the fundamental principle underlying route choice. It’s been used and is continued to be used in models all over, but it is not supported by the data.

In tomorrow’s post we will consider some reasons why people might not take the shortest path.