Hybrid Nested Partitions Method for the Traveling Salesman Problem
The nested partitions method (NPM) is a global optimization method, which can be applied to solve many large-scale discrete optimization problems. The basic procedure of this method for solving the traveling salesman problem (TSP) was introduced. Based on
- PDF / 453,124 Bytes
- 13 Pages / 439.37 x 666.142 pts Page_size
- 120 Downloads / 229 Views
Abstract The nested partitions method (NPM) is a global optimization method, which can be applied to solve many large-scale discrete optimization problems. The basic procedure of this method for solving the traveling salesman problem (TSP) was introduced. Based on the analysis and determination of the strategy of the four arithmetic operators of NPM, an improved NPM was proposed. The initial most promising region was improved by weighted sampling method; The historical optimal solution of every region was recorded in a global array; the 3-opt algorithm was combined in the local search for improving the quality of solution for every subregion; the improved Lin–Kernighan algorithm was used in the search for improving the quality of solution for surrounding region. Some experimental results of TSPLIB (TSP Library) show that the proposed improved NPM can find solutions of high quality efficiently when applied to the TSP.
Keywords Nested partitions method Local search algorithm algorithm 3-Opt algorithm Traveling salesman problem
Lin–Kernighan
1 Introduction The traveling salesman problem (TSP) is one of the classic NP-hard [1] combinatorial optimization problems. There are two kinds of algorithms for solving TSP problems: One kind is accurate algorithm that can find exact solutions for TSP D. Zong (&) College of Computer Science and Engineering, Changshu Institute of Technology, Changshu, China e-mail: [email protected] K. Wang School of Mathematics and Physics, Jiangsu University of Science and Technology, Zhenjiang, China
Z. Wen and T. Li (eds.), Foundations of Intelligent Systems, Advances in Intelligent Systems and Computing 277, DOI: 10.1007/978-3-642-54924-3_6, Springer-Verlag Berlin Heidelberg 2014
55
56
D. Zong and K. Wang
problems, but its computation time will increase exponentially with the expansion of the scale of the problem and will generate combinatorial explosion; the other kind of algorithm is stochastic optimization algorithm and heuristic algorithm, which can find approximate solution for the TSP in polynomial time. Inrecentyears,therehavebeenmanystochasticoptimizationalgorithmsorheuristic algorithm for the TSP such as nested partitions method (NPM), genetic algorithm, particle swarm optimization algorithm, simulated annealing algorithm, tabu search algorithm, 2-opt algorithm [2], 3-opt algorithm [3], and Lin–Kernighan algorithm [4]. These algorithms can find approximate solution for the TSP in relative short time. NPM [5] is a kind of global optimization method which can be applied to solve large-scale optimization problems. It is proved that NPM can converge with probability one to a global optimum in finite time. In this paper, we propose a new hybrid NPM for solving the symmetric TSP, which combines the global search and local search algorithm in a unified framework. The applications of the hybrid method to the symmetric TSP are presented in this paper. Some experimental results of TSPLIB 0 show that the hybrid method can find optimal solutions for TSP efficiently. The r
Data Loading...
