| 一种求解欧式平面TSP问题的混合算法 |
| |
| 引用本文： | 王兴起,薛晓春.一种求解欧式平面TSP问题的混合算法[J].计算机与现代化,2010(5):33-35,39. |
| |
| 作者姓名： | 王兴起 薛晓春 |
| |
| 作者单位： | 北京航空航天大学航空科学与工程学院,北京,100191 |
| |
| 摘 要： | TSP问题是一个经典的组合优化问题。本文采用基于凸多边形的插入方法来构造路径，然后使用调整算法对路径进行调整以缩短回路长度，最后采用遗传算法中的交叉算子，再对路径进行优化。实验结果表明，该算法具有较高精度和较强实用性。
|
| 关 键 词： | 旅行商问题 组合优化 凸多边形 交叉算子 |
A New Hybrid Algorithm to Solve Euclidean Plane TSP |
| |
| WANG Xing-qi,XUE Xiao-chun.A New Hybrid Algorithm to Solve Euclidean Plane TSP[J].Computer and Modernization,2010(5):33-35,39. |
| |
| Authors: | WANG Xing-qi XUE Xiao-chun |
| |
| Affiliation: | School of Aeronautic Science and Engineering/a>;Beihang University/a>;Beijing 100191/a>;China |
| |
| Abstract: | Traveling salesman problem(TSP) is a classic combinatorial optimization problem.This paper uses an insertion method which is based on convex polygon to form loop,then applies the adjustment algorithm to shorten the loop.At last the paper uses the crossover operator which is from the genetic algorithm to optimize the loop.The result of calculation shows that the method has high precision and good practicability. |
| |
| Keywords: | TSP combinatorial optimization convex polygon crossover operator |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
