最佳灾情巡视路线模型

一、摘要

一九九八年，我国东南大部遭受百年一遇的大洪灾。遭灾某县，县政府巡视人员走访全县各乡镇村庄体察民情，题目给出该县道路交通图，需要我们设计出各种最佳巡视路线，满足各乡镇、村庄可至且人力物力时间资源消耗较少的要求。

本文采用Kruskal算法生成最小生成树，于此基础上不断改进路线和优化分配模型，求出近似最优解。

在问题一中，由于人员和时间有限为了得出巡视的最短路，我们运用最小生成树-与直观分析相结合，将交通图分配成三个分组路线，用Floyd算法求得各分组最短路距离矩阵，进而运用lingo编程求得最短回路，然后我们参考TSP旅行售货员的问题，用改良圈算法对回路进行改良，发现结果一致。

针对问题二与问题三，首先观察发现图中H点为最远乡镇，单独往返共77.5公里，约需要6.4小时，因此可将问题三转化为问题二同类问题。在问题二中发现至少分为四组人员即可完成任务，于是本文采用问题一同样算法，对新的四组路线求解，并讨论均衡度。对于问题三则通过对目标函数的理论分析得出分组巡视方案，并求解。

于问题四，分析建立word/media/image1.gif时间模型，讨论word/media/image2.gif三个变量对于模型的影响，发现若要保证时间较短，则v应当尽量大，其次当路程较长时，停留的乡镇数目应当适当减少，以此保证路线的均衡度和工作效率。

关键词：Kruskal Floyd 改良圈 TSP 均衡度

二、问题重述

1．问题背景

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

2.问题内容

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

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

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

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

三、问题分析

本文研究的是最佳巡视路线设计问题，要求从O点出发巡视完所有乡(镇)村后，再回到O点。由于人力物力时间的资源有限，只能在调用较少人员和选取最佳路线的基础上完成任务。因此判断此问题属于图论中的网络优化问题。本文将采用图论中相关算法求解。首先设定均衡度word/media/image3.gif（B为自定义变量），在本文中，我们设定word/media/image4.gif为评判指标，均衡度越小，就越接近我们的求解目标，该变量用于验证各组最佳巡视路线。

针对问题一：若只有三组人员，要设计各组最短路线并保证各组工作量均衡，可以将问题转化为近似的TSP旅行售货员问题。利用kruskal避圈法求得最小生成树，根据题意图中共有53个点，分为三个子区域，每个区域应当分为17个点左右，根据Floyd法求得每个子区域的最短路径距离矩阵，然后用lingo编程求解，发现结果基本达到要求。

对于问题二，要求在24小时内完成所有巡视。 通过第一问的结果，求得在分三组的情况下所用的平均时间word/media/image5.gif大于24小时，所以我们先考虑分四组。我们的分组原则为：1、每子区域所分得的点近似相等；2、尽量使每一个子区域连通；3、使每一个子区域中与点O的最短路上的点在该区域内。根据以上分组原则将整个图大致划分为四个子图，同样利用哈密顿算法求得在相对均衡的情况每个小组的最短路径和所需时间。如果部分时间大于24小时，则调整分组方式；若所有时间均大于24小时再考虑多加一组。直到找到相对均衡条件下的最佳路线。

对于问题三，考虑在人员足够多的情况下，求出最短的巡视时间。假设一个小组只巡视一个点的情况下，则去巡视离word/media/image6.gif点最远的点所花时间最长。我们以巡视小组中所耗时间最长的小组所用时间作为这次整个巡视的最短时间。要使这次巡视时间最短，则要求去巡视离word/media/image6.gif点最远的点所花时间最小，由图一可知，离O点最远的点为H，所以就以巡视word/media/image7.gif所花时间作为word/media/image8.gif。当此小组只巡视H时，word/media/image8.gif最小。在不超过word/media/image8.gif的情况下，根据其他小组的剩余时间确定沿途是否巡视其他点。其中巡视原则为：①当一组人员巡视完规定点后时，在剩余时间允许的情况下，优先考虑原巡视点附近而距离word/media/image6.gif较远的点，②最大限度使用剩余时间，主要考虑原则①。按照此原则，逐个巡视，直至巡视完所有点。

针对问题四：要求在巡视组数已定和尽快完成巡视的条件下，讨论word/media/image9.gif，word/media/image10.gif和word/media/image11.gif改变对最佳巡视路线的影响。文中以分4组为例进行讨论。在讨论时，可以采用控制变量法分别对word/media/image12.gif进行理论分析和定量分析，并就各因素可能产生的影响提出改进的建议。

四、模型假设

