Penerapan Lightning Search Algorithm dengan Local Search untuk menyelesaikan Asymmetric Traveling Salesman Problem

Abstract

Asymmetric Traveling Salesman Problem (ATSP) adalah suatu permasalahan optimasi dimana terdapat seorang “salesman” yang harus mengunjungi beberapa kota dalam satu kali perjalanan. Setiap kota hanya boleh dikunjungi satu kali saja dan pada akhir kunjungan harus kembali ke kota pertama. ATSP merupakan salah satu variasi dari permasalahan Traveling Salesman Problem (TSP). Perbedaannya terdapat pada jarak yang ditempuh dari kota i ke j dapat berbeda dengan jarak dari kota j ke i. Tujuan dari ATSP adalah meminimasi jarak total yang ditempuh oleh sang “salesman”. ATSP diselesaikan dengan menggunakan Lighning Search Algorithm (LSA) dan 2-Opt Local Search Algorithm. LSA adalah sebuah algoritma metaheuristik yang terinspirasi dari proses perambatan lidah petir (step leader). Terdapat 3 buah parameter pada LSA, yaitu maximum channel time (max_ctime), forking probability (fork_prob), dan Boundaries (Bound). 2-Opt merupakan algoritma local search yang memecah sebuah rute menjadi dua sub-rute, dan salah satu sub-rute dimanipulasi sedemikian rupa yang kemudian kedua sub-rute akan digabungkan kembali. LSA dengan local search telah dirancang dan dapat menyelesaikan permasalahan ATSP. Nilai parameter terbaik didapat dengan metode 2k factorial experiment dan trial and error. LSA diimplementasi dan dibandingkan dengan Elephant Herding Optimization (EHO), Harmony Search Algorithm (HSA), dan Lion Optimization Algorithm (LOA). Algoritma LSA mencapai best known solution pada kasus BR17, dan menghasilkan solusi yang lebih baik dari LOA pada kasus FTV33, FTV44, FTV55, dan FTV70. LSA juga mampu menghasilkan solusi lebih baik dari HSA tetapi masih lebih buruk dari EHO pada kasus FTV33. Pada kasus FTV44, FTV55, dan FTV70 EHO dan HSA menghasilkan solusi yang lebih baik dari LSA.