p20 | World Food Program Food Distribution

See also

This problem is sourced from Ferchtandiker2025 [1].

Note

• We add implicit assumptions that all sets are non-empty and \(\mathrm{dem}_j, \mathrm{cap}_t, \mathrm{pc}_k, \mathrm{tc}_{ijk}, \mathrm{nutreq}_\ell, \mathrm{nutval}_{k\ell} \geq 0\).

• We assume the directed supply graph has no arcs entering suppliers and no arcs leaving beneficiary camps.

• The original problem is not NP-hard: shipments are continuous and the transshipment points have unlimited capacity, so the problem reduces to a linear program and is solvable in polynomial time. We restrict to integral shipments and add throughput capacities (mentioned in the original Ferchtandiker et al. [1] description), which couple the commodities and make the problem NP-hard.

NP-hard: yes

Description

Optimizing Emergency Food Distribution for the World Food Program (WFP)

In crisis-affected regions—such as conflict zones, post-disaster areas, or drought-stricken communities—the World Food Program (WFP) faces the monumental task of delivering life-saving food aid to vulnerable populations. This requires balancing cost efficiency, logistical feasibility, and nutritional adequacy while navigating complex supply chains, unreliable infrastructure, and urgent time constraints.

Context and Challenges Logistical Complexity:

Fragile Infrastructure: Many regions lack reliable roads, with routes often disrupted by conflict, flooding, or landslides. Transshipment points (e.g., warehouses, temporary hubs) are critical but may have limited capacity.

Geographic Dispersion: Beneficiary camps are frequently located in remote or inaccessible areas, requiring multi-stage transportation (supplier → transshipment point → camp).

Cost Variability: Procurement costs vary by commodity, while transportation costs depend on distance, road conditions, and fuel availability.

Nutritional Needs:

Each beneficiary requires a daily ration that meets minimum nutritional standards.

Commodities differ in nutritional value; for example, rice provides carbohydrates but lacks certain micronutrients, necessitating a mix of foods.

Resource Constraints:

Limited funding demands strict cost control across procurement and transportation.

Political or security pressures may restrict access to certain suppliers or routes.

Key Objectives The WFP aims to design a food distribution plan that:

Minimizes Total Costs:

Reduce expenses from procuring commodities and transporting them through complex networks.

Guarantees Food Availability:

Ensure all beneficiary camps receive sufficient quantities of each commodity.

Meets Nutritional Standards:

Provide rations that collectively satisfy all nutrient requirements.

Operational Components Suppliers: Procurement costs vary by commodity.

Transshipment Points: Intermediate hubs where food is consolidated, repackaged, or redirected. Bottlenecks must be avoided.

Beneficiary Camps: Final destinations where displaced populations receive food. Demand is determined by the number of people and required ration sizes.

Critical Constraints Network Directionality: The supply graph has no arcs entering supplier nodes and no arcs leaving beneficiary camps.

No Storage: No storage is assumed—food is immediately redirected.

Transshipment Capacity: Each transshipment point can handle only a limited number of kilograms, counted across all commodities passing through it.

Whole-Kilogram Shipments: Food is moved in sealed units, so the amount of each commodity shipped along an arc is a whole number of kilograms.

Demand Fulfillment: Each camp must receive enough of every commodity to meet its calculated ration size.

Nutritional Adequacy: The combination of commodities in the ration must meet all nutrient thresholds.

Formulations

Formulation a (valid)

See also

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

Note

• The efficient formulation is node-based with integral flow variables \(F_{ijk}\) on graph edges.

• In the Ferchtandiker et al. [1] formulation, the procurement cost was \(\sum_{k \in K} \mathrm{pc}_k \sum_{j \in N_B} \mathrm{dem}_j R_k\), which depends only on the ration size \(R_k\), while the inefficient formulation charges procurement on the total amount shipped \(\sum_{p \in P} x_{pk}\). Since the demand constraint \(\sum_{i \in N} E_{ij} F_{ijk} \geq \mathrm{dem}_j R_k\) permits shipping in excess of \(\mathrm{dem}_j R_k\) without additional procurement penalty, the objectives are misaligned. We therefore charge procurement on the supplier outflow \(\sum_{s \in N_S} \sum_{j \in N} E_{S_s, j} F_{S_s, j, k}\).