1.公路不考虑等级差别，也不受灾情或交通情况的影响；

2.汽车在公路上匀速行驶，且不停留，不考虑故障，忽略外部因素影响；

3.巡视过程中巡视人员除了正常停留外，不会出现特殊情况而延误时间；

4.巡视人员在巡视过程中巡视路线可以重复；

5.忽略不计巡视人员上、下车所用的时间；

6.对于要多次经过的乡镇或村只停留一次。

五、符号说明

word/media/image13.gif巡视总路程

word/media/image14.gif第word/media/image15.gif组巡视路线路程

word/media/image16.gif均衡度

word/media/image17.gif表示在每个乡镇停留的世界

word/media/image18.gif表示在每个村庄停留的人世间

word/media/image19.gif表示第word/media/image15.gif组的巡视时间

word/media/image11.gif表示汽车行驶速度

word/media/image20.gif表示乡镇数目

word/media/image21.gif表示村庄数目

word/media/image22.gif表示第word/media/image15.gif组巡视乡镇的数目

word/media/image23.gif表示第word/media/image15.gif组巡视村庄的数目

word/media/image24.gif以O点到H点的时间

word/media/image25.gif从0点出发到所有点的最大距离

word/media/image26.gif在不超过word/media/image24.gif的情况下，其他小组巡视点word/media/image27.gif的剩余时间

word/media/image28.gif第word/media/image15.gif组巡视路线的总长度

六、模型的建立与求解

1.问题一的求解

1）建立模型

公路网图中，每个乡(镇)或村，看作图中的一个节点，公路看作边，节点之间的距离看作对应边上的权，公路网问题就转化为加权网络图，问题一就转化为在加权网络图中，从给定点O出发，寻遍所有顶点再回到O，所得总权最小，即为多旅行商路线问题。

分三组巡视，则需要把图G分为3个子图，在每个子图Gi(i=1-2-3)中寻找最佳回路Li(i=1-2-3)。巡视路线要尽可能均衡，因而每组巡视顶点数要尽量接近。

综上建立的模型为：

目标函数：

word/media/image29.gif

约束条件：

word/media/image30.gif

word/media/image31.gif是对均衡度的度量，word/media/image31.gif越小表示均衡度越好；S表示总的巡视路线，S越小表示巡回路线越短。这两个目标函数不可能同时达到最小值，求解时要两者兼顾。

2）问题求解

若只有三组人员，要设计各组最短路线并保证各组工作量均衡，可以将问题转化为近似的TSP旅行售货员问题。利用kruskal避圈法求得最小生成树，如图1（程序详见附录一）。

图 1

根据题意图中共有53个点，分为三个子区域，每个区域应当分为17个点左右，划分的区域如图

然后根据Floyd算法求出各组路线的最短路径距离矩阵，依据题意

可以有约束条件：

（1）每一个乡镇或村庄的两端只能有一条道路；

word/media/image33.gif

（2）每一个分组的路线必须是一条回路。

word/media/image34.gif

（3）除起点和终点外，各边不构成圈。

运用lingo编程求解出回路方案的求解结果如图1和表1（lingo程序见附录一）

图 2

表 1

如表1所示，均衡度word/media/image39.gif符合我们设定的均衡度要求，可以视为最优解。

2.问题二的求解

1）问题分析

问题二要求巡视人员在各乡镇和村镇停留，并且在24小时内完成巡视任务，即求解含有约束条件的的规划问题，计算得停留时间总共为35+17*2=69小时，根据问题一可知最短路线为602公里，行走时间为word/media/image40.gif小时，上途中行走时间可得约束条件（69+17.2）K<24， 计算可知分组数K最小可以等于4。

2）模型建立

根据问题二分析，建立多目标规划模型。

要求设计最佳巡视路线，即使总路程最短，并且所用时间相对均衡，得出目标函数：

word/media/image41.gif

3）模型求解

根据问题二分析，得出整个区域的分组情况。利用问题一同样方法，先运用Floyd算法求得最短距离矩阵，然后带入lingo编程求得各小组最短巡视路线及所用时间如下：

第一组:

巡视区域：A-B-Q-R-1-29-30-31-32-33-34-35

最短路程word/media/image42.gif，所用时间word/media/image43.gif

第二组：

巡视区域：K-M-N-P-16-17-21-22-23-24-25-26-27-28

最短路程word/media/image44.gif，所用时间word/media/image45.gif

第三组

G-H-I-J-11-12-13-14-15-18-19-20

最短路程word/media/image46.gif，所用时间word/media/image47.gif

第四组

C-D-E-F-2-3-4-5-6-7-8-9-10

