Penerapan algoritma intelligent water drops untuk menyelesaikan quadratic assignment problem

Abstract

Quadratic Assignment Problem (QAP) merupakan salah satu permasalahan optimasi kombinatorial yang dapat ditemukan pada suatu pabrik, baik pada pabrik baru maupun bukan. Secara umum dapat dikatakan bahwa QAP merupakan suatu permasalahan pengalokasian fasilitas pada lokasi yang tersedia dengan mempertimbangkan flow antarfasilitas dan jarak antarlokasi. Pada dasarnya, semakin rumit suatu kasus QAP, ditandai dengan jumlah lokasi dan atau jumlah fasilitas yang semakin banyak, maka akan semakin banyak pula solusi yang dapat terjadi, sehingga akan semakin sulit untuk mendapatkan solusi yang optimal. Oleh karena itu, QAP kerap kali diselesaikan dengan menggunakan metode heuristik, antara lain Construction Procedure dan Improvement Procedure. Penelitian ini menggunakan algoritma Intelligent Water Drops (IWD) untuk menyelesaikan QAP. QAP merupakan salah satu metode heuristik yang cara kerjanya terinspirasi oleh proses yang dialami oleh tetesan air yang bergerak dari sumber ke tujuan melalui berbagai titik dan jalur. Penelitian ini dilakukan untuk menerapkan algoritma IWD untuk menyelesaikan QAP, mengetahui parameter algoritma yang berpengaruh pada solusi yang dihasilkan pada setiap kasus yang diuji dan secara umum, serta membandingkan performansi algoritma IWD dalam menyelesaikan QAP dengan menggunakan algoritma Viral System (VS) dan nilai lower bound sebagai pembanding pada setiap kasus yang duji dan secara umum. Penelitian ini mendapatkan kesimpulan bahwa algoritma IWD dapat diterapkan untuk menyelesaikan QAP. Berdasarkan pengujian pengaruh parameter yang telah dilakukan, didapatkan hasil bahwa terdapat 2 parameter algoritma IWD yang paling berpengaruh pada solusi yang dihasilkan, yaitu pembaharu jumlah tanah pada jalur IWD dan parameter pembaharu jumlah tanah pada jalur solusi terbaik iterasi. Parameter pembaharu jumlah tanah pada jalur IWD dinyatakan berpengaruh pada solusi yang dihasilkan algoritma IWD secara umum, sedangkan parameter pembaharu jumlah tanah pada jalur solusi terbaik iterasi memiliki pengaruh pada kasus yang relatif sederhana. Kesimpulan lain yang didapatkan melalui penelitian ini adalah berkenaan dengan performansi algoritma IWD dibandingkan dengan algoritma VS. Berdasarkan pengujian yang telah dilakukan, dapat disimpulkan bahwa secara umum algoritma IWD memiliki performansi yang lebih baik dibandingkan algoritma VS pada kasus yang relatif rumit.