Abstract
TSP, the Traveling Salesman Problem is a famous hard problem in computer science. Finding an optimal solution for TSP in a map consisting of huge number of locations will take huge amount of time (possibly years). A traveller (salesman) needs to visit a limited number of locations out of these thousands locations (each building is an address or location). It is desirable to solve TSP efficiently with real-time factors (traffic, distance, real-time delays). Online applications like Google maps, Yahoo maps, and many others do not give efficient solutions for a multiple-destinations queries. Minimizing the number of locations to exactly the number of destinations asked in the query (by the traveller) will make the optimal hard solution time-acceptable. This paper uses smart heuristics, intelligent algorithm A*, traditional graph Hamilton circuit algorithm, as well as efficient data structures to finding an efficient cycle path between multiple addresses, and hence finding and optimal solution for TSP in real-time. The main idea is to build a virtual graph VG built from a minimized list of vertices (equals exactly to desired list of destinations) and a list of virtual edges that are computed using the smart algorithms A*.
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
References
Ross, K., Wright, C.: Discrete Mathematics. Prentice Hall, Upper Saddle River, New Jersey (2003)
Russell, S., Norving, P.: Artificial Intelligence a Modern Approach. Prentice Hall, Upper Saddle River, New Jersey (2003)
Pearl, J.: Heuristics: Intelligent Search Strategies for computer Problem Solving. Addison Wesley, Reading, MA (1984)
Halaoui, H.: Smart Traffic Online System (STOS): Presenting road networks with time-weighted graphs. In: IEEE International Conference on Information Society (i-Society 2010) London, UK, June 2010, pp. 349–356
Google Earth Blog Google Earth Data Size, Live Local, New languages coming. http://whatis.techtarget.com/definition/Google-Maps. Accessed September 2015
Halaoui, H.: Smart traffic systems: dynamic A*Traffic in GIS driving paths applications. In: Proceeding of IEEE CSIE09, IEEE, Los Angeles, USA. March 2009, pp. 626–630
Halaoui, H.: Intelligent traffic system: road networks with time-weighted graphs. Int. J. Infonomics (IJI) 3(4), 350–359 (2010)
Google Maps. https://www.google.com/. Accessed September 2015
Halaoui, H.: Spatial and spatio-temporal databases modeling: approaches for modeling and indexing spatial and spatio-temporal databases. VDM Verlag (2009)
Halaoui, H.: SMART navigation: using artificial intelligent heuristics in navigating multiple destinations. In: Proceedings of SOTICS 2015 (The Fifth International Conference on Social Media Technologies, Communication, and Informatics). Barcelona, Spain. November 2015
Lawler, E.L., Lenstra, J.K., Rinooy Kan, A.H.G., Shmoys, D.B. (eds.): The Traveling Salesman Problem, pp. 145–180. Wiley, Chichester (1985)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Halaoui, H.F. (2020). An Optimal Real-Time Solution for Limited-TSP: Using Smart Algorithms to Find an Optimal TSP Real-Time Solution Over Limited Destinations. In: Ahram, T., Taiar, R., Colson, S., Choplin, A. (eds) Human Interaction and Emerging Technologies. IHIET 2019. Advances in Intelligent Systems and Computing, vol 1018. Springer, Cham. https://doi.org/10.1007/978-3-030-25629-6_37
Download citation
DOI: https://doi.org/10.1007/978-3-030-25629-6_37
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-25628-9
Online ISBN: 978-3-030-25629-6
eBook Packages: EngineeringEngineering (R0)