Penerapan Lightning Search Algorithm dengan 2-Opt Local Search untuk Penyelesaian Asymmetric Traveling Salesman Problem - Gunawan, Yulius Chandra; Sandy, Ignatius A. (Jurnal Rekayasa Sistem Industri, 2024)
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.