ResearchBib Share Your Research, Maximize Your Social Impacts
Sign for Notice Everyday Sign up >> Login

Optimal Solution of a Large-scale Travelling Salesman Problem applying DNN and k-opt

Journal: The Journal of the Institute of Internet, Broadcasting and Communication (Vol.15, No. 4)

Publication Date:

Authors : ;

Page : 249-257

Keywords : Traveling salesman roblem; Exhaustive search method; Edge exchange method; Heuristic method; Double-sided nearest neighbor search;

Source : Downloadexternal Find it from : Google Scholarexternal

Abstract

This paper introduces a heuristic algorithm to NP-hard travelling salesman problem. The proposed algorithm, in its bid to determine initial path, applies SW-DNN, DW-DNN, and DC-DNN, which are modified forms of the prevalent Double-sided Nearest Neighbor Search and searches the minimum value. As a part of its optimization process on the initial solution, it employs 2, 2.5, 3-opt of a local search k-opt on candidate delete edges and 4-opt on undeleted ones among them. When tested on TSP-1 of 26 European cities and TSP-2 of 49 U.S. cities, the proposed algorithm has successfully obtained optimal results in both, disproving the prevalent disbelief in the attainability of the optimal solution and making itself available as a general algorithm for the travelling salesman problem.

Last modified: 2015-11-23 10:31:36