Journal of Frontiers of Computer Science and Technology ›› 2023, Vol. 17 ›› Issue (1): 116-126.DOI: 10.3778/j.issn.1673-9418.2105035

• Theory·Algorithm • Previous Articles     Next Articles

GCN Deep Search Method for Optimal Path of Dynamic Road Network

FEI Ke, QIN Xiaolin, CHI Heyu, LI Tang   

  1. College of Computer Science and Technology, Nanjing University of Aeronautics and Astronautics, Nanjing 211106, China
  • Online:2023-01-01 Published:2023-01-01

面向动态路网的最优路径GCN深度搜索方法

费珂,秦小麟,迟贺宇,李瑭   

  1. 南京航空航天大学 计算机科学与技术学院,南京 211106

Abstract: The optimal path search and planning in the road network has received widespread attention as an important part of location-based services (LBS). Positioning technologies such as radio frequency identification (RFID) have brought a lot of traffic data, which has become the foundation and challenge of research. Travel scenarios in cities are very sensitive to the dynamic changes of the road network. At the same time, the traffic situation in the city is complex and changeable, and the real road network and the trajectories of moving objects contain rich temporal and spatial semantic information. These are difficulties faced by the optimal route search in the road network. In response to these challenges, after analyzing the deficiencies of existing algorithms, a machine learning model GCN-Search based on graph convolutional networks for deep search is proposed, with reference to the heuristic idea of A* algorithm. Firstly, the model uses the spatio-temporal graph convolutional network to aggregate the spatio-temporal information of adjacent areas and past periods to model the recent dynamic changes of the road network on which urban travel depends. Secondly, the model expands the search depth, defines the depth evaluation value of the node, and uses a neural network to replace the artificially designed evaluation function to search for nodes that are conducive to the overall optimal path until the final path is generated. Comparative experiments on the RFID dataset provided by a traffic management bureau show that the GCN-Search algorithm can effectively use the temporal and spatial semantic information of RFID data, and can improve the accuracy of the optimal route search for short-term travel on the dynamic road network.

Key words: graph convolution, optimal path, A* algorithm, radio frequency identification (RFID), spatio-temporal graph convolution

摘要: 路网中的最优路径搜索与规划作为位置服务中重要部分受到广泛关注,射频识别技术(RFID)等技术带来的大量交通数据成为了研究的基础与挑战。城市中出行场景对路网动态变化非常敏感,同时城市复杂多变的交通情况、真实路网与移动对象轨迹丰富的时空语义信息,都是动态路网中的最优路径搜索面临的难题。针对这些挑战,在分析现有算法不足的基础上,参考A*算法启发式思想,提出一种基于图卷积网络进行深度搜索的机器学习模型GCN-Search。模型首先通过时空图卷积网络,聚合相邻区域与过往时段的时空信息,对城市出行所依赖的路网近期动态变化进行建模;其次扩展路径搜索的深度,定义节点的深度估价值,并使用神经网络替代人工设计的估价函数,搜索利于路径整体最优的节点,直到生成最终路径。在某交管局提供的RFID数据集上进行的对比实验表明,GCN-Search算法可以有效利用RFID数据中的时空语义信息,提升动态路网出行的最优路径搜索的准确率。

关键词: 图卷积, 最优路径, A*算法, 射频识别技术(RFID), 时空图卷积