数模论文之灾情巡视路线相对优化方案.doc

《数模论文之灾情巡视路线相对优化方案.doc》由会员分享，可在线阅读，更多相关《数模论文之灾情巡视路线相对优化方案.doc（26页珍藏版）》请在课桌文档上搜索。

1、最佳灾情巡视路线问题的研究摘要本文分析的是最佳的巡视路线问题,我们用WinQSB,matlab,Excel对原路线图进行处理,求得其最小生成树,并以巡视总路程、各组巡视时间和路程时间均衡度为目标函数建立模型,通过图论软件包、Matlab软件求解,并对结果进行均衡度检验,设计出了最佳巡视路线,而且对影响最佳巡视路线的因素进行了定量分析。针对问题一：问题一我们运用了用WinQSB对原路线图进行处理,求得其最小生成树,提出了分块准则,我们根据分块准则,建立了以巡视总路程和路程均衡度为目标函数的多目标标模型,并通过分析比较和路程均衡度检验,最终得出了最佳巡视路线,此时巡视总路程,路程均衡度为。针对问题

2、二：我们通过分析可知在此种情况下至少需分4组巡视,并在题一得出的最小生成树的基础上,提出分块准则,建立了以个组巡视总时间和时间均衡度为目标函数的多目标模型,并通过分析比较和时间均衡度检验,得出了最佳巡视路线,此时小时,时间均衡度。针对问题三：我们通过图论软件包求出了所有的点到点的最短距离,以及离最远的点为点,我们以巡视点的最短时间为各组各组巡视时间的上限,运用图论软件包和自己分析判断,最终制订了最佳巡视路线,此分组组数为7组。针对问题四：我们假设该问题是已经定分为三组的情形,且在乡镇停留时间为在村停留时间整数倍情况下讨论的改变对最佳巡视路线的影响。由问题一的求解结果可知,第三组巡视路线较第一组

3、、第二组巡视路线长,所以我们只讨论在改变时对第三组巡视路线的影响进行分析以说明问题。最终得出结论：停留时间的改变对最佳巡视路线影响较大；汽车时速的改变对最佳巡视路线的确定影响较小。关键词：WinQSB matlab 图论软件包 最小生成树1.问题重述1.1问题的提出下图为某县的乡镇、村公路网络示意图,公路边的数字为该路段的公里数。今年夏天某县遭受水灾。为考察灾情、组织自救,县领导决定,带领有关部门负责人到全县各乡镇、村巡视,巡视路线指从县政府所在地出发,走遍各乡镇、村,又回到县政府所在地的路线。1.2需要解决的问题问题1：若分三组路巡视,试设计总路程最短且各组尽可能均衡的巡视路线图。问题2：假

4、定巡视人员在各乡镇停留时间T=2小时,在各村停留时间t=1小时,汽车行驶速度V=35公里/小时。要在24小时完成巡视,至少应分几组；给出这种分组下你认为最佳的巡视路线。 问题3：在上述关于T , t和V的假定下,如果巡视人员足够多,完成巡视的最短时间是多少；给出在这种最短时间完成巡视的要求下,你认为最佳的巡视路线。 问题4：若巡视组数已定如三组,要求尽快完成巡视,讨论T,t和V改变对最佳巡视路线的影响。2.问题分析2.1问题一的分析此题要求我们分三组巡视路线,使三组的总路程最小且各组尽可能的均衡,为此我们可以考虑建立以三组巡视路线总路程值最小和三组路程的均衡度两个目标函数的模型。首先我们可以运

5、用WinQSB构造巡视图的最小生成树,然后以最小生成树的主干将生成树分成三组,分别构造出每组总路线值最小的回路,如果以上两个目标值不佳,我们还可以重新分组,进过多次调整达到较为合理的结果。2.2问题二的分析此问在第一问基础上增加了时间限制,要求在24小时完成巡视,我们算得完成巡视所需的总停留时间为69小时,如果按照第一问中分三组巡视,完成巡视所需的总停留时间应该不大于小时,则每辆汽车行驶的时间不能超过小时,而车行驶速度为35公里/每小时,这显然不能满足需求,为此我们考虑至少需要分四组,如果分四组,完成巡视所需的总停留时间应该不大于小时,则每辆汽车行驶的时间不能超过小时,在这种情况下,巡视的总路

