野火扑救：计算复杂性、数学模型与实例基准
文章背景与核心概要
野火在全球范围内造成了巨大的经济损失和生态破坏，随着气候变化，极端火险天气的发生频率在许多地区呈上升趋势。为了有效减缓火势蔓延，科学合理地在时间和空间上分配扑救资源至关重要。本文研究了基于图论表示的地貌中，如何跨时间分配野火扑救资源这一计算与数学难题。
文章取得了三大核心突破：首先，在理论计算机科学方面，作者严格证明了野火扑救问题及其相关变体在平面图上具有强 NP 完全性（Strong NP-completeness），甚至在所有资源同时释放的极端情况下依然如此；其次，在算法建模方面，作者提出了一种全新的混合整数规划（MIP）公式，实现了最先进的性能，打破了以往认为 MIP 方法在该领域缺乏竞争力的传统认知；最后，针对现有数据集缺乏现实真实感和挑战性的痛点，作者基于 Rothermel 地表火蔓延物理模型开发了一个物理基础的实例生成器，为评估和测试各类扑救算法提供了严苛且科学的基准。
摘要 (Abstract)
野火在全球范围内造成重大损失，且许多地区的火险天气发生频率预计将进一步增加。我们研究了在基于图论表示的地貌中跨时间分配扑救资源以减缓火势蔓延的问题。我们的贡献涵盖理论和方法论两个方面。首先，我们证明了该问题及两个相关变体在平面图上具有强 NP 完全性，在全加权有向网格上其中两个问题也具备该性质。我们还证明了当所有资源同时释放时，该问题仍然是强 NP 完全的。其次，我们提出了一种新的混合整数规划（MIP）公式，获得了当前最先进的结果，这表明与先前的研究结论相反，MIP 仍然是一种极具竞争力的优化方法。第三，鉴于现有基准缺乏现实感和难度，我们引入了一个基于 Rothermel 地表火蔓延模型的物理基础实例 generator（实例生成器）。我们利用这些多样化的实例对现有文献中的算法进行了基准测试，明确了每种算法成功或失效的具体条件。
Wildfires cause major losses worldwide, and the frequency of fire-weather conditions is likely to increase in many regions. We study the allocation of suppression resources over time on a graph-based representation of a landscape to slow down fire propagation. Our contributions are theoretical and methodological. First, we prove strong NP-completeness on planar graphs for this problem and two related variants, and on full weighted directed grids for two of the three problems. We also show that this problem remains strongly NP-complete when all resources are released simultaneously. Second, we propose a new mixed-integer programming (MIP) formulation that obtains state-of-the-art results, showing that MIP is a competitive approach contrary to earlier findings. Third, showing that existing benchmarks lack realism and difficulty, we introduce a physics-grounded instance generator based on Rothermel's surface fire spread model. We use these diverse instances to benchmark the literature, identifying the specific conditions where each algorithm succeeds or fails.
文章元数据 (Article Metadata)
- arXiv ID: arXiv:2603.29865 [cs.CE]
- 学科分类: 计算工程、金融与科学 (
cs.CE); 人工智能 (cs.AI) - 作者: Gustavo Delazeri, Marcus Ritt
- 提交日期: 2026年1月17日（最后修订：2026年8月19日）
- DOI: 10.48550/arXiv.2603.29865
- arXiv ID: arXiv:2603.29865 [cs.CE]
- Subjects: Computational Engineering, Finance, and Science (
cs.CE); Artificial Intelligence (cs.AI)- Authors: Gustavo Delazeri, Marcus Ritt
- Submission Date: January 17, 2026 (Last revised: August 19, 2026)
- DOI: 10.48550/arXiv.2603.29865