《Safety Science》：Maritime search and rescue operations planning: A hybrid approach for multi-asset deconfliction and efficient resource allocation
编辑推荐：
针对海上搜救搜索规划的决策支持系统（如加拿大和美国现有的系统）可协助搜索任务协调员为失踪物体生成搜索计划。然而，由于这些系统依赖模拟来评估计划的成功概率，因此无法直接集成到传统的数学规划框架中。此外，现有工具，如加拿大高级搜索规划工具（CANSARP）中的规划
针对海上搜救搜索规划的决策支持系统（如加拿大和美国现有的系统）可协助搜索任务协调员为失踪物体生成搜索计划。然而，由于这些系统依赖模拟来评估计划的成功概率，因此无法直接集成到传统的数学规划框架中。此外，现有工具，如加拿大高级搜索规划工具（CANSARP）中的规划模块SAR Optimizer，缺乏强制执行某些作业约束的机制，并且不优化搜索资源数量和搜索持续时间。为解决这些局限，研究人员提出了一种混合优化框架，将搜索模拟器视为外部黑箱目标函数计算器。在该框架内，研究人员开发了强制搜索单元之间水平空间分离的模型，这是一项重要的作业安全约束。此外，研究人员将搜索持续时间作为决策变量引入，从而能够制定消耗更少搜索单元或缩短搜索时间的搜索计划。在现实场景上的数值实验表明，这种模拟与优化的混合集成不仅增强了安全性，还显著提高了效率，可能节省数百海里的飞行时间。
该研究发表于《Safety Science》，针对海上搜救（SAR）规划中模拟评估与数学优化难以结合的问题，提出并验证了一种模型与求解器融合的混合优化框架。
## 研究背景与问题
海上搜救（SAR）规划是决定稀缺搜救力量（如固定翼飞机、直升机、船舶）如何安全、高效定位失踪对象的关键环节。加拿大海岸警卫队（CCG）的SAR项目以100%挽救生命为目标，其联合救援协调中心管辖面积超过530万平方公里，需7×24小时运行。现有决策支持系统，如加拿大高级搜索规划工具（CANSARP）中的SAR Optimizer，通过蒙特卡洛模拟将失踪对象表示为大量离散粒子，并据此计算搜索计划的成功概率（POS）。然而，这种模拟型目标函数缺乏解析形式，无法直接纳入传统数学规划框架。同时，SAR Optimizer存在三个运行缺口：多架搜索单元在同一高度同时作业时，水平安全分区仍需人工完成；搜索单元数量和搜索时长被当作固定输入而非优化变量；搜索轨迹角度预先固定，不能随优化调整。因此，研究人员提出研究问题：如何在用模拟计算目标函数的同时，设计能够强制执行作业约束的数学模型？
## 研究内容与主要结论
研究人员提出了一种混合优化框架，将SAR Optimizer模拟器视为外部黑箱目标函数计算器，并用通用求解器替代原有启发式模块，以声明式模型描述问题、由求解器生成搜索矩形。研究人员构建了五个数学模型：M（固定努力量与固定角度）、MC（M加最小粒子覆盖约束）、ME（努力量为决策变量且可弃用搜索单元）、MEC（ME加粒子覆盖约束）、MECA（MEC加角度决策变量）。在18个由经验丰富的SAR任务协调员构建的加拿大真实场景实例上，研究人员比较了各模型的可行性、POS和努力量使用情况。结果表明，允许灵活搜索努力量并支持弃用不必要单元的模型ME在所有18个实例上均能产生可行解，而固定努力量模型M在7个实例上不可行。ME平均可节省数百海里的搜索飞行距离，显著提高资源效率，同时保持较高POS。研究还发现，增加角度决策变量和粒子覆盖约束会增加模型复杂度，在5分钟求解时限内反而降低中位POS；使用基于主成分分析（PCA）确定的固定漂移对齐角度，并通过后处理过滤空矩形，是更有效的建模策略。
## 关键技术与方法
研究人员采用模型-求解混合优化方法，将SAR Optimizer作为外部黑箱目标函数计算器，并选用支持黑箱外部函数、非线性约束和约束编程的Hexaly商用求解器。非重叠约束使用Python的shapely库实现，粒子覆盖判断采用射线法并由C语言实现以加速。实验基于18个由经验丰富的SAR任务协调员构建的加拿大真实场景实例，包括6种漂移文件（人员落水、救生筏、渔船、帆船等）和3种力量配置（4架固定翼、6架固定翼、3架直升机加3架固定翼），每个实例进行30次独立运行，主实验求解时限为5分钟。
## 研究结果
### 5.1 增加灵活努力量的影响
通过对比模型M与ME在18个实例上的30次5分钟运行结果，研究人员发现，模型ME在所有实例上均能找到可行解，而模型M在7个实例上无可行解，主要原因是固定努力量要求搜索矩形必须满足水平空间去冲突约束，但搜索环境空间有限，导致无法布置。模型ME允许求解器动态降低搜索时长或弃用部分搜索单元，从而恢复可行性。在3H3F Fishing Vessel和3H3F Life Raft1等较容易检测的实例中，两种模型均能达到接近99%以上的POS，但模型ME平均仅启用4.4和4.9个搜索单元（共6个），减少资源消耗。在所有模型M和ME均可行的实例上，模型ME使用的努力量均低于模型M，平均可节省数百海里飞行距离。延长求解时间至120分钟后，模型ME在多个实例上逐渐接近或超过模型M，表明更长的求解时间更有利于灵活努力量模型。
### 5.2 小结
研究人员以5分钟运行时间内达到最高POS为主要标准，以努力量使用效率为次要标准进行模型选择。模型M在能找到可行解的实例上往往获得较高的POS，但可行性较差；模型ME虽然在某些实例上因搜索空间增大导致5分钟内POS略低，但能在所有实例上保持可行性，并显著节约资源。增加灵活角度和最小粒子覆盖约束并未提升POS，反而因复杂度增加降低了中位POS。使用固定漂移对齐角度参数和后处理过滤空矩形，比在模型中直接加入粒子覆盖约束更有效。被弃用的搜索单元仍可保留，供后续任务或情况变化时重新分配。
## 讨论与结论
讨论部分指出，水平空间去冲突约束能够满足多机同时作业的安全需求，但与固定努力量组合时容易导致不可行；灵活努力量通过减少或弃用搜索单元有效解决了该问题。研究还讨论了封闭源代码商用求解器透明度有限、5分钟求解时限受硬件与实现影响、模型复杂度与求解质量存在权衡、非确定性求解过程可能带来法律可复现性问题，以及外部模拟器评估结果依赖SAR Optimizer内置假设等局限。
研究结论可概括为：该研究提出了一种将数学优化与模拟相结合的海上搜索规划模型-求解方法。通过开发五个模型，研究人员证明了使用数学规划为不同搜索对象和搜索单元类型生成可行搜索计划的能力，并增加了增强作业安全与资源效率的约束，从而满足了加拿大海岸警卫队在CANSARP的SAR Optimizer模块中目前尚不具备的关键需求。在18个现实加拿大SAR案例上的评估表明，海上搜索规划可以成功地表述为数学模型，而无需牺牲基于模拟的精确目标函数评估。研究同时揭示了模型细节与表达力之间的必要权衡：最复杂的模型MECA因计算开销增加并未持续优于简单模型；模型M在被迫协调固定努力量与严格水平空间去冲突时经常无法找到可行解。使用灵活努力量的模型ME成为最有前景的方案：其在所有18个实例上均实现可行性，并允许停用不必要的单元，最终通过节省数百海里的搜索努力量显著提高了资源效率。在5分钟求解时限内，这种灵活性有时导致平均POS低于固定努力量模型，但更长时间求解结果表明灵活努力量能在多个实例上产生更好方案。将通用求解器集成到海上决策支持系统具有双重优势：对开发者而言，它提供了灵活建模框架和稳健基准，可用于比较专门算法与先进优化求解器；对运行环境中的SAR任务协调员而言，它提供了尊重复杂安全约束且消除资源浪费的高质量搜索计划，确保每一个搜索努力单位都被有效使用，从而最大化救生行动的潜力。
