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: 2015-08-31
Authors : Sang-Un Lee;
Page : 249-257
Keywords : Traveling salesman roblem; Exhaustive search method; Edge exchange method; Heuristic method; Double-sided nearest neighbor search;
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.
Other Latest Articles
- A Study on Characteristics of Passenger Injury for Effective Impact Speed in Vehicles Frontal Collision and Rear-ender
- CMXML: A Conceptual Modeling Methodology for XML
- Simple Algorithm for Large-scale Unbalanced Transportation Problem
- Modal Characteristics of Grating-Assisted Directional Coupler with 2D Periodic Patterns
- A study on Folded Monopole Antenna for Wireless HDMI Dongle Applications
Last modified: 2015-11-23 10:31:36