Trajectory-aware lowest-cost path selection: A summary of results

Yan Li, Pratik Kotwal, Pengyue Wang, Shashi Shekhar, William Northrop

Research output: Chapter in Book/Report/Conference proceedingConference contribution


The trajectory-aware lowest-cost path selection problem aims to find the lowest-cost path using trajectory data. Trajectory data is valuable since it carries information about travel cost along paths, and also reflects travelers' routing preference. Path-centric travel cost estimation models using trajectory data grows popular recently, which considers the auto-correlation of the energy consumption on different segments of a path. However, path-centric models are more computationally expensive than edge-centric models. The main challenge of this problem is that the travel cost of every candidate path explored during the process of searching for the lowest-cost path need to be estimated, resulting in high computational cost. The current path selection algorithms that use path-centric cost estimation models still follow the pattern of “path + edge” when exploring candidate paths, which may result in redundant computation. We introduce a trajectory-aware graph model in which each node is a maximal trajectory-aware path. Two nodes in the trajectory-aware graph are linked by an edge if their union forms a trajectory-union path. We then propose a path selection algorithm to find a path in the proposed trajectory-aware graph which corresponds to the lowest-cost path in the input spatial network. We prove theoretically the proposed algorithm is correct and complete. Moreover, we prove theoretically that the proposed path selection algorithm cost much less computational time than the algorithm used in the related work, and validate it through experiments using real-world trajectory data.

Original languageEnglish (US)
Title of host publicationProceedings of the 16th International Symposium on Spatial and Temporal Databases, SSTD 2019
PublisherAssociation for Computing Machinery
Number of pages9
ISBN (Electronic)9781450362801
StatePublished - Aug 19 2019
Event16th International Symposium on Spatial and Temporal Databases, SSTD 2019 - Vienna, Austria
Duration: Aug 19 2019Aug 21 2019

Publication series

NameACM International Conference Proceeding Series


Conference16th International Symposium on Spatial and Temporal Databases, SSTD 2019

Bibliographical note

Funding Information:
This material is based upon work supported by the National Science Foundation under Grants No. 1541876, 1029711, IIS-1320580, IIS-0940818, and IIS-1218168, the USDOD under Grants No. HM1582-08-1-0017 and HM0210-13-1-0005, the Advanced Research Projects Agency-Energy (ARPA-E), U.S. Department of Energy under Award No. DE-AR0000795, the NIH under Grant No. UL1 TR002494, KL2 TR002492, and TL1 TR002493, the USDA under Grant No. 2017-51181-27222, and the OVPR Infrastructure Investment Initiative and Minnesota Supercomputing Institute (MSI) at the University of Minnesota. The views and opinions of authors expressed herein do not necessarily state or reflect those of the United States Government or any agency thereof. The authors would like to thank Kim Koffolt and the University of Minnesota Spatial Computing Research Group for their comments.

Publisher Copyright:
© 2019 Association for Computing Machinery.


  • Path selection
  • Path-centric
  • Routing
  • Shortest path
  • Trajectory


Dive into the research topics of 'Trajectory-aware lowest-cost path selection: A summary of results'. Together they form a unique fingerprint.

Cite this