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

Pujun Zhang, Shan Liu, Jia Shi, Liying Chen, Shuiping Chen, Jiuchong Gao and Hai Jiang

Transportation Research Part E: Logistics and Transportation Review, 2023, vol. 176, issue C

Abstract: 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, we advance these methods as follows: (1) We generalize the two-step process to a divide-and-conquer framework. We 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. We 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, we 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 our link representations, our 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 our model show fewer deviations from the actual routes compared with state-of-the-art route planning algorithms.

Keywords: Route planning; Landmark routing; Divide-and-conquer; Transformer; Graph attention network (search for similar items in EconPapers)
Date: 2023
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S1366554523001643
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:transe:v:176:y:2023:i:c:s1366554523001643

Ordering information: This journal article can be ordered from
http://www.elsevier.com/wps/find/journaldescription.cws_home/600244/bibliographic
http://www.elsevier. ... 600244/bibliographic

DOI: 10.1016/j.tre.2023.103176

Access Statistics for this article

Transportation Research Part E: Logistics and Transportation Review is currently edited by W. Talley

More articles in Transportation Research Part E: Logistics and Transportation Review from Elsevier
Bibliographic data for series maintained by Catherine Liu ().