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?

20130411-092841.jpg


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.