Solution approaches for sequence dependent traveling salesman problem

Sıraya Dayalı Seyyar Satıcı Problemi için Çözüm Yaklaşımları\nSı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.\nBu ç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.\nABSTRACT\nSolution Approaches for Sequence Dependent Traveling Salesman Problem\nThe 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.\nIn 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.