Tag Archives: Transportation

Happy 50th anniversary Transportation Science!

The early days of transportation science research

The early days of transportation science research.

Happy 50th anniversary Transportation Science. To celebrate, the editorial board put together a special issue of 12 classic papers published in Transportation Science over the past 50 years. I’ve pasted the list below – I believe all the articles can be downloaded without a subscription for a limited time. Head here to see the full list.

This is an excellent collection of papers – I’m even covering “A Maximum Expected Covering Location Model: Formulation, Properties and Heuristic Solution” by Mark Daskin in my course on public sector OR this semester.


An Algorithm for the Traffic Assignment Problem
S Nguyen
Transportation Science 8 (3), 203-216, 1974

On Stochastic Models of Traffic Assignment
CF Daganzo, Y Sheffi
Transportation Science 11 (3), 253-274, 1977

Traffic Equilibrium and Variational Inequalities
S Dafermos
Transportation Science 14 (1), 42-54, 1980

A Maximum Expected Covering Location Model: Formulation, Properties and Heuristic Solution
MS Daskin
Transportation Science 17 (1), 48-70, 1983

Network Design and Transportation Planning: Models and Algorithms
TL Magnanti, RT Wong
Transportation Science 18 (1), 1-55, 1984

The Distance Traveled to Visit N Points with a Maximum of C Stops per Vehicle: An Analytic Model and an Application
CF Daganzo
Transportation Science 18 (4), 331-350, 1984

A Column Generation Approach to the Urban Transit Crew Scheduling Problem
M Desrochers, F Soumis
Transportation Science 23 (1), 1-13, 1989

The General Pickup and Delivery Problem
MWP Savelsbergh, M Sol
Transportation Science 29 (1), 17-29, 1995

A Tabu Search Heuristic for the Vehicle Routing Problem with Soft Time Windows
É Taillard, P Badeau, M Gendreau, F Guertin, JY Potvin
Transportation Science 31 (2), 170-186, 1997

Flight String Models for Aircraft Fleeting and Routing
C Barnhart, NL Boland, LW Clarke, EL Johnson, GL Nemhauser, RG Shenoi
Transportation Science 32 (3), 208-220, 1998

A Joint Location-Inventory Model
ZJM Shen, C Coullard, MS Daskin
Transportation Science 37 (1), 40-55, 2003

Self-Organized Pedestrian Crowd Dynamics: Experiments, Simulations, and Design Solutions
D Helbing, L Buzna, A Johansson, T Werner
Transportation Science 39 (1), 1-24, 2005


Recommended: Anna Nagurney’s excellent post on Transportation Science’s 50th anniversary.

Related post:

waiting is torture, but it’s not so bad if there are mirrors or trees

Operations research is the discipline of making better decisions. We have to solve the right problem to better inform decisions, and sometimes solving the right problem doesn’t involve math.

One of my favorite stories about solving the right problem comes from MIT Professor Dick  Larson (Dr. Queue!). He summarized his story in an article in Slate about queuing theory [Link]:

Midcentury New York featured a rush-hour crisis—not out on the roads, but inside office tower lobbies. There weren’t enough elevators to handle the peak crowds. Complaints were mounting. “One solution would have been to dynamite the buildings and build more elevator shafts,” says Larson. “But someone figured out the real problem isn’t just the duration of a delay. It’s how you experience that duration.” Some buildings installed floor-to-ceiling mirrors near the elevators and, entertained by their own reflections and by the flirting that sometimes ensued, people stopped complaining quite as much about the wait time.

A NY Times article about queuing also contains this story [Link].

A recent article in The Atlantic about how public transit riders perceive waiting times [Link] reminded me of the elevator story. The perception of waiting time is one of many issues involved in incentivizing people to use public transit. If we can understand what makes for acceptable and unacceptable perceived wait times, then maybe we can mitigate what feels like long, torturous waiting times. It turns out that we just need mature trees by bus stops (much like the mirrors by the elevators!):

Riders who waited at stops where there was lots of pollution and traffic significantly overestimated their wait times. The effect was especially pronounced for those who were waiting for longer than five minutes, with those who waited for their rides for 10 minutes in areas that they felt were noisier and dirtier reporting that they had waited for over 12 minutes. Researchers also found a simple mitigating factor: trees. According to the data, the presence of mature trees helped make wait times feel less painful, for both short and long waits, and even in areas where other negative factors were present.