Parameters

Name	Description	Type	Shape
nN	Total number of nodes in the supply network (suppliers, transshipment points, and beneficiary camps)	integer	scalar
nS	Number of supplier nodes	integer	scalar
nT	Number of transshipment nodes	integer	scalar
nB	Number of beneficiary camps	integer	scalar
nK	Number of food commodities	integer	scalar
nL	Number of nutritional requirements	integer	scalar
S	Supplier node indices: \(S_s\) is the index in \(N\) of supplier \(s\)	integer	[nS]
T	Transshipment node indices: \(T_t\) is the index in \(N\) of transshipment node \(t\)	integer	[nT]
B	Beneficiary camp node indices: \(B_j\) is the index in \(N\) of beneficiary camp \(j\)	integer	[nB]
E	Adjacency matrix: \(1\) if a directed edge exists from node \(i\) to node \(j\), \(0\) otherwise	binary	[nN, nN]
dem	Number of beneficiaries at each beneficiary camp	integer	[nB]
cap	Throughput capacity, in kg, of each transshipment node	integer	[nT]
pc	Procurement cost per kg of each commodity	continuous	[nK]
tc	Transportation cost per kg of commodity \(k\) along the edge from node \(i\) to node \(j\)	continuous	[nN, nN, nK]
nutreq	Per-person nutritional requirement for each nutrient	continuous	[nL]
nutval	Nutritional value per kg of each commodity for each nutrient	continuous	[nK, nL]

Variables

Name	Description	Type	Shape / Indices
F	Amount of commodity \(k\) shipped from node \(i\) to node \(j\) (kg)	integer	[nN, nN, nK]
R	Ration size per person of each commodity (kg)	continuous	[nK]

Assumptions

Description	Formulation	Implicit
There is at least one node.	\(n_N \geq 1\)	yes
There is at least one supplier node.	\(n_S \geq 1\)	yes
There is at least one transshipment node.	\(n_T \geq 1\)	yes
There is at least one beneficiary camp.	\(n_B \geq 1\)	yes
There is at least one commodity.	\(n_K \geq 1\)	yes
There is at least one nutrient.	\(n_L \geq 1\)	yes
Each supplier node index is a valid node index (in range \([0, n_N)\)).	\(S_s \in N \quad \forall s \in N_S\)	no
Each transshipment node index is a valid node index (in range \([0, n_N)\)).	\(T_t \in N \quad \forall t \in N_T\)	no
Each beneficiary camp node index is a valid node index (in range \([0, n_N)\)).	\(B_j \in N \quad \forall j \in N_B\)	no
The supplier, transshipment, and beneficiary node-class maps partition \(N\) (every node belongs to exactly one class).	\(N = N_S \sqcup N_T \sqcup N_B\)	no
The supplier, transshipment, and beneficiary node-class maps are each injective.	\(S, T, B \text{ are injective}\)	no
No graph arc enters a supplier node.	\(E_{i,S_s} = 0 \quad \forall i \in N, s \in N_S\)	no
No graph arc leaves a beneficiary camp.	\(E_{B_b,j} = 0 \quad \forall b \in N_B, j \in N\)	no
Number of beneficiaries at each camp is non-negative.	\(\mathrm{dem}_j \geq 0 \quad \forall j \in N_B\)	yes
Throughput capacity of each transshipment node is non-negative.	\(\mathrm{cap}_t \geq 0 \quad \forall t \in N_T\)	yes
Procurement cost per kg of each commodity is non-negative.	\(\mathrm{pc}_k \geq 0 \quad \forall k \in K\)	yes
Transportation cost along each arc for each commodity is non-negative.	\(\mathrm{tc}_{ijk} \geq 0 \quad \forall i,j \in N, k \in K\)	yes
Per-person nutritional requirement for each nutrient is non-negative.	\(\mathrm{nutreq}_l \geq 0 \quad \forall l \in L\)	yes
Nutritional value per kg of each commodity for each nutrient is non-negative.	\(\mathrm{nutval}_{kl} \geq 0 \quad \forall k \in K, l \in L\)	yes

