Strategi Kombinasi untuk Menyelesaikan Quadratic Assignment Problem

Abstract

The quadratic assignment problem is a combinatorial problem of deciding the placement of facilities in specified locations in such a way as to minimize a nonconvex objective function expressed in terms of flow between facilities, and distance between location. Due to the non-convexity nature of the problem, therefore to get a good starting point is necessary in order to obtain a better optimal solution. In this paper we propose a combination strategy (random point strategy to get initial starting point and then forward exchange strategy and backward exchange strategy) to get optimal solution. As a computational experience we solve the problem of Had12, Esc 16b, Esc 16c and Esc 16h from QAPLIB. Finally, we present a comparative study between Combination Strategy, Data-Guided Lexisearch Algorithm (DGLSA), and Discrete Linear Reformulation (DLR). The computational study shows the effectiveness of our proposed Combination Strategy.

Quadratic Assignment Problem (QAP) adalah suatu permasalahan kombinatorial dalam menentukankan penempatan fasilitas pada lokasi tertentu sedemikian rupa sehingga meminimumkan fungsi tujuan nonconvex yang dinyatakan dalam bentuk alur antar fasilitas, dan jarak antar lokasi. Oleh karena sifat non-konveksitas dari masalah, maka diperlukan suatu titik awal yang ’baik’ untuk mendapatkan solusi optimal yang lebih baik. Dalam makalah ini penulis mengusulkan strategi kombinasi (dengan menggunakan random point strategy untuk mendapatkan titik awal, kemudian dilanjutkan dengan forward exchange strategy dan backward exchange strategy) untuk mendapatkan solusi ’optimal’. Sebagai pengalaman komputasi penulis menyelesaikan problema Had12, Esc 16b, Esc 16c dan Esc 16h dari QAPLIB. Akhirnya, penulis menyajikan studi komparatif antara Strategi Kombinasi, Data Guided Lexisearch Algorithm (DGLSA), dan Discrete Linear Reformulation (DLR). Studi komputasi menunjukkan efektivitas dari Strategi Kombinasi yang penulis usulkan.