A Branch-and-Price Algorithm for Fast and Equitable Last-Mile Relief Aid Distribution

AI summary

Overview

• Research area: Humanitarian logistics and operations research, specifically equitable last-mile relief aid distribution and vehicle routing, with a methodological contribution in combinatorial optimization (branch-and-price).
• Technical level: Advanced. The paper assumes familiarity with mixed integer programming, column generation, branch-and-price, the epsilon-constraint method for bi-objective optimization, and the Gini index.
• Scope: The paper develops a bi-objective MIP model and an exact branch-and-price algorithm for routing vehicles from a single depot to shelters while deciding how much scarce relief supply each shelter receives, balancing travel time against inequity in unsatisfied demand.

What This Paper Is About

After a large disaster, prepositioned relief supplies are often not enough to meet all demand, so aid agencies must decide both which shelters vehicles visit and how much supply each shelter receives. The authors model this as a vehicle routing problem extended with delivery-quantity decisions, and they optimize two conflicting goals: minimizing total vehicle travel time (efficiency) and minimizing inequity in unsatisfied demand across individual victims (fairness). The goal is a decision-support tool that produces fair and fast distribution plans, and an exact algorithm that can solve realistically sized instances quickly enough for the response phase.

Key Contributions

1. A Gini-based social welfare objective for relief distribution: The paper incorporates an inequity-averse aggregation function combining average unsatisfied demand with Gini's mean absolute difference of individual unsatisfied demand, weighing inequity between individuals rather than between shelters.
2. A bi-objective VRP-based MIP formulation: Efficiency (total travel time) and equity (the Gini-based measure) are handled through the epsilon-constraint method. The formulation extends the Capacitated Vehicle Routing Problem (CVRP) by adding delivery amount decisions, service-level constraints, a maximum route duration, and vehicle capacity constraints.
3. Mathematical properties and two novel valid inequalities: By deriving properties of optimal delivery allocations when routes are fixed, the authors introduce two valid inequalities that tighten the LP relaxation and accelerate column generation.
4. An exact branch-and-price algorithm: The algorithm includes a column generation method, a GRASP heuristic for the pricing problem, and a heuristic that generates an initial set of columns leading to a feasible solution.
5. Real-world computational study: Tests use datasets from a past earthquake in Van, Turkey, and predicted data for Istanbul's Kartal region.

Main Findings

• The B&P algorithm significantly outperforms commercial MIP solvers on the tested realistic datasets. (The truncated content does not report specific runtimes, instance sizes, or solver names for the comparison.)
• The bi-objective approach reduces aid distribution inequity by 34% without compromising efficiency, according to the abstract.
• The right objective strategy depends on how tight the time limit is. When time constraints are very loose or very tight, lexicographic optimization that prioritizes demand coverage over fairness is effective; for moderately restrictive time constraints, a balanced approach is essential to avoid inequitable outcomes.
• Inequity should be measured between individuals, not shelters. The authors show that shelter-level demand satisfaction ratios can look equally uneven while differing greatly in how many people are affected, and their formulation weights each ratio difference by the number of affected individuals.
• The weight parameter is bounded. For 0 ≤ λ ≤ 1/2 the inequity measure is guaranteed to be monotonous in individual costs (Axiom 4 in Porath and Gilboa, 1994), and the computational results use λ = 1/2.
• Linearization is needed for tractability. The absolute-value term in the objective requires 2·|V_c|² additional continuous variables and two sets of constraints.

Methodology in Plain English

The problem is set on a directed graph where one node represents the depot (split into two copies, node 0 and node n+1) and the remaining nodes are shelters. Travel times between nodes are computed as shortest paths over the post-disaster road network, may be asymmetric, and satisfy the triangle inequality in the constructed complete graph. The model assumes C < Σ d_i, meaning the supply at the depot is strictly less than total demand — the case where fairness matters most. A fleet of m homogeneous vehicles of capacity Q is based at the depot; each vehicle runs one route, no split deliveries are allowed, each shelter is visited once for delivery, and each route must finish within a maximum duration Ψ.

Two objectives are handled with the epsilon-constraint method: minimize total travel time, and minimize D·I, where I = μ + λ·Δ combines the average unsatisfied demand μ with Gini's mean absolute difference Δ. Because Δ = 2μG, using Δ instead of the Gini index G allows linearization and keeps λ dimensionless.

