Inferring the Parametric Weight of a Bicriteria Routing Model from Trajectories
Article No.: 59, Pages 1 - 4
Abstract
Finding a shortest path between two nodes in a graph is a well-studied problem whose applicability in practice crucially relies on the choice of the applied cost function. Especially, for the key application of vehicle routing the cost function may consist of more than one optimization criterion (e.g., distance, travel time, etc.). Finding a good balance between these criteria is a challenging and essential task. We present an approach that learns that balance from existing GPS-tracks. The core of our approach is to find a balance factor α for a given set of GPS-tracks such that the tracks can be decomposed into a minimum number of optimal paths with respect to α.
In an experimental evaluation on real-world GPS-tracks of bicyclists we show that our approach yields an appropriate balance factor in a reasonable amount of time.
References
[1]
M. Ahmed, S. Karagiorgou, D. Pfoser, and C. Wenk. 2014. A comparison and evaluation of map construction algorithms using vehicle tracking data. GeoInformatica 19, 3 (2014), 1--32.
[2]
S. P. A. Alewijnse, K. Buchin, M. Buchin, A. Kölzsch, H. Kruckenberg, and M. A. Westenberg. 2014. A framework for trajectory segmentation by stable criteria. In Proc. 22nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. 351--360.
[3]
A. Balteanu, G. Jossé, and M. Schubert. 2013. Mining driving preferences in multi-cost networks. In Proc. 13th International Symposium on Advances in Spatial and Temporal Databases (SSTD '13). 74--91.
[4]
L. Chen, M. Lv, Q. Ye, G. Chen, and J. Woodward. 2011. A personal route prediction system based on trajectory data mining. Information Sciences 181, 7 (2011), 1264--1284.
[5]
J. Dai, B. Yang, C. Guo, C. Jensen, and J. Hu. 2016. Path Cost Distribution Estimation Using Trajectory Data. Proc. Very Large Database Endowment 10 (2016), 85--96.
[6]
S. Funke, S. Laue, and S. Storandt. 2016. Deducing Individual Driving Preferences for User-aware Navigation. In Proc. 24th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (GIS '16). ACM, Article 14, 9 pages.
[7]
S. Funke and S. Storandt. 2013. Polynomial-time construction of contraction hierarchies for multi-criteria objectives. In Proc. Meeting on Algorithm Engineering & Expermiments (ALENEX '13). 41--54.
[8]
M. R. Garey and David S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, New York, NY, USA.
[9]
R. Gotsman and Y. Kanza. 2013. Compact representation of GPS trajectories over vectorial road networks. In Proc. 13th International Conference on Advances in Spatial and Temporal Databases (SSTD '13). 241--258.
[10]
J.-H. Haunert and B. Budig. 2012. An algorithm for map matching given incomplete road data. In Proc. 20th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL GIS '12). 510--513.
[11]
H.-P. Kriegel, M. Renz, and M. Schubert. 2010. Route skyline queries: A multi-preference path planning approach. In Proc. 26th International Conference on Data Engineering (ICDE '10). 261--272.
[12]
P. Laube. 2014. Computational Movement Analysis. Springer-Verlag, Berlin, Germany.
[13]
P. M. Lerin, D. Yamamoto, and N. Takahashi. 2013. Encoding network-constrained travel trajectories using routing algorithms. International Journal of Knowledge and Web Intelligence 4, 1 (2013), 34--49.
[14]
I. Massad and S. Dalyot. 2015. Towards the production of digital terrain models from volunteered GPS trajectories. Survey Review 47, 344 (2015), 325--332.
[15]
S. Reddy, K. Shilton, G. Denisov, C. Cenizal, D. Estrin, and M. Srivastava. 2010. Biketastic: Sensing and mapping for better biking. In Proc. SIGCHI Conference on Human Factors in Computing Systems (CHI '10). 1817--1820.
[16]
M. Shekelyan, G. Jossé, M. Schubert, and H.-P. Kriegel. 2014. Linear path skyline computation in bicriteria networks. In Proc. 19th International Conference on Database Systems for Advanced Applications (DASFAA '14). 173--187.
[17]
S. Storandt. 2012. Route planning for bicycles -- exact constrained shortest paths made practical via contraction hierarchy. In Proc. 22nd International Conference on Automated Planning and Scheduling (ICAPS '12). 234--242.
[18]
J. Yuan, Y. Zheng, C. Zhang, W. Xie, X. Xie, G. Sun, and Y. Huang. 2010. T-drive: Driving directions based on taxi trajectories. In Proc. 18th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL GIS '10). 99--108.
[19]
Y. Zheng and X. Zhou. 2011. Computing with Spatial Trajectories. Springer-Verlag, Berlin, Germany.
Index Terms
- Inferring the Parametric Weight of a Bicriteria Routing Model from Trajectories
Recommendations
Fractional routing using pairs of failure-disjoint paths
Given a set of commodities and a network where some arcs can fail while others are reliable, we consider a routing problem with respect to a survivability requirement that each commodity can be split among pairs of failure-disjoint paths. Two paths p ...
Improved algorithms for the k simple shortest paths and the replacement paths problems
Given a directed, non-negatively weighted graph G=(V,E) and s,t@?V, we consider two problems. In the k simple shortest paths problem, we want to find the k simple paths from s to t with the k smallest weights. In the replacement paths problem, we want ...
Generalization of Shortest Path Map
ITNG '10: Proceedings of the 2010 Seventh International Conference on Information Technology: New GenerationsWe consider the problem of constructing shortest path maps in two dimensions under angle constraint. Shortest path maps are used for planning short length paths from a fixed source point s to varying goal points. In the standard shortest path map the ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
November 2017
677 pages
ISBN:9781450354905
DOI:10.1145/3139958
Copyright © 2017 Owner/Author.
Permission to make digital or hard copies of part or all 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 third-party components of this work must be honored. For all other uses, contact the Owner/Author.
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 07 November 2017
Check for updates
Author Tags
Qualifiers
- Poster
- Research
- Refereed limited
Conference
SIGSPATIAL'17
Sponsor:
SIGSPATIAL'17: 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems
November 7 - 10, 2017
CA, Redondo Beach, USA
Acceptance Rates
SIGSPATIAL '17 Paper Acceptance Rate 39 of 193 submissions, 20%;
Overall Acceptance Rate 257 of 1,238 submissions, 21%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 113Total Downloads
- Downloads (Last 12 months)7
- Downloads (Last 6 weeks)0
Reflects downloads up to 23 Nov 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in