精心整理灾情巡视路线的数学模型摘要本文解决的是灾情巡视路线的设计问题。
由于路线图可看成网络图因此此问题可转化为在给定的加权网络图中寻找从给定点Ｏ出发行遍所有顶点至少一次再回到点Ｏ使得总权（路程或时间）最小的问题。
然后针对具体问题，采用一些启发式算法，建立模型进行求解。
对于问题一：基于设计分三组巡视时使总路程最短且各组尽可能均衡的巡视路线的要求我们采用Dijkstra算法，通过对初始圈进行二边逐次修正,处理三组的巡视路线长度，用lingo软件求解出较优方案。
定义分组的均衡度系数a检验分组均衡度，在均衡度为a=0.0751时得到分三组（路）巡视时，总路程最短且各组尽可能均衡的巡视路线见附表1。
1.问题重述1.1问题背景今年夏天某县遭受水灾。
为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视。
巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线。
附录一中给出了该县的乡（镇）、村公路网示意图，公路边的数字为该路段的公里数。
1.2本文需解决的问题问题一：若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线。
问题二：假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V=35公里/小时。
要在24小时内完成巡视，至少应分几组；给出这种分组下你认为最佳的巡视路线。
2.12.2路线。
因此问题就转化为一个图论问题，即在给定的加权网络图中，寻找从给定点Ｏ出发，行遍所有顶点至少一次再回到Ｏ点，使得总权（路程或时间）最小。
此即多个推销员的最佳推销员回路问题。
基于以上分析，运用图论知识和图论软件包进行求解，再利用均衡度分析对得到的分组路线进行微调，均衡度越小表示路线越均衡，微调后即可得到相对较优的分组路线。
可认为这样设计的分组方法和巡回路线能使总路线近似最短。
针对问题二：在问题一的基础上添加了巡视组在各乡镇停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V=35公里/小时等条件，要求在24小时内完成巡视的最少分组数以及相应的最佳巡视路线。
首先，由图中数据初步计算后判断分成四组可行，再针对分组为四组的情况进行线路设计，仍将问题转化为图论问题，运用问题一的求解方法，得到分为四组的路线，在通过均衡度分析之后得出近似最优巡视路线。
针对问题三：在问题二中关于T,t和V的假定下且巡视人员足够多时，要求在最短时间完成巡视的要求下所得的最佳的巡视路线，此时考虑到从Ｏ点巡视H点的最短时间是所有巡视线路中用时最长的，将计算出的最长路线巡视所用的时间作为巡视路线的最短时间限定，在此限定下对路线进行设计。
基于问题一二中图论的方法，从一些点的路线比较少的点开始，能够使搜素容易进行，因此选择从距离Ｏ点一些较远的点（如12101522等点）开始搜索，每次搜索时都要对该点的巡视时间进行判断，直到找到近似最优路线。
针对问题四：在巡视组数已定(如三组）的情况下，为尽快完成巡视就要求每组完成的巡视时间尽量均衡，因为总的完成巡视时间按线路最长的完成巡视时间计算，由于组数一定，T，t和V 改变，对每组内的最佳巡视路线是没有影响的，但可能会影响到各组件的均衡性，因此问题实质是讨论T，t和V对分组的影响，即在不破坏原来分组均衡的条件下T，t和V允许的最大变化范围。
需要用控制单一变量的方法，分别讨论T、t、V三个量中任意两个量不变时第三个量的变化范围。
从而确定T，t和V的改变对最佳巡视路线的影响。
1O 52.9 61.1 69.9 60.3 53.5 49 43.721 23 24 27 Q 30 32O 39.6 39 44.3 28.4 28 35.7 30.233 35 34图错误!未指定顺序。
由上图便于在第一问分析得到分组情况。
4.2问题二数据分析问题二中给出了巡视小组在乡（镇）村的停留时间和汽车行驶速度，分别为：巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V=35公里/小时。
对于要在24小时内完成巡视，至少应分几组的问题，应首先求出最长路线巡视所用的时间，用停留总时间加上行走时间除以4的结果与24进行比较，以此判断最少分组能否为4组。
计算如下：(17*2+35+599.8/35)/4=21.5<24(小时)（其中路线长度估算为599.8公里）因此最少分组可定为4组。
5．问题一的解答本文研究的是灾情巡视路线的最优设计问题，由于路线图可看成网络图，因此此问题可转化为5.1=（Ｖ，Ｅ’），即(,)x y ∀⑴Ｅ’）(,),(,)min (,)G x y E w x y d x y '∀∈=⑵输入图Ｇ’的一个初始Ｈ圈；⑶用对角线完全算法[2]产生一个初始Ｈ圈；⑷随机搜索出Ｇ’中若干个Ｈ圈，例如3000个；⑸对⑵⑶⑷步所得的每个Ｈ圈用二边逐次修正法[2]进行优化，得到近似最佳Ｈ圈； ⑹在第⑸步求出的所有Ｈ圈中，找出权最小的一个，此即要找的最佳Ｈ圈的近似解。
（算法程序见附录）由于二边主次修正法的结果与初始圈有关故本算法第⑵⑶⑷步分别用三种方法，产生初始圈，以保证能得到较优的计算结果。
在此问题是多个推销员的最佳推销员回路问题，即在加权图Ｇ中求顶点集Ｖ的划分Ｖ1，Ｖ２，…，Ｖｎ 将G 分成n 个生成子图G[Ｖ１]，Ｇ［Ｖ２］，…，Ｇ[V n ]，使得：⒈顶点Ｏ∈Ｖｉ，ｉ＝1,2,3，…，n.⒉1()ni U V V G =.⒊,max ()()max ()i j i jj w C w C w C -α≤，其中Ｃi 为导Ｖi 的导出子图G[Ｖ１]中的最佳Ｈ圈，w(C i )为C i 的权，i ，j=1，2，3，…，n.⒋1()min nj w C =∑.0≤0α≤4表如图2：④，⑤，⑥。
5.1.1综上所述，问题一的优化模型为： 5.2问题一的解答。
在本模型的基础上，运用lingo 软件求解出分三组巡视时近似最优的巡视路线（具体程序见附录三），如表2：由以上分三组所得的路线结果可以看出， 第一组的巡视路线为：5―2―O0α0.16.16.1.1个，计各组停留时间大约为：69/4=17.25（小时）则每组分配在路途的时间大约为：24－17.25=6.75（小时）问题分析时有分三组路线时，巡视总路线最长的是599.8公里，分四组时的总路程更不会比599.8公里大太多，不妨以599.8公里来计算，路途时间约为：（599.8/35)/4=4.25（小时）由于4.25<6.75（小时）因此分成四组是可以办到的。
现在尝试将顶点分为四组，分组准则为：准则一尽量使同一干枝上及其分支上的点分在同一组； 准则二应将相邻的干枝上的点分在同一组；准则三尽量将的干枝与短的干枝分在同一组； 准则四尽量使各组的停留时间相等。
以上原则将图1中的顶点分为四组，同时计算各组的停留时间，然后用模型一中的算法算出各组的近似最佳推销员巡回，得出路线长度及行走时间，从而得出完成巡视的近似最佳时间，用模型一的算法进行计算时，初始圈的输入与分三组时的处理方式一样。
利用lingo 软件求解得出分为四组时的近近似最优巡视路线。
6.1.1综上所述，问题二的优化模型为 6.2问题二的求解在模型二的基础上，运用lingo 软件求解出分四组巡视时近似最优的巡视路线（具体程序见附录三），如表3：－26―第三组巡视路线为：Ｏ－M －25－20―21―K ―18―I ―15―14―13―J ―19―L ―6―M ―O 第四组的巡视路线为：Ｏ－2－5－6―7―E ―8―E ―9―F ―10―F ―12―H ―12―G ―11―E ―7―6－5―2―O 对以上巡视线路的巡视距离进行均衡度分析：,0max ()()max ()i j i ji w C w C w C α-==19.33%=0.1933对以上巡视线路的巡视时间进行均衡度分析：,0max ()()max ()i j i ji w T w T w T α-==5.06%=0.0506由距离均衡度和时间均衡度可以看出，所分组的巡视路线的距离均衡度较好，时间均衡度也较好。
因此，所得路线可以认为是分组的近似最优解巡视线路。
7.问题三的解答7.1模型三的建立 7.1.1确定目标函数由于巡视人员足够多，故单独巡视所花的时间要小的多，所有组中完成的巡视时间最长的可看2），min 7.1.2 7.1.37.2i 个的路L i通过这种算法利用lingo 软件包处理得到分组数为23组，（具体程序见附录三）结果见表3：此时巡5.53－5.50－0―0.90―0.93―0α8.18.1.1方法一：正如问题三已经提到的要尽快完成巡视即要求各组巡视时间的最大值也要最小，用数学表达式就是：这里k 是给定的分组数，,j j m n 分别是第j 组停留的乡（镇）数和村数，j C 是第j 组巡视路线的长度（j =1，2，…,k ）在上述j h 的表达式中，由于,T t 的作用完全相仿，所以为简化起见对于任意给定的,T t ，不妨记Tp t=，即T pt =，这里j h 可简记为()j j j j C h p m n t V =⨯+⨯+⒈若t 增大而V 不变，为了使j h 的最大值尽可能小就要求j j p m n ⨯+的最大值尽可能小。
但是当T 和t 的关系确定后，()j j jp m n ⨯+∑是定值（等于p m n ⨯+，其中m 是全县的乡（镇）数17，n 是全县的村数35）。
上述要求就成为各组停留乡村数（加权之后之和）尽可能均衡，用数学式子表示即为：这里a ⎢⎥⎣⎦和a ⎡⎤⎢⎥分别表示数a 的上整数和下整数，当然在调整各组的停留的乡村数使之达到均衡时，自然会给各组的路线及其长度带来影响，这时应当考虑进行适当调整。
⒉若t 不变而V 增大，这种情况下，在j h 中可能导致j C 起主导作用。
因此和1的结论类似，更应使j jC 的j h 的可S i X i Y i i=1设均衡分组的最大允许时间均衡度为α，即： 则有：记max i T εα=⨯，1,2,3,.i n =则ε表示均衡分组所允许的最大时间误差，称为最大允许时间误差。
则：由上式我们得到由此式可推出以下结果：1当X i -X j >0时，要保持原均衡分组不变，T 必须满足的条件为： 2.当Y i -Y j >0时，要保持原均衡分组不变，t 必须满足的条件为： 3.当S i -S j >0时，有（1）当0()()j i j i X X T Y Y t ε≤-⨯+-⨯≤时，有 （2）当()j i X X T -⨯+时，有 由1.2.3.中的式子知，当T 、t 、V 三个变量中任意两个变量t ，V 不变时，T 只能减小，且下界为1.25小时，上界为2小时。