Solution Approaches for Sequence Dependent Traveling Salesman Problem
Sıraya Dayalı Seyyar Satıcı Problemi için Çözüm Yaklaşımları
- Tez No: 390682
- Danışmanlar: YRD. DOÇ. DR. ALİ FUAT ALKAYA
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2013
- Dil: İngilizce
- Üniversite: Marmara Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 72
Özet
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.
Özet (Çeviri)
The Sequence Dependent Traveling Salesman Problem (SDTSP) is a combinatorial optimization problem defined as a generalization of the TSP. It emerged during optimization of two kind of commonly used placement machines for production of printed circuit boards. The difference between SDTSP and TSP is that the cost incurred by transition from one point to another is dependent not only the distance between these points but also subsequent k points. In this study, we applied Simulated Annealing (SA), Artificial Bee Colony (ABC) and Migrating Birds Optimization (MBO) to solve real-world and random SDTSP instances. The metaheuristics were tested with 10 neighbour functions. In our computational study, we conducted five sets of computational experiments. Firstly, we obtained best parameter value combination for each metaheuristic. Secondly, we conducted experiments so as to determine best performing neighbour function for each metaheuristic. Thirdly, metaheuristic comparison tests were conducted. As a result, SA outperformed MBO and ABC. These tests were followed by the tests conducted to reveal how a parameter peculiar to the problem affects the complexity of the problem both in terms of run time and solution quality. As this parameter value increases, performances shown by all metaheuristics decrease. Therefore, we concluded that SDTSP is much more challenging than TSP. Finally, we programmed the mathematical model of the problem by means of GAMS and we obtained the best upper-bound solutions of some small-scale problem instances. These solutions were compared with those obtained by the metaheuristics and we observed that solution quality performance of the metaheuristics are comparable to the best upper-bound solutions returned from GAMS. In addition, we observed that the time required for obtaining the best upper-bound solution of an SDTSP instance increases exponentially with the problem size. Consequently, we deduced that using these metaheuristics to obtain solutions for medium- and large-scale instances of SDTSP and similar problems is a good choice.
Benzer Tezler
- A Hierarchical production planning model with sequence dependent set-up times
Başlık çevirisi yok
SERDAR AKIN
Yüksek Lisans
İngilizce
1993
Endüstri ve Endüstri MühendisliğiBoğaziçi ÜniversitesiDOÇ.DR. GÜLAY BARBAROSOĞLU
- Melez üretim sisteminde CONWIP kontrolü ve parti bölmesinin birlikte modellenmesi
Modelling of a hybrid manufacturing system with lot splitting under CONWIP production control
CANAN AĞLAN
Doktora
Türkçe
2014
Endüstri ve Endüstri Mühendisliğiİstanbul Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. MEHMET BÜLENT DURMUŞOĞLU
- EMPT ile enerji iletim sistemlerinde açma-kapama olayları analizleri
Switching phenomena analyses of power transmission systems with EMTP
TANER DENİZ
Yüksek Lisans
Türkçe
1995
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiDOÇ.DR. ADNAN KAYPMAZ
- Enerji iletim sistemlerinde açma-kapama olaylarının analizleri için hat parametrelerinin EMTP yardımıyla hesabı
Calculation of line parameters for the analyses of power system switching transient using EMTP
KORAY ŞERBETÇİOĞLU
Yüksek Lisans
Türkçe
1995
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiDOÇ.DR. ADNAN KAYPMAZ
- Enerji sistemlerinde geçici olayların analizinde bilgisayar desteğinin etkisi
The Effect of computer aid on analysis of power system transients
ERKAN MEŞE
Yüksek Lisans
Türkçe
1993
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiPROF.DR. NESRİN TARKAN