Tag Archives: traffic

Braess’ Paradox can be applied to physical systems and professional basketball

Braess’ Paradox is a famous result in game theory which states that in a network where users selfishly seek to lower their travel times, the Nash equilibrium flows may increase after a new arc/road is added.

Braess’ Paradox can be demonstrated physically with springs, as seen in this nifty YouTube video:

When searching for information about Braess’ Paradox, I found a delightful post on Anna Nagurney’s blog.

In the basketball world, according to Bill Simmons of ESPN, there is the Ewing Theory. According to Simmons: The theory was created in the mid-’90s by Dave Cirilli, a friend of his who was convinced that Patrick Ewing’s teams (both at Georgetown and with New York) inexplicably played better when Ewing was either injured or missing extended stretches because of foul trouble. Simmons has a primer, Ewings Theory 101, which lists examples in basketball history where the removal of a top player (paradoxically) results in a better outcome for the basketball team.

Brian Skinner, a physicist at the University of Minnesota, wrote an article, “The Price of Anarchy in Basketball” in which he developed an analogy, through a model, between certain basketball plays and the Braess paradox, in order to further explore the Ewing Theory.

I’ve been enjoying the NBA basketball playoffs since my favorite team (the Chicago Bulls) won their first round series and beat the Miami Heat in the first game in the second round. The Bulls are without Derrick Rose, the best player on the Bulls. I hope there is not a “Derrick Rose Effect” that would cause the Bulls to be worse when he returns.

Are you aware of other interesting applications of Braess’ paradox?


why women are (sort of) responsible for traffic congestion

This summer I read Traffic by Tom Vanderbilt and blogged about the OR and networks topics covered in the book. The follow-up post that I promised took nearly three months longer than I thought it would.

For those of you who are familiar with driving and traffic data, you will know that men, on average, drive more than women across all ages, and it’s not even close. Men age 55+ drive more than more than twice as many miles on average as women of the same age. On face value, it seems like men are disproportionately responsible for all the traffic congestion on the road. Tom Vanderbilt challenges this idea in Traffic, looking at why and when women drive rather than looking at how much they drive.

Both men and women drive a lot more than they did in the 1950s, leading to traffic and congestion. There are many reasons for this. Two that are often named are suburban sprawl (people living farther from where they work) and women joining the workforce. This naturally led to an increase in driving by both men and women. Let’s look a bit deeper.

Other things have changed–or not–since the 1950s. One thing that has not changed is that the women who have entered the workforce still do the lion’s share of errands, particularly those involving kids (think: “soccer moms”). In the 1950s, 40% of car trips were work trips. As of ~2010, a mere 16% of car trips were work trips. The difference is not that people aren’t working or taking public transportation to work (they are actually driving to work more!). The difference is that we’ve added many other driving trips to our schedules. And women do more of these extra errands and trips than men do.

Women do a lot of “trip chaining,” stopping at the grocery store on the way to or from work, taking Johnny to soccer practice, etc. The reason why women make such an impact on congestion is because (1) they are taking these trips during peak traffic times due to inflexible schedules, (2) they they use smaller roads less equipped for large traffic loads (these trips do not usually use the interstates), and (3) the distance between trips is significant (suburban sprawl!). Side note: We women are fairly efficient here in that we can minimize travel times by “chaining” – adding a TSP-like “tour” of errands rather than making individual trips that would take longer.

blogged about the issue of women having inflexible driving routes earlier, where I argue that dropping kids off at day care often makes taking public transportation impossible. Vanderbilt observes this, too. He also does not blame women for the extra traffic, as our travel patterns are what you would expect when considering the demands of both our families and careers. But there are implications.

In all seriousness, this post discussed traffic from the perspective of the “average” men and women. None of us are “average,” of course. The OR tie-in here is that the who, why, where, and when are important for understanding why congestion happens at certain times. The network structure is also important, as traffic network is reflected in trip chaining, and it sheds light on what parts of the network will experience the worst congestion. Vanderbilt’s writing on this topic suggests that encouraging people to contribute less to congestion is challenging, since there are many constraints on women’s driving patterns, and as a result, they might not be able to respond to incentives for reducing the amount they drive.

On a related note: for the first time in the US, the majority of licensed drivers are women.

Related posts:


what is the optimal way to find a parking spot?

A paper in Transportation Science exams how to find a parking space using operations research methodologies. Here, Richard Cassady and John Kobza use applied probability models to identify how to find a “good” parking space according to one of three performance measures:

  1. (Expected) Total walking distance
  2. (Expected) Time to space (ignoring walking distances)
  3. Time to door = expected walking distance + time to find a space

