Penyelesaian Traveling salesman Problem With Time Windows untuk meminimasi cost dengan algoritma Grey Wolf Optimizer

Abstract

Traveling Salesman Problem with Time Windows (TSPTW) merupakan sebuah kasus permasalahan yang menganalogikan seorang salesman yang harus memenuhi tugasnya untuk mengunjungi setiap kota yang ada dalam rentang waktu yang telah ditetapkan untuk masingmasing kotanya. Permasalahan ini bersifat non-deterministic polynomial Hard atau sering dikatakan NP-Hard. Hal tersebut dikarenakan permasalahan TSPTW jika semakin banyak jumlah kota maka akan semakin lama waktu komputasi yang dibutuhkan untuk menyelesaikannya. Selain itu juga terdapat time windows yang mengakibatkan banyaknya solusi yang infeasible. Salah satu metode yang dapat memberikan waktu komputasi yang cepat adalah metode metaheuristik. Salah satu algoritma metaheuristik adalah Grey Wolf Optimizer. Grey Wolf Optimizer adalah salah satu algoritma metaheuristik yang meniru perilaku daripada serigala dalam perilaku memburu mangsa. Pada algoritma GWO ini terdapat 4 jenis serigala yaitu alfa, beta, delta, dan omega. GWO diimplementasikan ke dalam 9 kasus TSPTW yang terdiri dari 5 sub-kasus untuk setiap kasusnya. Implementasi GWO menggunakan 8 kombinasi parameter dengan 5 kali replikasi. Kombinasi tersebut berasal dari 3 buah parameter dan masing-masing terdiri dari 2 level. Parameter yang diuji adalah jumlah serigala (n), jumlah iterasi (T), dan nilai awal parameter a (nawal). Hasil pengujian pengaruh parameter menunjukkan adanya pengaruh dari masing-masing parameter pada kasus TSPTW. Penelitian ini juga melakukan perbandingan performansi antara algoritma GWO dengan algoritma Tabu Search dan algoritma Compressed Annealing (CA). Hasil implementasi algoritma GWO menunjukkan bahwa performansi algoritma GWO sangat baik dalam permasalahan kasus 20 kota, akan tetapi algoritma GWO belum dapat menghasilkan solusi yang lebih baik daripada benchmark pada sebagian kasus 40 kota dan seluruh kasus 60 kota.