灾情最优路线设计 1998年数模A题.doc 23页

重大灾情最优巡查路线设计 承诺书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的,如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们参赛选择的题号是（从A/B/C/D中选择一项填写）：我们的参赛报名号为（如果赛区设置报名号的话）：所属学校（请填写完整的全名）：广东商学院参赛队员(打印并签名)：1.邓思文2.苏境财3.吴妙指导教师或指导教师组负责人(打印并签名)：戴宏亮日期：2012年8月11日赛区评阅编号（由赛区组委会评阅前进行编号）： 2010高教社杯全国大学生数学建模竞赛编号专用页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）： 重大灾情最优巡查路线设计摘要灾情巡视对于受灾地的救援工作有着重要意义，快速了解受灾地的情况，有利于加快援救工作，所以研究最佳巡视路线有着重要意义。本文针对最佳路线及相关问题做出如下解答：针对问题一，基于MTSP数学模型，运用了遗传算法，建立了最佳巡视路线模型，通过matlab编程，求解得出总路程最短且相对均衡的3组巡视路线，各组巡视路线如下：第一组：O→P→26→27→28→Q→30→Q→29→R→A→33→31→32→35→34→D→1→O第二组：O→M→25→20→L→19→J→18→I→15→I→16→17→22→K→21→23→24→N→26→P→O第三组：O→C→3→D→4→8→E→9→F→10→F→12→H→14→13→G→11→E→7→6→5→2→O针对问题二，通过估计方法估量组数范围，再利用问题一中所使用模型，对输入矩阵进行加权修改，构成定向时间矩阵，并通过matlab计算出结果，最后针对计算结果中的误差，验证估计结果是否正确，结果显示4组为最少组数。针对问题三，首先计算出最远结点的最近距离，得到最小时间为6.44小时，再利用“就远原则”，得到最少组数为24组。关键词：MTSP数学模型遗传算法定向时间矩阵就远原则 一、问题重述灾情视察是了解受灾地的重要方法，设计合理快速的巡视路线对提高了解灾情的效率非常有帮助，根据下图一，回答以下问题：图一1．若分三组（路）巡视，设计路线最短且相对均衡的路线。2．假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V=35公里/小时。要在24小时内完成巡视，至少应分几组。3．在上述关于T,t和V的假定下，如果巡视人员足够多，完成巡视的最短时间是多少，设计时间最短下的最佳巡视路线。二、问题分析设计最佳的巡视路线有利于提高视察灾情的效率，对尽快找到应对灾情的方案有很大的帮助。为方便计算和观察，我们将原图制成一下如图二：图二 针对问题一，题目要求3组总路线最短，且各组路线路程尽量达到均衡。经初步分析，当只有一组人遍历所有乡镇和村的时候所花的时间最短，而随着人数的增加，总路程会随之增加，因此，我们要达到均衡，才有计算最短路线的意义。我们可以根据MTSP数学模型和遗传算法的方法，构造出各乡镇或村之间距离矩阵A和最小距离矩阵B，以3组中路程最大的巡视路线路程尽量小为目标，利用matlab编程，近似设计出3组总路线最短且各组路程最均衡的最佳灾情巡视路线。针对问题二，问题要求在24小时内，在限定行车速度，巡视停留时间的前提下，寻找最佳巡视路线，此可基于问题一的遗传算法MTSP数学模型来解决，但比问题一相关问题稍为复杂。问题二要求在24小时内完成巡视，根据我们的经验可知，时间越短，要完成遍历，只能增加组数，因此，我们将时间定在24小时，就可以保证组数最少。为了避免运算的繁琐，我们事先对组数进行预计，然后再更改MTSP数学模型中的矩阵，将矩阵A改为有向时间矩阵，最后用matlab计算出最优解。又由于matlab在运行时会出现重复路过的结点，从而造成最优解的时间大于24，因此最后我们要对结果进行修正，再得出真正的最优解。针对问题三，为了确定完成巡视的最短时间，可直接找出距离县政府最远的乡镇或村，并对其沿路返回而不在其它乡镇或村停留，因此其所需的时间即为完成巡视的最短时间。虽允许巡视人员足够多，但现实灾情考察中希望能设计出各组路线均衡、合情合理的最佳巡视路线，因此可根据由远及近原则，每次在未被巡视的乡镇或村中找出距离县政府最远的乡镇或村，并通过穷举思想选择满足最短时间限制的关联乡镇或村结点，而巡视人员将会在该联乡镇停留，类似不断地进行循环直至回到县政府起点。这样由远到近不断循环地判断选择路线结点过程，能够设计出各组比较符合现实情况又满足在最短时间范围内的灾情巡视路线。三、模型假设（1）假设巡逻过程中没有出现特殊意外。（2）假设已被访问的点仅被巡逻一次，重复经过的点不作为巡逻结点加入路径。四、符号说明符号符号说明最佳巡视路线最小值距离矩阵道路被选择的概率路线组合的概率关联边权重关联边总权重所有道路与村镇停留总时间 县政府至各乡镇或村所需最短时间的最大值各结点的权，即在各乡镇或村停留的时间结点间连线弧长，即路经各乡镇或村之间的所需时间所需的最短时间路经任意乡镇或村两两之间所需的最短时间(不包括停留时间)五、模型的建立与求解5.1基于遗传算法的MTSP模型遗传算法是模拟生物界自然选择和遗传机制的一种随机搜索最优解的算法，主要通过随机方式产生若干个数字编码（染色体）从而形成初始种群，并设定一个适应度函数，优胜劣汰并选择适应高的个体进行遗传操作，直到找到最优解。针对从县政府分三组路线巡视考察灾情并使得总路线最短的情形，结合这两种原理，并考虑各组路线路程的均衡要求，即达到所有最大巡视路线的路程最小，这样能比较快速、准确地寻求出各组巡视路线。5.1.1问题一的模型建立(1)初始产生编码图中起点县政府表示为“1”，乡镇节点“A,B,C,…,R”分别表示为“2,3,…,18”，村节点“1,2,3,…,35”分别表示为“19,20,21,22,…,53”，则乡镇、村之间的对称距离矩阵为53X53的矩阵，记为A。其中，使用一个较大的数“inf”表示两节点间无直接连接。因灾情巡视路线分成三条，需再插入两个虚拟点54,55表示路线起点县政府（并没有将其纳入矩阵A内），从而得到一个55位随机染色体编码，如：1,6,2,7,9,…18,54,3,8,22,…，34,55,8,35,….45。对此，得到的三条路线可表示为：1—6—2—7—9—……—18—1；1—3—8—22—……—34—1；1—8—35—……—45—1。同时，矩阵A的应设为一个较大的数，“inf”，以防出现“1—1—1”的路线，并且计算任意两节点间最小距离，得到矩阵B。(2)建立目标函数目标函数是使三条巡视路线中路程最大的路线路程最小，满足均衡条件，即：y=min(max())其中， ，而表示弧(i,j)的长度，即为(i,j)的权。(3)确定适值函数，进行选择因为以路程最小作为优化目标，因此可将适值函数定为：，为正实数若某个节点i的适值为，则其被选择的概率为然后对各染色体编码计算出其累积的概率：最后利用轮盘赌选择法进行选择。为了选择匹配的节点，需进行多轮选，每一轮产生一个[0,1]均匀随机数，将随机数作为选择指针来确定备选节点。(4)部分匹配交叉与交换变异部分匹配交叉操作要求随机选取两个交叉点，由此确定一个匹配段，根据两个交叉点之间的中间段给出映射关系生成两个新节点。交换变异，即交换随机位置上的基因，变异的概率不宜过高或过低。(5)解码将的到的最有染色体进行解码，得出三条适宜的路线。在根据题目中所给的城镇距离构建一个5353的矩阵，将该矩阵设为D。最后利用矩阵D和三条最优路线解码得出结果。5.1.2模型的求解模型的求解过程主要是通过matlab编程实现，代码见【附录1】。(1)根据该县的乡镇和村公路网示意图，得出镇村之间距离矩阵A。其中，i,j均表示城镇，表示镇i与镇j的距离。则有： 将矩阵A输入到matlab程序中。(2)将矩阵输入后，程序运行得出结果如下:由此可知，三组的走的路程如表5.1-1所示：路线1的分组路线长度组数第一组第二组第三组路程194.9159.3215.9表5.1-1为比较均衡度，我们利用以上作法，做出多次结果，对其均衡度进行比较，比较根据为： 结果如表5.1-2：多组路线路程和均衡度比较表组数总路程第一组第二组第三组均衡度路线1570.1194.9159.3215.90.734路线2632.2199.1228.1205.10.874路线3622.9193.9236.5192.50.814路线4630.7230.3202.8197.60.858表5.1-2由此可知，路线1的均衡度最低，但是路程最短，因此我们还是选择路线1。路线如图5.1-3：路线1三条最短路线示意图图5.1-3第一组（红色线）：O→P→26→27→28→Q→30→Q→29→R→A→33→31→32→35→34→D→1→O第二组（绿色线）：O→M→25→20→L→19→J→18→I→15→I→16→17→22→K→21→23→24→N→26→P→O第三组（白色线）：O→C→3→D→4→8→E→9→F→10→F→12→H→14→13→G→11→E→7→6→5→2→O5.1.3结果分析由上述结果可知，三组路程分别为194.9,159.3和215.9,总路程为 570.1公里，而且三条路线长度相差不远，均衡度较高。因此这种方案是可取的优化路线。5.1.4模型评价对于问题一的解答，主要运用了遗传算法和MTSP模型。而这一个模型存在着随机性，而且得出的结果是近似解，不能保证每一次的结果都是符合实际要求的最优解。运用matlab进行求解的过程中，由于matlab的局限性，求解速度较慢。模型的求解中求得的是局部优化，求解过程容易导致形成局部最优解，而不是全局最优解，从而得到较大的误差。5.2MTSP数学估计模型通过对问题一的探究，我们知道了分三组的情况下，利用遗传算法和MTSP数学模型得出了均衡下的最短总路程的路线。问题二加入了限制条件，但理论上的内部机制是相同的。因此我们对第一问的MTSP数学模型进行修改，将MTSP中的矩阵A中的数据改变有向矩阵，将无向图以有向矩阵的形势表现。5.2.1问题二的模型建立（1）将矩阵A的数据改变，改变规则如下：i．将矩阵中表示距离的权重改为路程S除以速度V，即关联边的权重改为时间。并将节点的权重加入指向的边中。即，若i,j均表示城镇，则表示从镇i到镇j的时间加上镇j的权重。更改后的有向矩阵A如下：ii．预测分组数目。令路线权重为，=A,B,C,D,…R,1,2,3，…35求出所有关联边的权重：E==95.13 关联边的总权重表示的是走遍所有的路程所用的总时间，令N为分组数目，预测N约为：=3.96由此可知，分组数目大约在3至4组。下面我们将用修改后的MTSP数学模型进行验证。iii．利用matlab程序，将组数定为3和4，分别运行两次，观察结果。由于遗传算法的特点，导致最短路线有重复停留，计算结果会比实际结果大，因此要根据画出的路线，进行结果修正。5.2.2模型的求解模型的求解主要是利用matlab程序中的语句达成。将组数N定为3和4，分别运行两次。得到4组的结果如下：由此可知，四组的分别用的时间如下表5.2-1：软件求解四组的时间组数第一组第二组第三组第四组时间30.5422.0329.3226.48表5.2-1由得出的结果发现，当组数为3时，不管如何均衡，都无法使时间最长组的最小时间小于24，而组数为4时可以，因此我们认为在问题二的条件下，要在24小时内完成巡逻，至少要分4组。路线图如图5.2-2： 24时内完成巡逻的四组路线图图5.2-2由上图可知，在计算最短路径时易出现重复经过同一个节点，因此要进行结果修正，得出准确的最短时间。路线如下：第一组（红色线）：O→→→20→19→J→11→G→12→F→10→→9→E→8→4→D→→→O第二组（咖啡色线）：O→R→29→Q→30→32→31→33→35→34→A→1→B→C→O第三组（白色线）：O→→25→21→K→18→I→15→14→H→→13→→→L→7→6→5→2→3→→O第四组（绿色线）：O→P→26→27→28→→24→23→→17→16→→22→→N→M→→P→O5.2.3结果分析由上面结果求解的过程可知，由编程得出的最优解是有重复经过的，因此我们要将重复经过的节点的权重删去。上图中的，，，，，，，，，，，，均为重复遍历的结点。计算得每条路线的时间如下：第一组：=30.54-8=22.54（小时） 第二组：=22.03（小时）第三组：=29.32-8=21.32（小时）第三组：=26.48-7=19.48（小时）因此，我们至少可以用四组，在24小时内完成巡逻。时间分配如下表5.2-3：修改后的四组时间表组数第一组第二组第三组第四组时间22.5422.0321.3219.48表5.2-35.2.4模型评价第二问的解答是在第一问的基础上，加上了限制的条件，因此第二问计算时也存在着近似最优解的情况，因此需要对结果进行修正。模型二改造了MTSP数学模型中的矩阵A，将矩阵A变为有向矩阵，方便本题的计算，使最优解的得出得以实现。模型二利用简单估计的方法，为计算增加了便利性，减少计算中不必要的重复计算。5.3“就远原则”优化模型已知巡视人员在各乡(镇)停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V=35公里/小时。假定允许巡视人数足够多，即对巡视人员分组不作严格要求，但在灾情考察现实情形下，希望巡视效率高的同时每组参与人员也尽量多。因此，在最短时间内完成巡视并使得每组巡视人员访问的乡镇农村尽可能多，是我们需要寻找的最佳路线。此处，基于就远原则，对离县政府较远的乡镇或村进行优先巡视，然后在满足最短时间要求下逐次巡视较近的乡镇或村。5.3.1模型的建立(1)算出路线以及乡镇或村的时间权，并运用图论软件画出路线图，如图5.3-1： 图5.3-1(2)基于上图，直接利用图论软件Floyd表得出巡视任意乡镇和村之间的所需最小时间(不包括停留时间)矩阵C，取县政府到任意乡镇或村(不包括停留时间)所需最小时间，如表5.3-2：县政府至各乡(镇)或村之间的所需最小时间(不包括停留时间)表ABCDEFGHIJKLM0.460.340.330.630.201.581.802.221.711.561.251.120.57NPQR1234567890.891.580.830.370.170.260.400.990.500.780.991.431.42101112131415161718192021221.891.611.931.842.091.961.691.501.481.331.101.131.41232425262728293031323334351.121.270.910.590.810.640.601.050.630.860.670.791.02表5.3-2(3)计算出最短时间将各个乡镇或村记为“”，则各乡镇或村的权(停留时间)为，取.因此，所需最短时间为：2*+。(4)寻找路线i．当=时，表示从起点1到点k所需最短时间最大，有点1到点k最短时间路线序列，如：1—4—8—…—k，并沿路返回且不在其它乡镇或村停留，得到第一条巡视路线为：1—4—8—…45—k—45—…—8—4—1，所需时间为。 Ii．排除k点，记=，ik,得到巡视路线序列，此时，所用时间。设，，(i,j=2,3,…，53)且表示为从点i与j(不在i或j停留)所需的时间循环判断过程如下：假设=1，且满足，即表示点i与点之间可连通并且它们到起点i所需时间依次从大到小排列。若，则在序列中点i后添加点，得1—4—8—…—i—。此时，已用时间t=,=1，且将点形如点i上述步骤按有远到近进行顺序循环。否则，继续判断是否成立，若成立，如上述循环步骤，不断增长路线序列，直至回到县政府起点；若不成立，继续判断至。5.3.2模型的求解根据“就远原则”模型循环判断，在保证最短时间内，寻找出各组的最佳巡视路线，如表5.3-3：最佳巡视路线表组数最远乡镇或村路径被巡视乡镇或村时间t1H0-2-5-6-7-E-9-F-12-H-12-F-9-E-7-6-5-2-0H6.442140-2-5-6-L-19-J-13-14-13-J-19-L-6-5-2-013,146.183150-M-25-21-K-18-I-15-I-16-17-K-21-25-M-015,166.244120-2-5-6-7-E-9-F-12-G-11-E-7-6-5-2-011,125.955100-2-5-6-7-E-9-F-10-F-9-E-7-6-5-2-09,105.78 6G0-2-5-6-7-E-11-G-11-E-7-6-5-2-0G5.67I0-M-25-21-K-18-I-18-K-21-25-M-0I,186.428F0-2-5-6-7-E-9-F-9-E-7-6-5-2-0F,76.169J0-2-5-6-L-19-J-19-L-6-5-2-0J,196.1210170-M-25-21-K-17-22-24-N-26-P-017,22,246.211180-2-5-6-7-E-8-4-D-5-2-04,5,86.1912K0-M-25-21-K-21-25-M-0K,215.513E0-2-5-6-7-E-7-L-6-5-2-0E,65.9414L0-2-5-6-L-20-25-M-0L,205.2415230-P-26-N-23-N-26-P-0N,23,266,.2416300-R-29-Q-30-32-35-34-A-1-030,32,355.791740-2-3-D-4-D-3-2-0D,45.2118250-M-25-M-0M,254.8219Q0-R-29-Q-28-27-26-P-0Q,27,286.1120340-1-A-34-A-33-A-1-0A,33,34621310-R-31-R-1-0R,314.2622D0-2-3-D-3-2-0D,2,34.6323290-P-29-P-0P,294.4424B0-C-B-1-0B,C,15.88表5.3-35.3.3结果分析由上表可看出，在允许巡视人员足够多的情况下，完成巡视的最短时间是6.44小时，并可分成24条巡视路线。并且，巡视离县政府较远的乡镇或村路线所需的时间比尽可能大，比较接近最短时间6.44；巡视离县政府较远的乡镇或村路线所需的时间反而较小，一般在4-5小时范围内，这是由该“就远原则”由远及近地寻找最佳灾情巡视路线的特点。5.3.4模型评价(1)优点：容易理解，算法简单，能找出比较合适的最佳灾情巡视路线；(2)缺点：过程繁琐，实质上是按由远及近顺序的穷举法，解答消耗时间大，并且各路线之间有许多重复的乡镇或村结点，同时有些许路线相比其它路线并不是很均衡。5.3.4模型的改进与推广针对回答问题三所用的“就远原则”模型，过程繁琐，耗费时间长，出错率高的缺点，我们可以选择利用C++编程实现这个过程。因为C++运算速度高，准确率高，有利于我们更好完成“就远原则”模型。本文的求解方法可以适用于交通路线的选择等实际问题。 六、参考文献[1]胡运权，《运筹学基础及运用》（第五版），2008[2]赵静、但琦，《数学建模与数学实验》（第二版），2006[3]韩中庚，《实用运筹学》，2007[4]王海龙、周辉仁、魏颖辉，基于遗传算法的一类多旅行商问题，2009[5]代坤、鲁士文、蒋祥刚，基于遗传算法的多人旅行尚问题求解，2004【附录】functionvarargout=mtspf_ga(dmat,salesmen,min_tour,pop_size,num_iter,show_prog,show_res)%dmat任意两点的最短路径矩阵通过floyed算法求得结果。%salesmen考察组组数%min_tour每个巡查组访问的村（镇）数%pop_size种群个体数%num_iter迭代的代数%show_prog,show_res显示的参数设定nargs=7;%处理输入参数，用来给定一些默认的参数；fork=nargin:nargs-1switchkcase0dmat=10*rand(20,20);case1salesmen=5;case2min_tour=2;case3pop_size=80;case4num_iter=5e3;case5show_prog=1;case6show_res=1;otherwiseendend%检查输入矩阵[nr,nc]=size(dmat); ifnr~=ncerror("InvalidXYorDMATinputs!")endn=nr-1;%除去起始的点后剩余的城镇的数%输入参数的检查salesmen=max(1,min(n,round(real(salesmen(1)))));min_tour=max(1,min(floor(n/salesmen),round(real(min_tour(1)))));pop_size=max(8,8*ceil(pop_size(1)/8));num_iter=max(1,round(real(num_iter(1))));show_prog=logical(show_prog(1));show_res=logical(show_res(1));%初始化路线、断点的选择num_brks=salesmen-1;dof=n-min_tour*salesmen;%可以自由访问的点数addto=ones(1,dof+1);fork=2:num_brksaddto=cumsum(addto);endcum_prob=cumsum(addto)/sum(addto);%初始化种群pop_rte=zeros(pop_size,n);%路径集合的种群pop_brk=zeros(pop_size,num_brks);%断点集合的种群fork=1:pop_sizepop_rte(k,:)=randperm(n)+1;pop_brk(k,:)=randbreaks();end%选择绘图时的巡查组的颜色可删去；clr=[100;001;0.6701;010;10.50];ifsalesmen>5clr=hsv(salesmen)end%开始运行遗传算法过程global_min=Inf;%初始化最短路径total_dist=zeros(1,pop_size);dist_history=zeros(1,num_iter);tmp_pop_rte=zeros(8,n);%当前的路径设置tmp_pop_brk=zeros(8,num_brks);%当前的断点设置new_pop_rte=zeros(pop_size,n);%更新的路径设置new_pop_brk=zeros(pop_size,num_brks);%更新的断点设置 ifshow_progpfig=figure("Name","MTSPF_GA|CurrentBestSolution","Numbertitle","off");endforiter=1:num_iter%评价每一代的种群适应情况并作出选择。forp=1:pop_sized=0;p_rte=pop_rte(p,:);p_brk=pop_brk(p,:);rng=[[1p_brk+1];[p_brkn]]";fors=1:salesmend=d+dmat(1,p_rte(rng(s,1)));%添加开始的路径fork=rng(s,1):rng(s,2)-1d=d+dmat(p_rte(k),p_rte(k+1));endd=d+dmat(p_rte(rng(s,2)),1);%添加结束的的路径dis(p,s)=d;%d=d+myLength(dmat,p_rte(rng(s,1):rng(s,2)));%可调用函数处理endtotal_dist(p)=d;%distan(p)=max(dis(p,:));%计算三个人中的最大值end%在每代种群中找到最好的路径[min_dist,index]=min(total_dist);dist_history(iter)=min_dist;%+max(distan);ifmin_dist