Route planning using divide-and-conquer: A GAT enhanced insertion transformer approach

Route planning is widely used in areas such as car navigation. For some popular mobility services such as meal delivery and online car-hailing, planning routes that closely follow drivers’ actual routes is important. Some existing methods propose that drivers plan routes in two steps: first identify intermediate waypoints on the route that connects the origin and destination; then find a series of sub-routes between successive waypoints, respectively. In this research, the authors advance these methods as follows: (1) They generalize the two-step process to a divide-and-conquer framework. They first identify intermediate waypoints between the origin and the destination and decompose the route planning problem into several sub-problems, whose intermediate waypoints are identified again. They recursively repeat this process until no more waypoints are identified for all the sub-problems; and (2) Unlike existing studies that identify waypoints solely based on the travel frequency of links, they propose a Graph Attention Network (GAT) Enhanced Insertion Transformer (GEIT) model for waypoint identification. GEIT model uses an Insertion Transformer to learn the relationship among links, which can better capture the mobility pattern embedded in historical routes. In addition, by incorporating a GAT to enhance their link representations, their model spreads the learned information along the road network to address the trajectory sparseness problem. Numerical experiments on a real-world trajectory data set demonstrate that the routes planned by their model show fewer deviations from the actual routes compared with state-of-the-art route planning algorithms.


  • English

Media Info

Subject/Index Terms

Filing Info

  • Accession Number: 01886533
  • Record Type: Publication
  • Files: TRIS
  • Created Date: Jun 28 2023 4:57PM