PENYELESAIAN QUADRATIC ASSIGNMENT PROBLEM (QAP) DENGAN ALGORITMA ANT COLONY OPTIMIZATION (ACO)

Abstract

ABSTRACT

Quadratic Assignment Problem (QAP) is one extension of the assignment problem by setting n facilities to n certain locations to minimize the total assignment costs. QAP is also a combinatorial optimization problem that is a problem that has a finite set of solutions. Basically the solution of combinatorial problems can be obtained with the right results but for complex problems with larger data sizes it is quite difficult to calculate because the time used is long enough for the completion process. One of the algorithms implemented in the completion of QAP is the Ant Colony Optimization (ACO) algorithm is an algorithm that mimics the behavior of ants in finding food from the nest to a food source with the help of indirect communication called pheromone, so that pheromone is used to find optimal solutions with quite a short time. in this research ACO is used to solve the QAP problem by using a random proportional of rule formula then getting the smallest solution and renewing the pheromone until the assignment is stable and the solution obtained is fixed until the maximum assignment solution. The results obtained to complete the Quadratic Assignment Problem with the Ant Colony Optimization algorithm to get a solution to the QAP problems tested in the Nugent case resulted in a more minimal solution and the placement of appropriate location facilities through pheromone assistance and stored in a taboo list so that all facilities get a decent location with a worth it short time in completion.

Keywords: Quadratic Assignment Problem, Ant Colony Optimization, tabu list, pheromone

ABSTRAK

Quadratic Assignment Problem (QAP) merupakan salah satu perluasan dari masalah penugasan dengan menetapkan n fasilitas ke n lokasitertentu untuk meminimalkan total biaya penugasan. QAP juga merupakan masalah optimasi kombinatorial yaitu masalah yang mempunyai himpunan solusi terhingga. Pada dasarnya solusi dari masalah kombinatorial bisa didapatkan dengan hasil yang tepat namun untuk masalah kompleks dengan ukuran data yang lebih besar cukup sulit dalam perhitungan karena waktu yang digunakan cukup lama untuk proses penyelesaian. Salah satu algoritma yang diterapkan dalam penyelesaian QAP ini adalah algoritma Ant Colony Optimization (ACO) yaitu algoritma yang meniru tingkah laku semut dalam mencari makanan dari sarang ke sumber makanan dengan bantuan komunikasi tak langsung yang disebut pheromone, sehingga pheromone ini digunakan untuk mencari solusi optimal dengan waktu yang cukup singkat. pada penelitian ini ACO digunakan untuk menyelesaikan masalah QAP dengan menggunakan rumus random proportional rule kemudian mendapatkan solusi terkecil dan memperbaharui pheromone hingga penugasan stabil dan solusi yang didapatkan bernilai tetap sampai solusi maksimum penugasan. Hasil yang diperoleh untuk menyelesaikan Quadratic Assignment Problem dengan algoritma Ant Colony Optimization untuk mendapatkan solusi dari permasalahan QAP yang diujicobakan pada kasus Nugent menghasilkan solusi yang lebih minimal dan penempatan fasilitas kelokasi yang tepat melalui bantuan pheromone dan disimpan dalam tabu list sehingga semua fasilitas mendapatkan lokasi yang layak dengan waktu yang cukup singkat dalam penyelesaian.

Kata kunci: Quadratic Assignment Problem, Ant Colony Optimization, tabu list, pheromone

[1]      Hillier, S. F. dan Lieberman. 2004. Introduction To Operations Research.   Eighth Edition, New York: Mc Graw-Hil.

[2]      Cela Erlanda. 1998. The Quadratic Assignment Problem. Springer Science and  Business Media Dordrecht

[3]      Dorigo Marco & Stutzle Thomas. 2004. Ant Colony Optimization. Massachusetts Institute of Technology

[4]      Hahn, P, & Grant, T. 1998. Lower Bounds for the Quadratic Assignment Problem Based Upon a Dual Formulation”. Operation Research,Vol.46, No.6.

[5]      Bidyarthy S. Anjay & Gupta Vivek. 2013. Ant Colony Optimization for Quadratic Assignment Problem and School Bus Routing Problem. Departementof Mathematics Indian Institute of Technology Guwahati. Guwahati - 781039

 [6]     Davendra, D & Zelinka, I. 2009. Optimization Of Quadratic Assignment Problem Using Self Organising Migrating Algorithm. Computing and Informatics, Vol. 28, 1001–1012

 [7]     Nugent E. Christopher, dkk 1967. An Experimental Comparison Of Tech-Niques For The Assignment Of Facilities To Locations INFORMS

[8]      Nyberg Axel. 2014. Some Reformulations for the Quadratic Assignment Problem. Department of Chemical Engineering Åbo Akademi University

  http://www.qaplib/inst.html

(diakses tanggal 16 Januari 2017)