![](https://csdnimg.cn/release/download_crawler_static/88257058/bg3.jpg)
旅行商问题
(Traveling Salesman Problem,TSP)
也称为货郎担问题,是由爱尔兰数学 家
Sir
William Rowan Hamilton
和英国数学家
Thomas Penyngton Kirkman
在
19
世纪提出 的数学问题,它是
指给定
n
个城市并给出每两个城市之间的距离,旅行商必须以最短路 径访问所有的城市一次
且仅一次,并回到原出发地,现已证明它属于
NP(Non-deterministic Polynomial---
非确定多项式
)
难题⑴。历史上的第一个正式用来解决
TSP
问题的算法诞生于
1954
年
,
它被用来计算
49
个城市
的
TSP
问题。到现在为止
,
运用 目前最先进的计算机技术可解决找出游历
24978
个城市的
TSP
问题。
TSP
的历史很久,
最早的描述是
1759
年欧拉研究的骑士周游问题,即对于国际象棋棋盘中的
64
个方格,
走访
64
个方格一次且仅一次,并且最终返回到起始点。旅行商问题
(TSP)
由美国
RAND
公司于
1948
年引入,该公司的声誉以及线性规划这一新方法的出现使得
TSP
成为一个
知名且流行的问题⑵。
旅行商问题是一个经典的图论问题:设有
n
个城市,用
C
i,j
=1
,
2
,…,
n
表示。城
市
C
i,j
之间的距离为
d
i,j
,
i
,
j=1
,
2
,…,
n
,设所有城市间两两连通,旅行商需要跑遍
n
个城市去推销他的商品,而这些城市之间的距离都不一样,这推销员需要从其中一个城 市出
发,而他老板规定他必须把所有城市跑一遍, 则
TSP
问题就是寻找让旅行商遍访每
个城市一次且恰好一次的一条回路,且要求其路径总长度为最短。该问题也可以归结为: 有
N
个城市由公路相互连通,从任一城市到另外城市都要支付相应的费用, 一个销售商
从其中一城市出发,访问其他
N
-
1
个城市且仅一次,如何规划一条路径,使该旅行商 的花费
最少
[3]
。当城市数量较小时,通过枚举法就可以找出最短的路径,然而随着问题 规模的增
加,很难找到一个多项式时间复杂度的算法来求解该问题。
TSP
是一个典型的
组合优化问题,是诸多领域内出现的多种复杂问题的集中概括和简化形式,并且已成为 各种
启发式的搜索、优化算法的间接比较标准。因此,快速、有效地解决
TSP
有着重要
的理论价值和极高的实际应用价值。旅行商问题代表的一类组合优化问题
,
在物流配送、
计算机网络、电子地图、交通诱导、电气布线、
VLSI
单元布局等方面都有重要的工程
和理论价值,引起了许多学者的关注。
TSP
是典型的组合优化问题,并且是一个
NP-hard
问题。
TSP
描述起来很简单,早 期的研究
者使用精确算法求解该问题,
TSP
问题最简单的求解方法是枚举法。它的解是 多维的、多局部
极值的、趋于无穷大的复杂解的空间,搜索空间是
n
个点的所有排列的
集合,大小为(
n-1
)!。可以形象地把解空间看成是一个无穷大的丘陵地带,各山峰或 山谷的
高度即是问题的极值。求解
TSP
,则是在此不能穷尽的丘陵地带中攀登以达到山 顶或谷底的
过程⑵。常用的方法包括:分枝定界法、线性规划法和动态规划法等,但可 能的路径总数随
城市数目
n
是成指数型增长的,所以当城市数目在
100
个以上一般很难 精确的求出其全局最
优解。随着人工智能的发展,出现了许多独立于问题的智能优化算 法,如蚁群算法、遗传算
法、模拟退火、禁忌搜索、神经网络、粒子群优化算法、免疫 算法等,通过模拟或解释某些
自然现象或过程而得以发展,为解决复杂组合优化问题提 供了新的思路和方法
[4]
。模拟退
火算法在迭代搜索过程以
Boltzmann
分布概率接受目标 函数的劣化解”具有突出的具有脱离局
域最优陷阱的能力,同时具有较强的局部搜索 能力,从而可以获取目标函数的全局最优解。
因为模拟退火算法具有高效、通用、灵活 的优点,将模拟退火算法引入
TSP
求解,可以避免
在求解过程中陷入
TSP
的局部最优 解
[5]
。
本文首先介绍传统的
TSP
问题,先对其进行数学描述,又列举
TSP
问题的应用。 之后介
绍模拟退火算法,主要介绍其基本思想和关键技术,在此基础上将模拟退火的思 想引入
TSP
的求解,设计出
TSP
的一种模拟退火算法并用
MATLAB
语言编程予以实现。