6、程的最大值为公里,我们以题一巡视总路程609.3公里为参考值,将巡视人员分为四组是可行的,然后我们分别以四组巡视的总路程、四组路程均衡度、四组完成巡视的停留时间和时间均衡度为目标函数建立模型,并重点考虑四组完成巡视的停留时间和时间均衡度为目标函数建立模型。2.3问题三的分析此题在第二问基础上放宽了条件,即巡视人员不受限制,此时完成巡视的时间由离县政府最远的乡镇或村决定要求完成巡视的最短时间,我们只要求离点最短距离最大的巡视点,然后算出行驶时间与在巡视点停留的时间之和即为完成巡视的最短时间,在最短巡视时间要求下,如果我们可以分足够多的组,必定能完成巡视人物,但考虑到这在现实生活中是不可能的,所以

7、我们应该在满足条件的基础上尽量减少巡视组数,然后求出最小生成树后可以对每个结点进行遍历,借助图论软件包进行协助,这样可以求出最佳的巡视路线,2.4问题四的分析假设该问题是己定分三组的情形,且要求在尽快完成巡视的情况下讨论的改变对最佳巡视路线的影响。由问题一的求解结果可知 ,第三组巡视路线较第一组 、第二组巡视路线费时,故我们不妨讨论在改变时对第三组巡视路线的影响进行分析以说明问题。3.模型假设假设一：汽车在路上的速度时一定的,不会出现抛锚等现象。假设二：巡视过程中,在每个乡镇、村停留时间一定,不因特殊情况而延误时间。假设三：每个小组的汽车行书速度基本相同。假设四：分组后,各小组只能走自己区的路

8、,不能走其它小组的路,出公路外。假设五：忽略人员上下车的时间,因此村镇被巡视一次后,再次经过时会停留让人员上车,但时间不计入总时间计算。假设六：巡视时可以经过一条路多次4.符号约定巡视人员在各乡停留时间巡视人员在各村停留时间第组巡视人员巡视总时间巡视总时间汽车行驶速度汽车行驶总路程各组汽车行驶路程各组路程均衡度分组组数各组巡视的村庄数目各组巡视的乡镇数目赋权连通图的第个子图的第个子图的顶点数乡镇的巡视数村的巡视数是各巡视组中最长的路程各组时间均衡度5.数据处理为了便于制定出最佳的巡视路线,首先我们运用WinQSB求得巡视路线图的最小生成树：图1 最小生成树Node数值与地图中字符的对应表Nod

9、e12345678910字符OABCDEFGHINode11121314151617181920字符JKLMNPQR12Node21222324252627282930字符3456789101112Node31323334353637383940字符13141516171819202122Node41424344454647484950字符23242526272829303132Node515253字符3334356.问题一的解答针对问题一我们建立模型一6.1模型一的建立6.1.1确定目标函数根据题意,根据题目信息,我们将巡视路线图抽象为一个赋权无向连通图,现要分三组进行巡视,则需要将分成三个

10、子图,在每个子图中寻找路程最小的回路,于是我们以汽车行驶总路程和各组行驶路程的均衡度为目标函数：6.1.2 确定约束条件各组行驶路线路程最小值：则行驶路线总路程最小值：根据路线巡视图可知,除县政府意外有52个巡视点,则各组巡视点之和应该满足且各组行驶路程的均衡度应该小于0.1才算比较均衡即6.1.3综上所述,得到问题一的模型6.2 模型一的求解6.2.1确定准则 为了设计出更为合理的巡视路线,我们规定了以下准则准则一：尽量使同一支干上集分支上的点分在同一组；准则二：尽量使相邻干支上的点分到同一组；准则三：尽量将长的干支与短的干支分到同一组6.2.2求解过程在以上准则前提下,我们根据最小树分块原

