A Heuristic Solution Algorithm to Quadratic Assignment Problem

Abstract

Kareli Atama Problemleri, matematikteki tesis yerleşimi problemleri kategorisinden eniyileme veya yöneylem araştırması dalı içinde kombinatoryal eniyileme problemlerinden biridir. Tesis içi planı ve yerleşim çalışmalarında çoğunlukla görülen atama probleminin özel bir halidir. Kareli Atama Problemleri’nin klasik atama problemlerinden farkı doğrusal olmayan amaç fonksiyonunu esas alan atama çiftleri arasında bir etkileşim olmasıdır. Tesis yerleşim tasarımı problemleri, çeşitli akış ilişkilerinin de değerlendirilmesini gerektiren problemlerdir ve literatürde Kareli Atama Problemleri olarak çözümlendirilmesi yoluna sıkça gidilmiştir. Kareli Atama Problemi NP-zor sınıfında olan en zor problemlerden biridir. Kareli Atama Problemi olarak modellenen problemler için yeniden çözme tekniklerinden yola çıkılarak, en iyi sonuç elde edilenden sezgisel yaklaşıma ve yarı sezgisel yaklaşıma kadar farklı birçok metot mevcuttur. En iyi sonuç elde edilen metotlarla problemleri çözmek çok uzun zaman gerektirmektedir. Bu çalışmada, literatürde Kareli Atama Problemleri için en iyi sonuç elde edilen metotlar, en iyi sonucu bulunamayan problemler için geliştirilen sezgisel, yarı sezgisel birçok metot ve bunların Kareli Atama Problemi örnekleri üzerinde çözülebilirliği ve yeni geliştirilen yöntemler incelenmiştir. Bu çalışma, Kareli Atama problemlerinin sezgisel bir optimizasyon tekniği olan genetik algoritma ve komşuluk yaklaşımı ile çözümünü içermektedir. Çalışmada, geliştirilen genetik algoritma yaklaşımının Kareli Atama Problemi örnekleri üzerinde çözülebilirliği incelenmiştir.

Alternate abstract:

The quadratic assignment problem is one of fundamental combinatorial optimization problems in the branch of optimization or operations research in mathematics. The quadratic assignment problem is a special kind of assignment problem frequently seen in layout and location studies. The main difference between this problem and the classic assignment problem is that in this problem there are interactions between assignment pairs, leading to a non-linear objective function. Facility layout problems are problems that are needed the assessment of various flow relationship and in the literature Quadratic Assignment Problem is frequently used for solving these problems. This problem is one of the most difficult problems in the NP-hard class, which implies that finding a polynomial time algorithm to solve it is unlikely. In regards to the resolution techniques modeled as quadratic assignment problem, there are different methods ranging from exact to heuristic and meta-heuristic ones. It takes a long time to have an optimum solution with exact algorithms, so several heuristics have been proposed for handling near optimum solutions. In this thesis, a genetic algorithm as a heuristic optimization technique and neighborhood approximation is developed. This new algorithm’s solvability in benchmark problem instances is tested and results are listed.