Service allocation procedure

Service Allocation

Overview

The service allocation module determines which facilities (e.g. schools) to keep open and how clients (population grid cells) are assigned to them, balancing travel costs against scale inefficiency. The workflow is split between two environments:

1. GeoDMS (Analyses.dms): computes the origin–destination (OD) matrix and exports input data to Arrow files.
2. Julia: reads those Arrow files, solves the facility location and assignment problem, and writes results back to an Arrow file for use in GeoDMS.

GeoDMS (Analyses.dms)
  └─▶ {country}_od.arrow    (OD pairs: client, facility, t_ij, d_ij)
  └─▶ {country}_i.arrow     (clients: id, population)
  └─▶ {country}_j.arrow     (facilities: id)
        │
        ▼
Julia (one of the solvers below)
        │
        ▼
  {country}_j_greedy.arrow  (facilities: id, open)
  or
  {country}_j_mip.arrow
        │
        ▼
GeoDMS (Analyses.dms)
  └─▶ FacilityRemainsOpen, Openness, accessibility outputs

---

Problem formulation

Sets and indices

• Clients: $i \in \mathcal{I}$ — population grid cells with demand $Q_i \ge 0$
• Candidate facilities: $j \in \mathcal{J}$ — school locations

Decision variables

• Open decision: $x_j \in {0,1}$
• Demand flow: $y_{ij} \ge 0$, fraction of client $i$ assigned to facility $j$
• Facility load: $S_j := \sum_i y_{ij} \cdot Q_i$

Objective

Minimise total travel cost plus a scale-inefficiency penalty for under-enrolled facilities:

$$\min \sum_{ij} c(t_{ij}) \cdot Q_i \cdot y_{ij} + \lambda \sum_j \max(Q_{\min} - S_j,; 0)$$

where $t_{ij}$ is in minutes and $\lambda$ is a penalty weight (see Parameters below).

Constraints

1. Each client is fully assigned: $\sum_j y_{ij} = 1 \quad \forall i$
2. Assignment only to open facilities: $y_{ij} \le x_j \quad \forall i,j$
3. Deficit definition: $\text{deficit}j \ge Q{\min} \cdot x_j - S_j \quad \forall j$

Parameters

Symbol	Variable in code	Description
$Q_{\min}$	min_students	Minimum viable enrolment per facility (default: 100)
$\lambda$	λ	Penalty per unit of under-enrolment; derived as facility_cost / (min_students / 2)
facility_cost	—	Estimated annual operating cost per facility: 2 * total_travel_time * 200 / M
flag	flag	Set to 1 to activate the penalty term, 0 to ignore it

---

GeoDMS component: OD matrix generation (Analyses.dms)

The AllocateKidsToSchools unit in Analyses.dms computes OD pairs using a network impedance matrix. Key outputs per OD pair:

Field	Description
client_rel	Index of origin grid cell
facility_rel	Index of destination facility
t_ij	Travel time (seconds) along the shortest path
d_ij	Distance (km)
travelcost_ij	Monetary travel cost
Deterrence_ij	Distance-decay weight $\alpha \cdot c_{ij}^\beta$ based on surplus distance beyond the nearest facility

The deterrence function uses a power-law decay ($\beta = -2$) on the extra distance $c_{ij} = \max(d_{ij} - \text{ClosestDist}_i,; \epsilon)$, so clients are only penalised for travelling further than their nearest option.

After running a Julia solver, GeoDMS reads back the open/closed status and computes:

• FacilityRemainsOpen: boolean per facility
• Openness: a potential-based accessibility surface on the 1 km grid

---

Julia solvers

All solvers share the same data loading pattern:

od  = Arrow.Table(".../{country}_od.arrow")
loc = Arrow.Table(".../{country}_i.arrow")
fac = Arrow.Table(".../{country}_j.arrow")

And write results as:

Arrow.write(".../{country}_j_greedy.arrow", (id = facilities, open = open_vec))

where open is encoded as:

• 0 = closed
• 1 = open and $S_j \ge Q_{\min}$
• 2 = open but $S_j < Q_{\min}$ (under-enrolled)

1. Pure greedy heuristic (greedy-nn.jl)

No LP or MIP solver required. Steps:

1. Start with all facilities open (filtered by expected load from nearest-facility assignment).
2. Run a drop heuristic: iteratively close the facility whose removal saves the most (penalty saving minus extra travel cost for displaced clients), using a precomputed second-best facility per client.
3. Repeat until no improving closure exists.

Supports a grid search over min_students and λ_factor to explore the sensitivity of the number of open facilities to these parameters:

julia greedy-nn.jl

Set run_grid = true for a grid search, false for a single run. Also supports a quadratic travel cost function $f(t) = 0.05 \cdot (t/60)^2 + 0.5 \cdot (t/60)$ in addition to the linear option.

2. LP relaxation + greedy heuristic (lp-greedy.jl)

1. Solve the LP relaxation of the facility location problem using HiGHS via JuMP.
2. Classify facilities as: integer-open, integer-closed, or fractional.
3. Start with all non-closed facilities open, then apply the drop heuristic only to fractional facilities (integer-open ones are kept fixed).
4. Fix the resulting open/closed decisions and re-solve an assignment LP for optimal fractional flows.

This tends to give tighter solutions than the pure greedy approach for larger instances.

3. LP relaxation + greedy, no re-solve (lp-greedy-nn.jl)

Same as lp-greedy.jl but skips the final assignment LP re-solve. Faster but assignment is from the greedy step only.

4. MIP solver (mip.jl)

1. Solve the LP relaxation.
2. Fix variables that are already integer (within tolerance tol = 1e-6).
3. Set remaining $x_j$ as binary and solve the MIP using HiGHS (1% optimality gap).

Supports a force = true flag to fix all facilities open (useful for benchmarking travel costs with full network).

julia mip.jl

Solver comparison

Script	Method	Speed	Solution quality
greedy-nn.jl	Greedy drop	Fast	Heuristic
lp-greedy-nn.jl	LP + greedy drop	Medium	Better lower bound
lp-greedy.jl	LP + greedy + re-solve	Medium	Best heuristic
mip.jl	LP + MIP	Slow	Near-optimal (1% gap)

---

Policy options

1. Guaranteed availability

Each client $i$ must have at least one open facility $j$ with $t_{ij} \le t_{\text{set}}$.

2. Zoned availability

Availability is guaranteed only for clients within designated zones ($Z_i = 1$). For all such $i$, there must exist a provider $j$ with $t_{ij} \le t_{\text{zone}}$.

3. No-promises rule

Service providers may decline to serve sparsely populated areas. A provider $j$ may only open if it can supply at least $Q_{\min}$ demand within acceptable travel time. This corresponds to the penalty formulation used in the Julia solvers.

Notes 1 and 3 are special cases of 2 with $t_{\text{zone}} = \infty$ or $0$, respectively.

---

Economies of scale

Facility cost when open: $c_j := c_Q \cdot S_j$, but at least $c_0$.
Minimum optimal demand: $Q_{\text{opt}} := c_0 / c_Q$.

After removing fixed provision costs, the scale inefficiency costs are:

$$C_{\text{si}} = c_Q \cdot \max(Q_{\text{opt}} - S_j,; 0)$$

This is approximated in the objective by the $\lambda \cdot \text{deficit}_j$ penalty term.