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.