Abstract:

In this study, a novel solution algorithm taking advantage of the relationship between traveling salesman and transportation problems that are the most studied problems of operations research field since 1800s, is proposed. Many initial solution algorithms have been proposed for transportation problems. In this study, an approach called TPORT is proposed for the initial solution for the symmetric traveling salesman problem with similar approach and intuition. The performance of the initial solutions is developed with 2-Opt algorithm. As the developed heuristic has similarities with the nearest neighbor algorithm, the solution performances of the traveling salesman problems were compared with the solutions of the nearest neighbor algorithm and 2-Opt. The proposed approach has been analyzed by the well-known traveling salesman test instances and a group of test instances from the literature. The average solution performance of the proposed method was 26%, while the performance of the nearest neighbor algorithm was 16%. However, when the solutions of TPORT and nearest neighbor algorithm were developed with 2-Opt, the average deviation was obtained as 4% and 3%, respectively. In this context, it can be argued that the proposed solution approach is competitive in terms of solution performance. Also, there is a huge difference between the proposed method and the nearest neighbor algorithm in terms of solution times. As a result, it has been shown that the proposed method with 2-Opt improvement is superior for both the solution speed and the quality of the solutions. In particular, as the problem size is increased, the solution time of the comparable methods is almost constant, while the solution time of the nearest neighbor algorithm shows an asymptotic trend.

Keywords: