arXiv:2411.16667v2 宣告类型: 更改交叉引用 摘要: 多目标最短路径(MOS)问题是在多属性图中从起始节点到目的地节点找到一组帕累托最优解。文献探讨了求解NP难MOS问题的多目标A*风格算法方法。这些方法使用一致启发式来计算目标节点的精确解集。广义MOS算法在每个节点维护一个"前沿"的部分路径，并进行有序处理以确保生成到达目标节点的帕累托最优路径。由于非支配路径的搜索空间急剧增加以及帕累托最优解的显著增加，随着目标数量的增加，该算法变得计算上不可行。虽然先前的工作集中在通过算法方法降低复杂性上，我们通过利用并行性来加速MOS问题。关键洞察是MOS算法依赖于有序执行部分路径以保持高工作效率。提出的并行算法(OPMOS)解锁了有序并行性，有效地利用了MOS中多路径的并发执行。通过使用NVIDIA GH200超级芯片的72核ARM CPU进行实证评估，证明了OPMOS在工作效率和并行性方面具有性能扩展的潜力，并使用实际应用进行了船舶航线规划。