| Summary |
Hui-Peng Chein ,2006.06
Institute of Transportation Technology and Management
National Chiao Tung University
Traveling salesman problem is a well-known NP-hard combinatorial optimization problem. It has been one of the problems in some academic fields such as mathematics, computer science and management science want to resolve.
Due to the NP-hard complexity of TSP, it seems to be no way to find out an algorithm which can provide an optimal solution for the TSP without suffering from exponentially growing complexity. If we can find out a more efficient methods to solve the problem, it will help many industries to improve their operational costs.
This research presents an implementation of the Deterministic Noising Method, a combinational optimization meta-heuristics, for solving traveling salesman problem. The DNM revises the Noising Method form a stochastic method to a deterministic method. In this paper, we provide a new formula to disturb the cost matrix in order to escape from a local solution. We also consider different parameter settings to test the performance of the DNM. Sixteen problems from TSPLIB library are used to test the quality of the DNM. The average accuracy of the best solutions of the sixteen problems computed by the DNM is 0.19 % above the performance of the current best known solution. Overall, the heuristics should be a tool for real-world application of TSP. |
