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
Journal: INTERNATIONAL JOURNAL OF ENGINEERING SCIENCE TECHNOLOGIES (Vol.5, No. 5)Publication Date: 2021-10-31
Authors : Kin Neng Tong Iat In Fong In Iat Li Chi Him Anthony Cheng Soi Chak Choi Hau Xiang Ye; Wei Shan Lee;
Page : 41-53
Keywords : Combinatorial Optimization; Traveling Salesman Problem; Macao World Heritage Sites; Simulated Annealing and Metropolis Algorithm (SAMA); 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.
Other Latest Articles
- EXPORTS DIVERSIFICATION AS A KEY POINT OF CHINA’S TRADE STRATEGY
- APPLIED ASPECTS OF IMPROVING THE EFFICIENCY OF DAIRY ENTERPRISES BASED ON COMPREHENSIVE ECONOMIC DIAGNOSTICS
- CREATING A MODEL OF THE FUTURE OF THE EIGHTH TECHNOLOGICAL ORDER
- ACCOUNTING AND ANALYTICAL SUPPORT FOR THE MANAGEMENT OF MONETARY ASSETS IN FORESTRY ENTERPRISES
- MINIMIZING RISKS OF INTEGRATING UKRAINIAN INDUSTRY INTO GLOBAL VALUE CHAINS
Last modified: 2021-11-12 19:26:10