Constraints

• Flow conservation at transshipment nodes for each commodity: total inflow equals total outflow (no storage).

  \[ \sum_{i \in N} E_{i, T_j} F_{i, T_j, k} = \sum_{i \in N} E_{T_j, i} F_{T_j, i, k} \quad \forall j \in N_T, k \in K \]

• Total throughput at each transshipment node, summed over all commodities, is within its capacity.

  \[ \sum_{k \in K} \sum_{i \in N} E_{i, T_t} F_{i, T_t, k} \leq \mathrm{cap}_t \quad \forall t \in N_T \]

• Each beneficiary camp receives at least its ration demand on incoming edges for each commodity.

  \[ \sum_{i \in N} E_{i,B_j} F_{i,B_j,k} \geq \mathrm{dem}_j R_k \quad \forall j \in N_B, k \in K \]

• The ration collectively satisfies all per-person nutritional requirements.

  \[ \sum_{k \in K} \mathrm{nutval}_{kl} R_k \geq \mathrm{nutreq}_l \quad \forall l \in L \]

• Flow is supported on graph edges: no flow on non-edges. (implicit)

  \[ E_{ij} = 0 \implies F_{ijk} = 0 \quad \forall i,j \in N, k \in K \]

• Flow on each arc for each commodity is non-negative. (implicit)

  \[ F_{ijk} \geq 0 \quad \forall i,j \in N, k \in K \]

• Ration size per person of each commodity is non-negative. (implicit)

  \[ R_k \geq 0 \quad \forall k \in K \]

Objective

Minimize total procurement cost plus total transportation cost. Procurement cost is charged on the outflow of each commodity leaving supplier nodes.

\[ \min \sum_{k \in K} \mathrm{pc}_k \left( \sum_{s \in N_S} \sum_{j \in N} E_{S_s, j} F_{S_s, j, k} \right) + \sum_{i \in N} \sum_{j \in N} \sum_{k \in K} \mathrm{tc}_{ijk} F_{ijk} \]

Formulation b (valid)

See also

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

Note

• The inefficient formulation is path- and cycle-based.

• The Ferchtandiker et al. [1] inefficient formulation only ships along paths \(p \in P\). The efficient formulation is node-based with flow variables \(F_{ijk}\) on graph edges, so it admits feasible points that cycle flow around transshipment nodes. To resolve this discrepancy, we introduce a shipment variable \(y_{ck}\) for every simple directed cycle \(c \in C\) of the supply network.

Parameters

