Indexed by:
Abstract:
This paper presents a local search method based on a filled function transformation method. Given a current best local minimal solution of the TSP, the filled function transformation method converts the TSP into a combinatorial optimization problem with the same solution space, but with less number of local minimal solutions. The combinatorial optimization problem has only one prescribed local minimal solution in the solution space where the length of any tour of the TSP is larger than that of the current best local minimal solution of the TSP. Moreover, a local minimal solution of the combinatorial optimization problem is either the prescribed local minimal solution, or else, is a strictly better local minimal solution of the TSP than the current best solution. Then the well-known 3-opt algorithm is used to solve the combinatorial optimization problem to find a better local minimal solution of the TSP. If a better local minimal solution of the TSP is found, then a new combinatorial optimization problem is constructed using the filled function transformation method, and the 3-opt algorithm is applied to solve it again. This method is tested by some standard test instances, and the method presented in this paper is more efficient and more effective than the 3-opt algorithm for the TSP. It is easy to use, and can be directly generalized to solve other NP-hard combinatorial optimization problems.
Keyword:
Reprint 's Address:
Email:
Version:
Source :
Chinese Journal of Computers
ISSN: 0254-4164
CN: 11-1826/TP
Year: 2002
Issue: 7
Volume: 25
Page: 701-707
Cited Count:
SCOPUS Cited Count:
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 1
Affiliated Colleges: