大规模图上具有约束的多起点路径规划算法

来源：计算机工程与应用杂志2023年第6期北京时间：

作者：普林发, 杨雅君, 王鑫

单位：1.人民网传播内容认知国家重点实验室，北京 100733；2.天津大学 智能与计算学部，天津 300350；3.天津大学 国际工程师学院，天津 300350

摘要：路径规划查询是图数据上的一个基本问题，在众多的领域都有重要的应用价值。通常在实际问题中查询的路径是具有约束的，例如在外卖配送和共享出行问题中路径具有节点约束，其路径需要满足节点之间的先后关系约束。目前对于具有节点约束的路径查询问题，大多数的工作都在研究单起点的节点约束路径查询，但很难拓展到多起点节点约束问题中。因为具有节点约束的多起点路径查询问题是NP-hard的，所以该问题的大多数已有方法是使用贪心增量处理，但对于处理静态规则集拓展性不足。因此，提出了基于子路径的启发式算法和基于约束集拓展的精确算法，并在真实数据集上验证了算法的有效性。实验结果表明，启发式算法能够给出问题的精确解，而启发式算法能快速给出较好的近似解。

关键词：图数据,路径查询,最优化问题,启发式算法