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 masing-masing 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.