TRAVELING SALESMAN PROBLEM FOR OPTIMAL TOURIST ROUTE IN AYUTTHAYA

Tantikorn Pichpibul; Nareerat Prechatavanitchakul

Authors

Tantikorn Pichpibul Lecturer, School of Engineering, Bangkok University, 9/1, Moo 5 Phaholyothin Road, Khlong Luang District, Pathum Thani 12120
Nareerat Prechatavanitchakul Lecturer, School of Entrepreneurship, Sripatum University, 2410/2, Phaholyothin Road, Chatuchak District, Bangkok 10900

Keywords:

Traveling Salesman Problem, Tourist Route, Clarke-Wright Algorithm, Honey Bees Mating Optimization Algorithm

Abstract

This paper explores the traveling salesman problem (TSP) in the context of planning one-day trips for travelers to historical, cultural, and ecotourism sites in Ayutthaya Province, Thailand. A cloud-based decision-making software was introduced to address this issue which combines the Clarke-Wright algorithm with the honey bees mating optimization algorithm. Through experimental evaluations on TSP benchmark problems and real-world traveler data, it was found that the proposed method is on par with some of the leading existing algorithms. As a result, travelers can effectively plan optimal tourist routes.

References

Clarke G, Wright JW. Scheduling of vehicles from a central depot to a number of delivery points. Operations Research 1964;12:568-81.

Abbass HA. MBO: marriage in honey bees optimization-a haplometrosis polygynous swarming approach. In: Proceedings of the 2001 Congress on Evolutionary Computation (IEEE Cat. No.01TH8546) vol.1; 2001 May 27-30; Seoul, Korea. p. 207-14.

Dantzig G, Fulkerson R, Johnson S. Solution of a large-scale traveling salesman problem. Journal of the Operations Research Society of America 1954;2(4):393-410.

Lin S, Kernighan BW. An effective heuristic algorithm for the traveling salesman problem. Operations Research 1973;21(2):498-516.

Lawler EL, Lenstra JK, Rinnooy Kan AHG, Shmoys DB. The traveling salesman problem. Chichester: John Wiley; 1985.

Golden BL, Levy L, Vohra R. The orienteering problem. Naval Research Logistics 1987;34:307-18.

Balas E. The prize collecting traveling salesman problem. Networks 1989;19(6):621-36.

Papadimitriou CH. The Euclidean traveling salesman problem is NP-complete. Theoretical Computer Science 1977;4:237-44.

Kirkpatrick S, Gelatt CD., Vecchi MP. Optimization by simulated annealing. Science 1983;220:671-80.

Glover F. Tabu search-part I. ORSA Journal on Computing 1989;1(3):190-206.

Glover F. Tabu search-part II. ORSA Journal on Computing 1990;2(1):4-32.

Potvin JY. Genetic algorithms for the traveling salesman problem. Annals of Operations Research 1996;63:337-70.

Mladenovic N, Hansen P. Variable neighborhood search. Computers and Operations Research 1997;24:1097-100.

Dorigo M, Gambardella LM. Ant colony system: a cooperative learning approach to the traveling salesman problem. IEEE Transactions on Evolutionary Computation 1997;1:53-66.

Dorigo M, Gambardella LM. Ant colonies for the traveling salesman problem. Biosystems 1997;43:73-81.

Suksen K, Benchasattabuse N, Chongstitvatana P. Compact genetic algorithm with quantum-assisted feasibility enforcement. ECTI Transactions on Computer and Information Technology 2022;16(4):422-35.

Pan J, Ji X, Liang A, Huang K, Chu S. Parallel binary cat swarm optimization with communication strategies for traveling salesman problem. Journal of Internet Technology 2021;22(7):1621-33.

Jaiyen E, Leksakul K. Application of element decomposing method for solving traveling salesman problems. Thai Journal of Mathematics 2020;18(4):1715-31.

Phu-ang A, Jitkongchuen D. The Cluster crossover operation for the symmetric travelling salesman problem. ECTI Transactions on Computer and Information Technology 2018;12(2):98-105.

Wang Y. The hybrid genetic algorithm with two local optimization strategies for traveling salesman problem. Computers & Industrial Engineering 2014;70:124-33.

Chen L, Sun H, Wang S. A parallel ant colony algorithm on massively parallel processors and its convergence analysis for the travelling salesman problem. Information Sciences 2012;199:31-42.

Zhang J, Feng X, Zhou B, Ren D. An overall-regional competitive self-organizing map neural network for the Euclidean traveling salesman problem. Neurocomputing 2012;89:1-11.

Reinelt G. TSPLIB-a travelling salesman problem library. ORSA Journal on Computing 1991;3:376-84.

Chen S, Chien C. Solving the traveling salesman problem based on the genetic simulated annealing ant colony system with particle swarm optimization techniques. Expert Systems with Applications 2011;38(12):14439-50.

Geng X, Chen Z, Yang W, Shi D, Zhao K. Solving the traveling salesman problem based on an adaptive simulated annealing algorithm with greedy search. Applied Soft Computing 2011;11(4):3680-9.

Wang Y, Li J, Gao K, Pan Q. Memetic algorithm based on improved Inver-over operator and Lin-Kernighan local search for the euclidean traveling salesman problem. Computers and Mathematics with Applications 2011;62(7):2743-54.

Wei Z, Ge F, Lu Y, Li L, Yang Y. Chaotic ant swarm for the traveling salesman problem. Nonlinear Dynamics 2011;65:271-81.