Abstract
Situation-aware route planning gathers increasing interest. The proliferation of various sensor technologies in smart cities allows the incorporation of real-time data and its predictions in the trip planning process. We present a system for individual multi-modal trip planning that incorporates predictions of future public transport delays in routing. Future delay times are computed by a Spatio-Temporal-Random-Field based on a stream of current vehicle positions. The conditioning of spatial regression on intermediate predictions of a discrete probabilistic graphical model allows to incorporate historical data, streamed online data and a rich dependency structure at the same time. We demonstrate the system with a real-world use-case at Warsaw city, Poland.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
Our source code and the required virtual machine are publicly available as vagrant box at https://bitbucket.org/tliebig/developvm.
- 2.
- 3.
Data was provided via https://api.um.warszawa.pl.
References
Bast, H., Delling, D., Goldberg, A., Müller-Hannemann, M., Pajor, T., Sanders, P., Wagner, D., Werneck, R.F.: Route planning in transportation networks (2015). arXiv:1504.05140
Bast, H., Sternisko, J., Storandt, S.: Delay-robustness of transfer patterns in public transportation route planning. In: ATMOS-13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems-2013, vol. 33, pp. 42–54. Schloss Dagstuhl-Leibniz-Zentrum für Informatik (2013)
Bockermann, C., Blom, H.: The streams framework. Techical report 5, TU Dortmund University, December 2012. http://jwall.org/streams/tr.pdf. Accessed 28 Nov 2013
Dibbelt, J., Pajor, T., Strasser, B., Wagner, D.: Intriguingly simple and fast transit routing. In: Bonifaci, V., Demetrescu, C., Marchetti-Spaccamela, A. (eds.) SEA 2013. LNCS, vol. 7933, pp. 43–54. Springer, Heidelberg (2013). doi:10.1007/978-3-642-38527-8_6
Dijkstra, E.W.: A note on two problems in connexion with graphs. Numer. Math. 1(1), 269–271 (1959)
Gal, A., Mandelbaum, A., Schnitzler, F., Senderovich, A., Weidlich, M.: Traveling time prediction in scheduled transportation with journey segments. Inf. Syst. 64, 266–280 (2015)
Geisberger, R., Sanders, P., Schultes, D., Delling, D.: Contraction hierarchies: faster and simpler hierarchical routing in road networks. In: McGeoch, C.C. (ed.) WEA 2008. LNCS, vol. 5038, pp. 319–333. Springer, Heidelberg (2008). doi:10.1007/978-3-540-68552-4_24
Goerigk, M., Knoth, M., Müller-Hannemann, M., Schmidt, M., Schöbel, A.: The price of robustness in timetable information. In: OASIcs-OpenAccess Series in Informatics, vol. 20. Schloss Dagstuhl-Leibniz-Zentrum für Informatik (2011)
Hart, P.E., Nilsson, N.J., Raphael, B.: A formal basis for the heuristic determination of minimum cost paths. IEEE Trans. Syst. Sci. Cybern. 4(2), 100–107 (1968)
Heinemann, U., Globerson, A.: What cannot be learned with Bethe approximations. In: Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence, Barcelona, Spain (2011)
Higgins, A., Kozan, E.: Modeling train delays in urban networks. Transp. Sci. 32(4), 346–357 (1998)
Kschischang, F.R., Frey, B.J., Loeliger, H.A.: Factor graphs and the sum-product algorithm. IEEE Trans. Inf. Theor. 47(2), 498–519 (2001)
Liebig, T., Kemloh Wagoum, A.U.: Modelling microscopic pedestrian mobility using bluetooth. In: ICAART, pp. 270–275. SciTePress (2012)
Liebig, T., Peter, S., Grzenda, M., Junosza-Szaniawski, K.: Dynamic transfer patterns for fast multi-modal route planning. In: Bregt, A., Sarjakoski, T., van Lammeren, R., Rip, F. (eds.) GIScience 2017. LNGC, pp. 223–236. Springer, Cham (2017). doi:10.1007/978-3-319-56759-4_13
Liebig, T., Piatkowski, N., Bockermann, C., Morik, K.: Dynamic route planning with real-time traffic predictions. Inf. Syst. 64, 258–265 (2017). http://www.sciencedirect.com/science/article/pii/S0306437916000181
Liebig, T., Xu, Z., May, M.: Incorporating mobility patterns in pedestrian quantity estimation and sensor placement. In: Nin, J., Villatoro, D. (eds.) CitiSens 2012. LNCS, vol. 7685, pp. 67–80. Springer, Heidelberg (2013). doi:10.1007/978-3-642-36074-9_7
Mazimpaka, J.D., Timpf, S.: A visual and computational analysis approach for exploring significant locations and time periods along a bus route. In: Proceedings of the 9th ACM SIGSPATIAL International Workshop on Computational Transportation Science, pp. 43–48. ACM (2016)
Müller-Hannemann, M., Schnee, M.: Efficient timetable information in the presence of delays. In: Ahuja, R.K., Möhring, R.H., Zaroliagis, C.D. (eds.) Robust and Online Large-Scale Optimization. LNCS, vol. 5868, pp. 249–272. Springer, Heidelberg (2009). doi:10.1007/978-3-642-05465-5_10
Niu, X., Zhu, Y., Cao, Q., Zhang, X., Xie, W., Zheng, K.: An online-traffic-prediction based route finding mechanism for smart city. Int. J. Distrib. Sens. Netw. 2015, 18 (2015)
Schnitzler, F., et al.: Heterogeneous stream processing and crowdsourcing for traffic monitoring: highlights. In: Calders, T., Esposito, F., Hüllermeier, E., Meo, R. (eds.) ECML PKDD 2014. LNCS, vol. 8726, pp. 520–523. Springer, Heidelberg (2014). doi:10.1007/978-3-662-44845-8_49
Schnitzler, F., Liebig, T., Mannor, S., Souto, G., Bothe, S., Stange, H.: Heterogeneous stream processing for disaster detection and alarming. In: IEEE International Conference on Big Data, pp. 914–923. IEEE Press (2014)
Souto, G., Liebig, T.: On event detection from spatial time series for urban traffic applications. In: Michaelis, S., Piatkowski, N., Stolpe, M. (eds.) Solving Large Scale Learning Tasks. Challenges and Algorithms. LNCS, vol. 9580, pp. 221–233. Springer, Cham (2016). doi:10.1007/978-3-319-41706-6_11
Utsch, P., Liebig, T.: Monitoring microscopic pedestrian mobility using bluetooth. In: 2012 8th International Conference on Intelligent Environments (IE), pp. 173–177. IEEE (2012)
Zygouras, N., Zacheilas, N., Kalogeraki, V., Kinane, D., Gunopulos, D.: Insights on a scalable and dynamic traffic management system. In: EDBT, pp. 653–664 (2015)
Acknowledgements
This research received funding under the Horizon 2020 programme, grant number 688380 VaVeL - Variety, Veracity, VaLue: Handling the Multiplicity of Urban Sensors. We gratefully thank Nico Piatkowski for supply of his STRF library, support and discussion.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Heppe, L., Liebig, T. (2017). Real-Time Public Transport Delay Prediction for Situation-Aware Routing. In: Kern-Isberner, G., Fürnkranz, J., Thimm, M. (eds) KI 2017: Advances in Artificial Intelligence. KI 2017. Lecture Notes in Computer Science(), vol 10505. Springer, Cham. https://doi.org/10.1007/978-3-319-67190-1_10
Download citation
DOI: https://doi.org/10.1007/978-3-319-67190-1_10
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-67189-5
Online ISBN: 978-3-319-67190-1
eBook Packages: Computer ScienceComputer Science (R0)