• Complex
  • Title
  • Keyword
  • Abstract
  • Scholars
  • Journal
  • ISSN
  • Conference
成果搜索

author:

Zhu, Wen-Xing (Zhu, Wen-Xing.) [1] (Scholars:朱文兴) | Fu, Qing-Xiang (Fu, Qing-Xiang.) [2]

Indexed by:

EI Scopus CSCD

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:

Algorithms Approximation theory Optimization Traveling salesman problem

Community:

  • [ 1 ] [Zhu, Wen-Xing]Dept. of Comp. Sci. and Technol., Fuzhou Univ., Fuzhou 350002, China
  • [ 2 ] [Zhu, Wen-Xing]Inst. of Software, Chinese Acad. of Sci., Beijing 100080, China
  • [ 3 ] [Fu, Qing-Xiang]Dept. of Comp. Sci. and Technol., Fuzhou Univ., Fuzhou 350002, China

Reprint 's Address:

Show more details

Version:

Related Keywords:

Related Article:

Source :

Chinese Journal of Computers

ISSN: 0254-4164

CN: 11-1826/TP

Year: 2002

Issue: 7

Volume: 25

Page: 701-707

Cited Count:

WoS CC 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

Online/Total:255/10035873
Address:FZU Library(No.2 Xuyuan Road, Fuzhou, Fujian, PRC Post Code:350116) Contact Us:0591-22865326
Copyright:FZU Library Technical Support:Beijing Aegean Software Co., Ltd. 闽ICP备05005463号-1