最短路程word/media/image48.gif，所用时间word/media/image49.gif

4）均衡度分析

根据以上所求结果，发现所用时间都小于24小时。但第三组用时较多，几乎接近24小时，而第一组用时较少。我们对各组所用时间进行均衡度分析：

word/media/image50.gif

因为word/media/image51.gif，我们认为此分组结果不够合理，需要重新调整分组方式。

通过观察分析，将2分区中的村28划分到1中，同时将3分区中的村11划分到4中，同样利用matlab编程求得各组的最短巡视路线和所用时间，如下表2：

表 2

由于第四组巡视时间较长，故在C点不做停留，而由第一组增加路途进行巡视

根据表中数据可知，所有时间均小于24小时，对时间进行均衡度分析为：

word/media/image52.gif

我们认为此情况下的分组较为合理，同时得出各组的路线图如图3：

图 3

3.问题三的求解

由最短树路径树可知，从word/media/image6.gif点到所有点距离中的最大距离word/media/image54.gif，从word/media/image6.gif点出发到点word/media/image7.gif。同时计算出其所用时间：

word/media/image55.gif

即完成此次巡视所用的最短时间。

在不超过word/media/image8.gif的情况下，其他小组巡视点word/media/image27.gif的剩余时间：

word/media/image56.gif

其中

word/media/image57.gif

下面对剩余时间的利用进行讨论：

当word/media/image58.gif时，直接返回县政府；

当word/media/image59.gif时，巡视一个村；

当word/media/image60.gif时，巡视两个村或一个乡（镇）；

当word/media/image61.gif时，巡视三个村或一个村和一个乡（镇）；

当word/media/image62.gif时，巡视四个村、两个个乡（镇）或两个村和一个乡（镇）；

当word/media/image63.gif，巡视五个村、三个村和一个乡（镇）或一个村和两个乡（镇）；

当word/media/image64.gif，情况不存在。

根据对word/media/image65.gif的讨论和我们的巡视原则，逐个除去已巡视的点，直到所有点巡视完结束，最终求得需要23组。各小组巡视情况如表3：

表 3

4.问题四的求解

针对问题四，我们先进行理论分析，然后进行定量分析。

1）理论分析

以分四组为例，采用控制变量法来讨论word/media/image66.gif的变化对最佳巡视路线的影响 。依题意，巡视时间满足

word/media/image67.gifword/media/image68.gif

为了讨论的方便，可以令word/media/image69.gif，这样一来我们就可以将word/media/image70.gif和word/media/image71.gif当做同一个变量，讨论更加方便，则巡视时间的表达式为：

word/media/image1.gif

(1)当word/media/image72.gif数目完全相同时，即每一组的情况完全一样时，word/media/image12.gif的改变对最佳巡视路线没有影响；

(2)若word/media/image11.gif不变，word/media/image10.gif变化

i. 若word/media/image10.gif的变化幅度很小，则对每组巡视所用的时间word/media/image73.gif的影响很小，那么对最佳巡视路线影响不大；

ii. 若word/media/image10.gif的变化幅度大，则对word/media/image73.gif有显著影响，那么此时各村、乡（镇）的停留数目应该尽可能均衡，才能保证对最佳巡视路线的影响不大；否则，对于最佳巡视路线的影响就十分明显了，所以必须对路线进行调整。

(3)若word/media/image10.gif不变，word/media/image11.gif变化

iii. 若word/media/image11.gif的变化很小，则对最佳巡视路线的影响不大；

iv. 如word/media/image11.gif的变化幅度很大，则对word/media/image73.gif的值起主导作用，那么此时各条路线的总路程word/media/image74.gif应该尽可能均衡，才能保证word/media/image11.gif的变化对最佳巡视路线的影响不大；否则，对路线有显著影响，就必须对其进行调整。

2）定量分析

以分三组为例，为了方便可行，我们直接运用问题一的求解结果，进行定量分析。

当word/media/image75.gif，根据问题一的求解路线，结合上述理论分析里的公式，求得每组的巡视时间如表4。

表4表示 V-t都不发生改变

表 4

(1)针对理论分析(2)-即保持V不变，t发生改变的情况-根据条件设定两组变量进行分析：

A组：word/media/image77.gif

B组：word/media/image78.gif

得到的结果如下表 ：

表5表示V不变，t改变后的结果

表 5

将表4中的数据与表5中的数据进行对比，得到：word/media/image79.gif不变时，当word/media/image80.gif的变化幅度很小（此处变化值为0.1）时，对每组巡视所用的时间word/media/image81.gif的影响很小-则原最佳巡视路线可以不用改变；当word/media/image71.gif的变化幅度大（此处变化值取0.5）时，对word/media/image81.gif有显著影响，此时模型一最佳路线不再适用，必须作出改变。

