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

doi:10.3778/j.issn.1002-8331.2109-0496

Abstract

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

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

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

PU Linfa, YANG Yajun, WANG Xin. Constrained Multi-Start Path Planning Algorithm on Large-Scale Graphs[J]. Computer Engineering and Applications, 2023, 59(6): 283-290.

普林发, 杨雅君, 王鑫. 大规模图上具有约束的多起点路径规划算法[J]. 计算机工程与应用, 2023, 59(6): 283-290.

References

[1] TONG Y X，ZENG Y X，ZHOU Z M，et al.A unified approach to route planning for shared mobility[J].Proceedings of the VLDB Endowment，2018，11（11）：1633-1646.
[2] YANG Y J，LI Z F，WANG X，et al.Finding the shortest path with vertex constraint over large graphs[J].Complexity，2019：8728245.
[3] LI Z F，YANG Y J，WANG X.Rule based shortest path query algorithm[J].Journal of Software，2019，30（3）：515-536.
[4] ZHENG L B，CHEN L，YE J P.Order dispatch in price-aware ridesharing[J].Proceedings of the VLDB Endowment，2018，11（8）：853-865.
[5] CHENG P，XIN H，CHEN L.Utility-aware ridesharing on road networks[C]//Proceedings of the 2017 ACM International Conference on Management of Data.USA：ACM，2017：1197-1210.
[6] GE E Q，XU J，XU M，et al.MCSS：a model for car-sharing system[C]//Proceedings of the Workshops of the EDBT/ICDT 2016 Joint Conference.France：EDBT，2016.
[7] HASSAN M S，AREF W G，ALY A M.Graph indexing for shortest-path finding over dynamic sub-graphs[C]//Proceedings of the 2016 ACM International Conference on Management of Data.USA：ACM，2016：1183-1197.
[8] SASAKI Y，ISHIKAWA Y，FUJIWARA Y，et al.Sequenced route query with semantic hierarchy[C]//Proceedings of 21st International Conference on Extending Database Technology.Austria：EDBT，2018：37-48.
[9] CHEN L，GAO Y J，LIU Z X，et al.PTRider.a price-and-time-aware ridesharing system[J].Proceedings of the VLDB Endowment，2018，11（12）：1938-1941.
[10] HUANG Y，BASTANI F，JIN R M，et al.Large scale real-time ridesharing with service guarnantee on road networks[J].Proceedings of the VLDB Endowment，2014，7（14）：2017-2028.
[11] ALJUBAYRIN S，QI J Z，JENSEN C S，et al.The safest path via safe zones[C]//Proceedings of the 31st IEEE International Conference on Data Engineering.South Korea：IEEE，2015：531-542.
[12] BAKALOV P，HOEL E G，HENG W L.Time dependent transportation network models[C]//Proceedings of the 31st IEEE International Conference on Data Engineering.South Korea：IEEE，2015：1364-1375.
[13] TA N，LI G L，ZHAO T Y，et al.An efficient ride-sharing framework for maximizing shared routes[C]//Proceedings of the 34th IEEE International Conference on Data Engineering.France：IEEE，2018：1795-1796.
[14] ZHENG B L，SU H，HUA W，et al.Efficient clue-based route search on road networks（extended abstract）[C]//Proceedings of the 34th IEEE International Conference on Data Engineering.France：IEEE，2018：1783-1784.
[15] BRILHANTE I R，DE MACêDO J A F，NARDINI F M，et al.Where shall we go today?：planning touristic tours with tripbuilder[C]//Proceedings of 22nd ACM International Conference on Information and Knowledge Management.USA：ACM，2013：757-762.
[16] HANSKNECHT C，JOORMANN I，STILLER S.Dynamic shortest paths methods for the time-dependent TSP[J].Algorithms，2021，14（1）：21.
[17] MONAKHOVA E A，ROMANOV A Y，LEZHNEV E V.Shortest path search algorithm in optimal two-dimensional circulant networks：implementation for networks-on-chip[J].IEEE Access，2020，8：215010-215019.
[18] SHAN X，MA J，GAO J，et al.A subgraph query method based on adjacent node features on large-scale label graphs[C]//International Conference on Web Information Systems and Applications.Cham：Springer，2019：226-238.