## Saturday, December 4, 2010

### OR and ... Parking??

'Tis the season to shop our brains out.  Two trips to a local mall today (neither, oddly enough, for the purpose of shopping) has me reflecting on the science (art?) of finding and selecting parking spots.  Choosing a parking spot involves elements of stochastic search (anyone have a link for this?), optimization of a distance function, and (when the mall is busy) stochastic stopping rules.

The application of stopping rules is fairly obvious, although the rule to use may not be.  You're running a search pattern through the packed parking lot of a mall, looking for an empty spot, when lo and behold you find one.  Now comes the stopping rule:  do you grab it, or do you continue the search, hoping for one closer to your immediate destination (the first store you plan to hit)?  If you pass it up and fail to find something closer, it likely will not be there the next time you go by.  Add an objective function that balances your patience (or lack thereof), your tolerance for walking, the cost of fuel, any time limits on your shopping spree and the possibility of ending up in a contest for the last spot with a fellow shopper possessing less holiday spirit (and possibly better armed than you), and you have the stopping problem.

The other obvious aspect is optimization of a distance metric, and this part tends to amuse me a bit.  Some people are very motivated to get the "perfect" spot, the one closest to their target.  My cousin exhibits that behavior (in her defense, because walking is painful), as did a lady I previously dated (for whom it was apparently a sport).  Parking lots generally are laid out in a rectilinear manner (parallel rows of spaces), and most shoppers seem to adhere rather strictly to the L1 or "taxicab" norm.  That's the appropriate norm for measuring driving distance between the parking spot and the store, but the appropriate norm for measuring walking distance is something between the L1 and L2 or Euclidean norm.  Euclidean norm is more relevant if either (a) the lot is largely empty or (b) you are willing to walk over (or jump over) parked cars (and can do so without expending too much additional energy).  Assuming some willingness to walk between parked cars, the shortest path from most spots to the store will be a zig-zag (cutting diagonally across some empty spots and lanes) that may, depending on circumstances, be closer to a geodesic in the taxicab geometry (favoring L1) or closer to a straight line (favoring L2).  The upshot of this is that while some drivers spend considerable time looking for the L1-optimal spot (and often waiting for the current occupant to surrender it), I can frequently find a spot further away in L1 but closer in L2 and get to the store faster and with less (or at least not much more) walking.

This leaves me with two concluding thoughts.  The first is that drivers may be handicapped by a failure to absorb basic geometry (specifically, that the set of spots at a certain Euclidean distance from the store will be a circular arc, not those in a certain row or column of the lot).  Since it was recently reported that bees can solve traveling salesman problems (which are much harder), I am forced to conclude that bees have a better educational system than we do, at least when it comes to math.  The second is that, given the obesity epidemic in the U.S., perhaps we should spend more time teaching algorithms for the longest path problem and less time on algorithms for the shortest path problem.

[Confession:  This post was motivated by the INFORMS December Blog Challenge -- because I thought there should be at least one post that did not involve pictures of food!]

1. Great post!

There is a Transportation Science article about parking algorithms:

TRANSPORTATION SCIENCE
Vol. 32, No. 1, February 1998, pp. 30-42
A Probabilistic Approach to Evaluate Strategies for Selecting a Parking Space
C. Richard Cassady, John E. Kobza

2. @Laura: Thanks for the comment, and in particular thanks for the citation. I'm thrilled to OR being applied to one of the critical problems we face today. ;-)

3. I would like to pint you to the book (in Italian)

L'algoritmo del parcheggio
by Furio Honsell

Some notes on this subject are also available at the Prof. paolo Serafini website
http://users.dimi.uniud.it/~paolo.serafini/Markov.pdf

4. I would like to point to the following book (in Italian)
L'algoritmo del parcheggio
by Furio Honsell
L'algoritmo del parcheggio
di Honsell Furio

Some notes are also available at Prof. Paolo Serafini webpage
http://users.dimi.uniud.it/~paolo.serafini/DISPENSE.html

5. @Renato: Thanks for the references. Sadly, my ability to read Italian is barely enough to get me fed in an Italian restaurant, but perhaps some multilingual readers of this page will be interested in following up on your suggestions.

6. I think deserve to win the best blog contest this season! It was the perfect combination of humor and OR. But, of course, you did leave off the other "best" strategy that I have employed in large campus parking lots for decades. Just pick a close up spot, put the car in "Park",turn on the flashers, pull out a paper/journal to read, and wait till you see someone in your row pulling out.

7. @Barry: Thanks! I've used your strategy on occasion at work (substituting MP3 player for reading material at times), but in a shopping mall this tends to draw other people who will adopt an orbital approach, figuring that when someone pulls out they'll have momentum on their side (if they time the orbit correctly) and hit the spot before you do.

Due to intermittent spamming, comments are being moderated. If this is your first time commenting on the blog, please read the Ground Rules for Comments. In particular, if you want to ask an operations research-related question not relevant to this post, consider asking it on Operations Research Stack Exchange.