面向船舶路由的多目标路径规划智能搜索与自适应优化研究

《IEEE Journal of Oceanic Engineering》：Intelligent Search and Multiobjective Path Planning With Application to Ship Routing

本文针对船舶路由中多目标路径规划(MOSP)问题的计算复杂性和多目标冲突挑战，研究团队评估了四种新多目标A算法(NAMOA)的近似方法，包括两种动态校准参数的自适应策略。研究结果表明，结合机器学习动态选择近似方法可在86%的情况下满足时间限制，并获得比最差情况优三倍的解质量，为复杂海上导航问题提供了创新解决方案。

　　

在真实的船舶航行场景中，规划最优航线是一项极具复杂性的挑战。船舶路由需要考虑众多参数和经常相互冲突的目标，包括距离优化、气象和海洋学因素、燃油效率以及船舶响应特性等多重要求。这种多方面的路径规划问题属于多目标最短路径(MOSP)问题的范畴。传统的MOSP问题解决方法往往难以应对问题的复杂性和巨大的计算需求，特别是当目标数量增加时，计算复杂度呈指数级增长。

船舶航行中的多目标决策需要权衡各种竞争性目标，最佳权衡通常由人类决策者做出，因为他们能够理解上下文、借鉴经验和直觉、适应变化并管理风险。决策支持系统可以通过推荐来自非支配解帕累托前沿的多个行动方案来辅助这一过程，让决策者能够评估竞争选项，并根据对目标的偏好做出选择。

这项发表在《IEEE Journal of Oceanic Engineering》上的研究致力于解决船舶路由中的多目标最短路径问题，包含时间窗口约束和受海洋学参数影响的目标。目标可能包括燃油效率、运输时间、距离、安全性、资产疲劳、障碍物规避以及环境因素（如风浪等）。大量目标迅速将问题推向计算上难以处理的解空间， necessitating 使用近似技术。

为了解决这些限制，研究团队评估了四种新多目标A算法(NAMOA)的近似方法，包括两种新颖的方法，这些方法能够根据扩展的搜索空间动态校准其参数。研究人员还评估了非支配排序遗传算法-III(NSGA-III)，但总体上其性能被NAMOA*近似方法所超越。

评估表明，在解决方案质量（以世代距离(GD)和反向世代距离(IGD)的平均值衡量）以及运行时间方面，没有单一的近似方法在所有评估场景中 consistently 优于其他方法。为了应对这一限制，研究团队训练了一个机器学习模型，能够根据目标数量、特定海洋学条件以及用户定义的求解时间限制，动态选择最合适的近似方法和参数值。该机器学习模型在86%的情况下成功在时间限制内确定了合适的方法，并在51%的情况下获得了最佳解决方案。即使在时间限制内未获得最佳解决方案的情况下，所选方法提供的解决方案也比没有机器学习的最差情况优约三倍（以GD和IGD的平均值衡量）。

为了开展这项研究，研究人员采用了几个关键技术方法：首先，利用四叉树数据结构表示全球海洋的空间离散化，实现了不同地理区域的可变分辨率网格。其次，通过计算节点可行时间窗口来约束搜索空间，基于船舶速度限制和目的地到达时间要求。第三，开发了乌托邦点启发式函数，为多目标搜索提供可容许的启发式估计。第四，实现了四种NAMOA*近似方法，包括ε-支配、指数搜索空间划分以及两种自适应参数调整方法。最后，使用GD和IGD指标评估解质量，并训练随机森林分类器进行动态方法选择。

环境参数与目标函数

研究考虑了多达12个目标函数，包括距离、燃油消耗、船舶动态响应参数（横摇、纵摇、垂直加速度、水平加速度、垂直弯矩和垂直剪切力）以及海洋学参数（波高、波周期和相对波向）。这些目标函数基于欧洲中期天气预报中心再分析数据(ERA5)和船舶响应计算模型，考虑了平静水域所需的推进功率以及波浪引起的附加阻力。

四叉图表示与时间窗口

研究采用四叉树数据结构表示船舶路由图的空间组件，每个中间节点恰好有四个子节点。这种方法允许在不同地理区域实现可变分辨率的离散化——在靠近海岸线的区域需要更密集的节点，而在公海则可以使用较少的节点。通过计算每个节点的最早和最晚可行到达时间，进一步约束了状态空间，确保了船舶能够在指定时间窗口内到达目的地。

多目标搜索算法与近似方法

NAMOA*算法通过选择最佳路径进行扩展，使用一组启发式评估函数(HEFs)来指导搜索过程。研究人员评估了四种近似技术：ε-支配、指数搜索空间划分以及两种自适应参数调整方法。这些方法通过放松支配条件来减少需要维护的帕累托解数量，从而降低计算复杂度。自适应方法根据待扩展节点集的大小动态调整近似参数，在解质量和计算时间之间实现智能权衡。

评估指标与 bargaining 解决方案

为了评估不同近似方法的性能，研究使用了世代距离(GD)和反向世代距离(IGD)指标，分别衡量从近似解到最近精确解的平均距离和从精确解到最近近似解的平均距离。此外，研究还探讨了四种 bargaining 解决方案（平等主义解决方案、Kalai-Smorodinsky解决方案、纳什解决方案和妥协解决方案），为决策者从帕累托前沿中选择特定解提供系统方法。

结果分析与机器学习模型

实验结果表明，阿拉斯加到西雅图路线是唯一能够在1小时时间限制内完成所有近似方法的路线，而圣地亚哥到巴拿马路线则具有更多的帕累托最优解。自适应方法通常比非自适应方法完成得更快，特别是自适应ε支配方法，但解质量相对较差。研究人员训练的随机森林分类器能够根据目标数量、时间限制、最短路径距离和天气参数协方差矩阵的行列式等特征，动态预测最佳近似方法和参数值。该模型在满足计算时间约束方面 consistently 表现优异，在几乎所有情况下都能在时间限制内完成，同时提供高质量的解决方案。

路线可视化与选择

对于多目标情况下的路径可视化，研究使用平行坐标图展示帕累托前沿，每个路线表示为连接多个垂直轴上的点的线，每个轴代表一个目标函数。通过将目标函数值归一化到0-1范围内，所有路线可以在同一尺度上进行比较。研究还突出了帕累托 bargaining 解决方案，如独裁解决方案、平等主义解决方案、Kalai-Smorodinsky解决方案、纳什解决方案和妥协解决方案，为决策者提供有意义的参考点。

研究结论表明，结合自适应近似方法与机器学习技术，能够有效解决海上导航中复杂的多目标优化问题。这种方法不仅显著提高了船舶路由的决策支持能力，还为各种路径规划场景（如空中车辆、水面舰艇、潜水平台和地面车辆）提供了广泛的应用潜力。未来研究方向包括进一步提高NAMOA*算法的计算效率、开发并行处理实现、探索上下文多臂赌博机公式进行实时算法选择，以及研究考虑天气波动、障碍物和资产状态变化的鲁棒多目标路径规划方法。

这项研究的创新之处在于将自适应近似算法与机器学习智能选择相结合，为复杂环境下的多目标路径规划提供了实用且高效的解决方案框架，对提高海上航行的安全性、经济性和环保性具有重要意义。