Name	Description	Type	Shape
nN	Total number of nodes in the supply network (suppliers, transshipment points, and beneficiary camps)	integer	scalar
nS	Number of supplier nodes	integer	scalar
nT	Number of transshipment nodes	integer	scalar
nB	Number of beneficiary camps	integer	scalar
nP	Number of simple paths from a supplier to a beneficiary camp	integer	scalar
nC	Number of simple directed cycles in the supply network	integer	scalar
nK	Number of food commodities	integer	scalar
nL	Number of nutritional requirements	integer	scalar
S	Supplier node indices: \(S_s\) is the index in \(N\) of supplier \(s\)	integer	[nS]
T	Transshipment node indices: \(T_t\) is the index in \(N\) of transshipment node \(t\)	integer	[nT]
B	Beneficiary camp node indices: \(B_j\) is the index in \(N\) of beneficiary camp \(j\)	integer	[nB]
E	Adjacency matrix: \(1\) if a directed edge exists from node \(i\) to node \(j\), \(0\) otherwise	binary	[nN, nN]
pE	Path-edge indicator: \(1\) if edge \((i, j)\) is part of path \(p\), \(0\) otherwise	binary	[nP, nN, nN]
pRank	Rank/position of node \(v\) within path \(p\); strictly increases along path edges	integer	[nP, nN]
pCost	Shipping cost per kg of commodity \(k\) along path \(p\)	continuous	[nP, nK]
cE	Cycle-edge indicator: \(1\) if edge \((i, j)\) is part of cycle \(c\), \(0\) otherwise	binary	[nC, nN, nN]
cCost	Shipping cost per kg of commodity \(k\) along cycle \(c\)	continuous	[nC, nK]
q	Procurement cost per kg of commodity \(k\)	continuous	[nK]
nutval	Nutritional value per kg of commodity \(k\) for nutrient \(l\)	continuous	[nK, nL]
nutreq	Per-person nutritional requirement for nutrient \(l\)	continuous	[nL]
dem	Number of beneficiaries at beneficiary camp \(j\)	integer	[nB]
cap	Throughput capacity, in kg, of transshipment node \(t\)	integer	[nT]
e	Indicator: \(1\) if path \(p\) ends at beneficiary camp \(j\), \(0\) otherwise	binary	[nB, nP]

Variables

Name	Description	Type	Shape / Indices
x	Amount of commodity \(k\) shipped along path \(p\) (kg)	integer	[nP, nK]
y	Amount of commodity \(k\) shipped along cycle \(c\) (kg)	integer	[nC, nK]
R	Ration size per person of each commodity (kg)	continuous	[nK]

Assumptions

