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

李梓杨; 陈鹏程; 于炯; 蒲勇霖; 何贞贞; 李雪; 郑世杰

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

您当前的位置：

首页 >

文章列表页 >

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

学术通信 | 更新时间：2024-06-06

- 面向大规模图数据的关键词覆盖最优路径规划方法
- Keyword-aware optimal route planning method for large-scale graph data
- 通信学报 2023年44卷第9期页码：205-217
- 作者机构：
  
  1. 新疆大学软件学院，新疆乌鲁木齐 830002
  2. 新疆大学信息科学与工程学院新疆乌鲁木齐 830017
  3. 南京信息工程大学软件学院，江苏南京 210044
- 作者简介：
  
  [ "李梓杨（1993- ），男，新疆乌鲁木齐人，博士，新疆大学副教授、硕士生导师，主要研究方向为大数据分析、机器学习" ]
  [ "陈鹏程（1998- ），男，河南正阳人，新疆大学硕士生，主要研究方向为图计算、路径规划" ]
  [ "于炯（1964- ），男，北京人，博士，新疆大学教授、博士生导师，主要研究方向为网格计算、并行计算、分布式系统" ]
  [ "蒲勇霖（1991- ），男，山东淄博人，博士，南京信息工程大学讲师，主要研究方向为边缘计算、绿色计算等" ]
  [ "何贞贞（1994- ），女，新疆乌鲁木齐人，新疆大学博士生，主要研究方向为图查询优化、深度学习等" ]
  [ "李雪（1996- ），女，江苏新沂人，新疆大学博士生，主要研究方向为深度学习、图像处理等" ]
  [ "郑世杰（1998- ），男，四川广安人，新疆大学硕士生，主要研究方向为增量学习、异常检测" ]
- 基金信息：
  
  国家自然科学基金资助项目(62262064);国家自然科学基金资助项目(62266043);国家自然科学基金资助项目(61966035);新疆维吾尔自治区重点研发计划基金资助项目(2022295358);新疆维吾尔自治区自然科学基金资助项目(2022D01C56);新疆大学博士研究生创新基金资助项目(XJU2022BS072)
- DOI：10.11959/j.issn.1000-436x.2023171
  中图分类号： TP391
- 网络首发：2023-09，
  
  纸质出版：2023-09-25
- 稿件说明：
移动端阅览
李梓杨, 陈鹏程, 于炯, 等. 面向大规模图数据的关键词覆盖最优路径规划方法[J]. 通信学报, 2023,44(9):205-217.

Ziyang LI, Pengcheng CHEN, Jiong YU, et al. Keyword-aware optimal route planning method for large-scale graph data[J]. Journal on Communications, 2023, 44(9): 205-217.
李梓杨, 陈鹏程, 于炯, 等. 面向大规模图数据的关键词覆盖最优路径规划方法[J]. 通信学报, 2023,44(9):205-217. DOI： 10.11959/j.issn.1000-436x.2023171.

Ziyang LI, Pengcheng CHEN, Jiong YU, et al. Keyword-aware optimal route planning method for large-scale graph data[J]. Journal on Communications, 2023, 44(9): 205-217. DOI： 10.11959/j.issn.1000-436x.2023171.

摘要

针对个性化自驾游路径规划中存在规划路径无法满足不同用户个性化需求的问题，提出了基于不同用户兴趣点的关键词覆盖最优路径规划方法。首先，建立路网信息预处理模型并通过路网信息预处理算法绘制路网信息查询图；其次，使用倒排索引算法根据用户设定的个性化需求对路网信息查询图进行剪枝，在减小大规模数据处理内存开销的同时提升了关键词覆盖最优路径规划方法的执行效率；最后，通过双向并行拓展方式的关键词覆盖最优路径拓展算法实现满足用户兴趣点的个性化旅游路径推荐。实验结果表明，关键词覆盖最优路径规划方法不仅实现了满足用户个性化需求的路径规划，而且通过剪枝和双向并行拓展的方式提高了方法的执行效率。

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.

关键词

Keywords

references

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 .

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 .

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 .

丛玉良 , 孙闻晞 , 薛科 , 等 . 基于改进的混合遗传算法的车联网任务卸载策略研究 [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 .

金鹏飞 , 牛保宁 , 张兴忠 . 高效的多关键词匹配最优路径查询算法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 .

刘蒙蒙 , 牛保宁 , 杨茸 . 关键词最优路径查询的分段拓展算法 [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 .

TANG Z Z , MA H Z . An overview of path planning algorithms [J ] . IOP Conference Series:Earth and Environmental Science , 2021 , 804 ( 2 ): 022024 .

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 .

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 .

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 .

THAMMACHANTUEK I , KETCHAM M . Path planning for autonomous mobile robots using multi-objective evolutionary particle swarm optimization [J ] . PLoS One , 2022 , 17 ( 8 ): e0271924 .

刘丽珏 , 罗舒宁 , 高琰 , 等 . 基于回溯蚁群-粒子群混合算法的多点路径规划 [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 .

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 .

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 .

郝晋瑶 , 牛保宁 , 康家兴 . 大规模路网图下关键词覆盖最优路径查询优化 [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 .

LIU M M , NIU B N , YANG R . A segmented parallel expansion algorithm for keyword-aware optimal route query [J ] . GeoInformatica , 2022 : 1 - 27 .

JIN P F . Research on efficient keyword-aware optimal route query processing method [D ] . Jinzhong:Taiyuan University of Technology , 2017 .

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 .

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 .

浏览量

643

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

自适应多阈值图像分割算法

基于用户需求的景点路线利益规划算法

基于动态规划的矿井无线再编程最优基站选址算法