A Multilevel Reduction Algorithm to TSP
DOI:
Author:
Affiliation:

Clc Number:

Fund Project:

  • Article
  • |
  • Figures
  • |
  • Metrics
  • |
  • Reference
  • |
  • Related
  • |
  • Cited by
  • |
  • Materials
  • |
  • Comments
    Abstract:

    The TSP (traveling salesman problem) is one of the typical NP-hard problems in combinatorial optimization problem. The fast and effective approximate algorithms are needed to solve the large-scale problem in reasonable computing time. The known approximate algorithm can not give a good enough tour for the larger instance in reasonable time. So an algorithm called multilevel reduction algorithm is proposed, which is based on the analysis of the relation of local optimal tour and global optimal tour of the TSP. The partial tour of the global optimal tour is obtained by a very high probability through simply intersecting the local optimal tours. Using these partial tours it could contract the searching space of the original problem, at the same time it did not cut the searching capability down, this is the so-called reduction theory. And then the scale of the instance could be reduced small enough by multi-reduction. Finally it could solve the small-scaled instance using the known best algorithm and get a good enough tour by putting the partial tours together. The experimental results on TSPLIB (traveling salesman problem library) show that the algorithm could almost get optimal tour every time for instance in reasonable time and thus outperformed the known best ones in the quality of solutions and the running time.

    Reference
    Related
    Cited by
Get Citation

邹鹏,周智,陈国良,顾钧.求解TSP问题的多级归约算法.软件学报,2003,14(1):35-42

Copy
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:July 17,2001
  • Revised:December 27,2001
  • Adopted:
  • Online:
  • Published:
You are the firstVisitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063