(2)针对理论分析(3)-即保持t不变，V发生改变的情况，同理，根据条件设定两组变量进行分析：

C组：word/media/image82.gif

D组：word/media/image83.gif

得到的结果如表6

表6 t不变，V改变后的结果

表 6

将表6中的数据与表5中的数据进行对比，得到：t不变时，当V的变化幅度很小（此处变化值为2）时，对最佳巡视路线的影响不大，即模型一的路线仍然适用；当V的变化幅度很大（此处变化值为15）时，对word/media/image81.gif有显著影响，此时模型一的最佳路线不再适用，必须作出改变。

综上所述，得到量化分析的结果和理论分析的结果基本相符，具有一定的参考价值。

六、模型的评价与改进

1.模型评价

1)优点：

(1)问题一中运用最小生成树和最短路径树相结合的方法，将区域分成三个部分，使求解简化；

(2)引用均衡度的概念，使模型检验合理方便；

(3)在模型的结果表达和分析时与具体图相结合，使结果简单明了。

2)缺点：

(1)由于分组具有主观性，求出的只是一个近似最优解，并不能保证绝对最优。

(2)在划分区域的时候借助了划分经验，缺少严格的数学证明和推导。

(3)在问题四中只是定性理论分析结合少量数据给予数学证明，但是结果的严密性不强。

2.模型改进

1)此模型只针对当前数据，对灾情的广泛区域没有实用性，我们可以建立动态规划模型，这样在数据发生变动的情况下，也可使用；

2)问题三中，根据我们设计的巡回路线，部分小组剩余时间较多而未充分利用，我们可以改进设计路线原则，尽量减少人力。

3)可以采用其他的模型和算法(如遗传算法、中国邮递员回路算法)，来对此题进行求解，然后可对各自求得的结果进行对比和分析，从而得到更接近的最优解。

七、模型推广

该模型不仅可以运用到最佳灾情路线的确定问题，还可以推广到实际问题中，此外本文运用的分析问题方法和算法有助于解决实际生活中的许多问题，如推销、投递、旅行商等问题，具有广泛的参考价值。

八、参考文献

[1] 姜启源，谢金星，叶俊.数学模型（3版）.北京：高等教育出版社，2003.

[2] 徐玖平，胡知能.运筹学-数据·决策.北京：科学出版社，2006.

[3] 茆诗松，程依明，濮晓龙.概率论与数理统计（第二版）.北京:高等教育出版社，2002

[4] 赵静，但琦，数学建模与数学实验.北京:高等教育出版社，2003.

[5] Frank R.Giordano，Maurice D.Weir，William P.Fox(美).数学建模.叶其孝，姜启源等译.北京：机械工业出版社，2005

[6] 宋兆基等.MATLABA在科学计算中的应用.北京：清华大学出版社。2005.

九、附录

附录一：

Floyd算法

function [d,r]=floyd(a)

n=size(a,1);

d=a;

for i=1:n

for j=1:n

r(i,j)=j;

end

end

r;

for k=1:n

for i=1:n

for j=1:n

if d(i,k)+d(k,j)

d(i,j)=d(i,k)+d(k,j);

r(i,j)=r(i,k);

end

end

end

end

d;

end

附录二：

%求最小生成树的Kruskal算法
function[T c]=Krusf(d,flag)
%d为权值矩阵的一种表示方法，每一列三个数表示图上
%列数就是图上边的个数
%T表示生成树集合
%c表示生成树的权和
if nargin==1
    n=size(d,2);
    m=sum(sum(d~=0))/2;
    b=zeros(3,m);
    k=1;
    for i=1:n
        for j=(i+1):n
            if d(i,j)~=0
                b(1,k)=i;
                b(2,k)=j;
                b(3,k)=d(i,j);
                k=k+1;
            end
        end
    end
else
    b=d;

end

n=max(max(b(1:2,:)));
m=size(b,2);
[B,i]=sortrows(b',3);
B=B';
c=0;
T=[];
k=1;
t=1:n;
for i=1:m
    if t(B(1,i))~=t(B(2,i))
        T(1:2,k)=B(1:2,i);
        c=c+B(3,i);
        k=k+1;
        tmin=min(t(B(1,i)),t(B(2,i)));
        tmax=max(t(B(1,i)),t(B(2,i)));
        for j=1:n
            if t(j)==tmax
                t(j)=tmin;
            end
        end
    end
    if k==n
        break;
    end
end
T;
c;

灾情路线巡视网络优化问题