arXiv:2512.19882cs.AImath.OC2025-12被引 4

优化救灾物资分配,兼顾送达速度与公平性。

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

  • 用分支定价算法求解多目标配送问题,平衡效率与公平。
  • 实测显示不公平度降低34%,且比商用求解器快得多。
  • 在时间宽松或紧张时优先覆盖需求,中等约束下需平衡公平与效率。

灾后物资配送是人道主义物流的关键环节。重大灾害中预置物资常不足以满足全部需求。本文研究从分发中心到避难所的车辆路径规划与有限物资分配问题,提出双目标模型:最小化基于吉尼系数的未满足需求不平等度以实现公平分配,同时最小化总运输时间以确保及时送达。采用ε-约束法处理双目标问题,通过推导最优解的数学性质,引入有效不等式,并设计了在给定路线下的最优分配算法。进一步开发了分支定价(B&P)算法以高效求解。在土耳其凡省地震真实数据及伊斯坦布尔卡特尔地区预测数据上的测试表明,该算法显著优于商业MIP求解器。双目标方法使援助分配不平等程度降低34%,且不牺牲效率。结果表明,在时间约束极宽松或极紧时,优先保障需求覆盖的字典序优化有效;而在中等时间限制下,必须采取均衡策略以避免不公平结果。

原文摘要 · Abstract (English)

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&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&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.

救灾物流分支定价公平分配

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。