Finding an optimal parking spot for shopping

Here is the original discussion at 'Punk Rock OR'.  The blog below studies a parking objective in the shopping context, and where the entrance to the shopping complex and the exit are at different locations. The cost to be minimized consists of at least two components:
(objective-a) the 'work' done searching for a good parking spot, as well as
(objective-b) the total physical work done after parking. This includes the work done while walking to the entrance, as well as the work done after shopping and exiting the building. Let's focus on objective-b here, given that objective-a has been analyzed before, using the following notation.

Parking coordinates (O, D), where
O = walking distance from the parking spot to the entrance, and
D = walking distance from the exit to the parking spot.
M = mass of the person,
S = expected mass of purchased items, and
(μ, g) = constants denoting the coefficient of friction during walking, and the acceleration due to gravity, respectively.

Work done = force * distance = μg * mass * distance (A prior blog shows how to optimize our in-store shopping route.)

Objective is to minimize: M*O + (M+S)*D

A minimal work objective suggests these simple rules:
1) Heavy shopping: park close to the exit. 
2) Light shopping: park to minimize total walk.

Thus, the goodness of a parking spot depends on the shopping context. Let us figure out a good parking spot for the shopping scenario below.

Linear Store, Manhattan Distances
Consider a long, 'linear' store along the x-axis, with the exit @ x = 0, and entrance @ x = L. Assume 'Manhattan' walking distances (ℓ¹) and that prior customers selected spots nearest the building along y-axis, and picked their spots along the x-axis based on individual preferences. Given this, the distance we can expect to walk to/from the store along the y-axis is already (near) minimal. This leaves us with a (non-convex) one-dimensional search for open locations x(i) along the x-axis over three regions. Let us split this task into two steps. 

Step-1: Find the best spot within each region
A) x(i) = -a ≤ 0 
Minimize M(O+D)+S*D = M(L+a +a) + Sa = ML + (2M+S)a*

B) 0 ≤ x(i) = b ≤ L
Minimize M(L-b + b) + Sb = ML +Sb*

C)  x(i) = L+c ≥ L
Minimize M(c+L+c) + S(L+c) = ML+SL + (2M+S)c*

The optimal x* within each of these regions is the one closest to the exit. This is independent of S and L, and identifiable by greedy search.

Step-2: Finding the least cost spot among (a*, b*, c*)
The worst spot in B is no worse than c*, independent of S and L, yielding a binary choice: pick a* or b*.
x(i) ≤ 0: incremental cost = (2M+S)a*, a* ≥ 0
x(i) ≥ 0: incremental cost = Sb*, b* ≥ 0

For small values of S, b* dominates and is optimal for light shopping or window shoppers. As S increases and becomes comparable to M, b* is preferable when:
b*/a*  ≤ 1 +2(M/S)

Even if we 'shop till we drop' and carry our own weight, b* can be as much as 3a* and still dominate.

Practically speaking, b* is a solid bet, but when B is full, the shopper is forced to choose between disjoint regions A and C.
x(i) ≤ 0: incremental cost = (2M+S)a*
x(i) ≥ L: incremental cost = SL + (2M+S)c*

shoppers would prefer a* to c* unless:

(a*-c*) > L/[2(M/S)+1]

Scenarios:
i) Between spots equidistant from the entrance and exit, a* dominates c*, independent of S and L. 
ii) For the 'carry our own weight' scenario, a* is preferable when
(a*-c*) ≤  L/3
iii) For unmanageably large S, a* remains preferable if:
(a*-c*) ≤ L

We can now draw some conclusions.

Finding a Minimum-Work Parking Spot
Preferred order of parking is:
b* > a* > c*

which is out of order. The actual search pattern we employ may depend on whether the aisles in the parking lot are along the x- or y-axis. 

Light/medium shopping context
Clockwise, starting from the exit, scan B, park if feasible. Else scan C, and park if feasible. Else, turn around choose a spot in A. 

Heavy shopping context
Clockwise, starting from the exit, scan B, park if feasible. Else turn around, scan A, and park if feasible. Else, choose a spot in C.

Alternative Optimal Solutions to the Coin Mix Problem

The solution to the 'optimal change' problem analyzed in the previous post is further examined from a practice perspective. Again, we use CPLEX to do this since it is quite convenient for such analyses.

Problem 1 is an integer knapsack problem that is known to be theoretically NP-Hard but fairly easy to solve in practice using Dynamic Programming. For this specific coin instance, enumeration with simple pruning rules that exploit the problem structure would work too.

Globally Robust versus Scenario-Optimal
Problem 2 is relatively trickier. It attempts to minimize the maximum weight across the feasible solutions to each of the change scenarios. The value of the 10-coin min-weight solution in the previous post:

Pennies:Quarters:Dimes:Nickels::4:3:2:1 is slightly more than a dollar (1.04$). This coin mix will be able to satisfy any random change request in the range 1-100c. Note: If we only cared about change between 1-99c, an optimal solution (35.412g, 99c) is: PQDN::4241.

However, while an optimal solution to Problem 2 is robust in terms of this ability to meet any request, it is not necessarily optimal in terms of meeting specific coin requests. For example, if we only ever use change for a 3pm $1.68 cup of Starbucks in the cafeteria, then the 4-3-2-1 solution may not be the best. However, if by chance, we choose to downsize to a smaller $1.29 cup one day, then the 68c solution may not work.

First Among Equals
We only used a single goal within the optimization formulations: either min-sum, min-count, or min-weight. As mentioned in a recent post, practical optimization models almost never go into production carrying just a single goal. Consider these alternative optimal optimal solutions for 96c:

v   #     wt         p n d q
96 9    24.046    1 0 7 1
96 6    24.046    1 0 2 3

The second solution has the same weight but fewer quarters + dimes, and does the same job a little more efficiently. On the other hand, the first solution perhaps allows greater flexibility in terms of meeting other change requests (e.g. 30c, 40c).  

Continuing along this path,
a) if we set the lower bound on the number of dimes in Problem 2 = 7, we obtain the following 13-coin alternative to the 4-3-2-1 answer, having the same weight and value (36.546g, $1.04) PQDN::4171


b) If we want a least-value solution to Problem 2, then an optimal objective function value whose corresponding weight is only 1.5g more than the min-weight is 1.0$ (37.912g)
PQDN::5241 or PQDN::5091
(If you ever change a dollar bill in the future, do so in a robust manner via this mnemonic: PQDN 5241 :)


Interestingly, these 1$ solutions include five pennies (a feasible 4-penny solution has a value of 1.04$ or more).

Depending on the context, one of these solutions is more preferable than the others, and this preference can be quantified by suitably incorporating secondary and tertiary goals within the objective function. In contrast, a pure constraint satisfaction model will solely focus on generating feasible solutions ignoring any preference. These principles are the cornerstone of many mission-critical optimal planning systems and operational decision support applications deployed across industries.