Solution Approaches for Sequence Dependent Traveling Salesman Problem

---

Tezin Türü: Yüksek Lisans

Tezin Yürütüldüğü Kurum: Marmara Üniversitesi, Mühendislik Fakültesi, Bilgisayar Mühendisliği Bölümü, Türkiye

Tezin Onay Tarihi: 2013

Tezin Dili: İngilizce

Öğrenci: SAMET TONYALI

Danışman: Ali Fuat Alkaya

Açık Arşiv Koleksiyonu: AVESİS Açık Erişim Koleksiyonu

Özet:

Solution Approaches for Sequence Dependent Traveling Salesman Problem 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.