More Web Proxy on the site http://driver.im/

research-article

Public Access

Trajectory-aware Lowest-cost Path Selection: A Summary of Results

Authors:

Shashi Shekhar,

William NorthropAuthors Info & Claims

SSTD '19: Proceedings of the 16th International Symposium on Spatial and Temporal Databases

Pages 61 - 69

https://doi.org/10.1145/3340964.3340971

Published: 19 August 2019 Publication History

Abstract

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.

References

[1]

Sabeur Aridhi, Philippe Lacomme, Libo Ren, and Benjamin Vincent. 2015. A MapReduce-based approach for shortest path problem in large-scale networks. Engineering Applications of Artificial Intelligence 41 (May 2015), 151--165.

Digital Library

[2]

Andreas Artmeier, Julian Haselmayr, Martin Leucker, and Martin Sachenbacher. 2010. The Shortest Path Problem Revisited: Optimal Routing for Electric Vehicles. In KI 2010: Advances in Artificial Intelligence (Lecture Notes in Computer Science). Springer, Berlin, Heidelberg, 309--316.

Digital Library

[3]

JÃÿrgen Bang-Jensen and Gregory Z. Gutin. 2008. Digraphs: Theory, Algorithms and Applications. Springer.

Digital Library

[4]

Favyen Bastani, Songtao He, Sofiane Abbar, Mohammad Alizadeh, Hari Balakrishnan, Sanjay Chawla, and Sam Madden. 2018. Machine-assisted Map Editing. In Proceedings of the 26th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (SIGSPATIAL '18). ACM, New York, NY, USA, 23--32. event-place: Seattle, Washington.

Digital Library

[5]

B. Y. Chen, W. H. K. Lam, Q. Li, A. Sumalee, and K. Yan. 2013. Shortest Path Finding Problem in Stochastic Time-Dependent Road Networks With Stochastic First-In-First-Out Property. IEEE Transactions on Intelligent Transportation Systems 14, 4 (Dec. 2013), 1907--1917.

Digital Library

[6]

Yuche Chen, Lei Zhu, Jeffrey Gonder, Stanley Young, and Kevin Walkowicz. 2017. Data-driven fuel consumption estimation: A multivariate adaptive regression spline approach. Transportation Research Part C: Emerging Technologies 83, 0 (Oct. 2017). https://trid.trb.org/view/1482146

[7]

J. Dai, B. Yang, C. Guo, and Z. Ding. 2015. Personalized route recommendation using big trajectory data. In 2015 IEEE 31st International Conference on Data Engineering. 543--554.

[8]

Daniel Delling, Andrew V. Goldberg, Andreas Nowatzyk, and Renato F. Werneck. 2013. PHAST: Hardware-accelerated shortest path trees. J. Parallel and Distrib. Comput. 73, 7 (July 2013), 940--952.

[9]

Yong Deng, Yuxin Chen, Yajuan Zhang, and Sankaran Mahadevan. 2012. Fuzzy Dijkstra algorithm for shortest path problem under uncertain environment. Applied Soft Computing 12, 3 (March 2012), 1231--1237.

Digital Library

[10]

E. W. Dijkstra. 1959. A note on two problems in connexion with graphs. Numer. Math. 1, 1 (Dec. 1959), 269--271.

Digital Library

[11]

Daniel Duque, Leonardo Lozano, and AndrÃl's L. Medaglia. 2015. An exact method for the biobjective shortest path problem for large-scale road networks. European Journal of Operational Research 242, 3 (May 2015), 788--797.

[12]

Jochen Eisner, Stefan Funke, and Sabine Storandt. 2011. Optimal Route Planning for Electric Vehicles in Large Networks. In Proceedings of the Twenty-Fifth AAAI Conference on Artificial Intelligence (AAAI'11). AAAI Press, San Francisco, California, 1108--1113. http://dl.acm.org/citation.cfm?id=2900423.2900599

Digital Library

[13]

Yuan Gao. 2011. Shortest path problem with uncertain arc lengths. Computers & Mathematics with Applications 62, 6 (Sept. 2011), 2591--2600.

Digital Library

[14]

V. M. V. Gunturi, S. Shekhar, and K. Yang. 2015. A Critical-Time-Point Approach to All-Departure-Time Lagrangian Shortest Paths. IEEE Transactions on Knowledge and Data Engineering 27, 10 (Oct. 2015), 2591--2603.

Digital Library

[15]

P. E. Hart, N. J. Nilsson, and B. Raphael. 1968. A Formal Basis for the Heuristic Determination of Minimum Cost Paths. IEEE Transactions on Systems Science and Cybernetics 4, 2 (July 1968), 100--107.

[16]

Songtao He, Favyen Bastani, Sofiane Abbar, Mohammad Alizadeh, Hari Balakrishnan, Sanjay Chawla, and Sam Madden. 2018. RoadRunner: Improving the Precision of Road Network Inference from GPS Trajectories. In Proceedings of the 26th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (SIGSPATIAL '18). ACM, New York, NY, USA, 3--12. event-place: Seattle, Washington.

Digital Library

[17]

Xianan Huang and Huei Peng. 2018. Eco-Routing based on a Data Driven Fuel Consumption Model. arXiv:1801.08602 {stat} (Jan. 2018). arXiv: 1801.08602.

[18]

Phil LeBeau. 2019. Traffic jams cost the US an estimated $87 billion in lost productivity. https://www.cnbc.com/2019/02/11/americas-87-billion-traffic-jam-ranks-boston-and-dc-as-worst-in-us.html

[19]

Yaguang Li, Kun Fu, Zheng Wang, Cyrus Shahabi, Jieping Ye, and Yan Liu. 2018. Multi-task Representation Learning for Travel Time Estimation. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (KDD '18). ACM, New York, NY, USA, 1695--1704. event-place: London, United Kingdom.

Digital Library

[20]

Yan Li, Shashi Shekhar, Pengyue Wang, and William Northrop. 2018. Physics-guided Energy-efficient Path Selection: A Summary of Results. In Proceedings of the 26th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (SIGSPATIAL '18). ACM, New York, NY, USA, 99--108.

Digital Library

[21]

Wuman Luo, Haoyu Tan, Lei Chen, and Lionel M. Ni. 2013. Finding Time Period-based Most Frequent Path in Big Trajectory Data. In Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data (SIGMOD '13). ACM, New York, NY, USA, 713--724.

Digital Library

[22]

Paul Newson and John Krumm. 2009. Hidden Markov Map Matching Through Noise and Sparseness. In Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (GIS '09). ACM, New York, NY, USA, 336--343. event-place: Seattle, Washington.

Digital Library

[23]

Daniele Quercia, Rossano Schifanella, and Luca Maria Aiello. 2014. The Shortest Path to Happiness: Recommending Beautiful, Quiet, and Happy Routes in the City. In Proceedings of the 25th ACM Conference on Hypertext and Social Media (HT '14). ACM, New York, NY, USA, 116--125.

Digital Library

[24]

Christian Sommer. 2014. Shortest-path Queries in Static Networks. ACM Comput. Surv. 46, 4 (March 2014), 45:1--45:31.

Digital Library

[25]

U.S. Energy Information Administration. 2017. Total U.S. energy expenditures in 2015 were the lowest in more than a decade. https://www.eia.gov/todayinenergy/detail.php?id=32432

[26]

Dong Wang, Junbo Zhang, Wei Cao, Jian Li, and Yu Zheng. 2018. When Will You Arrive? Estimating Travel Time Based on Deep Neural Networks. In Thirty-Second AAAI Conference on Artificial Intelligence. https://www.aaai.org/ocs/index.php/AAAI/AAAI18/paper/view/16657

[27]

Bin Yang, Jian Dai, Chenjuan Guo, Christian S. Jensen, and Jilin Hu. 2018. PACE: a PAth-CEntric paradigm for stochastic path finding. The VLDB Journal 27, 2 (April 2018), 153--178.

Digital Library

[28]

L. Zhu, J. Holden, E. Wood, and J. Gonder. 2017. Green routing fuel saving opportunity assessment: A case study using large-scale real-world travel data. In 2017 IEEE Intelligent Vehicles Symposium (IV). 1242--1248.

Cited By

Martín LAlonso MAmarís HFuentetaja RLopez BMartin DIglesias J(2023)Electric Ambulance Routing Based on Heuristic Cost-Based Planners in Pandemic SituationsCongress on Smart Computing Technologies10.1007/978-981-99-2468-4_30(395-406)Online publication date: 11-Jul-2023
https://doi.org/10.1007/978-981-99-2468-4_30
Li YXie YShekhar S(2023)Spatial Data ScienceMachine Learning for Data Science Handbook10.1007/978-3-031-24628-9_18(401-422)Online publication date: 18-Aug-2023
https://doi.org/10.1007/978-3-031-24628-9_18
Lupa MChuchro MSarlej WAdamek K(2021)Emergency ambulance speed characteristics: a case study of Lesser Poland voivodeship, southern PolandGeoInformatica10.1007/s10707-021-00447-wOnline publication date: 13-Aug-2021
https://doi.org/10.1007/s10707-021-00447-w
Show More Cited By

Index Terms

Trajectory-aware Lowest-cost Path Selection: A Summary of Results
1. Information systems
  1. Information systems applications
    1. Data mining
    2. Spatial-temporal systems
      1. Geographic information systems

Recommendations

Physics-guided energy-efficient path selection: a summary of results
SIGSPATIAL '18: Proceedings of the 26th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems

Given a spatial road network, an origin, a destination, and trajectory data of vehicles on the network, the Energy-efficient Path Selection (EPS) problem aims to find the most energy-efficient path (i.e., with least energy consumption) between the ...
Finding min-sum disjoint shortest paths from a single source to all pairs of destinations
TAMC'06: Proceedings of the Third international conference on Theory and Applications of Models of Computation

Given a graph G = (V, E) with |V| = n, |E| = m, and a source node s, we consider the problem of finding two disjoint paths from s to two destination nodes t₁ and t₂ with minimum total length, for every pair nodes t₁, t₂ ∈ V–{s}. One efficient solution ...
An A* Algorithm with a New Heuristic Distance Function for the 2-Terminal Shortest Path Problem

The 2-terminal shortest path problem is to find a shortest path between two specified vertices in a given graph G. In this paper, we consider this problem in the following situation: G is given before the two vertices are specified so that some ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

SSTD '19: Proceedings of the 16th International Symposium on Spatial and Temporal Databases

August 2019

245 pages

ISBN:9781450362801

DOI:10.1145/3340964

Copyright © 2019 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

In-Cooperation

TU Wien: TU Wien

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 19 August 2019

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed limited

Funding Sources

Conference

SSTD '19

SSTD '19: 16th International Symposium on Spatial and Temporal Databases

August 19 - 21, 2019

Vienna, Austria

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
363
Total Downloads

Downloads (Last 12 months)58
Downloads (Last 6 weeks)9

Reflects downloads up to 18 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Martín LAlonso MAmarís HFuentetaja RLopez BMartin DIglesias J(2023)Electric Ambulance Routing Based on Heuristic Cost-Based Planners in Pandemic SituationsCongress on Smart Computing Technologies10.1007/978-981-99-2468-4_30(395-406)Online publication date: 11-Jul-2023
https://doi.org/10.1007/978-981-99-2468-4_30
Li YXie YShekhar S(2023)Spatial Data ScienceMachine Learning for Data Science Handbook10.1007/978-3-031-24628-9_18(401-422)Online publication date: 18-Aug-2023
https://doi.org/10.1007/978-3-031-24628-9_18
Lupa MChuchro MSarlej WAdamek K(2021)Emergency ambulance speed characteristics: a case study of Lesser Poland voivodeship, southern PolandGeoInformatica10.1007/s10707-021-00447-wOnline publication date: 13-Aug-2021
https://doi.org/10.1007/s10707-021-00447-w
Li YKotwal PWang PXie YShekhar SNorthrop W(2020)Physics-guided Energy-efficient Path Selection Using On-board Diagnostics DataACM/IMS Transactions on Data Science10.1145/34065961:3(1-28)Online publication date: 14-Sep-2020
https://dl.acm.org/doi/10.1145/3406596

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents