Service allocation procedure

Coordinated location selection

• Equitable accessibility versus cost efficiency.
• Constraints: facility size, bandwidths, maximum allowed travel time.
• Define zones in which a facility needs to be at least within x minutes, even if this is inefficient; then apply three variants:
  • Everything is in the zone (full equity variant)
  • Locations that meet a set of criteria are in the zone (restricted intervention variant)
  • Free market variant

Policy options

1. Guaranteed availability: each client location $i$ must have at least one available service provider $j$ with $t_{ij} \leq t_{set}$.
2. Zoned availability: availability is guaranteed only for clients within designated zones:
   • Let $Z_i = 1$ indicate that client $i$ lies within a protected zone.
   • For all such $i$, there must exist a provider $j$ with $t_{ij} \leq t_{zone}$.
3. No-promises rule: service providers may choose not to serve sparsely populated areas. A provider $j$ may only open if it can supply at least $Q_{opt}$ demand within acceptable travel time $t_{max}: for each $y_j = 1$ $\sum_{i} x_{ij} \ge Q_{opt}$.

Note that 1 and 3 are special cases of 2 with $t_{zone} = \inf$ or $0$, respectively.

Economies of scale: demand constraints

Sets and indices

• Clients: $i \in \mathcal{I}$ with $|\mathcal{I}| \approx 10^6$
• Candidate facilities: $j \in \mathcal{J}$ with $|\mathcal{J}| \approx 10^6$, choose $p \approx 10^3$

Decision variables

• Open decision: $y_j \in {0,1}$
• Assigned demand flow: $x_{ij} \ge 0$
• Facility load: $S_j := \sum_i x_{ij}$

Demand

• Demand at client location $i$: $Q_i \ge 0$
• For each client $i$: $\sum_j x_{ij} = Q_i$
• If $y_j = 0$, then $x_{ij} = 0$

Costs

• Unit service cost: $c_Q$
• Minimum facility cost: $c_0$
• Facility cost when $y_j = 1$: $c_j := c_Q \cdot S_j$, but at least $c_0$
• Minimum optimal demand: $Q_{opt} := c_0 / c_Q$
• Total costs: $t_{tot} = \sum_j [ y_j \cdot c_j ]$
• After removal of fixed provision costs $\sum C_Q \cdot x_{ij}$, the scale inefficiency costs remain $C_{si} = c_Q \cdot \min(Q_{opt} - S_j, 0)$

Travel and suitability

• Potential travel cost: $c_{ij} = f(t_{ij})$, e.g. $f(t)=t$ or $f(t)=t^2$
• Aggregate demand cost term: $C_{tot} := \sum_j c_j = \sum_j $
  • split up total demand related costs and costs of scale inefficiency: $c_{tot} = c_{mar} + c_{si}$
  • $c_{mar} := c_Q \cdot \sum_j S_j$
  • $c_{si} = \sum_j [ S_j \le Q_{opt} ] \cdot c_Q \cdot (Q_{opt} - S_j) \cdot y_j$
• Suitability of facility location $j$ for client location $i$ $s_{ij}$;
  • $s_{ij} = 0$ if $t_{ij} > t_{set}$ inside the service zone, i.e $Z_i = 0$ or $t_{ij} > t_{max}$ outside the service zone.
• Travel time: $t_{ij}$
• Acceptable travel time: $t_{set}$
• Hard cutoff: $t_{max}$

Assignment rule

• Demand allocation for client $i$ to facility $j$: $$x_{ij} := A_i \cdot B_j \cdot y_j \cdot s_{ij} \cdot e^{-\beta t_{ij}}$$
• $A_i$ is set to constrain the demand $Q_i$ of client location $i$.
• $B_j$ is an optional damping factor
• $\beta > 0$ governs how strongly clients prefer nearby facilities

Optimisation problem as MILP

Given $t_{ij}$, $c_{ij}$, $s_{ij}$, $Q_{opt}$, $c_j$, $\beta$, $t_{max}$, $t_{set}$

Define

$$m_{ij} := s_{ij} \cdot e^{-\beta t_{ij}}$$

Objective

min over $y_j \in {0,1}$ and $x_{ij} \ge 0$:

$$\sum_{ij} c_{ij} x_{ij} + \sum_j (S_j < Q_{opt}) \cdot c_x \cdot (Q_{opt} - S_j) \cdot y_j$$

Constraints

1. Demand satisfaction

$$\sum_j x_{ij} = Q_i \quad ⇒ \quad A_i = \frac{Q_i}{\sum_j [ y_j \cdot m_{ij} ]} \qquad \forall i$$

2. Assignment

$$x_{ij} := A_i \cdot y_j \cdot m_{ij}$$

3. Assignment only to open locations

$$x_ij \le Q_i \cdot s_{ij} \cdot y_i \qquad \forall i, \forall j$$

4. Facility load

$$S_j = \sum_i x_{ij} \qquad \forall j$$

Notes

• $y_j \cdot m_{ij}$ is non-zero only for a limited number of $j$ for each $i$ in low-demand areas, motivating a sparse representation.
• If for some $i$ all facilities with $y_j = 1$ have $t_{ij} &gt; t_{max}$, add a ghost facility $g$ with $t_{ig} = t_{max}$ and $c_{ig}$ prohibitive.