Çok amaçlı karesel atama problemleri için matematiksel ve sezgisel çözüm yaklaşımları
Mathematical and heuristics solution approaches to the multiobjective quadratic assignment problems
Yazar: MERVE ULUEL
Danışman: YRD. DOÇ. DR. ZEHRA KAMIŞLI ÖZTÜRK
Anadolu Üniversitesi / Fen Bilimleri Enstitüsü / Endüstri Mühendisliği Ana Bilim Dalı
Derece: Yüksek Lisans, 2016
Konu: Endüstri ve Endüstri Mühendisliği = Industrial and Industrial Engineering

Özet:
Karesel atama problemleri (QAP) 1957 yılında Koopmans ve Beckman tarafından geliştirilmiştir. Amaç tesis ve lokasyonlar arasındaki atamaların toplam maliyetinin enküçüklenmesinin sağlanmasıdır. QAP'ın matematiksel modelindeki kısıtlar 0-1 tamsayı atama kısıtları iken, amaç fonksiyonu da karesel yapıya sahip olduğu için doğrusal olmayan bir fonksiyondur. Bu iki nedenle, karesel atama problemleri çok zor problem sınıfına (NP-Zor) girmektedir ve 20'den fazla lokasyona sahip problemler için en iyi çözümün bulunması neredeyse imkânsızdır.
2002 yılında ise gerçek hayat problemlerinin çok amaçlı yapıya sahip olması nedeniyle, Çok Amaçlı Karesel Atama Problemi (mQAP) Knowles ve Corne tarafından geliştirilmiştir. Bundan sonra 2005 yılı itibariyle farklı yazarlar tarafından bu konu ile ilgili farklı çözüm yaklaşımları sunan çalışmalar yapılmıştır. Bu çalışmalar sezgisel ve metasezgisel algoritmalar temeline dayanmaktadır. 
mQAP da, QAP gibi NP-Zor problem sınıfındadır. Ayrıca çözümü için doğrusal olmayan birden fazla amacın ele alınması gerekmektedir. Bu çalışmada, henüz literatürde nispeten yeni bir konu olan mQAP için bilinen test problemleri ele alınmış ve özellikle doğrusal olmayan yapıdaki çok amaçlı problemlerin çözümünde etkinliği kanıtlanmış Konik Skalerleştirme yöntemi ve çok amaçlı evrimsel algoritmalarından biri olan NSGA-II algoritması ile mQAP problemlerine çözüm aranmıştır. Çalışma sonucunda ayrıca evrimsel algoritma ve skalerleştirme yöntemlerinin güçlü yönleri bir araya getirilerek melez bir algoritma geliştirilmiştir. Elde edilen sonuçlar literatürdeki diğer yöntemlerle elde edilen sonuçlarla karşılaştırılarak performansları incelenmiştir.

Abstract:
Quadratic Assignment Problems (QAP) were firstly defined by Koopmans and Beckmann in 1957. For this problem, the objective is cost minimization of total assignment between locations and facilities. While the constraints of QAP are 0-1 assignment constraints, the objective function is nonlinear because of the quadratic structure. Based on these two reasons, QAP is classified as NP-Hard. And it is almost impossible to find optimal solutions for number of locations are greater than 20. 
Because of the fact that the multiobjective structure of real life problems, Multiobjective Quadratic Assignment Problems (mQAP) are suggested by Knowles and Corne in 2002. After this, as regards 2005, different researchers have studied about this subject based on different solution approaches. These studies are about heuristics and metaheuristic algorithms. 
mQAP is also a NP-Hard problem like QAP. In addition, more than one nonlinear objective function have to be considered. In this study, mQAP which is a relatively new subject in the literature will be studied. And we will handle test problems from the literature and seek solutions with conic scalarization method. Conic scalarization method's effectiveness is proved in solution of multiobjective problems with non-linear structure. We also seek solutions with one of the multiobjective evolutionary algorithm NSGA-II. At the end of this study, we propose a hybrid method with evolutionary algorithm and scalarization method. Obtained results were compared with the results from the other methods in the literature and performances were compared.