旅行商问题(TSP)的几种求解方法

基金项目：国家自然基金（!"#$%""&）

收稿日期：&""% ’ "! ’ ("

) ) 第 &( 卷 ) 第 "* 期

计 ) 算 ) 机 ) 仿 ) 真

&""! 年 "* 月 ) )

文章编号：+""! ’ ,(#*（&""!）"* ’ "+%( ’ "%

旅行商问题（TSP）的几种求解方法

田贵超，黎明，韦雪洁

（南昌航空工业学院测试技术与控制工程系，江西 南昌 ((""(#）

中图分类号：-/("+9 ! ) ) 文献标识码：:

Several Methods for Solving Traveling Salesman Problem

-;:0 <=5 ’ >?@2，A; B5CD，EF; G=6 ’ H56

ABSTRACT：-?6 -J@S675CD .@76ML@C /J2T76L（-./）5M 2C6 24 K?6 KP35>@7 0/ ’ O2L376K6 ?@J8 3J2T76LM 5C

>2LT5C@K2J5@7 23K5L5U@K52C

5C>J6@M6 6R32C6CK5@77P V5K? K?6 @L2=CKM 24 >5KP，M2 5K 5M S6JP 85445>=7K K2 M27S69 W=K K2 M27S6 -./ X=5>Y7P @C8

6446>K5S67P ?@M 5L32JK@CK K?62J6K5>@7 S@7=6M @C8 ?5D? 3J@>K5>@7 @3375>@K52C S@7=6M9 -./ 5M 45JMK 5CKJ28=>68 5C K?5M

M27S5CD -./ 5M 3J2S58689

KEYWORDS：-J@S675CD M@76ML@C 3J2T76L（-./）；O2LT5C@K2J5@7 23K5L5U@K52C；/@K?；/J2M36>K

旅行商问题（-J@S675CD .@76ML@C /J2T76L，简称 -./）即

给定 C 个城市和两两城市之间的距离，要求确定一条经过各

城市当且仅当一次的最短路线。其图论描述为：给定图

! "

（#，$），其中 # 为顶点集，$ 为各顶点相互连接组成的边集，

设 % "（&

）是由顶点 ’ 和顶点 ( 之间的距离所组成的距离矩

，

’，( " +，&，(，…，)）。

商问题的求解。

# " ｛*

，*

，*

，,

，,

，…，,

，…，,

｝，其中 ,

#（’ " +，&，(，…，)），且

。

难题，是诸多领域内出现的多种复杂问题的集中概括和简化

形式，并且已成为各种启发式的搜索、优化算法的间接比较

标准。因此，快速、有效地解决

-./ 有着重要的理论价值和极

高的实际应用价值