{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:31:33Z","timestamp":1740123093979,"version":"3.37.3"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"10","license":[{"start":{"date-parts":[[2022,7,5]],"date-time":"2022-07-05T00:00:00Z","timestamp":1656979200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,7,5]],"date-time":"2022-07-05T00:00:00Z","timestamp":1656979200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100004527","name":"Energimyndigheten","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100004527","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002835","name":"Chalmers University of Technology","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100002835","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Mach Learn"],"published-print":{"date-parts":[[2022,10]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Trip destination prediction is an area of increasing importance in many applications such as trip planning, autonomous driving and electric vehicles. Even though this problem could be naturally addressed in an online learning paradigm where data is arriving in a sequential fashion, the majority of research has rather considered the offline setting. In this paper, we present a unified framework for trip destination prediction in an online setting, which is suitable for both online training and online prediction. For this purpose, we develop two clustering algorithms and integrate them within two online prediction models for this problem. We investigate the different configurations of clustering algorithms and prediction models on a real-world dataset. We demonstrate that both the clustering and the entire framework yield consistent results compared to the offline setting. Finally, we propose a novel regret metric for evaluating the entire online framework in comparison to its offline counterpart. This metric makes it possible to relate the source of erroneous predictions to either the clustering or the prediction model. Using this metric, we show that the proposed methods converge to a probability distribution resembling the true underlying distribution with a lower regret than all of the baselines.<\/jats:p>","DOI":"10.1007\/s10994-022-06175-y","type":"journal-article","created":{"date-parts":[[2022,7,5]],"date-time":"2022-07-05T19:02:46Z","timestamp":1657047766000},"page":"3839-3865","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A unified framework for online trip destination prediction"],"prefix":"10.1007","volume":"111","author":[{"given":"Victor","family":"Eberstein","sequence":"first","affiliation":[]},{"given":"Jonas","family":"Sj\u00f6blom","sequence":"additional","affiliation":[]},{"given":"Nikolce","family":"Murgovski","sequence":"additional","affiliation":[]},{"given":"Morteza","family":"Haghir Chehreghani","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,7,5]]},"reference":[{"key":"6175_CR35","doi-asserted-by":"crossref","unstructured":"\u00c5kerblom, N., Chen, Y., & Chehreghani, M. H. (2020). An online learning framework for energy-efficient navigation of electric vehicles. In Proceedings of the twenty-ninth international joint conference on artificial intelligence, IJCAI-20 (pp. 2051\u20132057).","DOI":"10.24963\/ijcai.2020\/284"},{"key":"6175_CR1","doi-asserted-by":"crossref","unstructured":"\u00c5kerblom, N., Chen Y., & Haghir,\u00a0C. M. (2021). Online learning of energy consumption for navigation of electric vehicles. CoRR, arxiv:abs\/2111.02314","DOI":"10.24963\/ijcai.2020\/284"},{"key":"6175_CR2","unstructured":"\u00c5kerblom, N., Hoseini, F.\u00a0S., & Chehreghani, M.\u00a0H. (2021). Online learning of network bottlenecks via minimax paths. CoRR, arxiv:abs\/2109.08467"},{"issue":"12","key":"6175_CR3","doi-asserted-by":"publisher","first-page":"8166","DOI":"10.1016\/j.eswa.2010.05.070","volume":"37","author":"JA Alvarez-Garcia","year":"2010","unstructured":"Alvarez-Garcia, J. A., Ortega, J. A., Gonzalez-Abril, L., & Velasco, F. (2010). Trip destination prediction based on past GPS log using a hidden Markov model. Expert Systems with Applications, 37(12), 8166\u20138171.","journal-title":"Expert Systems with Applications"},{"issue":"5","key":"6175_CR4","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1007\/s00779-003-0240-0","volume":"7","author":"D Ashbrook","year":"2003","unstructured":"Ashbrook, D., & Starner, T. (2003). Using GPS to learn significant locations and predict movement across multiple users. Personal and Ubiquitous computing, 7(5), 275\u2013286.","journal-title":"Personal and Ubiquitous computing"},{"key":"6175_CR5","unstructured":"Br\u00e9bisson, A., Simon, \u00c9., & Auvolat, A. (2015). Artificial neural networks applied to taxi destination prediction. 09 2015."},{"key":"6175_CR6","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511546921","volume-title":"Prediction, learning, and games","author":"N Cesa-Bianchi","year":"2006","unstructured":"Cesa-Bianchi, N., & Lugosi, G. (2006). Prediction, learning, and games. Cambridge: Cambridge University Press."},{"key":"6175_CR7","doi-asserted-by":"crossref","unstructured":"Chehreghani, M.\u00a0H. (2021). Reliable agglomerative clustering. In International joint conference on neural networks (IJCNN) (pp. 1\u20138). IEEE, 2021.","DOI":"10.1109\/IJCNN52387.2021.9534228"},{"issue":"1","key":"6175_CR8","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1016\/j.datak.2008.06.006","volume":"67","author":"MH Chehreghani","year":"2008","unstructured":"Chehreghani, M. H., Abolhassani, H., & Chehreghani, M. H. (2008). Improving density-based methods for hierarchical clustering of web pages. Data & Knowledge Engineering, 67(1), 30\u201350.","journal-title":"Data & Knowledge Engineering"},{"issue":"10","key":"6175_CR9","first-page":"830","volume":"44","author":"C Chen","year":"2010","unstructured":"Chen, C., Gong, H., Lawson, C., & Bialostozky, E. (2010). Evaluating the feasibility of a passive travel survey collection in a complex urban environment: Lessons learned from the new york city case study. Transportation Research Part A: Policy and Practice, 44(10), 830\u2013840.","journal-title":"Transportation Research Part A: Policy and Practice"},{"key":"6175_CR10","unstructured":"Chen, Y., & Chehreghani, M. H. (2018). Trip prediction by leveraging trip histories from neighboring users. CoRR, arxiv:abs\/1812.10097"},{"key":"6175_CR11","doi-asserted-by":"crossref","unstructured":"Davami, E., & Sukthankar, G. (12 2012). Online learning of user-specific destination prediction models, pp. 40\u201343.","DOI":"10.1109\/SocialInformatics.2012.58"},{"key":"6175_CR12","doi-asserted-by":"crossref","unstructured":"Epperlein, J.\u00a0P., Monteil, J., Liu, M. , Gu, Y., Zhuk, S., & Shorten, R. (2018). Bayesian classifier for route prediction with Markov chains. In 2018 21st international conference on intelligent transportation systems (ITSC) (pp. 677\u2013682). IEEE.","DOI":"10.1109\/ITSC.2018.8569895"},{"key":"6175_CR13","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1016\/j.trc.2017.01.020","volume":"77","author":"A Ermagun","year":"2017","unstructured":"Ermagun, A., Fan, Y., Wolfson, J., Adomavicius, G., & Das, K. (2017). Real-time trip purpose prediction using online location-based search and discovery services. Transportation Research Part C: Emerging Technologies, 77, 96\u2013112.","journal-title":"Transportation Research Part C: Emerging Technologies"},{"key":"6175_CR14","unstructured":"Ester, M., Kriegel, H.-P., Sander, J., Xiaowei, X., et al. (1996). A density-based algorithm for discovering clusters in large spatial databases with noise. In In kdd (Vol. 96, pp. 226\u2013231)."},{"key":"6175_CR15","doi-asserted-by":"crossref","unstructured":"Ester, M., & Wittmann, R. (1998). Incremental generalization for mining in a data warehousing environment. In International conference on extending database technology (pp. 135\u2013149). Springer.","DOI":"10.1007\/BFb0100982"},{"key":"6175_CR16","doi-asserted-by":"crossref","unstructured":"Filev, D., Tseng, F., Kristinsson, J., & McGee, R. (2011). Contextual on-board learning and prediction of vehicle destinations. In 2011 IEEE symposium on computational intelligence in vehicles and transportation systems (CIVTS) proceedings (pp. 87\u201391).","DOI":"10.1109\/CIVTS.2011.5949539"},{"key":"6175_CR17","doi-asserted-by":"crossref","unstructured":"Froehlich, J., & Krumm, J. (2008). Route prediction from trip observations. SAE Technical Paper: Technical report.","DOI":"10.4271\/2008-01-0201"},{"issue":"8","key":"6175_CR18","doi-asserted-by":"publisher","first-page":"1677","DOI":"10.1080\/13658816.2018.1458984","volume":"32","author":"Y Gao","year":"2018","unstructured":"Gao, Y., Jiang, D., & Yan, X. (2018). Optimize taxi driving strategies based on reinforcement learning. International Journal of Geographical Information Science, 32(8), 1677\u20131696.","journal-title":"International Journal of Geographical Information Science"},{"issue":"1","key":"6175_CR19","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1007\/BF01908075","volume":"2","author":"L Hubert","year":"1985","unstructured":"Hubert, L., & Arabie, P. (1985). Comparing partitions. Journal of Classification, 2(1), 193\u2013218.","journal-title":"Journal of Classification"},{"key":"6175_CR20","unstructured":"Karlsson, S. (2013). The Swedish car movement data project final report. Technical report, Chalmers University of Technology."},{"issue":"2\u20133","key":"6175_CR21","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1007\/s10994-010-5178-7","volume":"80","author":"R Kleinberg","year":"2010","unstructured":"Kleinberg, R., Niculescu-Mizil, A., & Sharma, Y. (2010). Regret bounds for sleeping experts and bandits. Machine Learning, 80(2\u20133), 245\u2013272.","journal-title":"Machine Learning"},{"key":"6175_CR22","doi-asserted-by":"crossref","unstructured":"Kum, D., Peng, H., & Bucknor, N. K. (2010). Optimal control of plug-in hevs for fuel economy under various travel distances. In IFAC proceedings, 6th IFAC symposium on advances in automotive control (Vol. 43, No. 7, pp. 258\u2013263).","DOI":"10.3182\/20100712-3-DE-2013.00197"},{"key":"6175_CR23","unstructured":"Laasonen, K. (2005). Route prediction from cellular data. In Workshop on context-awareness for proactive systems (CAPS), Helsinki, Finland (Vol. 1617)."},{"key":"6175_CR24","doi-asserted-by":"crossref","unstructured":"Larsson, V., Johannesson, L., Egardt, B., & Lassson, A. (2012). Benefit of route recognition in energy management of plug-in hybrid electric vehicles. In 2012 American control conference (ACC) (pp. 1314\u20131320).","DOI":"10.1109\/ACC.2012.6314910"},{"key":"6175_CR25","unstructured":"Nikulin, M.\u00a0S. (2001). Hellinger distance. Encyclopedia of Mathematics, 78."},{"key":"6175_CR26","doi-asserted-by":"crossref","unstructured":"Panahandeh, G. (2017). Driver route and destination prediction. In 2017 IEEE intelligent vehicles symposium (IV) (pp. 895\u2013900).","DOI":"10.1109\/IVS.2017.7995829"},{"issue":"1","key":"6175_CR27","doi-asserted-by":"publisher","first-page":"38","DOI":"10.2307\/2309088","volume":"64","author":"CC Robusto","year":"1957","unstructured":"Robusto, C. C. (1957). The cosine-haversine formula. The American Mathematical Monthly, 64(1), 38\u201340.","journal-title":"The American Mathematical Monthly"},{"key":"6175_CR28","unstructured":"Rosenberg, A., & Hirschberg, J. (2007). V-measure: A conditional entropy-based external cluster evaluation measure. In Proceedings of the joint conference on empirical methods in natural language processing and computational natural language learning (EMNLP-CoNLL) (pp. 410\u2013420)."},{"key":"6175_CR29","doi-asserted-by":"crossref","unstructured":"Simmons, R., Browning, B., Zhang, Y., & Sadekar, V. (2006). Learning to predict driver route and destination intent. In 2006 IEEE intelligent transportation systems conference (pp. 127\u2013132).","DOI":"10.1109\/ITSC.2006.1706730"},{"key":"6175_CR30","doi-asserted-by":"crossref","unstructured":"Vahedian, A., Zhou, X., Tong, L., Li, Y., & Luo, J. (2017). Forecasting gathering events through continuous destination prediction on big trajectory data. In Proceedings of the 25th ACM SIGSPATIAL international conference on advances in geographic information systems, SIGSPATIAL \u201917, New York, NY, USA, 2017. Association for Computing Machinery.","DOI":"10.1145\/3139958.3140008"},{"key":"6175_CR31","first-page":"2837","volume":"11","author":"NX Vinh","year":"2010","unstructured":"Vinh, N. X., Epps, J., & Bailey, J. (2010). Information theoretic measures for clusterings comparison: Variants, properties, normalization and correction for chance. The Journal of Machine Learning Research, 11, 2837\u20132854.","journal-title":"The Journal of Machine Learning Research"},{"key":"6175_CR32","doi-asserted-by":"publisher","first-page":"447","DOI":"10.1016\/j.trc.2016.08.008","volume":"71","author":"G Xiao","year":"2016","unstructured":"Xiao, G., Juan, Z., & Zhang, C. (2016). Detecting trip purposes from smartphone-based travel surveys with artificial neural networks and particle swarm optimization. Transportation Research Part C: Emerging Technologies, 71, 447\u2013463.","journal-title":"Transportation Research Part C: Emerging Technologies"},{"issue":"1","key":"6175_CR33","doi-asserted-by":"publisher","first-page":"394","DOI":"10.1109\/TCST.2017.2768042","volume":"27","author":"X Zeng","year":"2019","unstructured":"Zeng, X., & Wang, J. (2019). Optimizing the energy management strategy for plug-in hybrid electric vehicles with multiple frequent routes. IEEE Transactions on Control Systems Technology, 27(1), 394\u2013400.","journal-title":"IEEE Transactions on Control Systems Technology"},{"key":"6175_CR34","doi-asserted-by":"publisher","first-page":"258","DOI":"10.1016\/j.physa.2018.09.090","volume":"515","author":"F Zong","year":"2019","unstructured":"Zong, F., Tian, Y., He, Y., Tang, J., & Lv, J. (2019). Trip destination prediction based on multi-day GPS data. Physica A: Statistical Mechanics and its Applications, 515, 258\u2013269.","journal-title":"Physica A: Statistical Mechanics and its Applications"}],"container-title":["Machine Learning"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10994-022-06175-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10994-022-06175-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10994-022-06175-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,7]],"date-time":"2022-10-07T17:14:23Z","timestamp":1665162863000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10994-022-06175-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7,5]]},"references-count":35,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2022,10]]}},"alternative-id":["6175"],"URL":"https:\/\/doi.org\/10.1007\/s10994-022-06175-y","relation":{},"ISSN":["0885-6125","1573-0565"],"issn-type":[{"type":"print","value":"0885-6125"},{"type":"electronic","value":"1573-0565"}],"subject":[],"published":{"date-parts":[[2022,7,5]]},"assertion":[{"value":"30 December 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 January 2022","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 March 2022","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 July 2022","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"Not Applicable. The datasets and the work do not contain personal or sensitive information, no ethical issue is concerned.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethics approval"}},{"value":"The authors are fine that the work is submitted and published by Machine Learning Journal. There is no human study in this work, so this aspect is not applicable.","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent to participate"}},{"value":"The authors are fine that the work (including all content, data and images) is published by Machine Learning Journal.","order":5,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for publication"}},{"value":"The code will be publicly available once the work is published upon agreement of different sides.","order":6,"name":"Ethics","group":{"name":"EthicsHeading","label":"Code availability"}}]}}