key: cord-0180858-wrgc8cez authors: Tong, Kin Neng; Fong, Iat In; Li, In Iat; Cheng, Chi Him Anthony; Choi, Soi Chak; Ye, Hau Xiang; Lee, Wei Shan title: 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 date: 2021-08-29 journal: nan DOI: nan sha: 91627b0ba80d3c619d409ecd154f68bf5cb676c3 doc_id: 180858 cord_uid: wrgc8cez 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. Macao, [1] one of the two special administrative regions of People's Republic of China, is a very famous historical city. In 2005, the UNESCO World Heritage Committee [2] announced that the Historic Center of Macao was inscribed on the UNESCO World Heritage List. The Historic Center of Macao [3] represents the architectural heritage of the city's historical remains, including city squares, streetscapes, churches and temples, such as the ruins of St Paul's Church, Senado Square, A-Ma Temple and the Leal Senado Building, and many others. Statistics records [4] showed that there are roughly 30 million tourists a year visiting Macao during last decade. Even if some visitors are prone to casinos, there is significant portion of visitors who are more interested in the heritage sites. Therefore, looking for an efficient route for tourists to visit all the heritage sites remains an important issue for tourism management. Generally speaking, a global optimization problem [5] is difficult to solve. Some specific problems have already had promising regular ways to solve. For example, the knapsack problem, assignment problem, as well as the set-cover problem, may be solved by linear programming. [6] Meanwhile, convex functions and some specific concave functions may be solved by nonlinear programming. [7] Without doubt, the generic method on the optimization is still hard to find. After H Whitney [8] proposed the traveling-salesman problem (TSP) in a seminar talk in Princeton in 1930s, there have been several attempts that have been trying to tackle the problem. For example, Flood [9] provided the obvious brute-force algorithm to deal with the problem, while proposing that the aim of the algorithm was to find, for finitely many points whose pairwise distances are known, the shortest route connecting the points. In 1954, Dantzig et al. [10] calculated a path with the shortest road distance for 49 cities out of the 48 states and Washingtond D.C. Bently [11] proposed a fast algorithm for this problem in a geometric aspect. Moreover, some techniques in Machine Learning also were applied to TSP. For instance, Tarkov [12] solved TSP with Hopfield Recurrent Neural Network(RNN). In addition, the Generic Algoritm with Reinforcement Learning [13] − [15] was also applied to solving TSP. Also, for several countries, one may make use of smopy and networkx libraries in Python to create a GPS-like route plan, exploiting the Dijkstra's algorithm [16] to find out the shortest path. However, TSP study specifically for Macao World Heritage sites remains unknown. In our study, we first collected data from GOOGLE MAP about the least time or shortest distance between pairs of Macao World Heritage Sites by either driving a car, taking a bus, or on foot. Later, after comparing the efficiency between brute-force enumeration and SAMA, we used SAMA to search for the routes with optimal time or distance for tourists to go over all the world heritage sites without repeating any site. Finally, in certain transportation methods, we observed that there could be only one optimal route that is not circular or mirrored repetitive. Suppose the N Macao world heritage sites are labeled as [0, 1, 2, . . . , N − 1]. Also, let Ei,j denote time or distance required when traveling between a pair of sites i and j. For example, the straight distance between site i and site j is Ei,j = | ri − rj|, where ri and rj are the respective coordinates of the two sites. We describe the problem as looking for a specific tour orders of N such that the total traveling time or distance is minimized. We may enumerate all possible site orders, and for each route of sightseeing orders we calculate the total distance or time, among which we could find out the minimum. The other possibility could be that we may make use of the algorithm of Traveling Salesman Problem [17] , for which the simulated annealing and Metropolis algorithm were used. Because of the theory of permutation, it is easy to calculate, for the case of N , the number of all possibilities N { ri; ∀i} that have no either circular or mirrored repetitions is One approach to generate all possibilities could be Sawada's algorithm [18] . Nevertheless, because our case is k-ary, it would be a lot more straight-forward to consider the following algorithm. while term ∈ orders do 11: generate first term in List + term 2.2 Simulated Annealing and Metropolis Algorithm(SAMA) The first idea of is Simulated Annealing [21] could be based on the fact that minimizing a mathematical formula, such as Eq. 1, is comparable to looking for a minimum energy state of a system in nature. There is a caution, however, in the nature of work with hot materials, known for a long time. In order to get a good crystallization, we need to cool down the material slowly, finding out its energy configuration of global minimum. On the other hand, if we cooled down the material too quickly, we might got glassy solids because we only reached the energy configuration of the "local" minimum for the material. Second, the nature of simulated annealing has the stochastic components, making it possible to assist in the asymptotic convergence analysis [22] . First, we randomly generate an initial configuration of our system, then calculate the initial value of the quantity Ei. Then, because the system is ergodic, we randomly modify a little bit the configuration, calculating again the quantity after the change, say Ej. If the new quantity is smaller than the old one, we know that we find out a new configuration with smaller value of the quantity for which we would like to minimize. However, if the new quantity is larger than the old one, we may not be able to carelessly reject the new configuration. Because in this way we may "cool down" our system too quickly, possibly falling into the local minimum. The idea of Metropolis Algorithm is that when the new quantity in the new configuration is larger than the old one, instead of absolutely rejecting the new configuration, we make it possible to accept the new configuration by the following Metropolis probability: [17] In practice, while randomly generating a number z between 0 and 1, we decide to accept the new configuration, with aid of Eq.(3), if the random number z satisfies otherwise we reject the swap and return to the last tour order. To be more specific, throughout our study we have chosen the maximum temperature Tmax, minimum temperature Tmin, and τ = k b T as in Table 1 . Theoretically we may demonstrate that it is possible to find out the global minimum under infinite number of iterations. [22] But it is not realistic to iterate infinitely number of times. Therefore, we need to compensate between the optimized value and time we need to consume. It is worth mentioning that in the optimization problem it is quite impossible to assure that we already reached the global minimum. All we can do is to find out another new solution to see if the new one out-reaches a smaller value compared with the old one. We collected our data about coordinates on latitudes and longitudes of the Macao World Heritage Sites from GOOGLE MAP, tabulated in Table A .1, with indications of names [23] . Figure 1 depicts the plot of site locations. Haversine formula [24] was used to convert from latitudes and longitudes to kilometers for a pair of sites. Coordinates of the Sites Figure 1 : Coordinates of sites with the Site ID number used throughout the paper, indicating name of every site in Table A .1. Site 17, 18, and 19 are too close to distinguish from one another. We first compared the computation time between the brute-force method and SAMA. Later, for the first trial of SAMA, we introduced the latitudes and longitudes of the Macao World Heritage sites and calculated the optimal route with the minimum total distance by assuming that any pair of sites could be reached by a straight line. But this assumption is not realistic because in practice the real roads, streets or avenues in Macao are mostly not straight lines. Therefore, taking into consideration of real situations, for every pair of sites, we searched on GOOGLE MAP for the genuine time or distance required by either driving a car( In order to compare time required by brute-force method and SAMA, we first randomly generate fictitious 12 sites, whose coordinates are lists in Table 2 . Table 3 showed results of required computation time, after taking the average value on five times for each number of sites, under the condition of same shortest distance. It was evident that computation time for SAMA remained roughly less than 1 seconds for number of sites N less than 11, while for N = 12, 4.28 seconds. On the other hand however, for the brute-force method, for fewer number of sites, the required time was less than that of SAMA, referring to the fact that for fewer number of sites, the brute-force method prevails SAMA. But the advantage of SAMA gradually appeared for larger N at least for two aspects. First, for N = 12, the brute-force method required roughly 1600 seconds to compute, while SAMA only required 4.28 seconds. The other advantage was that for larger number of N , brute-force method demands a lot of computer memory, causing it impractical to implement in reality. Meanwhile, it is not a problem for SAMA because of the characteristic nature in randomly selecting the state of the system to compute. Figure 2 shows plots of required time vs. number of sites. It is obvious that demanding time for brute-force method increased dramatically for larger number of sites. Codes may be obtained via Ref. [25]. First, we randomly chose a site to be the origin and the end, initiating a tour path with a (perhaps high) value of total traveling distance. Afterward, SAMA cooled down the system, trying to find out a route with shorter total distance. Figure 3 showed the curve of total traveling distance vs. iteration. Keeping in mind that instead of absolutely rejecting all states with higher energy, SAMA also allows a state with higher energy described by the rule in Eq.3, which is the reason for SAMA to put out the noisy curve within the iteration range 0 to 3000. Within Iteration 3000 to 5000, the curve remained relatively flat with the total distance roughly 6 km. Nevertheless, this could only be a local minimum for the particular initial condition. In order to search for the global optimization, we started all over again by randomly initializing another starting point. This was shown at Iteration 4750 with a dramatically increase of the total traveling distance. SAMA would cool down the system again to reach another (probably) local minimum. We repeated the process until a targeted value of total distance was achieved. Codes may be obtained via Ref. [26]. In order to calculate the optimal route with genuine least time or shortest distance, we collected, for each transportation method, the true value of distance or time between a pair of sites with the form of matrices presented from Also, we provided a simple algorithm to generate the k-ary necklace. Based on this we calculated computation time required in the brute-force method to obtain the optimal time or distance by enumerating all possible routes. Whereas for small number of sites, the brute-force enumeration performed much faster in calculating the optimal value, SAMA prevailed when number of sites increased. In our study, we demonstrated that when number of sites was 12, SAMA only required 3 orders of magnitude less in time than the brute-force method to obtain the optimal total distance. Last but not least, we provided several optimal routes in different kinds of transportation for tourists in Macao, from which choices may be made to manage their visiting plans more efficiently. We thank Pui Ching Middle School in Macao PRC for the kindness to support this research project. Appendix C Car Driving distance for Pairs of Sites A gentle Introduction to Optimization Applied Mathematical Programming The Travelling Salesman Problem: A Guided Tour of Combinatorial Optimization (Repr. with corrections The Traveling-Salesman Problem Solution of a Large Scale Traveling Salesman Problem Fast Algorithms for Geometric Traveling Salesman Problems Solving the traveling salesman problem using a recurrent neural network Study of genetic algorithm with reinforcement learning to solve the TSP Reinforcement Learning for Combinatorial Optimization: A Survey Reinforcement learning for the traveling salesman problem with refueling IPython Interactive Computing and Visualization Cookbook Computational Physics, Revised and Expanded A fast algorithm to generate necklaces with fixed content Optimization by Simulated Annealing Simulated Annealing 4 3 3 3 2 0 4 5 7 6 8 10 9 17 17 24 22 19 19 15 12 11 12 11 12 8 7 6 6 7 5 4 0 1 3 9 5 7 6 19 18 24 22 19 19 14 12 11 11 11 12 7 7 6 6 7 5 4 1 0 1 9 7 7 6 19 19 27 25 22 22 17 15 14 14 14 14 10 10 9 9 9 8 7 3 1 0 9 7 10 9 19 20 25 22 19 19 16 14 13 14 13 14 9 9 8 8 7 6 6 9 9 9 0 Route 1 Route 2 Route 3 Route 4 Route 5 17 23 19 10 0 18 22 17 12 13 19 20 21 6 14 21 24 23 5 15 23 4 22 8 16 22 3 20 7 18 20 2 15 9 17 24 1 16 4 19 11 0 24 2 21 10 5 11 3 23 12 8