Description	Formulation	Implicit
There is at least one node.	\(n_N \geq 1\)	yes
There is at least one supplier node.	\(n_S \geq 1\)	yes
There is at least one transshipment node.	\(n_T \geq 1\)	yes
There is at least one beneficiary camp.	\(n_B \geq 1\)	yes
There is at least one commodity.	\(n_K \geq 1\)	yes
There is at least one nutrient.	\(n_L \geq 1\)	yes
Each supplier node index is a valid node index (in range \([0, n_N)\)).	\(S_s \in N \quad \forall s \in N_S\)	no
Each transshipment node index is a valid node index (in range \([0, n_N)\)).	\(T_t \in N \quad \forall t \in N_T\)	no
Each beneficiary camp node index is a valid node index (in range \([0, n_N)\)).	\(B_j \in N \quad \forall j \in N_B\)	no
The supplier, transshipment, and beneficiary node-class maps partition \(N\) (every node belongs to exactly one class).	\(N = N_S \sqcup N_T \sqcup N_B\)	no
The supplier, transshipment, and beneficiary node-class maps are each injective.	\(S, T, B \text{ are injective}\)	no
No graph arc enters a supplier node.	\(E_{i,S_s} = 0 \quad \forall i \in N, s \in N_S\)	no
No graph arc leaves a beneficiary camp.	\(E_{B_b,j} = 0 \quad \forall b \in N_B, j \in N\)	no
Each path edge must be a graph edge.	\(pE_{p,i,j} \leq E_{ij} \quad \forall p \in P, i, j \in N\)	yes
Within each path, every node has in-degree at most 1.	\(\sum_{i \in N} pE_{p,i,v} \leq 1 \quad \forall p \in P, v \in N\)	yes
Within each path, every node has out-degree at most 1.	\(\sum_{j \in N} pE_{p,v,j} \leq 1 \quad \forall p \in P, v \in N\)	yes
Each path has a unique source node (in-degree 0, out-degree 1) and that node is a supplier.	\(\forall p \in P, \exists! v \in N : \sum_{j \in N} pE_{p,v,j} = 1 \land \sum_{i \in N} pE_{p,i,v} = 0; \text{ moreover } v \in \{S_s : s \in N_S\}\)	yes
Each path has a unique sink node (in-degree 1, out-degree 0) and that node is a beneficiary camp.	\(\forall p \in P, \exists! v \in N : \sum_{i \in N} pE_{p,i,v} = 1 \land \sum_{j \in N} pE_{p,v,j} = 0; \text{ moreover } v \in \{B_b : b \in N_B\}\)	yes
End indicator \(e\) is consistent with \(pE\): \(e_{j,p} = 1\) iff path \(p\) ends at beneficiary camp \(j\).	\(e_{j,p} = \sum_{i \in N} pE_{p,i,B_j} - \sum_{k \in N} pE_{p,B_j,k} \quad \forall j \in N_B, p \in P\)	yes
Each path is acyclic: rank strictly increases along path edges.	\(pE_{p,i,j} = 1 \implies pRank_{p,j} = pRank_{p,i} + 1 \quad \forall p \in P, i, j \in N\)	yes
Path indexing is complete: every valid simple supplier-to-beneficiary path is indexed by some \(p \in P\).	\(\forall \text{ valid simple } S\text{-to-}B \text{ path } \pi, \exists p \in P : pE_p = \pi\)	yes
Path indexing is injective: distinct path indices give distinct edge sets.	\(p_1 \neq p_2 \implies \exists i, j \in N : pE_{p_1,i,j} \neq pE_{p_2,i,j}\)	yes
Shipping cost along each path for each commodity is non-negative.	\(pCost_{pk} \geq 0 \quad \forall p \in P, k \in K\)	yes
Each cycle edge must be a graph edge.	\(cE_{c,i,j} \leq E_{ij} \quad \forall c \in C, i, j \in N\)	yes
Within each cycle, every node has in-degree at most 1.	\(\sum_{i \in N} cE_{c,i,v} \leq 1 \quad \forall c \in C, v \in N\)	yes
Within each cycle, every node has out-degree at most 1.	\(\sum_{j \in N} cE_{c,v,j} \leq 1 \quad \forall c \in C, v \in N\)	yes
Within each cycle, each node’s in-degree equals its out-degree (flow conservation), so every node is either skipped or visited with exactly one incoming and one outgoing edge. Together with the degree bounds this makes the active edges a node-disjoint union of simple cycles.	\(\sum_{i \in N} cE_{c,i,v} = \sum_{j \in N} cE_{c,v,j} \quad \forall c \in C, v \in N\)	yes
Each cycle is connected: the active edges of every cycle form a single simple directed cycle rather than a union of two or more node-disjoint cycles. Equivalently, starting from any active node and following successors returns to the start only after visiting every active node.	\(\{(i, j) : cE_{c,i,j} = 1\} \text{ forms a single directed cycle} \quad \forall c \in C\)	yes
Cycle indexing is complete: every valid cycle is indexed by some \(c \in C\).	\(\forall \text{ valid cycle } \pi, \exists c \in C : cE_c = \pi\)	yes
Cycle indexing is injective: distinct cycle indices give distinct edge sets.	\(c_1 \neq c_2 \implies \exists i, j \in N : cE_{c_1,i,j} \neq cE_{c_2,i,j}\)	yes
Shipping cost along each cycle for each commodity is non-negative.	\(cCost_{ck} \geq 0 \quad \forall c \in C, k \in K\)	yes
Procurement cost per kg of each commodity is non-negative.	\(q_k \geq 0 \quad \forall k \in K\)	yes
Nutritional value per kg of each commodity for each nutrient is non-negative.	\(\mathrm{nutval}_{kl} \geq 0 \quad \forall k \in K, l \in L\)	yes
Per-person nutritional requirement for each nutrient is non-negative.	\(\mathrm{nutreq}_l \geq 0 \quad \forall l \in L\)	yes
Number of beneficiaries at each camp is non-negative.	\(\mathrm{dem}_j \geq 0 \quad \forall j \in N_B\)	yes
Throughput capacity of each transshipment node is non-negative.	\(\mathrm{cap}_t \geq 0 \quad \forall t \in N_T\)	yes

Constraints

