旅行推销员问题算法综述.pdf

第 30 卷第 2 期 数学的实践与认识 V o l30　N o 2　 2000 年 4 月 M A TH EM A T IC S IN PRA CT ICE AN D TH EO R Y A p r il, 2000　 旅行推销员问题的算法综述 马　 良 (上海理工大学, 上海　200093) 摘要: 　本文综述了旅行推销员问题(T SP ) 近几十年来的算法研究进展, 给出了一些主要算法的求解思想及其 时间复杂度 关键词: 　旅行推销员问题; 启发式; 算法 1　引　　言 　　旅行推销员问题(T ravellin g Sa le sm an P rob lem , 简记 T SP ) 是组合数学中一个古老而 又困难的问题, 至今尚未彻底解决, 现已归入所谓的N P 完备问题类 问题的经典提法为: 有一货物推销员要去若干个城市推销货物, 从城市 1 出发, 经其余各城市至少一次, 然后回 ( ) 到城市 1, 问选择怎样的行走路线, 才能使总行程最短 各城市间距离为已知 该问题在图论的意义下就是所谓的最小H am ilton 圈问题, 由于在许多领域中都有着广 泛的应用, 因而寻找其实际而有效的算法就显得颇为重要了 遗憾的是, 计算复杂性理论给 予我们的结论却是, 这种可能性 尚属未知 尽管已有一些指数级的算法可精确地求解 ( ) T SP , 但随着它们在大规模问题上的失效 组合爆炸 , 人们退而求其次, 转向寻找近似算法 或启发式算法, 经过几十年的努力, 取得了相当的进展 本文将从算法的角度对 T SP 发展 至今的一些主要成果作一概要介绍 2　数学模型 记 = ( , ) 为赋权图, = {1, 2, …, }为顶点集, 为边集, 各顶点间距离 ij 已知( ij G V E V n E d d 0, = + ∞, , ∈ ) , 并设 d ii i j V ( ) 1, 边 i, j 在最优路线上 x ij = 0, 其它 　　则 T SP 的数学模型可写成如下的线性规划形式: M inZ = d ij x ij ∑ i≠j x ij = 1, i ∈V ∑ j ≠i x ij = 1, j ∈V ∑ s. t　 i≠j x ij ≤ S - 1, 对所有V 的子集S ∑ i, j ∈