计算机工程与应用 ›› 2023, Vol. 59 ›› Issue (6): 283-290.DOI: 10.3778/j.issn.1002-8331.2109-0496

• 工程与应用 • 上一篇    下一篇

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

普林发,杨雅君,王鑫   

  1. 1.人民网传播内容认知国家重点实验室,北京 100733
    2.天津大学 智能与计算学部,天津 300350
    3.天津大学 国际工程师学院,天津 300350
  • 出版日期:2023-03-15 发布日期:2023-03-15

Constrained Multi-Start Path Planning Algorithm on Large-Scale Graphs

PU Linfa, YANG Yajun, WANG Xin   

  1. 1.State Key Laboratory of Communication Content Cognition, Beijing 100733, China
    2.College of Intelligence and Computing, Tianjin University, Tianjin 300350, China
    3.Tianjin International Engineering Institute, Tianjin University, Tianjin 300350, China
  • Online:2023-03-15 Published:2023-03-15

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

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

Abstract: Path planning query is a basic problem on graph data, which has important application value in many fields. Usually, the path queried in actual problems is constrained. For example, in the problems of food delivery and shared travel, the path has node constraints, and the path needs to meet the constraints of the sequence relationship between nodes. At present, for the path query problem with node constraints, most of the work is on the single-start node-constrained path query, but it is difficult to extend to the multi-start node constraint problem. Because the multi-start path query problem with node constraints is NP-hard, most of the existing methods for this problem use greedy incremental processing, but it is insufficient for processing static rule sets. Therefore, a heuristic algorithm based on sub-paths and an accurate algorithm based on constraint set expansion are proposed, and the effectiveness of the algorithm is verified on the real data set. The experimental show that the heuristic algorithm can give an accurate solution to the problem, and the heuristic algorithm can quickly give a better approximate solution.

Key words: graph data, path querying, optimization problem, heuristic algorithm