摘要
A new local search method for the traveling salesman problem based on an original greedy representation of solution space and neighborhood structure is proposed. First, a partial closed route that only consists of three cities is given; then other cities are added to this route by a greedy procedure successively. Implemented on a personal computer, this algorithm finds optimal solutions for 24 out of 27 standard benchmarks, and outperforms the Full Subpath Ejection Algorithm (F-SEC) proposed by Rego in 1998.
A new local search method for the traveling salesman problem based on an original greedy representation of solution space and neighborhood structure is proposed. First, a partial closed route that only consists of three cities is given; then other cities are added to this route by a greedy procedure successively. Implemented on a personal computer, this algorithm finds optimal solutions for 24 out of 27 standard benchmarks, and outperforms the Full Subpath Ejection Algorithm (F-SEC) proposed by Rego in 1998.
基金
TheNationalGrandFundamentalResearch973ProgramofChina(No.G1998030600).
