数学建模优秀论文-灾情巡视路线的数学模型.doc

灾情巡视路线的数学模型摘 要本文解决的是灾情巡视路线的设计问题。由于路线图可看成网络图因此此问题可转化为在给定的加权网络图中寻找从给定点出发行遍所有顶点至少一次再回到点使得总权（路程或时间）最小的问题。然后针对具体问题，采用一些启发式算法，建立模型进行求解。对于问题一：基于设计分三组巡视时使总路程最短且各组尽可能均衡的巡视路线的要求我们采用Dijkstra算法，通过对初始圈进行二边逐次修正,处理三组的巡视路线长度，用lingo软件求解出较优方案。定义分组的均衡度系数a检验分组均衡度，在均衡度为a=0.0751时得到分三组（路）巡视时，总路程最短且各组尽可能均衡的巡视路线见附表1。对于问题二：将问题转化为图论问题，运用问题一的求解方法，得到分为四组的路线，在通过均衡度分析之后得出近似最优巡视路线。利用lingo软件求得，至少要分四组，且四组的近似最优巡视路线见附表2。对于问题三：基于问题一二中图论的方法，考虑到从点巡视H点的最短时间是所有巡视线路中用时最长的，将计算出的最长路线巡视所用的时间作为巡视路线的最短时间限定，在此限定下对路线进行设计。求得的最短时间为6.43小时，最佳巡视路线分为23组。（具体分组见附录二）对于问题四：由于组数一定， T，t和V改变，对每组内的最佳巡视路线是没有影响的，但可能会影响到各组件的均衡性，因此问题实质是讨论T，t和V对分组的影响，即在不破坏原来分组均衡的条件下T，t和V允许的最大变化范围。关键词：启发式算法 Dijkstra算法 均衡度 图论 二边逐次修正1. 问题重述1.1问题背景今年夏天某县遭受水灾。为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视。巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线。附录一中给出了该县的乡（镇）、村公路网示意图，公路边的数字为该路段的公里数。1.2本文需解决的问题问题一：若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线。问题二：假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V=35公里/小时。要在24小时内完成巡视，至少应分几组；给出这种分组下你认为最佳的巡视路线。问题三：在上述关于T , t和V的假定下，如果巡视人员足够多，完成巡视的最短时间是多少；给出在这种最短时间完成巡视的要求下，你认为最佳的巡视路线。问题四：若巡视组数已定(如三组），要求尽快完成巡视，讨论T，t和V改变对最佳巡视路线的影响。 2. 模型的假设与符号说明2.1模型的假设假设1：公路不考虑等级差别，不受灾情和交通情况的影响。假设2：各条公路段上的汽车行驶速度均匀。假设3：各巡视组巡视的乡（镇）、村不受行政区划分的影响。假设4：各巡视组行动统一，一个巡视组不可再分成若干小组。假设5：巡视当中在每个乡（镇）村的停留时间一定，不会出现特殊情况而延误时间。2.2符号说明符号符号说明巡视小组在乡（镇）巡视的停留时间巡视小组在村巡视的停留时间汽车行驶速度为导出子图中的最佳圈。（其中=1，2，3，n.）为的权，（其中=1，2，3，n.）最大允许均衡度分组后的实际均衡度第个点距起始点的路线长度点的时间权重分组数第组巡视时要停留的乡（镇）数第组巡视时要停留的村数最短时间下限第巡视路线的长度第巡视所用的时间3. 问题分析此题研究的是某县灾情巡视路线的设计问题。问题要求设计出最佳的巡视路线，即：保证总路程最短或时间最小而且各组尽可能均衡的巡视路线。基于图论相关理论，借助于几何直观和生活体验的启发作用，便于为计算机搜索制定行之有效的操作规则，接着利用图论软件包通过计算机求解出较精确的路线。再通过线路均衡性比较，对均衡性不好的线路进行微调。以此方法确定最佳巡视路线。针对问题一：基于对问题的分析，借助图论知识，将所给公路网就转化为图论中的加权网络图，因此问题就转化为一个图论问题，即在给定的加权网络图中，寻找从给定点出发，行遍所有顶点至少一次再回到点，使得总权（路程或时间）最小。此即多个推销员的最佳推销员回路问题。基于以上分析，运用图论知识和图论软件包进行求解，再利用均衡度分析对得到的分组路线进行微调，均衡度越小表示路线越均衡，微调后即可得到相对较优的分组路线。可认为这样设计的分组方法和巡回路线能使总路线近似最短。针对问题二：在问题一的基础上添加了巡视组在各乡镇停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V=35公里/小时等条件，要求在24小时内完成巡视的最少分组数以及相应的最佳巡视路线。首先，由图中数据初步计算后判断分成四组可行，再针对分组为四组的情况进行线路设计，仍将问题转化为图论问题，运用问题一的求解方法，得到分为四组的路线，在通过均衡度分析之后得出近似最优巡视路线。针对问题三：在问题二中关于T , t和V的假定下且巡视人员足够多时，要求在最短时间完成巡视的要求下所得的最佳的巡视路线，此时考虑到从点巡视H点的最短时间是所有巡视线路中用时最长的，将计算出的最长路线巡视所用的时间作为巡视路线的最短时间限定，在此限定下对路线进行设计。基于问题一二中图论的方法，从一些点的路线比较少的点开始，能够使搜素容易进行，因此选择从距离点一些较远的点（如12 10 15 22等点）开始搜索，每次搜索时都要对该点的巡视时间进行判断，直到找到近似最优路线。针对问题四：在巡视组数已定(如三组）的情况下，为尽快完成巡视就要求每组完成的巡视时间尽量均衡，因为总的完成巡视时间按线路最长的完成巡视时间计算，由于组数一定， T，t和V改变，对每组内的最佳巡视路线是没有影响的，但可能会影响到各组件的均衡性，因此问题实质是讨论T，t和V对分组的影响，即在不破坏原来分组均衡的条件下T，t和V允许的最大变化范围。需要用控制单一变量的方法，分别讨论T、t、V三个量中任意两个量不变时第三个量的变化范围。从而确定T，t和V的改变对最佳巡视路线的影响。4. 数据分析4.1问题一数据分析基于对该县公路图的初步分析，可以统计出该县有乡（镇）17个，村35个。（线路图见附录一）应用lingo软件求解(具体程序见附录三)得出巡视点距离县政府所在地的最短距离，如表1所示：表1：点到其余各点的最短距离PR1C2M26O10.112.9611.59.219.820.6282931AB35O22.220.822.116.311.91417.5N2520L67DO31.131.838.33927.234.522.248E9F1012O34.949.741.749.555.165.967.311GH1314J19O55.962.777.564.172.754.346.218I15161722KO52.961.169.960.353.54943.721232427Q3032O39.63944.328.42835.730.2333534O23.73627.8由此表格画出了最短路径生成图，如图1图 1由上图便于在第一问分析得到分组情况。4.2问题二数据分析问题二中给出了巡视小组在乡（镇）村的停留时间和汽车行驶速度，分别为：巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V=35公里/小时。对于要在24小时内完成巡视，至少应分几组的问题，应首先求出最长路线巡视所用的时间，用停留总时间加上行走时间除以4的结果与24进行比较，以此判断最少分组能否为4组。计算如下：(17*2+35+599.8/35)/4=21.524(小时)（其中路线长度估算为599.8公里）因此最少分组可定为4组。 5 问题一的解答本文研究的是灾情巡视路线的最优设计问题，由于路线图可看成网络图，因此此问题可转化为在给定的加权网络图中寻找线路使总权（路程或时间）最小的问题。然后针对具体问题，采用一些启发式算法，建立模型。5.1模型一的建立5.1.1模型一的准备经对问题的初步分析，基于图论的相关知识，将公路网图中每个乡（镇）、村看成图中的一个节点，各乡镇村之间的公路看作图中对应节点间的边，各条公路的长度（或行驶时间）看作对应边上的权，所给公路网就转化为图论中的加权网络图，问题就转化为一个图论问题，即在给定的加权网络图中寻找从定点出发，行遍所有顶点至少一次再回到点，使得总权（路程或时间）最小。定义经过图的每个顶点正好一次的圈，称为的哈密尔顿圈，简称圈。定义 在加权图中（）权最小的哈密尔顿圈称为圈：（）经过每个顶点至少一次且权最小的闭通路称为最佳推销员回路。由定义（2）可知本问题是一个寻求最佳推销员回路的问题，最佳推销员回路的问题可以转化为最佳圈的问题，方法是由给定的图（，）构造一个以为顶点集的完备图=（，）中每条边（x y）权等于顶点x与y在图中最短路径的权，即。在图论中有以下定理：定理 加权图的最佳推销员回路的权和的最佳圈的权相同。定理2 在加权完备图中求最佳圈的问题是NP完全问题。我们采用一种近似算法求出该问题的一个近似最优解，来代替最优解，算法如下：算法一 求加权图（，）的最佳推销员回路的近似算法：用图论软件包求出中任意两个顶点间的最短路，构造出完备图（，）输入图的一个初始圈；用对角线完全算法2产生一个初始圈；随机搜索出中若干个圈，例如3000个；对步所得的每个圈用二边逐次修正法2进行优化，得到近似最佳圈；在第步求出的所有圈中，找出权最小的一个，此即要找的最佳圈的近似解。（算法程序见附录）由于二边主次修正法的结果与初始圈有关故本算法第步分别用三种方法，产生初始圈，以保证能得到较优的计算结果。在此问题是多个推销员的最佳推销员回路问题，即在加权图中求顶点集的划分1，将G分成n 个生成子图G， ，Vn，使得：顶点，1,2,3，n.，其中i 为导i的导出子图G中的最佳圈，w(Ci)为Ci 的权，i，j=1，2，3，n.定义3 称为该分组的实际路线均衡度，为最大允许均衡度，显然01，越小说明分组的均衡性越好，取定一个后，与满足条件3的分组，条件4表示总巡视路程最短。此问题包含两个方面：第一，对点分组；第二，在每组中寻求最佳推销员回路，即为单个推销员的最佳推销员问题，我们只能去寻求一种较合理的划分准则，对图进行初步划分后，求出各部分的最佳推销员回路的权，在进一步进行调整，使得各部分满足均衡性条件3.从点出发去其它点，要使路程较小应尽量走点到该点的最短路，故用图论软件包求出点到其余顶点的最短路，这些最短路构成一棵以为树根的树，将从点出发的树枝称干枝，如图2：图 2从图中可以看出，从点出发到其它点共有6条干枝，他们的名称分别为，。根据实际工作的经验及上述分析，在分组时应遵循以下准则：准则一 尽量使同一干枝上及其分支上的点分在同一组；准则二 应将相邻的干枝上的点分在同一组；准则三 尽量将的干枝与短的干枝分在同一组。由上述分组原则，为我们找到两组分组形式如下：分组一：（，），（，），（，）分组二：（，），（，），（，）显然由图中可以直接看出分组一的方法极不均衡，故考虑分组二。对分组二中每组顶点的生成子图，用算法一求出近似最优解及相应的巡视路线，使用算法一时在每个子图所构造的完备图中，取一个尽量包含图1中树上的边的圈作为其第二步输入的初始圈。依次求解得到巡视路线的近似最优解。5.1.1综上所述，问题一的优化模型为：5.2问题一的解答。在本模型的基础上，运用lingo软件求解出分三组巡视时近似最优的巡视路线（具体程序见附录三），如表2：表2：分三组巡视的近似最优路线图组号路 线路线长度路线总长度IOP282726N2423221716I15I18K212025MO191589.8IIOR29Q303231333534A1BC3D4D32O192.3IIIO256L19J11G1314H12F10F9E8E7652O206.55.3问题一的结果分析由以上分三组所得的路线结果可以看出，第一组的巡视路线为：282726N2423221716I1518K212025MO 第二组巡视路线为：R29Q303231333534A1BC3D4D32O第三组巡视路线为：256L19J11G1314H12F10F9E8E7652O将以上巡视线路的巡视距离进行均衡度分析：=7.46%=0.0746当规定距离均衡度=0.1时，此三组的巡视路线的设计均符合要求。而且实际均衡度比0.1小得多，可见路线设计很合理。6. 问题二的解答6.1模型二的建立6.1.1确定目标函数由于T=2小时，t=1小时，V=35公里/小时，需访问的乡（镇）共有17个，村共有35个，计算出在乡镇的总停留时间为：17*2+35=69（小时）需要在24小时内完成巡视，考虑行走时间有： (17*2+35+599.8/35)/4=21.524(小时)（其中最长路线长度估算为599.8公里）因此最少分组可定为4组。由于该网络的乡（镇）、村分布较均匀，故有可能找处停留时间计量均衡的分组，当分四组时各组停留时间大约为：69/4=17.25（小时）则每组分配在路途的时间大约为：2417.25=6.75（小时）问题分析时有分三组路线时，巡视总路线最长的是599.8公里，分四组时的总路程更不会比599.8公里大太多，不妨以599.8公里来计算，路途时间约为：（599.8/35)/4=4.25（小时）由于4.250时，要保持原均衡分组不变，T必须满足的条件为：2.当Yi-Yj0时，要保持原均衡分组不变，t必须满足的条件为：3.当Si-Sj0时，有（1）当时，有（2）当时，有由1.2.3.中的式子知，当T 、t、V三个变量中任意两个变量无论如何变化，都可计算出为保持均衡分组不变，三个变量所允许的最大变化范围。（二）分三组的实例讨论。现对分三组的情况进行实际讨论。对问题一中所得的三个分组，若考虑停留时间和行驶时间，且取T=T0=2小时，t=t0=1小时，V=V0=35公里/小时时，结果如下表4所示：表4：分三组巡视相关表编号XiYiSi行驶时间总时间I5131915.4628.46II611192.35.4928.49III612206.55.929.9由表可计算时间的实际均衡度为：=4.8%=0.048实际时间误差=0.048*29.9=1.44（小时）现分别规定均衡分组的最大允许均衡度为=4.8%和=9.6%,即最大允许的时间误差分别为：1.44小时和2.88小时。计算出T , t和V中三个参量中任意两个固定时，要不破坏原平衡分组，另一个参量所要允许的变化范围。计算结果如下表5：表5：T ，t，V中三个参量的变化范围T，V不变t，V不变T，t不变=4.8% =1.44=9.6% =2.88由上表可以看出：（1）当实际均衡度=4.8%，刚好等于最大允许均衡度=4.8%时，要保持原均衡分组，当：t，V不变时，T只能减小，且下界为1.25小时，上界为2小时。T，V不变时，t只能增大，且上界为1.38小时，下界为1小时。T，t不变时，V只能增大，且无上界，V的下界为35公里/小时。（2）当实际均衡度=4.8%，小于最大允许均衡度=9.6%时，要保持原均衡分组，当：t，V不变时，T的变化上界为0.51小时，下界为2.74小时。T，V不变时，t的变化上界为0.63小时，下界为1.75小时。T，t不变时，V无上界，V的下界为17.3公里/小时。9. 模型的评价、改进及推广9.1模型评价优点：（1）本文提出的分组准则简便易行，可操作性强，且可逐步调整使分组达到均衡。（2）引用均衡度的概念定量的刻画了分组的均衡性。（3）再用近似法求解最佳推销员回路时采用了三种不同的方法产生初始圈，使得算法比较完善，得到了误差很小的而近似最优解。（4）从理论上定量的讨论了T，t和V的变化对均衡分组灵敏度的影响，得到了很好的结果。缺点：使用的方法不能求得最优解，只能求得近似最优解。9.2模型改进（1）求解时可建立将多组路线转化为一组路线来求解的思想，如果能够找出一种准则，使三个代表县城点之间的距离尽量大，则在最好的情况下，将使两个县城点均分整个一条路线，这种改进将简化问题的求解，并可以得到较好的解。（2）由于线路的设计是在假设条件下取得的近似最优解，因此，需要减少假设更多的考虑实际情况下的最优路线的设计。9.3模型推广本文建立的模型可以广泛它应用于实际生活中涉及到图论的有关问题，例如公交线路的而选择问题，城市相关设施的布置等相关问题。参考文献1 运筹学与实验/薛毅，耿美英编著。北京：电子工业出版社，2008.9 2 运筹学教材编写组编，运筹学（3版），北京：清华大学出版社，2005.63 图论算法及其MATLAB实现/王海英等编著. 北京：北京航空航天大学出版社，2010.2附录附录一：县政府线路图附录二：编号巡视路径停留地所需时间时间差1O-2-5-6-7-E-9-F-12-H-12-F-9-E-7-6-5-2-OH6.4302O-2-5-6-L-19-J-13-14-13-J-19-L-6-5-2-O13,146.150.283O-2-5-6-7-E-9-F-10-F-9-E-7-6-5-2-O10,75.770.664O-2-5-6-7-E-9-F-12-F-9-E-7-6-5-2-O12,95.850.585O-M-25-21-K-18-I-15-I-18-K-21-25-M-O15,185.990.446O-2-5-6-7-E-11-G-11-E-7-6-5-2-OG5.580.557OM-25-K-18-I-18-K-25-M-0-OI5.490.948O-M-25-21-K-17-16-17-K-21-25-M-O16,175.450.989O-2-5-6-7-E-11-E-7-6-5-2-O11,E6.190.2410O-2-5-6-7-E-9-F-9-E-7-6-5-2-OF5.151.0811O-2-5-6-L-19-J-19-L-6-5-2-OJ,196.100.3312O-P-26-N-23-22-23-N-26-P-O22,23,265.800.6313O-2-5-6-7-E-8-E-7-6-5-2-O8,5,25.800.6314O-P-26-N-24-N-26-P-O24,N5.530.9015O-M-25-21-K-21-25-M-OK,215.500.9316O-2-5-6-L-6-5-2-OL,65.231.0217OM-25-20-25-M-O20,25,M6.190.2418O-R-31-32-35-34-A-1-O31,32,34,356.320.1119O-29-Q-30-29-R-O30,Q,296.040.3920O-2-3-D-4-D-3-2-O4,D,35.990.4421O-1-B-C-O1,B,C5.980.4522OP-26-27-28-P-O-27,P,26,286.380.0523O-1-A-33-A-R-OA,33,R6.410.02附录三最短路径算法% 求两点间最短路的 Dijkstra 算法function d index1 index2 = Dijkf(a)% a 表示图的权值矩阵; d 表示所求最短路的权和% index1 表示标号顶点顺序； index2 表示标号顶点索引% 参数初始化M = max( max(a) );pb(1 : length(a) = 0;pb(1) = 1;index1 = 1;index2 = ones(1, length(a);d(1 : length(a) = M;d(1) = 0; temp = 1;% 更新1(v), 同时记录顶点顺序和顶点索引while sum(pb) = 2 index = index(1); end index2(temp) = index;endd;index1;index2;第一组路径的程序SETS:city/1, 2, 7, 8, 9, 16, 17, 18, 37, 38, 39,40, 41,42, 43, 44, 45, 46,47/:u;link(city, city):w, x;ENDSETSDATA:!w = FILE(C:UsersAdministratorDesktopdata51.txt);w = 0 10.1 19.8 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10.1 0 10000 10.5 12.1 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 19.8 10000 0 10000 10000 14.2 12.0 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10.5 10000 0 10000 10.5 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 7.8 10000 12.1 10000 10000 0 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 7.9 10000 10000 14.2 10.5 10000 8.8 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 7.9 13.2 10000 10000 12.0 10000 10000 8.8 0 6.5 10000 10000 10000 10000 10000 10000 10000 7.8 10000 10000 10000 10000 10000 10000 10000 10000 10000 6.5 0 10000 10000 10000 10000 10000 10000 10000 7.9 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 0 8.2 10000 10000 10000 10000 9.2 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 8.2 0 8.8 11.8 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 8.8 0 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 11.8 10000 0 6.8 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 6.8 0 6.7 9.8 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 6.7 0 10.1 10000 10.0 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 9.2 10000 10000 10000 9.8 10.1 0 4.1 10000 10000 10000 10000 10000 10000 10000 10000 10000 7.8 7.9 10000 10000 10000 10000 10000 10000 4.1 0 9.1 10000 10000 10000 10000 10000 10000 10000 7.9 10000 10000 10000 10000 10000 10000 10000 10.0 10000 9.1 0 8.9 10000 10000 10000 10000 10000 10000 13.2 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 8.9 0 18.8 10000 10000 10000 7.8 7.9 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 18.8 0ENDDATAn = SIZE( city ); MIN = SUM( link: w * x );FOR( city(k):SUM( city(i) | i #ne# k : x(i,k) ) = 1;SUM( city(j) | j #ne# k : x(k,j) ) = 1;);FOR( link(i,j) | i #gt# 1 #and# j #gt# 1 #and# i #ne# j:u(i) - u(j) + n * x(i,j) = n - 1 );FOR( link: BIN(x) );第二组路径的程序SETS:city/1, 3, 4, 5, 6, 10, 11, 12, 13, 14, 22, 23, 48, 49, 50, 51, 52, 53/:u;link(city, city):w, x;ENDSETSDATA:!w = FILE(C:UsersAdministratorDesktopdata51.txt);w = 012.9611.59.21000010000100001000010000100001000010000100001000010000100001000012.901000010000100007.99.28.810000100001000010000100001000010000100001000010000610000011.210000100001000010.35.910000100001000010000100001000010000100001000011.51000011.2010000100001000010000117.910000100001000010000100001000010000100009.21000010000100000100001000010000100004.81000010000100001000010000100001000010000100007.910000100001000001000010000100001000010000100007.21000010000100001000010000100009.2100001000010000100000100001000010000100001000010000100008.17.31000010000100008.810.3100001000010000100000100001000010000100001000010000100007.41000011.510000100005.911100001000010000100000100001000010000100001000010000100001000017.61000010000100007.94.81000010000100001000008.2100001000010000100001000010000100001000010000100001000010000100001000010000100008.2012.7100001000010