• Total throughput at each transshipment node, summed over all commodities, is within its capacity. A route through the node carries its shipment through that node exactly once, so the node’s in-degree within a path or cycle indicates whether the route consumes its capacity.

  \[ \sum_{k \in K} \left( \sum_{p \in P} \left( \sum_{i \in N} pE_{p,i,T_t} \right) x_{pk} + \sum_{c \in C} \left( \sum_{i \in N} cE_{c,i,T_t} \right) y_{ck} \right) \leq \mathrm{cap}_t \quad \forall t \in N_T \]

• Each beneficiary camp receives at least its ration demand from paths ending there for each commodity.

  \[ \sum_{p \in P} e_{jp} x_{pk} \geq \mathrm{dem}_j R_k \quad \forall j \in N_B, k \in K \]

• The ration collectively satisfies all per-person nutritional requirements.

  \[ \sum_{k \in K} \mathrm{nutval}_{kl} R_k \geq \mathrm{nutreq}_l \quad \forall l \in L \]

• Amount shipped along each path for each commodity is non-negative. (implicit)

  \[ x_{pk} \geq 0 \quad \forall p \in P, k \in K \]

• Amount shipped along each cycle for each commodity is non-negative. (implicit)

  \[ y_{ck} \geq 0 \quad \forall c \in C, k \in K \]

• Ration size per person of each commodity is non-negative. (implicit)

  \[ R_k \geq 0 \quad \forall k \in K \]

Objective

Minimize total shipping cost plus total procurement cost.

\[ \min \sum_{p \in P} \sum_{k \in K} pCost_{pk} x_{pk} + \sum_{c \in C} \sum_{k \in K} cCost_{ck} y_{ck} + \sum_{k \in K} q_k \sum_{p \in P} x_{pk} \]

Reformulations

Each entry below pairs two formulations of this problem, records whether the second is a reformulation of the first, and gives the parameter map carrying the first formulation’s parameters to the second’s.

a → b (valid)

Note

• Formulation a ships over the arcs of the supply network \((N, E)\); formulation b ships along whole supplier-to-camp routes, so the map enumerates the network’s simple paths and derives \(nP\), \(pE\), \(pRank\), \(pCost\), and \(e\) from them.

• Since a admits cyclic flows, the map also enumerates the network’s simple directed cycles and derives \(nC\), \(cE\), and \(cCost\).

Definitions

Name	Derived from a’s parameters
paths	\(P = \{\text{simple paths } (v_0, \dots, v_r) \text{ in } (N, E) : v_0 \in N_S,\; v_r \in N_B\}\)
cycles	\(C = \{\text{simple directed cycles of } (N, E)\}\)

Parameter map

Name	Definition in terms of a
nN	\(nN = nN\)
nS	\(nS = nS\)
nT	\(nT = nT\)
nB	\(nB = nB\)
nP	\(nP = |P|\)
nC	\(nC = |C|\)
nK	\(nK = nK\)
nL	\(nL = nL\)
S	\(S_s = S_s\)
T	\(T_t = T_t\)
B	\(B_j = B_j\)
E	\(E_{ij} = E_{ij}\)
pE	\(pE_{p,i,j} = 1 \iff (i, j) \text{ is an edge of path } p\)
pRank	\(pRank_{p,v} = \text{position of } v \text{ along path } p\text{, and } 0 \text{ if } v \notin p\)
pCost	\(pCost_{pk} = \sum_{(i,j) \in p} tc_{ijk}\)
cE	\(cE_{c,i,j} = 1 \iff (i, j) \text{ is an edge of cycle } c\)
cCost	\(cCost_{ck} = \sum_{(i,j) \in c} tc_{ijk}\)
q	\(q_k = pc_k\)
nutval	\(\text{nutval}_{kl} = \text{nutval}_{kl}\)
nutreq	\(\text{nutreq}_l = \text{nutreq}_l\)
dem	\(\text{dem}_j = \text{dem}_j\)
cap	\(\mathrm{cap}_t = \mathrm{cap}_t\)
e	\(e_{jp} = 1 \iff \text{path } p \text{ ends at } B_j\)