面向大规模图数据的关键词覆盖最优路径规划方法

doi:10.11959/j.issn.1000-436x.2023171

Abstract

Abstract:

Focused on the problem that the planned routes cannot meet the personalized demand of different users in route planning of personalized self-driving tour, a keyword-aware optimal route planning method based on different user interests was proposed.Firstly, the road network information preprocessing model was set up and the road network information query graph was built by the road network information preprocessing algorithm.Secondly, the inverted index algorithm was proposed to prune the road network information query graph according to the personalized requirements from users, which improved the execution efficiency of keyword-aware optimal route planning method and reduced the memory cost of large-scale data processing effectively.Finally, the keyword-aware optimal route planning algorithm was proposed to realize personalized recommendation according to user interest by bidirectional parallel extension.The experimental results show that the method not only realizes the route planning to meet the individual needs of users but also improves the execution efficiency of the method through pruning and bidirectional parallel extension.

Key words: graph data, route planning, dynamic programming, inverted index algorithm, bidirectional parallel extension

CLC Number:

TP391

Ziyang LI, Pengcheng CHEN, Jiong YU, Yonglin PU, Zhenzhen HE, Xue LI, Shijie ZHENG. Keyword-aware optimal route planning method for large-scale graph data[J]. Journal on Communications, 2023, 44(9): 205-217.

Figures/Tables 15

References 19

[1]	ZHANG H F , GE H W , YANG J L ,et al. Review of vehicle routing problems:models,classification and solving algorithms[J]. Archives of Computational Methods in Engineering, 2022,29(1): 195-221.
[2]	FENG Y , WANG H , LU H ,et al. A novel faster all-pair shortest path algorithm based on the matrix mul-tiplication for GPUs[J]. arXiv Preprint,arXiv:2208.04514, 2022.
[3]	HUANG T , GONG Y J , ZHANG Y H ,et al. Automatic planning of multiple itineraries:a niching genetic evolution approach[J]. IEEE Transactions on Intelligent Transportation Systems, 2020,21(10): 4225-4240.
[4]	丛玉良, 孙闻晞, 薛科 ,等. 基于改进的混合遗传算法的车联网任务卸载策略研究[J]. 通信学报, 2022,43(10): 77-85.
	CONG Y L , SUN W X , XUE K ,et al. Research on task offloading strategy of Internet of vehicles based on improved hybrid genetic algorithm[J]. Journal on Communications, 2022,43(10): 77-85.
[5]	金鹏飞, 牛保宁, 张兴忠 . 高效的多关键词匹配最优路径查询算法KSRG[J]. 计算机应用, 2017,37(2): 352-359.
	JIN P F , NIU B N , ZHANG X Z . KSRG:an efficient optimal route query algorithm for multi-keyword coverage[J]. Journal of Computer Applications, 2017,37(2): 352-359.
[6]	刘蒙蒙, 牛保宁, 杨茸 . 关键词最优路径查询的分段拓展算法[J]. 计算机工程, 2022,48(6): 79-88.
	LIU M M , NIU B N , YANG R . Segmentation expansion algorithm for keyword-aware optimal route query[J]. Computer Engineering, 2022,48(6): 79-88.
[7]	TANG Z Z , MA H Z . An overview of path planning algorithms[J]. IOP Conference Series:Earth and Environmental Science, 2021,804(2): 022024.
[8]	WANG S , LIU B , LIU W P ,et al. Research on the shortest path for crossing desert based on Floyd algorithm[C]// Proceedings of 2021 IEEE 3rd International Conference on Frontiers Technology of Information and Computer (ICFTIC). Piscataway:IEEE Press, 2021: 1-4.
[9]	JU C Y , LUO Q H , YAN X Z . Path planning using an improved A-star algorithm[C]// Proceedings of 2020 11th International Conference on Prognostics and System Health Management (PHM-2020 Jinan). Piscataway:IEEE Press, 2020: 23-26.
[10]	LIU R , FENG F . Optimization model of pipeline laying based on immune genetics and improved second-order prim algorithm[C]// Proceedings of 2021 International Conference on Communications,Information System and Computer Engineering (CISCE). Piscataway:IEEE Press, 2021: 620-626.
[11]	THAMMACHANTUEK I , KETCHAM M . Path planning for autonomous mobile robots using multi-objective evolutionary particle swarm optimization[J]. PLoS One, 2022,17(8): e0271924.
[12]	刘丽珏, 罗舒宁, 高琰 ,等. 基于回溯蚁群-粒子群混合算法的多点路径规划[J]. 通信学报, 2019,40(2): 102-110.
	LIU L J , LUO S N , GAO Y ,et al. Multi-point path planning based on the algorithm of colony-particle swarm optimization[J]. Journal on Communications, 2019,40(2): 102-110.
[13]	LIU L S , WANG B , XU H . Research on path-planning algorithm integrating optimization A-star algorithm and artificial potential field method[J]. Electronics, 2022,11(22): 3660.
[14]	ATTIQUE M , AFZAL M , ALI F ,et al. Geo-social top-k and skyline keyword queries on road networks[J]. Sensors, 2020,20(3): 798.
[15]	郝晋瑶, 牛保宁, 康家兴 . 大规模路网图下关键词覆盖最优路径查询优化[J]. 软件学报, 2020,31(8): 2543-2556.
	HAO J Y , NIU B N , KANG J X . Optimization of keyword-aware optimal route query on large-scale road networks[J]. Journal of Software, 2020,31(8): 2543-2556.
[16]	LIU M M , NIU B N , YANG R . A segmented parallel expansion algorithm for keyword-aware optimal route query[J]. GeoInformatica, 2022: 1-27.
[17]	JIN P F . Research on efficient keyword-aware optimal route query processing method[D]. Jinzhong:Taiyuan University of Technology, 2017.
[18]	LI X T , HUANG T P , CHEN H H ,et al. Path planning of mobile robot based on dynamic chaotic ant colony optimization algorithm[C]// Proceedings of 2022 IEEE 10th International Conference on Information,Communication and Networks (ICICN). Piscataway:IEEE Press, 2023: 515-519.
[19]	YUAN D C . Research on path-planning of particle swarm optimization based on distance penalty[C]// Proceedings of 2021 2nd International Conference on Computing and Data Science (CDS). Piscataway:IEEE Press, 2021: 149-153.

Metrics

Recommended 0

No Suggested Reading articles found!

关键词	包含关键词顶点集
K₁	v₅
K₂	v₃
K₃	v₄,v₁
K₄	v₂,v₆,v₇

环境	类别	描述
硬件	CPU	Intel(R) Xeon(R) Gold 5117 CPU @ 2.00 GHz
	内存	256 GB
软件	数据库	PostgreSQL
	编译环境	IntelliJ IDEA2020
	辅助软件	QGIS 3.26.1

路网信息图	顶点数/10³个	边数/10³条	顶点平均关键词数
G₁	230	230	6.81
G₂	2 142	2 670	7.16
G₃	2 670	3 544	7.59
G₄	3 242	4 218	7.4

Keyword-aware optimal route planning method for large-scale graph data

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 15

References 19

Related Articles 2

Metrics

Recommended 0

[1]	Nan WANG,Honglei ZHOU,Jinbao LI,Lingli LI. Algorithm for scenario benefit route planning based on user’s requests [J]. Journal on Communications, 2018, 39(5): 189-198.
[2]	Jiang-hong HAN,Zhang-ling DUAN,Xing WEI,Yang LU,Jian-jun ZHANG. Optimal base station selection based on dynamic programming for reprogramming in mine wireless network [J]. Journal on Communications, 2017, 38(3): 7-15.