The article is about a paper by Marina Lagune-Reutler, Andrew Guthrie, Yingling Fan, and David Levinson (@trnsprttnst) at the University of Minnesota.

What are your favorite and least favorite transit stops?

Related posts:

Type II errors are the ones that get you fired: the Atlanta edition

A couple weeks ago, a comment on twitter reminded me about Type I and Type II errors, which in turn reminded me of my first introduction to Type II errors in a probability and statistics course as an undergraduate student.

A type I error is the incorrect rejection of a true null hypothesis.

A type II error is the failure to reject a false null hypothesis.

Type I and Type II errors are a little confusing when you are first introduced to them. To make things easier, my professor gave us some practical information about Type II errors to help us put them in perspective:

And that brings us to the mess that was Atlanta this past week. If you recall, about 3″ of snowfall iced over, leading to mayhem. Schools and government did not shut down before the storm. Instead, they all closed at the same time, leading to an incredible amount of congestion that overwhelmed the impaired transportation network. Cars were abandoned on the highway and students camped out at school and in grocery stores for the night (presumably, everyone was stopping for bread and milk on the way home). I recommend these two articles from the Atlantic Cities to see just how bad it was in Atlanta [Link and Link]. Here is a time-lapse of the highways in Atlanta. Traffic went from fine to a disaster in an hour:

In this case, the weather itself was not a disaster. Poor management of the situation led to a disaster. (That almost sounds like it should be a bumper sticker: Weather doesn’t make disasters, people make disasters! At other times, the weather really is a disaster) David Levinson, a civil engineering professor at the University of Minnesota (a former Atlanta inhabitant, find him at @trnsprttnst) wrote an excellent piece on CNN about his perspective [Link]. I don’t have a whole lot to add except that managing the effects of severe weather has been and will continue to be a big issue in operations research (and civil engineering too).

  • Should you instead try to mitigate the ice by investing in salt and trucks to prepare the roads? This is not very practical in the South where it rarely snows.
  • Do you always play it safe and close schools? I lived that way in Virginia, and while it is safer, the Type I errors aren’t ideal. One year, school was canceled 5 days for a sum total of 1″ of snow across all of the days of canceled school.
  • If you decide not to close schools and later change your mind, should you stagger the closures? Yes. This is critical in congested cities like Atlanta and DC.

Related posts:

Many of my readers are from or have lived in Atlanta. What is your take?



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?

what is the (conditional) probability of exploding when filling your car up with gas?

What is the probability that you will cause an explosion when filling up gas?

I like to wait inside my car when my car is filling up with gas. I do this to reset my trip odometer, stay warm, etc. One — and only one — of the local gas stations has a sign (pictured below) warning me to not get in and out of my car when fueling up. The implicit claim here is that getting in and out of my car raises my conditional probability of exploding. I as curious to see if (a) that claim was true and (b) how significant that rare risk would be if it were true, and (c) why only one gas station wants to protect me from this risk.

Snopes has some interesting data about this issue based on a PEI report [Link] The data is apparently a mess, but it looks like there were 81 fires over ~7 years, and information about 64 of these fires was available for further analysis. Most of the fires occurred in the most recent year. I assumed that maybe older fires were less likely to be recorded and therefore assumed that this represented 2 years worth of fires (~24B re-fuelings). The report implicates women in entering the car but the report’s authors don’t actually identify gender in their statistics (read the Snope article). I’ll take this into account.

It’s worth noting that men get struck by lightning way more than women. Maybe women balance this out by causing more fuel fires?

Claim (a) appears to be true. Let’s say there are 81 gas explosions in 2 years (24B refuelings). That is a base rate of 3.4×10^-9, a rare risk. This doesn’t give any insight into whether going back into one’s car is a bad idea, so let’s look at that issue further. To do so, I will assume that the 17 fires are randomly either caused by reentering or not reentering one’s car. Then, we know:

P(fire and reenter) = 1.5×10^-9

P(fire and no reenter) = 1.0×10^-9

