Application of the Lightning Search Algorithm with 2-Opt Local Search for Solving the Asymmetric Traveling Salesman Problem
DOI:
https://doi.org/10.26593/jrsi.v13i2.7760.191-202Keywords:
Asymmetric Traveling Salesman Problem, Lightning Search Algorithm, Metaheuristics, Local Search, Optimization ProblemAbstract
The Asymmetric Traveling Salesman Problem (ATSP) is an optimization problem where a "salesman" must visit several cities in a single trip. In the ATSP, the distance traveled from city i to j differs from the distance from city j to i. The goal of the ATSP is to minimize the total distance traveled by the "salesman." In this study, the Lightning Search Algorithm (LSA) and the 2-Opt local search algorithm are used to find solutions for the ATSP. LSA is a metaheuristic algorithm inspired by the process of lightning propagation to the earth's surface. 2-Opt is a local search algorithm that can manipulate routes to produce better solutions. This research aims to design LSA with 2-Opt for solving the ATSP and to identify the parameters that influence the ATSP solution. Three parameters are used in this study: maximum channel time (max_ctime) and forking probability (fork_prob), which are responsible for the forking phenomenon, and Boundaries (Bound), which define the solution space. ANOVA testing was conducted on 8 parameter combinations implemented on 5 ATSP cases from TSPLIB: BR17, FTV33, FTV44, FTV55, and FTV70 to determine the best parameter values. The ANOVA results show that the Bound parameter affects the solution in the FTV33, FTV44, and FTV70 cases, while the max_ctime parameter affects the solution in the FTV55 case. Based on the determined parameter values, the LSA with 2-Opt was re-implemented on the five ATSP cases. The results show that the LSA with 2-Opt was able to find the best-known solution for the BR17 case but was unable to find the best-known solution for the other cases.
References
Brest, J., & Zerovnik, J. (2003). An Approximation Algorithm for the Asymmetric Traveling Salesman Problem. Elektrotehniski Vestnik/Electrotechnical Review, 70(1).
Croes, G. (1958). A Method for Solving Traveling-Salesman Problems. Operations Research, 6(6), 791-812. doi:https://doi.org/10.1287/opre.6.6.791
Elim, Y. (2018). Penerapan lion optimization algorithm untuk menyelesaikan kasus asymmetric traveling salesman problem. Skripsi, Universitas Katolik Parahyangan, Industrial Engineering, Bandung.
Geem, Z. W., Kim, J. H., & Loganathan, G. V. (2001). A New Heuristic Optimization Algorithm: Harmony Search. Simulation, 76(2), 60-68. doi:https://doi.org/10.1177/003754970107600201
Gutin, G., & Punnen, A. (2002). The Traveling Salesman Problem and Its Variations (Vol. 12). Springer Science & Business Media.
Johnson, D. S., & McGeoch, L. A. (2003). The traveling salesman problem: a case study. In E. Aarts, & J. K. Lenstra, Local Search in Combinatorial Optimization (pp. 215-310). Princeton: Princeton University Press. doi:https://doi.org/10.1515/9780691187563-011
Kevin, P. (2016). Penerapan harmony search algorithm untuk menyelesaikan kasus asymmetric traveling salesman problem. Skripsi, Universitas Katolik Parahyangan, Industrial Engineering, Bandung.
Lawler, E. L., Lenstra, J. K., Kan, R. A., & Shmoys, D. B. (1985). The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization. Chichester: Wiley.
Reinelt, G. (1991). TSPLIB-A Traveling Salesman Problem Library. ORSA Journal on Computing, 3(4), 376-384.
Santosa, I. (2017). Penyelesaian kasus asymmetric traveling salesman problem untuk meminimasi jarak tempuh menggunakan algoritma elephant herding optimization. Skripsi, Universitas Katolik Parahyangan, Industrial Engineering, Bandung.
Shareef, H., Ibrahim, A. A., & Mutlag, A. H. (2015). Lightning search Algorithm. Applied Soft Computing, 36, 315-333. doi:https://doi.org/10.1016/j.asoc.2015.07.028
Talbi. (2009). Metaheuristics: From Design to Implementation. New Jersey: John Wiley & Sons, Inc.
Wang, G.-G., Deb, S., & Coelho, L. d. (2015). Elephant Herding Optimization. 2015 3rd International Symposium on Computational and Business Intelligence (ISCBI), (pp. 1-5). Bali. doi:10.1109/ISCBI.2015.8.
Winston, W. L., & Goldberg, J. B. (2004). Operations Research: Applications and Algorithms (4 ed.). Canada: Thomson Learning-Brooks/Cole.
Yazdani, M., & Jolai, F. (2016). Lion Optimization Algorithm (LOA): A nature-inspired metaheuristic algorithm. Journal of Computational Design and Engineering, 3(1), 24-36. doi:https://doi.org/10.1016/j.jcde.2015.06.003
