Application of Recently Proposed Metaheuristics to the Sequence Dependent TSP

Abstract

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 kinds 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 neighbor functions. In our computational study, we conducted extensive computational experiments. Firstly, we obtained best parameter value combination for each metaheuristic. Secondly, we conducted experiments so as to determine best performing neighbor function for each metaheuristic. Computational experiments show that twoopt function can be considered as the most suitable function for all the three metaheuristics.