Of course, we want to find P(fire | reenter) and P(fire | enter). To do so, let’s assume that women do 36% of all fuelings (same as the proportion of miles driven by women) and that women reenter their cars 50% of the time and men reenter 10% of the time.

P(fire | reenter) = 6.25×10^-9

P(fire | no reenter) = 1.4×10^-9

Fires in cars where someone reenters their car occur 4.5 as often as when they don’t. If we look at an extreme example where all women reenter but no men do

P(fire | reenter) = 4.22×10^-9

P(fire | no reenter) = 1.65×10^-9

Here, people that reenter (all women) cause fires 2.5 more than those that do not reenter (all men).

But those that reenter may not always cause fires at a higher rate than those that do not reenter – it all depends on how often people reenter their car. Let X = the probability that people reenter their cars while fueling:

P(fire and reenter) / X >= P(fire and no reenter) / (1-X)

This is true when X < 0.591. This appears to be true, but it's a fairly realistic number even though I bet it's a bit high. Given the rarity of fires, people that reenter probably do not cause fires at statistically significantly higher rates than those that do not reenter.

Any risk that happens about once every billion fuelings is very rare. I will not fuel my car that often over the course of my lifetime, so I can expect to escape without causing a fire.

Let’s compare the risk associated with causing an explosion due to reentering one’s car to the risk associated with dying in a car accident. To do so, let’s assume that one drives 300 miles between refuelings for an apples to apples comparison. Then, the risk of dying between refuelings is 3.3×10-6 (1.1 deaths per 100M miles driven). When compared to the risk of exploding given that you reenter, you are 528 more likely to die driving than explode when reentering your car while fueling.  Therefore, I’ll conclude that if a risk from reentering my car exists but that it’s fairly insignificant (Claim b), which explains why most gas stations are not concerned about warning me (Claim c).

Have you ever caused a fire while filling your car up with gas? Do you even know of anyone second- or third-hand who exploded while fueling?


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:

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.

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.

Why don’t teenagers drive any more?

I got my driver’s license on my 16th birthday. I liked to be able to drive places when I needed to, but I was happy to let my friends do the driving if they wanted to. I didn’t do a whole lot of driving until I bought my first car at age 21 (and I’m still driving it – here is a link to a blog post about my car).

An article in the Atlantic summarized the percentage of people in the US who have drivers licenses by age in 1983, 2008, and 2010. The real surprise was the change that occurred between 1983 and 2008. Here, we see that many fewer young people (aged 34 and younger) had drivers licenses in 1983 than in 1983, and many people aged 55+ had licenses in 2008 than in 1983.

I posted this to twitter and google+ and received quite a bit of feedback.  I was surprised that fewer teenagers would drive. Here are some reasons why more or less teenagers would be willing to drive. I apologize in advance for the stereotypes of teenagers and their parents: these generalizations are not meant to hold on the individual level (of course!)

Reasons why fewer teenagers would have licenses today than in 1983

  1. The Internet has eroded reasons why teenagers need to drive, since they can shop online and communicate with their friends online.
  2. Everyone owns a car, so there are other people to give teenagers rides.
  3. Parents like to “helicopter” and taxi their kids around.
  4. Laws in some states restrict teenagers from giving their friends rides.
  5. People have smaller families today, so teenagers do not need to taxi siblings around as much.
  6. Students are not as independent as they once were (not sure if that is true).
  7. Teenagers are “buddies” with their parents and do not feel the need to escape from home to study, for example.
  8. The teenage right of passage to be caught doing something embarrassing on FaceBook has displaced the right of passage of getting a drivers license.

Reasons why more teenagers would have licenses today than in 1983

  1. More live in surburban neighborhoods where “destinations” are not within walking distance. The suburban model of building shopping centers with giant parking lots in the middle of nowhere are commonplace.
  2. Students are more active in student activities and need to get to and fro.
  3. People own more cars today, so teenagers have more of an opportunity to drive.
  4. Public transportation hasn’t gotten better since 1983.

The reasons for more teen driving seem to be quite compelling to me, but clearly, they do not overwhelm the reasons why teenagers do not drive. What other reasons may teenagers have for not wanting to drive?