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.

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

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?

A news story about the traffic in my hometown of Chicago suggests that perhaps the traffic isn’t horrible. When I mean horrible, I mean like last year’s ten day traffic jam in China. Chicago’s traffic is pretty bad. The US Federal Highway Administration has reported that Chicago has the worst traffic in the US. Whenever I visit my family back in Chicago, that becomes painfully obvious. The sheer number of traffic reporters in Chicagoland is a sign that the traffic is bad. However, IBM reports that although the traffic in Chicago and elsewhere in the US is bad, it could be worse.

Of the 20 cities surveyed by IBM, Chicago is the third least bad in terms of the “commuter pain index.” That’s not something to be too proud of, since only the cities with the worst traffic in the world were surveyed (see the infographic here).  The traffic in the other US cities surveyed (New York and Los Angeles) is not as painful relative to the traffic in Beijing and Mexico City. This is a reminder of how operations research models of traffic systems and networks will be needed for many years to come, particularly in countries that are rapidly becoming more industrialized.

When I was growing up in the suburbs of Chicago in the 1980s, the ‘burbs were rapidly expanding. The transportation network didn’t keep pace. New subdivisions were added and only later were the narrow two lanes roads connecting the subdivisions widened. It didn’t solve all of the traffic congestion, but it helped. I used to watch traffic collect at various intersections and try to understand why it occurred. Sometimes the demand just exceeded capacity (as it did during rush hour) and sometimes lights were too short and turn lanes were needed. I always had an eye for efficiency, and the constant traffic gave me plenty of opportunities to think about efficiency.  As a result, I have a weird kind of fondness for Chicagoland’s traffic. Traffic was my gateway to operations research. It was an indirect path, but my fascination with traffic motivated me to take optimization courses when I was in college. I don’t research traffic or networks, but I eat up news about traffic, why a piece of paper blowing across the highway can make it so bad, and what can be done about it.

Did you have any childhood interests that directly or indirectly led you to operations research?
Related blog posts:

• managing oversaturated traffic intersections
• Snow removal using a plow, a shovel, and operations research
• do not text and drive