Solution approaches for sequence dependent traveling salesman problem
Samet Tonyalı · Dspace Repository (Marmara Üniversitesi) · 2013
Sıraya Dayalı Seyyar Satıcı Problemi için Çözüm Yaklaşımları Sıraya Dayalı Seyyar Satıcı Problemi (SDSSP), Seyyar Satıcı Problemi’nin (SSP) genellemesi olarak tanımlanmış bir birleşimsel eniyileme problemidir. Bu problem, Baskılı Devre Kartı (BDK) üretiminde çokça kullanılan iki önemli dizgi makine tipinin eniyilenmesi sırasında ortaya çıkmıştır. SDSSP’yi SSP’den ayıran fark şu şekilde ifade edilebilir: SDSSP’de bir noktadan diğerine gitmenin maliyeti sadece noktalar arasındaki uzaklığa değil, gezinme sırasında sonradan gelecek k tane noktanın hangileri olduğuna da bağlıdır. Bu çalışmada, Benzetimli Tavlama (BT), Yapay Arı Kolonisi (YAK) ve Göç eden Kuşlar (GK) isimli üç üstsezgiselden yararlandık. Bu üstsezgiseller 10 komşu fonksiyonu ile test edildi. Yaptığımız sayısal çalışmada, beş ayrı kümeden oluşan testler yaptık. İlk olarak, her bir üstsezgisel için en iyi parametre kombinasyonunu elde ettik. Daha sonra her bir üstsezgiselin en iyi başarım gösterdiği komşu fonksiyonu belirlemek için testler yaptık. Bu testlerden sonra üstsezgisellerin başarımlarını karşılaştırmak için testler yaptık. BT, GK ve YAK’tan daha iyi başarım gösterdi. Bu testleri, problem özgün önemli bir parametrenin problemin karmaşıklığını hem çözüm kalitesi hem de çalışma zamanı açısından nasıl etkilediğini ortaya çıkarmak için yaptığımız testler takip etti ve bu parametrenin değerinin artmasıyla üstsezgisellerin başarımının düştüğünü gözlemledik. Burdan yola çıkarak SDSSP’nin SSP’den çok daha zor bir problem olduğu sonucuna vardık. Son olarak, problemin matematiksel modelini, GAMS’i kullanarak programladık ve bazı küçük ölçekli problem örnekleri için en iyi üst sınır çözümlerini elde ettik. Üstsezgisellerin aynı örnekler için elde ettiği çözümlerle karşılaştırdık ve üstsezgisellerin performansının problemin büyüklüğü arttıkça en iyi üst sınır çözümleriyle kıyaslanabilir olduğunu gözlemledik. Yaptığımız testler sonucunda, en iyi üst sınır çözümlerini elde etmek için gereken zamanın, problemin büyüklüğüyle üssel olarak arttığını gözlemledik. Bunun bir sonucu olarak, SDSSP ve benzeri problemlerin orta ve büyük ölçekli örneklerinin çözümlerini elde etmede, bu üstsezgiselleri kullanmanın iyi bir tercih olduğu sonucuna vardık.