改进的遗传算法求解TSP问题3旅行商问题2434.pdf

3 旅行商问题 3.1 旅行商问题概述 3.1.1 旅行商问题的定义和数学模型 ① 定义 旅行商问题(Traveling Salesman Problem，简记 TSP)是组合数学中一个古老而 又困难的问题，它易于描述但至今尚未彻底解决，现己归入所谓的 NP 完全问题类， 经典提法为： 有一货物推销员要去若干个城市推销货物，从城市 1 出发，经其余各城市一 次，然后回到城市 1，问选择怎样的行走路线，才能使总行程最短（各城市间距离 为己知）。 该问题在图论的意义下就是所谓的最小 Hamilton 圈问题，由于在许多领域中 都有着广泛的应用，因而寻找其实际而有效的算法就显得颇为重要了。遗憾的是， 计算复杂性理论给予我们的结论却是，这种可能性尚属未知。 若设城市数目为 n 时，那么组合路径数则为(n-1)! 。很显然，当城市数目不多 时要找到最短距离的路线并不难，但随着城市数目的不断增大，组合路线数将呈 指数级数规律急剧增长，以至达到无法计算的地步，这就是所谓的“组合爆炸问题” 。 假设现在城市的数目增为 20 个，组合路径数则为(20-1)! ，如此庞大的组合数目， 若计算机以每秒检索 1000 万条路线的速度计算，也需要花上 386 年的时间。 尽管现在计算机的计算速度大大提高，而且已有一些指数级的算法可精确地 求解旅行商问题，但随着它们在大规模问题上的组合爆炸，人们退而求其次，转 向寻找近似算法或启发式算法，经过几十年的努力，取得了一定的进展。 ② 数学模型 设G (V , E) 为赋权图，V {1,2,n}为顶点集，E 为边集，各顶点间距离为cij ， 已知(cij 0, cij =+∞,i, j ∈V ) ，并设 ⎧1, 边 (i , j )在最优路线上 xij ⎨ ⎩0, 其它 则旅行商问题的数学模型可写成如下的线性规划形式： M inZ ∑c x ij ij i≠j 17 ⎧∑xij 1, i =∈V ⎪≠ j i ⎪ ⎪∑xij 1, j =∈V s.t ⎨i≠j ⎪ ≤ − ⊂ ∑xij K 1, K V ⎪ , i j∈S ⎪ ∈ ∈ xij {0,1} i , j V ⎩ 这里，K 为V 的所有非空子集，K 为集合K 中所含图G 的顶点个数。前两个 约束意味着对每个顶点而言，仅有一条边进出，后一约束则保证了没有任何子回 路解的产生。于是，满足上述约束的解构成了一条 Hamilton 回路。除此之外，模 型还有其它一些等价的书写形式。 3.1.2 旅行商问题的分类 旅行商问题按不同的分类方法可以分成为不同的种类。 ① 据距离矩阵划分 当cij c ji ,(i, j =∈V ) 时，问题被称为对称型旅行商问题。反之，称为非对称型 旅行商问题。非对称型旅行商问题可以化为对称型旅行商问题，用对称型的方法 求解。 当对所有i, j, k ∈[1, n] ，有不等式cij +c jk