Inferring the Parametric Weight of a Bicriteria Routing Model from Trajectories

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

• Applied computing

  • Operations research

    • Decision analysis

      • Multi-criterion optimization and decision-making

• Information systems

  • Information systems applications

    • Spatial-temporal systems

      • Geographic information systems

• Theory of computation

  • Design and analysis of algorithms

    • Graph algorithms analysis

      • Shortest paths