在紧急服务中协调道路修复和物资分配：一种具有分布鲁棒性的优化方法

《European Journal of Operational Research》：Coordinating road recovery and supply distribution in emergency services: A distributionally robust optimisation approach

该研究针对灾害后道路修复与物资分配的协同优化问题，提出基于分布鲁棒优化（DRO）的模型，通过ε约束方法分解为多团队调度和物资分配两个子问题，并采用自适应大邻域搜索结合商业求解器进行高效求解。实验验证了DRO方法在不确定条件下的鲁棒性优势及资源投入的边际效益递减规律。

　　

白秦阳|周晨豪|任轩|杨振|周志立

西安交通大学，中国陕西省西安市西安宁西路28号，710049

摘要

当灾难发生时，道路网络的连通性往往会受到严重破坏，阻碍了救援物资的分配。在这种情况下，协调不力不仅会浪费有限的救援资源，还会加剧危机，对受灾人群造成更大的伤害。因此，道路恢复和物资分配的调度是相互依存的，在启动救援任务之前需要周密规划。在本研究中，我们解决了这个规划层面的优化问题，即在不确定性条件下，通过协调道路恢复和救援物资分配来最小化分配时间和救援物资的短缺。鉴于灾后关于供需和恢复能力的有限信息，以及道路网络连通性可能的变化，我们开发了一个分布式鲁棒优化（DRO）模型，并采用ε约束方法将DRO模型转化为两个子问题。第一个子问题规划维修队伍的调度和路线安排，同时制定相应的物资分配计划；第二个子问题进一步确定救援物资的分配方案。我们提出了一个计算上可行的模型重构方法，并开发了一种结合自适应大邻域搜索（ALNS）和商业求解器的数学启发式算法。广泛的实验验证了DRO方法的鲁棒性、集成优化的优越性、目标之间的权衡，以及增加救援资源所带来的边际效益递减现象。

引言

近年来，全球自然灾害的频率急剧增加，导致大量人员伤亡和财产损失。仅2000年至2019年间，就记录了7348起灾害，影响了42亿人，造成估计的全球经济损失达2.97万亿美元（Akbari & Sayarshad, 2022）。地震、洪水、台风和山体滑坡等灾害尤其具有破坏性，常常使基础设施（包括道路、桥梁和隧道）瘫痪，从而阻碍救援工作并延迟关键救援物资的分配。然而，受灾地区的伤亡可能并非直接由灾害造成，而是由于救援物资（如药品、食物、水和衣物）的延迟或无效配送所致。及时配送这些物资对于灾后挽救生命至关重要（Wang, Yang, Yang, & Gao, 2023）。例如，2013年海燕台风造成了广泛的基础设施破坏，导致救援行动和关键物资分配严重延误，由于缺乏必要的资源而造成了大量人员伤亡（Kundu, Sheu, & Kuo, 2022）。

如图1(a)所示，交通基础设施的恢复与救援物资的分配之间存在密切关联。一些地区只有在受损的基础设施（特别是道路网络）得到修复后才能通行，这凸显了将道路网络恢复优化与救援物资分配相结合的重要性。现有文献（Akbari, Sayarshad, 2022, Briskorn, Kimms, Olschok, 2020, Duque, Dolinskaya, S?rensen, 2016, Lakzaei, Rahmani, Tosarkani, Nasiri, 2023, Moreno, Munari, Alem, 2020b）已经探讨了救援物资分配与道路网络恢复的集成优化问题。然而，由于修复能力有限，往往无法同时修复所有受损设施。Akbari & Sayarshad (2022)、Duque等人（2016）、Lakzaei等人（2023）以及Shin, Kim, & Moon (2019)在假设只有一个维修队伍的情况下的模型在实践中应用性较低，因为实际情况通常是会派遣多个维修队伍尽快恢复基础设施。这一限制强调了有效协调修复和分配工作的必要性（Lakzaei, Rahmani, Tosarkani, Nasiri, 2023, Moreno, Munari, Alem, 2019）。

本研究解决了一个规划层面的优化问题，即在启动救援任务之前，协调多个维修队伍和物资分配队伍的调度，以最小化分配时间和救援物资的短缺。物资分配队伍能否到达受灾地区取决于连接道路的修复情况，因此维修队伍的调度是一个关键因素，它决定了每个受灾地区何时能够通行，从而决定了物资分配的路线。