They compare two parking strategies:

  1. Pick a row, closest space (PRCS): The simple strategy of choosing a row close to the parking lot entrance, and picking the closest available space.
  2. Cycling (CYC): a more complicated and aggressive strategy that involves first entering the closest row and parking in the closest of the 20 closest spaces if one is available. If not, the driver proceeds to the next row and chooses the closest of the 40 closest spaces. If one is not available, the driver moves to surrounding rows and selected the closest available space.

parking lot

To visualize how the analysis in this paper is performed, see the figure on the right that shows one of the parking lot geometries considered in the analysis. The analysis is applied to large, Wal-Mart-like parking lots with multiple entrances. I discuss other parking strategies at the end.

The analysis considers six cases (3 performance measures x 2 strategies), and for each, Cassady and Kobza
use a probabilistic approach “to construct general expressions for the performance measure. The
approach treats the decisions made by the driver and the availability of parking spaces as random experiments. By
conditioning on the outcomes of these experiments, the performance of the strategy can be evaluated using the Law of Total Probability.”

Not surprisingly, the PRCS strategy has a lower time to space, since drivers using PRCS find parking spaces fast. Likewise, the CYC has a lower total walking time, since extra driving time finds spaces that are closer to the front door.

Surprisingly, the PRCS strategy performs slightly better when considering the time to door. That is, the time saved finding a parking spot more than makes up for the extra walking time. In a conversation with John Kobza a couple of years ago, he recommended not to cycle and rather to drive to the front of a row. If a close spot is available, take it. Otherwise, park in the closest available spot in the  next row.

Cassady and Kobza acknowledge that the performance measures considered can be misleading in situations when a parking spot is not guaranteed. They also acknowledge that other issues can be incorporated into the analysis (like taking into account the time pushing a shopping cart over to a cart corral).

Cassady and Kobza  implicitly assume that time spent parking and walking are equally weighted in the Time to Door strategy. I use a variant of this strategy when I parallel park on the street when I come to campus that uses unequal weights. Near campus, decent spots are  not guaranteed, so I sometimes have to walk ~10 minutes to my office door. I try not to cycle in the mornings, but I sometimes cycle to shave a little bit off of my walking time if it is raining or I am wearing heels (the brick sidewalks in Richmond are quite uneven).

How do you find a parking spot?

Citation:

A Probabilistic Approach to Evaluate Strategies for Selecting a Parking Space
C. RICHARD CASSADY and JOHN E. KOBZA
Transportation Science , Vol. 32, No. 1 (February 1998), pp. 30-42


a book about traffic

I recently had the pleasure of reading the book Traffic by Tom Vanderbilt (@tomvanderbilt) as my summer beach read based on the recommendation of a reader or tweep. It is an excellent book. The book is about all aspects of traffic, including operational, psychological, and human factors. Research by several OR professors were included in this book, including research by Anna Nagurney (UMass), Richard Larson (MIT), and John Kobza (Texas Tech). I rarely read books about operations research, so this book was a real treat.

I won’t summarize the entire book, but I will discuss a couple of small parts.

The book starts with a argument for who one should be a late merger at merge points on the expressway, a habit that I picked up after testing a few approaches. The argument here is a mix of traffic theory and psychology.  The traffic arguments is that the total throughput at a merge points depends on how people merge. In the US, we tend to merge way before we have to and assume that anyone who violates this rule is a jerk. Germans like to coordinate their merges to increase efficiency. Efficiency is the German Way. It turns out that it is most efficient to maintain two lanes of traffic up until the merge point, where drivers in the two lanes take turns. This is exactly what happens in the merging lanes in I-95 south of DC when driving toward Richmond, where it works pretty well. The total throughput across all lines of traffic is best if drivers obey this rule, and experiments validate this approach.  One of the US states changed their merge signs during the summer construction season to urge drivers to merge late and take turns. They noticed a large improvement with throughput. Other experiments had limited success, since drivers ignored the new instructions, merged too early, and were aggressive with drivers who obeyed the new rule.  So why do drivers like to merge early? Merging, according to psychologists, is the single most stressful aspect of routine driving.  When we attempt to merge, we can’t help but wonder, “What if I cannot get into the lane?”

