Optimasi Rute Rencana Perjalanan Pesawat Menggunakan Algoritma Late Acceptance Hill Climbing (Studi Kasus : Travelling Salesman Challenge 2.0) - Ahmad Muklason; I Gusti Agung Premananda (Jurnal Teknologi Informasi dan Ilmu Komputer)
Permasalahan Traveling Salesman Problem (TSP) merupakan permasalahan klasik yang popular diteliti dalam bidang optimasi kombinatorika. Permasalahan ini bertujuan menentukan rute perjalanan terpendek untuk  mengunjungi setiap lokasi tepat satu kali dan diakhir perjalanan harus kembali ke lokasi awal perjalanan dimulai. Permasalahan ini telah digolongkan sebagai permasalahan NP-Hard, sehingga membutuhkan algoritma non-deterministic untuk dapat menyelesaikan permasalahan ini. Dalam permasalahan nyata, salah satu penerapan TSP ada pada permasalahan untuk menentukan rute perjalanan termurah untuk mengunjungi beberapa kota di beberapa negara. Kompetisi Travelling Salesman Challenge 2.0 (TSC 2.0) mengangkat permasalahan ini dalam sebuah kompetisi pada tahun 2018. Untuk menyelesaikan studi kasus tersebut, penelitian ini menyembangkan algoritma Late Acceptance Hill Climbing (LAHC) menggunakan metode hiper-heuristik. Algoritma LAHC merupakan algoritma yang sederhana namun telah terbukti mampu mengoptimasi dengan baik pada beberapa permasalahan TSP. Algoritma LAHC diuji coba pada 14 dataset dari TSC 2.0. Hasil penelitian menunjukan algoritma LAHC menghasilkan solusi yang kompetitif dengan mampu menurunkan biaya perjalanan dengan rata-rata 58% dan menghasilkan hasil yang lebih baik dengan rata-rata 9% dari algoritma Threshold Acceptance (TA) yang digunakan sebagai algoritma pembanding.