旅行商问题基于参考点的相邻插入法及其改进.pdfVIP

业 业 业 业 ．{I·学术探讨· 带 带 带 带 旅行商问题基于参考点的相邻插入法及其改进 童行行 王 凌 何京芮 (清华大学自动化系，北京 100084) E-mail：tonghh@moon．bjnet．edu．cn 摘 要 旅行商问题(Traveling Salesman Problem。TSP)~ 型的NP—hard f*-I题。通过对已有以最近插入法为代表的构 造性算法的分析，提 出了一种具有多项式时间性能的基于参考点的相邻插入法及其改进策略，其时间复杂度分别为 0(n )和 O(n )，同时基于典型算例的仿真研究验证所提出算法的有效性和高效性。 关键词 旅行商问题 构造性算法 参考点 相邻插入法 多项式时间算法 文章编号 1002—8331-(2002)20—0063—03 文献标识码 A 中图分类号 TP301．6 Reference Point-based Near Insertion Approach and Its Improvement for Traveling Salesman Problem Tong Hanghang Wang Ling He Jingrui (Dept．of Automation，Tsinghua University，Beijing 100084) Abstract： Traveling salesman problem (TSP)is a typical NP—hard problem．By analyzing constructive algorithms repre— sented by the nearest insertion，this paper proposes a kind of reference point-based near insertion approach and its im— provement version with O(n )and O(n )polynomial time performances respectively．Moreover，simulation results based on typical benchmarks demonstrate the effectiveness and efficiency of the proposed approaches． Keywords：Traveling salesman problem(TSP)，Constructive Algorithm，Reference point，Near insertion approach，Polynomi— l—time algora ithm l 引言 果往往很差(该文仅考虑二维平面TSP)。其原因可由图 1来说 旅行商问题(TSP)是典型的 NP—hard问题 ，其图论描述 明。假定A—B—C 是已求得的三个城市的解，当新增加一个 为：给定图 G=(V，A)，其中 V为顶点集，A为连接各顶点的边 位于曰C段上的城市D时，根据最近插入法原理，D应插入到 集，已知各顶点间的连接距离，要求确定一条长度最短的 AC或AB之间，但显然，由于D在线段曰C上，插入到曰C之间 Hamilton回路…。鉴于TSP的组合爆炸特性，大规模TSP问题不 会更好一些。因此，在考虑 D的插入位置时，如果仅仅考虑与 可能用穷举法求解，因此很多场合追求高效地得到满意解。构 它距离最近的城市则有可能会使解劣化。较合理的想法是，考 造性算法，如最近邻点、最近合并、最远插入、最近插入、贪婪插 虑已有路线上的所有相邻点来找到新城市的插入位置。另外， 入和极小代数法_I_51等虽具有快速性，但