11、则,将图初步分块成三个子图,提出了三种设计方案,每种方案是在前种方案基础上进行调整,最终确定方案三时最佳的。设计方案一：我们根据分组原则确定第一条分组方案,方案一如下表一：巡视路线图1组号巡视路线巡视路程1O1B3435323133AR29Q30Q282726PO154.02OP26N242321K221716I18I1514H1413J19L2025M0239.33O2567E9F10F12G11E84D3CO185.2 此种情况下总的行驶路程为：公里,路程的均衡度为：方案一结果分析由计算结果可知,行驶总路程,结果较满意,但均衡度,说明此分组方案明显不能达到均衡的要求,故需重新调整分组方案,

12、为此我们考虑第二种分组方案。设计方案二：鉴于方案一不能满足要求,故我们提出来方案二,方案二如下表二：巡视路线图2组号巡视线路巡视路程1O1B3435323133AR29Q30Q28272423N26PO192.32OM2521K17221716I18I1514H1413J19L2025M0223.03O2567E9F10F12G11E84D3CO185.2此种情况下总的行驶路程为：公里,路程的均衡度为：方案二结果分析此结果虽然较第一种行驶总路程有所增加,但均衡度明显有所改善,考虑到此时均衡度仍然大于0.1,故我们需进一步改进。设计方案三：分析表2可知,第二组与第三组走的路程间的差值还是比较大,

13、也就是说这样分组的均衡性还有待改善。于是,我们在基于最小生成树的原则之上对初步改进后的分组进行适当的调整。为了缩小第二、三组间的路程差,首先,我们将第二组的H点分到第三组；然后采用上述中同样的方法求解得到最终改进后各组的巡视路线图见表3。第三组方案如下表三：巡视路线图3组号巡视路线巡视路程1OP26N23242728Q3029RA3331323534B1O197.62OP26N2521K22171618I151413J19L2025MO204.93OC3D48E9F10F12H12G11E7652O206.8此种情况下总的行驶路程为：路程的均衡度为：方案三结果分析经调整以后计算发现,总的行驶路

14、程有所增加,但增加不大；路程的均衡度已经满足要求,故我们认为方案三是合理的分组方案,下图是我们确定的具体的三组巡视路线图 三组巡视路线图7.问题二的解答针对问题二,我们建立了模型二。7.1模型二的建立7.1.1确立目标函数此题在要求在24小时完成巡视,且各乡镇停留时间T=2小时,在各村停留时间t=1小时,汽车行驶速度V=35公里/小时。所以我们建立以下目标函数：7.1.2确定约束条件各组的巡视时间为如果要在24小时完成巡视,则且分组的组数应满足下式同样巡视的总地点数且时间均衡度也应当满足7.1.3综上所述,得到问题二的模型7.2模型二的求解7.2.1确定准则首先,为了制定更加合理的巡视路线,在

15、分组时应遵从以下准则：准则一：尽量使同一干枝及其分枝上的点分在同一组；准则二：应将相邻的干枝上的点分在同一组；准则三：尽量将长的干枝与短的干枝分在同一组.准则四：尽量使各组的停留时间相等.7.2.2求解过程由题意算得停留总时间,要在24小时完成巡视,则应满足,由问题一结果可知的值最小也有578公里,将带入前式得,可见至少为4.为此,我们同样采用问题一的准则,根据最小生成树的分块原则,我们将图分块成四个子图。并找出满足条件每个子图的最佳回路,最终我们经过计算分析得到了是符合要求的,再此情况下设计方案和有关结果如下其中用红色标记的是经过却不停留的村或乡镇,：表四：巡视路线图4组号巡视路线巡视路程行

16、驶时间停留时间总时间1OR29Q303231333534ABC1O141.74.051822.052OP282726N2423221716I18K2125MO166.94.771822.773OM252021K18I1514H1413J19L652O183.45.241722.244O23D7E9F10F12G11E84D32O183.85.251621.25此种情况下总的行驶路程为：路程的均衡度为：时间均衡度为：巡视路线图如下：四组巡视路线图7.3模型二结果分析 由结果可知,行驶的总路程叫第一问结果增大,由于此种情况会不可避免的走重复路,所以总路程增大时在情理之中；路程的均衡度,但此时我们主

