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!]