Abstract
With the growing volumes of vehicle trajectory data, it becomes increasingly possible to capture time-varying and uncertain travel costs in a road network, including travel time and fuel consumption. The current paradigm represents a road network as a weighted graph; it blasts trajectories into small fragments that fit the under-lying edges to assign weights to edges; and it then applies a routing algorithm to the resulting graph. We propose a new paradigm, the hybrid graph, that targets more accurate and more efficient path cost distribution estimation. The new paradigm avoids blasting trajectories into small fragments and instead assigns weights to paths rather than simply to the edges.
We show how to compute path weights using trajectory data while taking into account the travel cost dependencies among the edges in the paths. Given a departure time and a query path, we show how to select an optimal set of weights with associated paths that cover the query path and such that the weights enable the most accurate joint cost distribution estimation for the query path. The cost distribution of the query path is then computed accurately using the joint distribution. Finally, we show how the resulting method for computing cost distributions of paths can be integrated into existing routing algorithms. Empirical studies with substantial trajectory data from two different cities offer insight into the design properties of the proposed method and confirm that the method is effective in real-world settings.
- C. Guo, C. S. Jensen, and B. Yang. Towards Total Traffic Awareness. SIGMOD Record, 43(3):18--23, 2014. Google ScholarDigital Library
- C. Guo, B. Yang, O. Andersen, C. S. Jensen, and K. Torp. EcoSky: Reducing vehicular environmental impact through eco-routing. In ICDE, pages 1412--1415, 2015.Google ScholarCross Ref
- O. Andersen, C. S. Jensen, K. Torp, and B. Yang. EcoTour: Reducing the Environmental Footprint of Vehicles Using Eco-routes. In MDM, pages 338--340, 2013. Google ScholarDigital Library
- J. Dai, B. Yang, C. Guo and Z. Ding. Personalized route recommendation using big trajectory data. In ICDE, pages 543--554, 2015.Google ScholarCross Ref
- Y. M. Bishop, S. E. Fienberg, and P. W. Holland. Discrete multivariate analysis: theory and practice. Springer, 2007.Google Scholar
- A. Chen and Z. Ji. Path finding under uncertainty. Journal of Advanced Transportation, 39(1):19--37, 2005.Google ScholarCross Ref
- J. Darroch and T. Speed. Additive and multiplicative models and interactions. The Annals of Statistics, 11(3):724--738, 1983.Google ScholarCross Ref
- C. Guo, Y. Ma, B. Yang, C. S. Jensen, and M. Kaul. Ecomark: evaluating models of vehicular environmental impact. In SIGSPATIAL, pages 269--278, 2012. Google ScholarDigital Library
- C. Guo, B. Yang, O. Andersen, C. S. Jensen, and K. Torp. Ecomark 2.0: empowering eco-routing with vehicular environmental models and actual vehicle fuel consumption data. GeoInformatica, 19(3):567--599, 2015. Google ScholarDigital Library
- M. Hua and J. Pei. Probabilistic path queries in road networks: traffic uncertainty aware path selection. In EDBT, pages 347--358, 2010. Google ScholarDigital Library
- T. Idé and M. Sugiyama. Trajectory regression on road networks. In AAAI, pages 203--208, 2011. Google ScholarDigital Library
- H. V. Jagadish, N. Koudas, S. Muthukrishnan, V. Poosala, K. C. Sevcik, and T. Suel. Optimal histograms with quality guarantees. In VLDB, pages 275--286, 1998. Google ScholarDigital Library
- S. Lim, C. Sommer, E. Nikolova, and D. Rus. Practical route planning under delay uncertainty: Stochastic shortest path queries. Robotics: Science and Systems, 8(32):249--256, 2013.Google Scholar
- Y. Ma, B. Yang, and C. S. Jensen. Enabling time-dependent uncertain eco-weights for road networks. In GeoRich, Article 1, 2014. Google ScholarDigital Library
- F. M. Malvestuto. Approximating discrete probability distributions with decomposable models. IEEE Transactions on SMC, 21(5):1287--1294, 1991.Google ScholarCross Ref
- P. Newson and J. Krumm. Hidden Markov map matching through noise and sparseness. In SIGSPATIAL, pages 336--343, 2009. Google ScholarDigital Library
- E. Nikolova, M. Brand, and D. R. Karger. Optimal route planning under uncertainty. In ICAPS, pages 131--141, 2006.Google ScholarDigital Library
- P. Smyth. Model selection for probabilistic clustering using cross-validated likelihood. Statistics and Computing, 10(1):63--72, 2000. Google ScholarDigital Library
- Y. Wang, Y. Zheng, and Y. Xue. Travel time estimation of a path using sparse trajectories. In SIGKDD, pages 25--34, 2014. Google ScholarDigital Library
- M. P. Wellman, M. Ford, and K. Larson. Path planning under time-dependent uncertainty. In UAI, pages 532--539, 1995. Google ScholarDigital Library
- B. Yang, C. Guo, and C. S. Jensen. Travel cost inference from sparse, spatio-temporally correlated time series using Markov models. PVLDB, 6(9):769--780, 2013. Google ScholarDigital Library
- B. Yang, C. Guo, C. S. Jensen, M. Kaul, and S. Shang. Stochastic skyline route planning under time-varying uncertainty. In ICDE, pages 136--147, 2014.Google ScholarCross Ref
- R. Geisberger, and C. Vetter. Efficient routing in road networks with turn costs. In ESA, pages 100--111, 2011. Google ScholarDigital Library
- M. Kaul, B. Yang, and C. S. Jensen. Building Accurate 3D Spatial Networks to Enable Next Generation Intelligent Transportation Systems. In MDM, pages 137--146, 2013. Google ScholarDigital Library
- M. Asghari, T. Emrich, U. Demiryurek, and C. Shahabi Probabilistic estimation of link travel times in dynamic road networks. In SIGSPATIAL, Article 47, 2015. Google ScholarDigital Library
- B. Yang, M. Kaul, and C. S. Jensen. Using incomplete information for complete weight annotation of road networks. TKDE, 26(5):1267--1279, 2014. Google ScholarDigital Library
- J. Yuan, Y. Zheng, X. Xie, and G. Sun. T-drive: Enhancing driving directions with taxi drivers' intelligence. TKDE, 25(1):220--232, 2013. Google ScholarDigital Library
- B. Yang, C. Guo, Y. Ma, and C. S. Jensen. Toward personalized, context-aware routing. VLDB Journal, 24(2):297--318, 2015. Google ScholarDigital Library
- J. Zheng and L. M. Ni. Time-dependent trajectory regression on road networks via multi-task learning. In AAAI, pages 1048--1055, 2013. Google ScholarDigital Library
- J. Dai, B. Yang, C. Guo, and C. S. Jensen. Efficient and Accurate Path Cost Estimation Using Trajectory Data. CoRR, abs/1510.02886, 2015.Google Scholar
- Supplementary document. http://people.cs.aau.dk/%7Ebyang/218-appendix.pdf.Google Scholar
Recommendations
Path-based queries on trajectory data
SIGSPATIAL '14: Proceedings of the 22nd ACM SIGSPATIAL International Conference on Advances in Geographic Information SystemsIn traffic research, management, and planning a number of path-based analyses are heavily used, e.g., for computing turn-times, evaluating green waves, or studying traffic flow. These analyses require retrieving the trajectories that follow the full ...
Trajectory-aware Lowest-cost Path Selection: A Summary of Results
SSTD '19: Proceedings of the 16th International Symposium on Spatial and Temporal DatabasesThe 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 Cover Problems with Length Cost
WALCOM: Algorithms and ComputationAbstractFor a graph , a collection of vertex-disjoint (simple) paths is called a path cover of G if every vertex is contained in exactly one path of . The Path Cover problem (PC for short) is to find a minimum cardinality path cover of G. In ...
Comments