实际上，虽然灾后可以迅速确定受损道路段和受影响需求节点的位置，但对物资的实际需求和道路损坏程度的评估只能粗略进行，这给恢复时间和物资需求带来了很大的不确定性。一些研究使用了随机规划（SP）（Ya?a, Aksu, & ?zdamar, 2022）、动态规划（DP）（Akbari & Sayarshad, 2022）或在线优化（Akbari & Shiri, 2022）来处理这些不确定性。对于规划而言，SP和DP通常依赖于不确定参数的精确概率分布，但任何地区的灾害发生频率都不高，且每次灾害都具有独特性，导致观测数据稀少，相应的概率分布难以估计。在线优化适用于在信息不完全的情况下进行操作层面决策，其中道路障碍在救援行动进行过程中逐渐显现（Akbari & Shiri, 2022）。在我们的研究中，灾后可以迅速知道受损道路段和需求节点的位置，但需求水平和恢复时间（以修复时间为单位）仍然不确定。因此，我们采用了分布式鲁棒优化（DRO）方法，该方法非常适合在数据不确定性和历史数据有限的情况下进行规划决策。

因此，我们的贡献如下：

1

本研究解决了多个维修队伍和物资分配队伍的集成规划问题，以最小化分配时间和救援物资的短缺。为了应对修复时间和救援需求的不确定性，我们构建了一个双目标DRO模型。

2

采用ε约束方法将DRO模型转化为两个子问题。我们利用模糊集的结构提出了一个计算上可行的模型重构方法，并开发了一种结合自适应大邻域搜索（ALNS）和商业求解器的数学启发式算法来解决问题。

3

广泛的数值实验验证了所提出的DRO方法的鲁棒性，并证明了将道路恢复与物资分配相结合的优越性。同时进一步揭示了两个目标之间的关系，并强调了增加维修队伍和物资分配队伍的边际效益递减现象。

本研究的其余部分安排如下：第2节概述了相关研究并讨论了研究空白；第3节介绍了双目标DRO模型；第4节介绍了解决方法；第5节进行了数值实验；最后，第6节讨论了结论和未来的扩展方向。

文献综述

灾难发生后，道路网络的连通性和可通行性对物资分配有重大影响，这引发了大量关于道路网络恢复和物资分配挑战的研究。本节从三个方面简要回顾了现有文献：第2.1节讨论了道路恢复，第2.2节讨论了物资分配，第2.3节重点讨论了道路网络恢复与物资分配的整合。

问题描述与建模

灾难发生时，紧急救援机构会同时开展道路网络恢复和救援物资分配工作。然而，由于灾难的不可预测性和救援工作的紧迫性，受灾地区的需求以及道路网络损坏的程度仍然存在不确定性。为了避免因协调不力而浪费救援资源，因此在资源投入现场之前制定更好的计划至关重要。

解决方法

根据模型中的两个目标函数（方程3.3和方程4.3），我们首先使用ε约束方法将问题转化为两个子问题，即P1和P2。ε约束方法对于获取双目标问题的帕累托前沿非常有效（Curtis, Liu, Robinson, 2024, Govindan, Salehian, Kian, Hosseini, Mina, 2023）。通过将一个目标视为由一组ε向量界定的额外不等式约束集，ε约束方法可以有效地处理这个问题。

数值实验

在本节中，我们评估了所提出模型的性能和解决方法。具体来说，我们在第5.1节生成了八个不同规模的实例，并定义了相应的模糊集。然后我们在第5.2节评估了DRO方法所得决策的鲁棒性，并评估了将道路恢复与物资分配相结合的好处。接下来，我们分析了两个目标之间的关系以及改变维修队伍数量的影响。

结论

本研究探讨了一个规划层面的优化问题，涉及灾后救援行动，重点关注道路恢复和救援物资分配。为了解决修复活动和物资需求的不可预测性，我们提出了一种DRO方法，以最小化救援物资的分配时间和短缺。我们采用ε约束方法将原始问题分解为两个子问题，包括维修队伍的调度和路线安排。

利益冲突声明

作者未报告任何潜在的利益冲突。

CRediT作者贡献声明

白秦阳：撰写 – 审稿与编辑、撰写 – 原稿、验证、软件开发、方法论研究、数据分析、概念构建。周晨豪：撰写 – 审稿与编辑、撰写 – 原稿、可视化、验证、监督、方法论研究、资金获取、数据分析、概念构建。任轩：撰写 – 审稿与编辑、方法论研究、数据分析。杨振：数据分析、数据分析。周志立：监督、资源协调。