17、要考虑的是在规定时间完成巡视,故时间和时间均衡度时考虑的主要因素,而路程的均衡度为次要因素,结果显示时间均衡度,符合题目要求,所以此时分四组巡视不仅满足要求,而且其设计方案也是最佳的。8.问题三的解答针对问题三,我们建立了模型三。8.1模型三的建立8.1.1确立目标函数按照题意我们以完成巡视最短时间和各组巡视时间建立目标函数,目标函数为：8.1.2确定约束条件离点最远的最短距离为,则各组巡视时间如果要要在最短时间完成巡视,则各组巡视时间必须满足：同样巡视的地点总数也应满足8.1.3综上所述,得到问题三的模型8.2模型三的求解此问题就是要求如果有足够多的巡视人员,怎样确定最佳路线是完成巡视的时间

18、最短。实际上,完成巡视的最短时间受到单独巡视离县城最远的乡镇、村所需时间的制约,同时我们可以求出离县城最远的点是H点,距离为77.5公里。因此,单独巡视返回该乡所需的时间为小时。由此可知,即使巡视人员再多,分组再细,完成巡视至少需要6.4小时。基于此,此题就可以转化为求在6.4小时完成巡视的最少分组数和最佳巡视路线。为达到以上目标,我们制定了以下分组巡视原则：1、对图中偏西且距县政府较远的乡镇、村：1在6.4小时,每组巡视人员尽可能走足够多的乡镇、村。 2在巡视时,尽量按出发点到该次巡视终点最短路径的路线巡视,但在不超过6.4小时的原则下,为了能够途经更多的点,我们可以不走最短路线。3巡视车从

19、县政府出发,途中每到达一个乡镇、村,部分巡视人员下车巡视,车不停留忽略不计巡视人员上、下车的时间继续开往下个站点,直到到达最远点,车停下等待；然后按原路返回,依次到达每点接回巡视人员,直至出发点。2、由于第一种分组原则下,在最远点必须要花1或者2个小时的停留时间,针对这一浪费时间的缺点,对图中偏东且距县政府较近的乡、村,我们改进一种按圈巡视的方法,原则如下：1每组巡视人员巡视路线构成一个圈,且巡视两圈。2第一圈巡视时,途中每到达一个乡镇、村,部分巡视人员下车巡视,车不停留忽略不计巡视人员上、下车的时间继续开往下个站点,直至出发点,仍不停留继续第二圈巡视,到达每点依次接回巡视人员,直至回到出发点

20、,结束。3在遵循不超过6.4小时原则下,按圈巡视时,总路线不能过长,不超过112公里；总路线也不能过短,避免车停留等待而浪费时间。依据以上原则,我们在6.4小时完成巡视,总共分成了7组,前5组遵循的第一种分组原则,后2组依据的第二种按圈分组原则。具体的分组巡视路线和所需时间见下表五。表五时间单位：小时组号巡视路线总时间1O2567E9F12H14H12F9E7652O6.432OM252021K18I15I18K212025MO5.873O256L19J13G11G13J19L652O6.154O23D48E9F10F9E84D32O6.385OP282726N2423221716172223

21、24N262728PO6.376OR3133A1COR3133A1CO47OR29Q30323534B1OOR29Q30323534B1O5.64注：红色标记的表示经过此点但无巡视人员上、下车。各组巡视路线8.3模型三的结果分析9.问题四的解答针对问题四,我们建立了模型四。9.1模型四的建立9.1.1确立目标函数由问题一的求解结果可知 ,第三组巡视路线较第一组 、第二组巡视路线长,故我们不妨讨论在改变时对第三组巡视路线的影响进行分析以说明问题。假设乡镇停留时间是村停留时间的倍,则以该组完成巡视需要的时间为目标函数：则9.1.3综上所述,得到问题四的模型9.2模型的求解将第三组巡视的有关数据带入

