提出新模型与生成器，解决林火扑救资源分配难题
Wildfire Suppression: Complexity, Models, and Instances
- 基于图结构建模火势蔓延，证明问题强NP难
- 新混合整数规划法达当前最优，验证其有效性
- 用物理模型生成更真实测试实例，助算法评估
野火在全球造成重大损失，且许多地区火险天气频率可能上升。本文研究在基于图的景观表示上，随时间分配扑救资源以减缓火势蔓延的问题。贡献包括：首先，在平面图和全加权有向网格上证明该问题及两个相关变体为强NP完全；即使所有资源同时释放，问题仍保持强NP完全。其次，提出一种新的混合整数规划（MIP）公式，取得当前最优结果，表明MIP是有效方法，反驳了早期观点。第三，指出现有基准缺乏真实性和难度，提出基于Rothermel表面火势蔓延模型的物理驱动实例生成器。利用这些多样化实例对文献进行基准测试，识别各算法在不同条件下的优劣表现。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。