The authors then study the subproblem that remains when vehicle routes are fixed: the total travel time becomes constant, and only the delivery quantities need optimizing. From properties of that subproblem they derive valid inequalities and an algorithm for optimal delivery allocations. These feed into a branch-and-price framework, in which column generation repeatedly solves a pricing problem — handled with a GRASP heuristic — and the search is warm-started with a heuristic that produces an initial column set and a feasible solution.

Why This Matters

• Research impact: The paper targets a gap the authors identify — no prior research solves a bi-objective problem that integrates explicit routing, delivery-amount decisions, and Gini-based equity. It also answers a call noted in Eisenhandler and Tzur (2019a), who stated that solving their model via column generation and branch-and-price would be a complex task; this paper provides an exact algorithm for problems of similar structure at real-world sizes.
• Real-world applications:
  • Distributing water, food, blankets, tents, and medical items to temporary shelters after a major earthquake, as in the February 2023 Maras earthquakes, which caused over 54,000 fatalities, more than 100,000 injuries, and left 2.5 million people needing shelter across Southeastern Turkey and Northwestern Syria.
  • Planning deliveries to tent cities and container settlements — by May 2023, over 400 tent cities and container settlements with a collective capacity of approximately 100,000 containers were accommodating nearly one million displaced individuals.
  • Urban disaster preparedness in dense districts such as Istanbul's Kartal region, using predicted demand data.
  • Any humanitarian operation where prepositioned stock is insufficient and the agency must justify how shortfalls are shared.
• Industry relevance: Although the application focus is humanitarian, the authors note that CVRP extensions balancing efficiency and service equity are also relevant to commercial logistics. Vidal et al. (2020) and Matl et al. (2017) highlighted equity measures — including the Gini index — as promising for vehicle routing problems more broadly.

Future Directions

• Time-dependent travel times. The paper assumes constant travel times over a short horizon, but notes that in reality damaged roads may be repaired, reducing t_ij over time (as studied by Moreno et al., 2019 and 2020). The authors state that longer time horizons where this assumption must be relaxed are left for future work.
• Scaling the exact method. The computational content beyond the abstract is truncated here; how the B&P algorithm behaves on larger or stochastic instances remains an open question. The paper names Section 6 as the place where future research directions are discussed.
• Alternative fleet and network assumptions. The model uses homogeneous vehicles, a single depot per shelter, no split deliveries, and a single commodity. Whether the B&P approach extends to heterogeneous fleets, multiple depots, split deliveries, or multi-period distribution is not reported.
• Broader equity measure comparisons. The paper contrasts its Gini-based approach with maxmin (Rawlsian) approaches and with standard-deviation- and variance-based measures used by other authors, but does not report a systematic comparison of how these alternatives perform under the same routing and scarcity conditions.

Target Audience

This paper is most valuable to operations research and optimization researchers working on vehicle routing, column generation, and branch-and-price methods, particularly those applying exact methods to multi-objective problems. It is also aimed at humanitarian logistics researchers and practitioners — aid agencies, NGOs, and government disaster-response planners — who must allocate scarce prepositioned supplies across shelters. Readers interested in the measurement of fairness through social welfare functions and the Gini index will find the modeling treatment relevant, and methodologically inclined readers will benefit from the valid inequalities and pricing heuristics.

Authors’ abstract

The distribution of relief supplies to shelters is a critical aspect of post-disaster humanitarian logistics. In major disasters, prepositioned supplies often fall short of meeting all demands. We address the problem of planning vehicle routes from a distribution center to shelters while allocating limited relief supplies. To balance efficiency and equity, we formulate a bi-objective problem: minimizing a Gini-index-based measure of inequity in unsatisfied demand for fair distribution and minimizing total travel time for timely delivery. We propose a Mixed Integer Programming (MIP) model and use the $ε$-constraint method to handle the bi-objective nature. By deriving mathematical properties of the optimal solution, we introduce valid inequalities and design an algorithm for optimal delivery allocations given feasible vehicle routes. A branch-and-price (B&amp;P) algorithm is developed to solve the problem efficiently. Computational tests on realistic datasets from a past earthquake in Van, Turkey, and predicted data for Istanbul's Kartal region show that the B&amp;P algorithm significantly outperforms commercial MIP solvers. Our bi-objective approach reduces aid distribution inequity by 34% without compromising efficiency. Results indicate that when time constraints are very loose or tight, lexicographic optimization prioritizing demand coverage over fairness is effective. For moderately restrictive time constraints, a balanced approach is essential to avoid inequitable outcomes.