Learning Route With Graph Neural Network Based On Trajectory

With the widespread application of vehicle GPS equipment,more and more trajectory data are becoming available.Learning the driver's routing preferences from trajectory data and conducting trajectory-based route planning have become a hot research topic.Traditional research that directly recommends the most popular route suffers from the highly sparsity and non-uniformity of trajectory data.Furthermore,traditional research uses trajectory data to build a weighted graph and then obtains routes using classic graph theory-based search algorithms,which has difficulty in estimating multiple preferences.Recently,a study has utilized GNN(Graph Neural Network),transforming the shortest path problem to a classification problem,i.e.,given arbitrary source and destination pair to determine whether each node or edge is on the shortest path.This paper intends to use GNN's non-linear feature representation ability and multiple feature fusion ability to improve trajectory-based route planning.However,in large road networks,the severe sparsity and spatiotemporal inhomogeneity of the actual trajectory data lead to a serious shortage of sample size,exacerbating the severe imbalance of positive and negative classes,which brings challenges to learning trajectory routing with GNN.Based on the feature analysis of trajectory data,this paper proposes an LSTM-GN model that introduces a Long-Short-Term Memory network(LSTM)to extend the depth of the GNN,thereby enhancing the fusion and diffusion of multi-level trajectory feature information and overcoming the sparseness and imbalance to achieve effective few-shot learning.This paper further utilizes the real-world trajectory data to demonstrate the effectiveness and generalization ability of the proposed algorithm.The main contributions are as follows.(1)In this paper,data processing and data mining are carried out on map data and trajectory data.This paper builds a road network for route planning based on map data.This paper maps the raw trajectory to the road network,and then performs trajectory data mining from multiple dimensions to find features that reflect the user's preference for routing.And this paper utilizes the Dijkstra routing algorithm to evaluate the effectiveness of different features on routing.(2)This paper proposes a graph neural network model called LSTM-GN to learn driver's routing rules.In order to solve the problems of trajectory sparsity and spatio temporal inhomogeneity,a deep LSTM-style stacked GN message passing module is introduced to enhance the feature fusion and transferring,thereby realizing few-shot routing learning based on fewer trajectory data.In order to solve the imbalance between positive and negative classes,a dynamic weighted loss function is designed to strengthen the positive class,and the subgraph filtering algorithms are proposed to indirectly implement negative class downsampling.(3)In this paper,experiments based on real-world trajectory dataset demonstrates the performance of the LSTM-GN algorithm.LSTM-GN learns trajectory routing with nodelevel features,edge-level features and graph-level features from fewer trajectory samples(less than 10,000),supporting End-to-End route planning in road networks.The experimental results prove the effectiveness of the model.The F1-score and Trajectory Acceptance Ratio of LSTM-GN are higher than those of the model using shortest path algorithm(baseline using graph theory algorithm)by 33.25% and 61.61%.The F1-score and Trajectory Acceptance Ratio of LSTM-GN are higher than those of RGN(baseline using deep learning algorithm)by 18.82% and 20.42%.19 figures,16 tables,72 references.