Çok amaçlı karesel atama problemleri için matematiksel ve sezgisel çözüm yaklaşımları

Abstract

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.