22、上式得：9.3模型四的讨论分析下面就,的改变即行程速度和停留时间的改变,对上式模型的分析如下：1若为定值,则式中是常数,分别是自变量和因变量,且,之间为反比例函数。假设,则如下：由上图可知,此时提高汽车的时速,变化很小,说明对影响不明显,即增大时速对最佳巡视路线的选择影响不大。2若为定值,则式中是常数,之间是正比例函数关系。假设,则如下：由上图可知,此时停留时间减小,成线性递减趋势,从而说明对的影响明显,即停留时间对最佳巡视路线的选择影响较大。综上所述,停留时间的改变对最佳巡视巡视路线影响比较大；汽车时速的改变对最佳巡视路线的确定影响很小。10模型优缺点10.1 模型的优点优点一： 模型一和模

23、型二分部采用了路程均衡度和时间均衡度进行了评估,提高了模型的实用性；优点二：在模型的求解时,先进行了主观判断,再利用计算机软件进行求解,大大减少了计算量。优点三：模型求解过程,对模型进行了逐步调整,增加了结果的准确度 10.2 模型的缺点缺点一：由于本模型要分析比较,运算量较大,出现误差在所难免；缺点二：本文是在假定汽车匀速行驶 ,巡视组在乡镇的停留时间为村的倍数等条件下建立模型 ,在操作时根据实际情况可以适当调整；缺点三：在分块的过程中,没有明确的算法,只是通过主观判断来将子图的顶点进行调整；11.模型的改进与推广11.1模型的改进1由于该模型采用网络图的最小树形图与以为出发点的最短路树形图

24、相结合的方法求解是比较好的 ,2由于在建模过程中对实际可能发生的情况考虑较少 所以在实际应用中,某些情况仍需进步讨论 ,使得到的方案更加实用11.2模型的推广这种设计最佳路线的问题在实际生活中有很多,所以此模型在日常中发挥了很重要的作用。在解决多路旅行商,车辆路线组织、考察某地灾情和作业调度等方面的问题时可以用这些方法来解决。12.参考文献1 宋来忠,王志明,数学建模与实验,：科学,2005。2 中庚,数学建模方法及其应用,高等教育,2007。3 学桢,数学建模方法,大学,1999。附录附录一：clc,cleara=zeros; a=6.0;a=12.9;a=11.5;a=9.2;a=19.8

25、;a=10.1;a=10.3; a=5.9;a=11.2;a=4.8;a=8.3;a=7.9;a=8.2;a=12.7;a=20.4;a=11.4;a=11.3;a=9.7;a=9.5;a=7.3;a=11.8;a=15.1;a=7.2;a=14.5;a=8.0;a=7.8;a=5.6;a=10.8;a=13.2;a=14.2;a=6.8; a=7.8;a=12.2;a=10.2;a=16.4;a=9.8;a=8.6;a=8.6;a=15;a=9.9;a=8.8;a=6.8;a=11.8;a=6.7;a=9.8;a=9.2;a=8.2;a=8.2;a=93;a=7.2;a=8.1;a=7.9;

26、a=6.5;a=5.5;a=9.1;a=6.5;a=4.1;a=10.0;a=10.1;a=8.9;a=7.9;a=18.8;a=13.2;a=8.8;a=12.0;a=7.8;a=10.5;a=10.5;a=7.9;a=8.3;a=12.1;a=7.2;a=7.9;a=15.2;a=10.3;a=7.7;a=8.1;a=7.3; a=9.2;a=19;a=14.9;a=7.4;a=8.2;a=11.5;a=17.6;a=12.2;a=8.8;a=11.0;a=15.8;a=14.2;a=a+a;afind=inf;result=;p=1;tb=2:length;while length=length1 temp=a;temp=temp; d=min; ,kb=finda=d; j=p;k=tbkb; result=result,j;k;d; p=p,k; tbfind=;endresult