I enjoyed the part of the book about networks and congestion. One of the main themes was that networks make driving non-intuitive. We have all heard that adding capacity does not reduce congestion. Tom does a wonderful job of making this intuitive. One reason is that more congestion encourages people to take unneeded trips, live farther from work, etc. More capacity = more miles driven = more congestion. Another reason is due to Braess’ paradox, a game theory model for congestion. Anna Nagurney’s work was cited here, and she has blogged about this before, so I will only briefly elaborate. Here, adding a new superhighway that promises shorter travel times to all if it is not congested, then everyone will want to use it (the Nash equilibrium). The congested road will make everyone’s driving time worse.

Another network example dealt with the monorails at Disney that operate on a simple network. For safety, the trains have to slow down if they get close to other trains. If a train catches up to another train in the network, it has to wait for the first train to make its stops. Disney found that service would speed up if they reduced the number of trains in their system by 1.

Traffic is a fascinating book about many OR-related topics. I highly recommend it if you are looking for a book to read. The blog about the book is here. I may write another post or two about this book. Stay tuned.

 

HT to @iamreddave for recommending the book to me.


how do GPS devices find the best route?

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?


car fatality rates: an international perspective

Yesterday, Peter K. requested that I put the US driving safety statistics in an international perspective. Here are four figures on this topic.

The driving fatality rates in the EU by region. These rates include fatalities caused by driving, and therefore, pedestrians killed by cars are included. “The total road death toll was cut by 48 % between 1991 and 2008 and has fallen by 31 % since the year 2000.” Eastern Europe looks kinda dangerous here, and Italy doesn’t live up to its dangerous driving reputation.

Here are the traffic fatalities per 100K inhabitants. Only about half of the people who died were in cars, although I suspect that less developed countries contributed to more pedestrian deaths.

Here are the traffic fatalities per 100M miles driven. The last figure didn’t normalize the fatalities according to how much people drive in different countries. This figure, on the other hand, better reflects how good the drivers are in different countries. However, countries with high speed limits (think of the Autobahn) may fare a little worse, since accidents at high speeds tend more be more deadly. Again, half of the victims were not in cars. Therefore, you might not want to be a pedestrian in UAE.

This is my favorite figure. Here I tested whether people who drove more got more practice, and therefore, led to safer driving conditions in their countries, a possible upside to driving a lot [link to data from the EU countries]. The x-axis shows the number of cars per 1000 inhabitants, a proxy for how much people drove (This isn’t perfect, but I couldn’t find the actual number of miles driven). The y-axis has per capita car fatality rates (per 100K). There is certainly a negative relationship here, with more cars associated with fewer fatalities. However, this only explains ~19% of the variation.


five charts about Americans and their cars

My post yesterday on why teenagers don’t have drivers licenses continues to generate discussion (thank you readers!). I’m going to continue the discussion here.

Despite the poor economy and expensive gas, Americans still love their cars. This love goes way, way back to the invention of cars (see my other blog post on super-highways). Here are some other interesting figures about Americans and their cars.

There are more cars than licenses drivers in the US. This is not a recent trend: there have been more cars than drivers since 1971. This gap is getting smaller, but it’s still wide, historically speaking. My husband pointed out that commercial and government vehicles may be included here. Another report shows that cars outnumbered drivers c. 2000.

This figure shows the miles of road (red). More recently, the total number of lane-miles (green) are shown, which takes multi-lane roads into account. This is a bit misleading, since adding a second lane does not double the road capacity. Compare the total number of road-miles to the total number of miles driven (blue). This suggests that there may be a road shortage. However, building more roads only encourages people to drive even more. Still, Americans love to drive more than ever.

The average annual number of miles driven per driver has steadily increased over time. Only recently people have been cutting back on their mileage, probably due to a poor economy and expensive gas. However, we have only cut back to our 1998 driving level.

Look at the purple line here. This is the average mpg relative to 1987 cars (the 1.0 level), and low is good. This shows that the average mpg has been more or less constant since 1980. This is largely because of the growing popularity of SUVs and minivans. We’ll have to see if the trend of tiny cars and Cash For Clunkers improves these values in the future.

Car, light truck (read: SUVs) and motorcycle fatalities per mile driven. This should convince you not to get around by motorcycle! You cannot see the car fatalities rates well. The fatality rate on rural rates is more than twice as large as the fatality rate on urban roads. This is probably due to urban congestion (congestion = slow driving = safer accidents) and the danger surrounding 2-lane rural highways (2-lane highways = head on collisions at high speeds). Both rural and urban fatality rates have come way down since 1980, probably due to air bags and other safety features (and despite of road rage). The urban fatality rate has dropped faster than the rural fatality rate. Again I would suspect urban congestion here. This is the upside to traffic. Takeaway: Driving is safer than ever.