| Novel Local Search Method for the Traveling Salesman Problem |
| |
| 作者姓名： | 黄文奇 王磊 |
| |
| 作者单位： | CollegeofComputerScienceandTechnology,HuazhongUniversityofScienceandTechnology,Wuhan430074,China |
| |
| 基金项目： | TheNationalGrandFundamentalResearch973ProgramofChina(No.G1998030600). |
| |
| 摘 要： | 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.
|
| 关 键 词： | 局部搜索 旅行推销员 启发式法 路线管理 计算机管理 |
Novel Local Search Method for the Traveling Salesman Problem |
| |
| Huang Wenqi,Wang Lei.Novel Local Search Method for the Traveling Salesman Problem[J].Journal of Southwest Jiaotong University,2005,13(1):1-4. |
| |
| Authors: | Huang Wenqi Wang Lei |
| |
| Abstract: | 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. |
| |
| Keywords: | Traveling salesman problem Heuristics Local search |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
