In recent years, route prediction and planning services have gained significant popularity, thanks to the abundance of geo-information and the rise of various applications. With the increasing global population and widespread adoption of smartphones and GPS devices, a vast amount of geo-data is being generated. Route prediction plays a crucial role in reducing travel time, effort, and cost. In this project, our main objective is to develop a web-based application that can generate scalable travel itineraries. To achieve this, we propose the Multiple-Destination Route Prediction (MDRP) algorithm, which predicts optimal paths based on geographical data. These geographical data points are then visualized on a map using a map matching tool, providing the user with the final results. Real datasets, publicly available, Utilizing Road network spatial data along with GPS traces collected from users, are used to conduct experiments. Generating multiple valid node sequences of varying lengths in a sequential manner poses a challenge due to the need for multiple passes through the database. However, the experiments conducted on these real datasets have demonstrated that our proposed MDRP algorithm efficiently predicts optimized shortest paths to multiple locations.

Geographic Information Systems (GIS), Route Prediction Systems, Data Mining, GPS, Travel Pattern, Geospatial Database, Spatial Data Analysis, Location-Based Services, Path Prediction, Trajectory Analysis, Context-Aware Computing, Probabilistic Model, Map Matching.

[1]. C. Ganesh, E. Kesavulu Reddy, "Overview of the Predictive Data Mining Techniques", International Journal of Computer Sciences and Engineering, Vol.10, Issue.1, pp.28-36, 2022.
[2]. Jiawei Han and Micheline Kamber, “Data Mining: Concepts and Techniques”, 2nd edition, In: Morgan Kaufmann Publishers, San Francisco, 2006.
[3]. R.Agrawal and R. Srikant, “Mining Sequential patterns”, In proc. Int. conf. Data Engineering, Taipei, Taiwan, pp.3-14, March 1995.
[4]. D Singh, Pritam, N Duhan and KK. Bhatia, “A comprehensive study of route prediction algorithms”. In proceedings of international journal of computer science and engineering, vol.7, Issue. 9, pp.78-85.
[5]. N. Ye, Z. Wang, R. Malekian, Q. Lin, & R. Wang, “A Method for Driving Route Predictions Based on Hidden Markov Model”. Mathematical Problems in Engineering, pp.1–12, 2015.
[6]. Preeti Nair, Indu Kashyap, "Reduced Distance Computation k Nearest Neighbor Model", International Journal of Computer Sciences and Engineering, Vol.7, Issue.5, pp.658-666, 2019.
[7]. Y. Takeuchi and M. Sugimoto, “CityVoyager: An outdoor recommendation system based on user location history,” Ubiquitous Intelligence and Computing, Vol.4159, pp.625-636, 2006.
[8]. A. Karbassi and M. Barth, “Vehicle route prediction and time of arrival estimation techniques for improved transportation system management,” in Proceedings of Intelligent Vehicles Symposium, pp. 511-516, 2003.
[9]. W.H. Lee, S.S. Tseng, W.Y. Shieh, “Collaborative real-time traffic information generation and sharing framework for the intelligent transportation system,” Information Sciences, vol. 180, No.1, pp.62-70, Jan 2010.
[10]. K. Torkkola, K. Zhang, H. Li, H. Zhang, C. Schreiner and M. Gardner, “Traffic advisories based on route prediction,” Proceedings of Workshop on Mobile Interaction with the Real World, pp.33–36, 2007.
[11]. Claire F. Minett, A. Maria Salomons, Winnie Daamen, Bart van Arem and Sjon Kuijpers, “Eco-routing: Comparing the fuel consumption of different routes between an origin and destination using field test speed profiles and synthetic speed profiles,” 2011 IEEE Forum on Integrated and Sustainable Transportation System, Jun. 2011.
[12]. Y. Deguchi, “HEV charge/discharge control system based on car navigation information,” Proceedings of SAE Convergence International Congress & Exposition on Transportation Electronics, pp.1–4, 2004.
[13]. E. D. Tate and S.P. Boyd, “Finding Ultimate Limits of Performance for Hybrid Electric Vehicles,” SAE Transactions - Journal of Passenger Car - Mechanical Systems, vol.109, 2001.
[14]. R.Agrawal and R. Srikant, “Mining Sequential patterns”, In proc. Int. conf. Data Engineering, Taipei, Taiwan, pp.3-14, March 1995.
[15]. R.Srikant and R. Agrawal, “Mining Sequential Patterns: Generalizations and Performance improvements”, In Proc. 5th International Conf. Extending Database Technology (EDBT’ 96), pp 3-17, March 1996.
[16]. H. Mannila, H.Toivonen, A.I. Verkamo, “Discovery of frequent episodes in event sequences”, In: Data Mining & Knowledge Discovery, pp. 259-289, 1997.
[17]. J. Han, J. pei, Y. Yin, “Mining frequent patterns without candidate generation”, In Roc, 2000 ACM-SIGMOD Int. Conf. Management of Data (SIGMOD00), pp. 1-12, May 2000.
[18]. J.Han, J.Pei, B. Mortazavi-Asl, Q.Chen, U. Dayal, M.C. Hsn, “FreeSpan: Frequent pattern-projected sequential pattern mining” In: proceedings of 2000 International Conference, 2000.
[19]. J. Pei, J. Han, H. Pinto, Q. Chen, U. Dayal, & Hsu, M.C, “Prefixspan: Mining sequential patterns efficiently by prefix-projected pattern growth”, In Proceedings of 2001 International Conference on Data Engineering, 2001.
[20]. R. Agrawal and R. Srikant, “Fast algorithms for mining association Rules”, In Proc. 1994 int. conf. very large Databases, pp. 487-499, September 1994.
[21]. Ling Chen, Mingqi Lv, Qian Ye, Gencai Chen and John Woodward, “A personal route prediction system based on trajectory data mining,” Information Sciences, vol.181, pp.1264-1284, April 2011.
[22]. J. M. Kim, H. Baek and Y. T. Park, “Probabilistic graphical model based personal route prediction in mobile environment,” Applied Mathematics and Information Sciences, vol. 6, No. 2S, pp. 651S-659S, January 2012.
[23]. Mingqi Lv, Yinglong Li, Zhenming Yuan and Qihui Wang, “Route Pattern Mining From Personal Trajectory Data”, Journal of Information Science and Engineering, vol.31, pp.147-164, 2015.
[24]. Seongwon Min, Jong-Yong Lee and Kye-Dong Jung, “Real-time path prediction and grid-based path modeling method using GPS,” International Journal of Applied Engineering Research, Vol.12, No.20, pp. 9997-10001, 2017.
[25]. Vishnu Shankar Tiwari and Arti Arya, “Horizontally scalable probabilistic generalized suffix tree (PGST) based route prediction using map data and GPS traces,” Journal of Big Data, vol.4, No. 23, 2017.
[26]. Vishnu Shankar Tiwari and Arti Arya, “Distributed Context Tree Weighting (CTW) for route prediction,” Open Geospatial Data, Software and Standards, vol. 3, No10, 2018.
[27]. Shun Taguchi, Satoshi Koide and Takayoshi Yoshimura, “Online Map Matching With Route Prediction,” IEEE Transactions on Intelligent Transportation Systems, vol.20, No.1 pp.338-347, Jan. 2018.
[28]. Sudhir Kumar Adhlaka, Neelam Duhan, Komal Kumar Bhatia and Himanshu Sharma, “Route Prediction Techniques using GPS Traces and Spatial Data,” Proceedings of INDIACom IEEE International Conference on “Computing for Sustainable Global Development”, BVICAM, New Delhi, 13th-15th, March, pp.1475-1481, 2019.
[29]. Zaki, J. Mohammed, “SPADE: An Efficient Algorithm for Mining Frequent Sequences.” in proceedings of Machine Learning, vol.42, pp. 31-60, 2001.