建模经典问题——旅行商问题图文 文档全文预览.pptxVIP

第7章 旅行商问题 目录 第7章 旅行商问题 1.问题概述 2.求解算法 2.1.下界和上界算法 2.2.分支定界法 2.3.动态规划法 2.5.近似算法 2.5.竞赛题 2 §7-1 问题概述 一 、数学模型 1.标准TSP 旅行商问题(简称TSP ), 也称货郎担问题或 旅行推销员问题，是运筹学中一个著名的问题，其 一般提法为：有一个旅行商从城市1出发，需要到 城市2、3、 …、n 去推销货物，最后返回城市1,若 任意两个城市间的距离已知，则该旅行商应如何选 择其最佳行走路线? 3 TSP在图论意义下又常常被称为最小Hamilton圈问题， Euler等人最早研究了该问题的雏形，后来由英国的 Hamilton爵士作为一个悬赏问题而提出。但这个能让普通人 在几分钟内就可理解的游戏之作，却延续至今仍未能完全解 决，成了一个世界难题。 TSP有着明显的实际意义，如，邮局里负责到各信箱开 箱取信的邮递员，以及去各分局送邮件的汽车等，都会遇到 类似的问题。有趣的是，还有一些问题表面上看似乎与TSP 无关，而实质上却可以归结为TSP 来求解。已经证明， TSP 是个NP难题，除非P=NP, 否则不存在有效算法。 4 记为赋权图G=(V,E),V 为顶点集，E 为边集， 各顶点间的距离d;已知。设 若(i,j) 在回路路径上 其他 i∈V j∈V √ S∈V,2≤|S|≤n-1 则经典的TSP可写为如下的数学规划模型： (7-1) (7-2) (7-3) 5 模型中，为集合中所含图的顶点数。约束(7- 1 和 (7-2) 意味着对每个点而言，仅有一条边进和一条 边出；约束(7-3)则保证了没有任何子回路解的产生。 于是，满足约束(7- 1)、 ( 7 - 2 ) 和 ( 7 - 3 ) 的 解 构 成了一条Hamilton回路。 6 i∈V j∈V VScV,2≤|S|≤n-1 (7-1) (7-2) (7-3) s.t 当d,=d(i,j∈V ) 时，问题被称为对称型TS P, 否 则称为非对称型TSP 。 若对所有1≤i,j,k≤n, 有不等式dy;+dx≥d 成 立，则问题被称为是满足三角形不等式的，简称为 △TSP。 7 2.扩展TSP (1)瓶颈TSP 瓶颈问题是最早从TSP 延伸出来的一种扩展型 TSP, 其含义与经典的TSP类似，仅目标不同，要 求巡回路线中经过的最长距离最短，即最小化瓶颈 距离。该情形体现了那些并不追求总巡回路线最短， 而只希望在巡回路线中每次从一个地点至另一个地 点的单次行程尽可能短的实际应用问题的特征。 8 从严格的数学意义而言，瓶颈TSP (简称BTSP ) 并没有降低问题的难度，也未能提供任何特殊的解决 办法。 瓶颈TSP的数学模型与标准TSP类似，仅目标函 数不同： min Z=max{d,·xi|i,jeV} 由于目标函数为瓶颈值，故求得的最佳巡回路 线与标准TSP的往往截然不同。 9 (2)最小比率TSP 最小比率TSP (简称MRTSP ) 是从经典TSP引 申出来的另一个变形问题，假定从一个城市走到另 一个城市可得到某种收益(记为),则MRTSP 的 目标就是确定最佳行走路线，使得回路的总行程与 总收益之比最小。这种优化目标的思想类似于人们 日常生活中经常使用的费用效益比，与单纯的总行 程最短相比，往往更具实际意义。 10 假定收益的数学性质与相同，则最小比率TSP的 数学模型也与标准TSP 类似，仅目标函数不同： 毫无疑问，由于目标函数中的非线性因素，最 小比率TSP的求解比之标准TSP显得更为困难。 11 (3)多人TSP 若标准TSP中，出发点有多个推销员同时出发，各自行 走不同的路线，使得所有的城市都至少被访问过一次，然后 返回出发点，要求所有推销员的总行程最短，则问题就成为 一个多人的旅行商问题(简记MTSP )。 令决策变量 若有某推销员从城市i 到城市j 否则 则 MTSP 的数学模型为： 12 假定原问题为对称型MTSP, V={vo,V₁…Vn}, v₀ 为名推销员出发点，记V={Von)Vo₂…Vom;Vo,₁,…Vn- } , 扩 大 的m-1 个顶点称为“人造顶点”,其距离 矩阵也相应扩大，其中，位于出发点的m 个顶点相 互间的距离设定为o, 其他数值不变。 s.t. 13 二 、多面体理论 从上世纪70年代开始的关于算法复杂性的研究 表明，要想为TSP找到一个好的算法，也即多项式 算法，似乎是不可能的。由于推销员的每条路线可 以用一个以1开始的