APPLICATIONS OF TRAVELING SALESMAN PROBLEM ON THE OPTIMAL SIGHTSEEING ORDERS OF MACAO WORLD HERITAGE SITES WITH REAL TIME OR DISTANCE VALUES BETWEEN EVERY PAIR OF SITES
DOI:
https://doi.org/10.29121/ijoest.v5.i5.2021.220Keywords:
Combinatorial Optimization, Traveling Salesman Problem, Macao World Heritage Sites, Simulated Annealing and Metropolis Algorithm, K-ary NecklaceAbstract
The optimal route of sightseeing orders for visiting every Macao World Heritage Site at exactly once was calculated with Simulated Annealing and Metropolis Algorithm (SAMA) after considering real required time or traveling distance between pairs of sites by either driving a car, taking a bus, or on foot. We found out that, with the optimal tour path, it took roughly 78 minutes for driving a car, 115 minutes on foot, while 117 minutes for taking a bus. On the other hand, the optimal total distance for driving a car would be 13.918 km while for pedestrians to walk, 7.844 km. These results probably mean that there is large space for the improvement on public transportation in this city. Comparison of computation time demanded between the brute- force enumeration of all possible paths and SAMA was also presented, together with animation of the processes for the algorithm to find out the optimal route. It is expected that computation time is astronomically increasing for the brute-force enumeration with more number of sites, while it only takes SAMA much less order of magnitude in time to calculate the optimal solution for larger number of sites. Several optimal options of routes were also provided in each transportation method. However, it is possible that in some types of transportation there could be only one optimal route having no circular or mirrored duplicates.
Downloads
References
B. Guenin, J. KoneMann, and L. Tuncel (2014), A gentle Introduction to Optimization, Cam- bridge University Press. Retrived from https://doi.org/10.1017/CBO9781107282094
C. Rossant (2018), IPython Interactive Computing and Visualization Cookbook, 2nd Ed., Packt Publishing, pp 481-486.
E. L. Lawler (1985), The Travelling Salesman Problem: A Guided Tour of Combinatorial Opti- mization (Repr. with corrections. ed.). John Wiley & sons. ISBN 978-0471904137.
Emile H.L. Aarts, Jan H.M. Korst, Peter J.M. van Laarhoven (1997), "Simulated Annealing", Local Search in Combinatorial Optimization. Edited by E. Aarts and J.K. Lenstra, John Wiley & Sons Ltd, pp 91-120. Retrieved from https://doi.org/10.2307/j.ctv346t9c.9
Fei Liu and GuangZhou Zeng (2009), "Study of genetic algorithm with reinforcement learning to solve the TSP ", Expert Systems with Applications, Volume 36, Issue 3, Part 2, April, pp 6995-7001. Retrieved from https://doi.org/10.1016/j.eswa.2008.08.026
G. Dantzig, R. Fulkerson, and S. Johnson (1954), "Solution of a Large Scale Traveling Salesman Problem", Rand Paper, P-510. Retrieved from https://www.rand.org/pubs/papers/P510.html
J. Sawada (2003), "A fast algorithm to generate necklaces with fixed content", Theoretical Computer Science, 301, 477-489. Retrieved from https://doi.org/10.1016/S0304-3975(03)00049-5
Jon Jouis Bentley (1992), "Fast Algorithms for Geometric Traveling Salesman Problems", In- forms Journal on Computing, Vol. 4, pp. 357-452. Retrieved from https://doi.org/10.1287/ijoc.4.4.387
M.S. Tarkov (2015), "Solving the traveling salesman problem using a recurrent neural network", Numerical Analysis and Applications volume 8, pp. 275-283. Retrieved from https://doi.org/10.1134/S1995423915030088
Mark Newman (n.d.), Computational Physics, Revised and Expanded 2013. ISBN 978- 148014551-1. pp. 490-492.
Merrill M. Flood (1956), "The Traveling-Salesman Problem", Operations Research, Vol. 4, pp. 1- 137,. Retrieved from https://doi.org/10.1287/opre.4.1.61
N Mazyavkina, S. Sviridov, S. Ivanov, and E. Burnaev (n.d.), "Reinforcement Learning for Combinatorial Optimization: A Survey", arXiv:2003.03600v3. Retrieved from https://arxiv.org/pd f/2003.03600
Ottoni, A.L.C., Nepomuceno, E.G., Oliveira, M.S.d. et al (2021). Reinforcement learning for the traveling salesman problem with refueling. Complex Intell. Syst.. Retrieved from https://doi.org/10.1007/s40747-021-00444-4
S. Kirkpatrick, C. D. Gelatt Jr., and M. P. Vecchi (n.d.), "Optimization by Simulated Anneal- ing", Science, Vol. 220, pp. 671-680. Retrieved from https://doi.org/10.1126/science.220.4598.671
Stephen. P. Bradley (1977), Arnoldo C. Hax, and Thomas, L. Magnanti, Applied Mathematical Programming, Addison-Wesley Publishing Company Inc.
https://en.wikipedia.org/wiki/Global_optimization
https://en.wikipedia.org/wiki/Haversine_formula
https://en.wikipedia.org/wiki/Historic_Centre_of_Macau
https://en.wikipedia.org/wiki/Macau
https://github.com/weishanlee/SAMAV2_2
https://github.com/weishanlee/SAMAV2_2/tree/main/4.29773
https://github.com/weishanlee/SAMAV3_1
https://github.com/weishanlee/brute-force-vs-simulated-annealing-metropolisalgorithm
https://stackoverflow.com/questions/51531766/python-algorithms-necklace-generation- circular-permutations
https://stackoverflow.com/questions/960557/how-to-generate-permutations-of-a-list- without-reverse-duplicates-in-python-us
https://www.macaotourism.gov.mo/zh-hant/sightseeing/macao-world-heritage
https://www.statista.com/statistics/319153/macau-visitor-arrivals/ Note that in 2020 the number of visitors dropped significantly to 5.9 millions because of the COVID-19 outbreak.
