p14 | Blood Bank Netherlands

See also

This problem is sourced from Ferchtandiker2025.

Note

• We add implicit assumptions that sets are non-empty, travel times \(T_{ij} \geq 0\), \(T_{\text{limit}} \geq 0\), and \(n \leq |\mathcal{S}|\).

Description

Sanquin, the Dutch blood bank, aims to optimize the distribution of blood products to hospitals across the Netherlands. To ensure timely and efficient delivery, Sanquin plans to establish a network of blood distribution centers (DCs) at select hospitals. The goal is to minimize the average drive time between hospitals and their assigned DCs while adhering to logistical constraints.

Key Components of the Problem Facilities Involved: Hospitals (Demand Points): All hospitals in the Netherlands require regular blood deliveries. Candidate Distributoion Center (DC) Locations: A subset of hospitals has been pre-identified as potential sites for DCs. Only these candidate hospitals can host a DC.

Decisions to Make: Sanquin needs to know which hospitals should serve as DCs such that the average drive time to other hospitals is minimized.

Critical Constraints: Travel Time Limit: A hospital can only be assigned to a specific DC if the travel time between them does not exceed T minutes. This ensures blood products reach hospitals within a safe timeframe.

DC Activation Requirement: A hospital can only be assigned to a DC if that DC is operational (i.e., selected as one of the n DCs).

Objective: Minimize the average drive time between hospitals and their assigned DCs. This is equivalent to minimizing the total drive time across all hospital-DC pairs, as the number of hospitals is fixed.

Operational Details Drive Time vs. Cost: The drive time between a DC and a hospital directly translates to a transportation cost. Minimizing total cost in the model corresponds to minimizing total drive time.

Travel Time Limit (T): Assignments violating the T-minute threshold are strictly prohibited. For instance, if T = 60, no hospital can be paired with a DC more than 60 minutes away.

Why This Matters Blood products have limited shelf lives, and emergencies require rapid delivery. By optimizing DC locations and assignments, Sanquin ensures:

Faster emergency response via minimized average drive times. Compliance with time-sensitive delivery requirements through the T-minute constraint. Cost-effective operations by avoiding unnecessary infrastructure (only n DCs are activated).

Formulations

Formulation a (valid)

See also

This formulation is sourced from Ferchtandiker2025 (formulation id: efficient).

Note

• The efficient formulation pre-computes a feasibility indicator \(\delta_{ij}\) to avoid the need for big-M constraints.

• We add an assumption that the feasibility indicator \(\delta_{ij} \in \{0,1\}\) and \(\delta_{ij} = 1\) if and only if \(T_{ij} \leq T_{\text{limit}}\).

Parameters

Name	Description	Type	Shape
nS	Number of candidate DC locations	integer	scalar
nH	Number of hospital locations	integer	scalar
n	Number of DCs that must be opened	integer	scalar
T_limit	Maximum allowed travel time from a DC to any hospital it serves	continuous	scalar
T	Travel time from candidate DC location i to hospital j	continuous	[nS, nH]
delta	Feasibility indicator: 1 if travel time from DC i to hospital j is within the limit, 0 otherwise	binary	[nS, nH]

Variables

Name	Description	Type	Shape / Indices
x	1 if candidate DC location i is opened, 0 otherwise	binary	[nS]
y	1 if hospital j is assigned to DC i, 0 otherwise	binary	[nS, nH]

Assumptions

Description	Formulation	Implicit
Number of candidate DC locations is positive.	\(|\mathcal{S}| > 0\)	yes
Number of hospital locations is positive.	\(|\mathcal{H}| > 0\)	yes
Travel times are non-negative.	\(T_{ij} \geq 0 \quad \forall i \in \mathcal{S},\, j \in \mathcal{H}\)	yes
The travel time limit is non-negative.	\(T_{\text{limit}} \geq 0\)	yes
The number of DCs to open does not exceed the number of candidate locations.	\(n \leq |\mathcal{S}|\)	yes
delta encodes feasibility: 1 iff travel time is within the limit.	\(\delta_{ij} = 1 \iff T_{ij} \leq T_{\text{limit}}, \quad \delta_{ij} = 0 \iff T_{ij} > T_{\text{limit}} \quad \forall i \in \mathcal{S},\, j \in \mathcal{H}\)	no

Constraints

• Select exactly n DC locations.

  \[ \sum_{i \in \mathcal{S}} x_i = n \]

• Hospitals can only be allocated to active DCs, bounded by the number of feasibly reachable hospitals.

  \[ \sum_{j \in \mathcal{H}} \delta_{ij}\, y_{ij} \leq x_i \cdot \sum_{j \in \mathcal{H}} \delta_{ij} \quad \forall i \in \mathcal{S} \]

• Each hospital must be assigned to exactly one feasible DC.

  \[ \sum_{i \in \mathcal{S}} \delta_{ij}\, y_{ij} = 1 \quad \forall j \in \mathcal{H} \]

• No allocation allowed if travel time between DC and hospital exceeds the limit.

  \[ y_{ij} = 0 \quad \forall i \in \mathcal{S},\, j \in \mathcal{H} \text{ with } \delta_{ij} = 0 \]

Objective

Minimize total drive time across all feasible hospital-DC assignments.

\[ \min \sum_{i \in \mathcal{S}} \sum_{j \in \mathcal{H}} \delta_{ij}\, y_{ij}\, T_{ij} \]

Formulation b (valid)

See also

This formulation is sourced from Ferchtandiker2025 (formulation id: inefficient).

Parameters

Name	Description	Type	Shape
nS	Number of candidate DC locations	integer	scalar
nH	Number of hospital locations	integer	scalar
n	Number of DCs that must be opened	integer	scalar
T_limit	Maximum allowed travel time from a DC to any hospital it serves	continuous	scalar
T	Travel time from candidate DC location i to hospital j	continuous	[nS, nH]

Variables

Name	Description	Type	Shape / Indices
x	1 if candidate DC location i is opened, 0 otherwise	binary	[nS]
y	1 if hospital j is assigned to DC i, 0 otherwise	binary	[nS, nH]

Assumptions

Description	Formulation	Implicit
Travel times are non-negative.	\(T_{ij} \geq 0 \quad \forall i \in \mathcal{S},\, j \in \mathcal{H}\)	yes
The travel time limit is non-negative.	\(T_{\text{limit}} \geq 0\)	yes
The number of DCs to open does not exceed the number of candidate locations.	\(n \leq |\mathcal{S}|\)	yes

Constraints

• Select exactly n DC locations.

  \[ \sum_{i \in \mathcal{S}} x_i = n \]

• Hospitals can only be allocated to active DCs, using the loose big-M bound of |H|.

  \[ \sum_{j \in \mathcal{H}} y_{ij} \leq x_i \cdot |\mathcal{H}| \quad \forall i \in \mathcal{S} \]

• Each hospital must be assigned to exactly one DC.

  \[ \sum_{i \in \mathcal{S}} y_{ij} = 1 \quad \forall j \in \mathcal{H} \]

• Travel time limit: a hospital may only be assigned to a DC within the time limit.

  \[ T_{ij} \cdot y_{ij} \leq T_{\text{limit}} \quad \forall i \in \mathcal{S},\, j \in \mathcal{H} \]

Objective

Minimize total drive time across all hospital-DC assignments.

\[ \min \sum_{i \in \mathcal{S}} \sum_{j \in \mathcal{H}} y_{ij}\, T_{ij} \]