在灾难响应的高风险世界中，时机往往是控制住事态与演变成灾难之间的分水岭。对于野火而言尤其如此，因为火的行为并非静态的，而是一个会随着被忽视而发生变化的、活生生的、呼吸着的实体。如果火灾没有得到立即处理，它并不仅仅是停留在原地；它会不断扩大规模，消耗更多价值，并最终蔓延到新的区域，从而产生需要关注的新紧急情况。这为前线的指挥官们制造了一个复杂的谜题：他们不仅必须决定将资源派往何处，还必须决定何时派遣，因为每一秒的延迟都会改变问题本身的景观。挑战在于，如何在扑灭当前火灾的紧迫需求与防止其点燃附近新火灾的战略必要性之间取得平衡，同时还要管理一支必须通过加油来维持工作的无人机机队。
一组研究人员通过开发一种全新的无人机森林消防调度与路径规划方法，解决了这一错综复杂的问题。他们的工作聚焦于一个特定且困难的现实：会引发新火灾的火灾。在他们的模型中，一场火灾始于特定位置，并有一个指定的熄灭时间窗口。如果火灾燃烧时间过长，它就会增长到临界规模，届时它会自然地蔓延到相邻区域，从而产生必须去扑救的新任务。目标不仅是扑灭最初的火焰，还要在足够早的时间进行干预，以阻止这种连锁反应，从而保护该地区土地、房屋和基础设施的价值。研究人员创建了一个数学框架，作为一个决策引擎，计算无人机机队的最佳路径，以实现整个森林区域内所能挽救价值的最大化。
研究人员使用一个模拟森林网格的计算机模型测试了他们的方法，其中每个方格代表一块具有自身价值和潜在火灾蔓延性的土地。他们在模型中设定，无人机在任务之间必须前往水源补充水箱，这增加了路径规划的另一层复杂性。在模拟实验中，他们引入了各种场景，包括不同数量的无人机、不同的飞行速度以及不同的初始火灾模式。他们发现，这种结合了精确计算与灵活、逐步优化过程的新方法，比以往的方法更快且更可靠。旧模型往往难以在合理的时间内找到最优解，尤其是在火灾数量较多时，而新方法总能快速找到高质量的方案。它成功地在“冲向最近的火场”与“等待以防止更具价值的区域被烧毁”之间的权衡中寻找到了平衡，确保无人机被部署在能挽救最多价值的地方。
为了证明其工作的实用性，该团队将模型应用于基于加利福尼亚多样化地形的现实场景。他们创建了代表不同地形类型的数字地图，从植被茂密的城市密集区到稀疏的无人区。在这些模拟中，模型成功引导无人机机队扑灭火灾，并防止其蔓延至关键区域。结果显示，通过使用这种优化的调度，受保护区域的总价值与缺乏协调的努力相比显著提高。研究人员还将他们的计算机代码向公众开放，允许其他专家使用自己的数据进行测试，并完善实际部署中的策略。这项工作为灾难管理者提供了一个切实的工具，使他们能够将野火这种混乱且蔓延的本质转化为一系列可控的决策，从而挽救生命与财产。
技术摘要：由退化触发的任务到达的调度与路径规划
问题定义
本文研究了一种新型的集成车辆路径问题（VRP）与作业调度问题（JSP）变体，称之为“由退化触发任务到达的调度与路径规划”。其核心挑战在于一个潜在的任务位置网络，其中新任务并非随机出现，而是由现有任务的退化动态触发。
在无人机（UAV）空中森林灭火这一特定背景下，该问题被定义如下：
- 网络结构： 一个基于网格的图，代表包含易燃节点、防火节点（屏障）、水源和无人机基地的森林区域。
- 任务动态： 每个着火区域（任务）都有指定的时窗。在此期间，火势增长（规模退化），且该节点的价值发生退化。
- 退化触发的到达： 如果火灾在达到临界规模阈值（tm）之前未被扑灭，它会蔓延到相邻节点，从而触发新的任务到达。这产生了一种双向交互作用：路径规划和调度决策决定了火灾蔓延的时间（以及随之而来的新任务到达时间），而新任务的到达又会影响后续的路径规划决策。
- 目标： 最大化区域的总剩余价值。这涉及在火灾导致总价值损失之前进行扑灭，并防止火灾蔓延至高价值相邻节点。模型考虑了无人机的约束条件，包括在任务之间需要前往水资源点补充水箱，以及无论火灾大小都必须释放满载水量的要求。
方法论
作者开发了一个由两个主要模型组成的数学优化框架：
精确混合整数规划模型 (EM)：
- EM 使用二进制变量处理车辆路径、任务选择和火灾蔓延逻辑，并使用连续变量处理时间和价值。
- 它采用了火灾规模增长和价值退化的线性近似，以平衡现实性与计算可处理性。
- 该模型明确地将调度决策（到达时间）与火灾演进逻辑联系起来。它使用“大 M”（Big-M）约束来模拟基于以下条件的四种不同火灾蔓延情况：节点是否有火、是否有车辆到达，以及到达时间相对于火灾临界增长阶段的时机。
- 目标函数旨在最大化收集到的节点价值，并对返回基地的耗时进行惩罚。
混合模型：精确模型引导的延迟补给模型 (E-RDM)：
- 意识到 EM 由于线性规划（LP）松弛较弱以及水资源补给约束的复杂性而在可扩展性方面存在困难，作者提出了一种混合方法。
- 延迟补给 EM (RDM)： 这是 EM 的一个松弛版本，省略了要求在连续任务之间访问水资源以及相关的时序耦合约束。
- 带有延迟约束的分支切割法： E-RDM 算法首先求解 RDM 以生成高质量的可行解。然后，它采用带有延迟约束回调的分支切割框架。如果解违反了被省略的水资源补给或时序耦合约束，则动态添加相应的约束作为切割（cuts）。
- 两阶段策略： 算法将总时间限制的一部分分配给求解完整的 EM（以便尽可能快速地找到最优解），其余部分则分配给带有动态约束生成的 RDM（以提高边界并处理更大规模的实例）。
主要贡献
论文确定了三个主要贡献：
- 理论进展： 它将“退化触发任务到达”的概念引入了调度与路径规划文献。与任务到达是随机或独立的标准动态 VRP 不同，该模型具有双向交互作用，即决策直接影响新任务的到达。
- 灾害管理应用： 它提供了一个规范性的决策模型用于空中森林灭火。该模型集成了物流（路径、补给）与运营规划（火灾扑灭时机），以解决野火场景中的“资产保护问题”（APP）。
- 可复现性与工具化： 作者开发了一个与 Python/Gurobi 代码库相连的软件接口（基于电子表格），允许从业者生成问题实例并寻找最优解，而无需直接操作原始代码。代码库通过 GitHub 分享，以促进研究的可复现性。
结果
计算实验是在一台配备 2 核、28 线程的工作站上使用 Gurobi Optimizer 10.0.1 进行的。
- 性能比较： 混合 E-RDM 模型显著优于精确 EM 模型。由于在任务到达量高或机队容量有限的情况下，EM 经常无法在时限（3,600 秒）内证明最优性，而 E-RDM 在 1,260 次运行中始终保持了小于 3% 的最优间隙（optimality gap）。
- 可扩展性： E-RDM 在不同的机队规模（2 架 vs. 4 架无人机）和飞行速度（60 vs. 120 km/h）下均表现出鲁棒性。它求解实例的平均运行时间为 47 秒。
- 任务到达的影响： 研究证实，随着任务到达数量的增加（由初始火灾和蔓延速率驱动），EM 的计算难度急剧上升。E-RDM 通过利用松弛后的公式来引导搜索，有效地缓解了这一问题。
- 案例研究： 基于加州野火特征（使用 SILVIS 土地分类数据）的案例研究展示了该模型处理多样化景观的能力，涵盖了从高密度城市交界区到无人居住植被区。模型成功生成了能够最大化价值保留的扑灭计划，涵盖了七种不同的场景类型。
意义与主张
论文将自身工作定位为“防患于未然”这一格言的实际应用，强调早期、协调一致的干预可以防止不成比例的破坏。作者声称，通过显式建模扑灭延迟与新火灾任务（星火）生成之间的因果关系，其模型相比现有方法有了显著改进。
该研究并不声称解决了火灾行为的连续物理过程，而是通过使用线性近似来处理火灾蔓延和价值退化，从而在现实性与可处理性之间取得了平衡。其意义在于提供了一个决策支持系统，能够处理野火扑灭中动态且相互依赖的性质——在这种情况下，延迟单个任务可能会呈指数级增加工作量并减少受保护区域的总价值。作者总结道，他们的混合方法为解决此前在计算上难以处理的复杂现实世界灾害响应物流问题提供了一条可行路径。
每周获取最佳 computer science 论文。
受到斯坦福、剑桥和法国科学院研究人员的信赖。
请查收邮箱确认订阅。
出了点问题，再试一次？
无垃圾邮件，随时退订。