Penerapan Lightning Search Algorithm dengan 2-Opt Local Search untuk Penyelesaian Asymmetric Traveling Salesman Problem
DOI:
https://doi.org/10.26593/jrsi.v13i2.7760.191-202Kata Kunci:
Lightning Search Algorithm, Metaheuristik, Local Search, Asymmetric Traveling Salesman Problem, Optimization ProblemAbstrak
Asymmetric Traveling Salesman Problem (ATSP) adalah suatu permasalahan optimasi dimana terdapat seorang “salesman” yang harus mengunjungi beberapa kota dalam satu kali perjalanan. Pada ATSP, jarak yang ditempuh dari kota i ke j berbeda dengan jarak dari kota j ke i. Tujuan dari ATSP adalah meminimasi total jarak yang ditempuh oleh “salesman”. Pada penelitian ini Lightning Search Algorithm (LSA) dan 2-Opt local search algorithm digunakan untuk menemukan solusi dari ATSP. LSA adalah sebuah algoritma metaheuristik yang terinspirasi dari proses perambatan lidah petir (step leader) ke permukaan bumi. 2-Opt merupakan algoritma local search yang dapat memanipulasi rute agar menghasilkan solusi yang lebih baik. Penelitian ini bertujuan untuk merancang LSA dengan 2-Opt dalam menyelesaikan ATSP dan menemukan parameter yang berpengaruh terhadap solusi ATSP. Tiga parameter digunakan dalam penelitian ini, yaitu maximum channel time (max_ctime) dan forking probability (fork_prob) yang bertanggungjawab atas terjadinya fenomena forking, dan Boundaries (Bound) yang mendefinisikan ruang solusi. Pengujian ANOVA dilakukan terhadap 8 kombinasi parameter yang diimplementasi ke 5 kasus ATSP dari TSPLIB, yaitu kasus BR17, FTV33, FTV44, FTV55, dan FTV70 untuk menentukan nilai parameter terbaik. Hasil ANOVA menunjukkan parameter Bound berpengaruh terhadap solusi pada kasus FTV33, FTV44, dan FTV70. Sedangkan parameter max_ctime berpengaruh terhadap solusi pada kasus FTV55. Berdasarkan nilai parameter yang ditentukan, LSA dengan 2-Opt diimplementasikan kembali ke 5 (lima) kasus ATSP. Hasil yang didapat adalah LSA dengan 2-Opt mampu menemukan best known solution untuk kasus BR17, tetapi tidak mampu menemukan best known solution untuk kasus lain-nya.
Referensi
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
