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

  • Kin Neng Tong Pui Ching Middle School Macao Special Administrative Region, People’s Republic of China
  • Iat In Fong Pui Ching Middle School Macao Special Administrative Region, People’s Republic of China
  • In Iat Li Pui Ching Middle School Macao Special Administrative Region, People’s Republic of China https://orcid.org/0000-0002-7651-1865
  • Chi Him Anthony Cheng Pui Ching Middle School Macao Special Administrative Region, People’s Republic of China
  • Soi Chak Choi Pui Ching Middle School Macao Special Administrative Region, People’s Republic of China
  • Hau Xiang Ye Pui Ching Middle School Macao Special Administrative Region, People’s Republic of China
  • Wei Shan Lee Pui Ching Middle School Macao Special Administrative Region, People’s Republic of China https://orcid.org/0000-0003-4801-0817
Keywords: Combinatorial Optimization, Traveling Salesman Problem, Macao World Heritage Sites, Simulated Annealing and Metropolis Algorithm, K-ary Necklace

Abstract

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

Download data is not yet available.

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 DOI: 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 DOI: 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 DOI: 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 DOI: 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 DOI: 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 DOI: 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 DOI: 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 DOI: 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 DOI: 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.

https://www.wh.mo/en/site/

Published
2021-09-24
How to Cite
Tong, K. N., Fong, I. I., Li, I. I., Cheng, C. H. A., Choi, S. C., Ye, H. X., & LEE, W. S. (2021). 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. International Journal of Engineering Science Technologies, 5(5), 41-53. https://doi.org/10.29121/ijoest.v5.i5.2021.220