1、旅行商问题

旅行商问题（Traveling Salesman Problem，简记TSP）的标准形式为：给出一个完全图（任意两点间均有边相连的图），给图中的每条边赋权（注：不一定要满足三角不等式）得到一个网络。求由此网络上的一个顶点出发，经过所有顶点恰好一次，最后返回原出发顶点的最短回路（即求最短哈密顿圈）。例如，你想游玩n个确定的城市，这n个城市之间两两都存在着航线，在你打听好这n个城市之间的机票价格后想确定一条旅行路线，以遍访这些城市并最大限度地节省经费时，你遇到的就是一个旅行商问题。旅行商问题决不会比哈密顿圈问题容易，只要你能给出一个求解旅行商问题的多项式时间算法，我就可以利用你的算法轻而易举地构造出求解哈密顿圈问题的多项式时间算法（见习题6），但这是不可能的，因为1972年，Cook已经在其著名的论文中证明了哈密顿圈问题是NPC问题。

2、多旅行商问题

设有n个城市，这n个城市中任意两个城市间的旅行票价已知，现拟派m名商人到这些城市去推销商品，每个城市都必须有一人去且只需派一人去，问应如何分派任务，每一名商人的旅行线路又应当如何设计，才能使推销商品的总支出最少？

    多旅行商问题（Multi-TSP，简记MTSP）又被称为有女朋友的旅行商问题（TSP with a girlfriend），因为你也可以假设只有一个旅行商，但他有一个女朋友，在旅行期间该旅行商要回家探望m-1次女朋友，故而他将行程剖分成了m个子圈。MTSP显然也是NP难的，因为求解MTSP包含以下两步：

    步1  将n个城市划分成m组（需求出最佳分组方法）

    步2  对每一组求解一个TSP问题

其中步2要解的问题已经是NP难的了，不可能有多项式算法，除非ℙ=ℕℙ。

1999年全国大学生数学建模竞赛的赛题A（灾情巡视问题）就是一个多旅行商问题的实例，题目要求参赛学生能给出巡视灾情的较好办法。多旅行商问题虽然是NP难的，但对于灾情巡视这样MTSP的实例，我们仍可想出一些求其较为理想结果的办法，这正是该竞赛题要求参赛学生们做的事。

B题 灾情巡视路线

下图为某县的乡（镇）、村公路网示意图，公路边的数字为该路段的公里数。

今年夏天该县遭受水灾。为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视。巡视路线指从县所在地出发，走遍各乡（镇）、村，又回到县所在地的路线。

1.若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线。 

2.假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V=35公里/小时。要在24小时内完成巡视，至少应分几组；给出这种分组下你认为最佳的巡视路线。 

3.在上述关于T , t和V的假定下，如果巡视人员足够多，完成巡视的最短时间是多少；给出在这种最短时间完成巡视的要求下，你认为最佳的巡视路线。 

4.若巡视组数已定(如三组），要求尽快完成巡视，讨论T，t和V改变对最佳巡视路线的影响。 

CMCM 98B赛题简析

98年全国大学生数学建模竞赛B题“水灾巡视问题”，是一个多旅行商（MTSP）问题（典型的NP难问题），本题有53个点，所有可能性大约为exp(53), 目前没有好方法求出精确解，既然求不出精确解，我们使用模拟退火法求出一个较优解，将所有结点编号为1到53，1到53的排列就是系统的结构，结构的变化规则是：从1到53的排列中随机选取一个子排列，将其反转或将其移至另一处，能量E自然是路径总长度。具体算法描述如下：

步1： 设定初始温度T，给定一个初始的巡视路线。

步2：步3 --8循环K次

步3：步 4--7循环M次

步4：随机选择路线的一段

步5：随机确定将选定的路线反转或移动，即两种调整方式：反转、移动。

步6：计算代价D，即调整前后的总路程的长度之差

步7：按照如下规则确定是否做调整：

如果D<0，则调整

如果D>0，则按照EXP(-D/T)的概率进行调整

步8：T*0.9-->T，降温

模拟退火法实例：

1．MCM91B(通讯网络中的极小生成树)是一个求STEINER生成树问题，参见《工科数学专辑》Page：70－78。

2、CMCM 97A题

97年全国大学生数模竞赛A题“零件的参数设计”，可以归结为非线性规划模型，由于目标函数很复杂，且又是一个函数，因此求解比较困难，为应用模拟退火法进行求解，将7个自变量的取值范围进行离散化，取步长为0.0001，这样，所有7个变量取值就组成了一个极为庞大的离散空间, 而这个问题变成组合优化模型。下载本文