灾情巡视路线的最优解决方案(2)

5.问题一的解答

5.1模型的准备

因为最小生成树包含G中所有顶点E，而且最小树的边权是相邻顶点之间的距离，它描述相邻顶点之间的相似程度，故可考虑用最小生成树进行分块。

现在对已经得到的最小生成树G进行分解，以获得三个子图Gi使得分解结果尽量均衡。由于最小生成树上，边权接近，可略认为均衡度即各子图包含的顶点数接近，各子图包含的顶点尽量接近[(35+17)/3]=17个。 最小生成树分组原则：

(1)分解点为O点或尽可能接近O点；

(2)尽量使分解所得的三个子图Gi为连通图，且所包含的顶点树尽可能接近17； (3)尽量使子图Gi与点O最短路上的点在该子图内，并且子图内的点形成回路。 根据以上原则，将最小生成树以O点为原点，树干为基础分为三组，图形如下：

图4：最小生成树G

组别 1 2 3 顶点编号 数量 A,N,P,Q,R,22,23,24,26,27,28,29,30,31,32,33,34,35 18 I,J,K,L,M,2,5,6,15,16,17,18,19,20,21,25 16 B,C,D,E,F,G,H,1,3,4,7,8,9,10,11,12,13,14 18 图5：问题1的分组情况 6

5.2模型的建立 5.2.1确定目标函数

该模型是为解决最佳灾情巡视路线问题，本问中巡视人员分成三组进行巡视，为使总巡视路线尽可能短且每组巡视路线尽可能均匀，我们确立了两个目标函数

1：分成的三组回路中每组回路对应的权值w(Ck)最小

NN?1,城镇i与城镇j之间联通令xij??，则w(ck)???wijcij

i?1j?1?0,城镇i与城镇j之间不联通3所以

?w(c)?min

i12：均衡度a最小: 我们定义a?maxw(ci)?w(cj)maxw(ci)为该分组的实际均衡度，显然0?a?1。a越小说

maxw(ci)?w(cj)maxw(ci)明分组的均匀性越好。因此mina?所以我们建立了一下目标函数：

?3??w(ci)?min?1 ?

maxwc(?)wc()ij?mina??maxwc()i?5.2.2确定约束条件

在加权网络图G中，将顶点集V划分为V1 , V2, V3,则G的三个子图为G[V1], G[V2], G[V3],需满足一下几个条件

1:顶点O包含在每个顶点集Vi 中，即O ?Vi，i=1,2,3

2：顶点集Vi的为V（G）的子集，即

?V13i?V(G)

3：在加权图G中，G的三个子图G[V1], G[V2], G[V3],必须形成一条回路，即

?p??xij?1,j?N;?i?1?p

?x?1,i?N?ij??j?1

7

5.2.3综上所述得到问题一的最优化模型为

?3??w(ci)?min?1 ?

maxw(c)?w(c)ij?mina??maxw(ci)?

?O?Vi，i?1,2,3?3??V?V(G)?1i? s.t?p

x?1,j?N??ij?i?1?p??xij?1,i?N?j?15.3模型的解答

首先我们对数据进行处理，表示为邻接矩阵的形式。利用Kruskal算法，在Matlab中求出它的最小生成树。根据我们确定的分组原则把最小生成树大致分成三组，在Lingo中依次求出每组的最优哈密尔顿回路（详见附录 2）。再依据均衡度的大小进行调整，最后得到的结果为近似最优解。 通过对最小生成树分三组后，得到以下最优路径：

编号 巡视路线 长度 1 2 3 O->2->5->6->L->19->J->13->J->18->I->16->17->K->21->20->25->M->O O->2->5->6->7->E->9->F->10->F->12->H->14->13->G->11->E->8->4->D->3->C->B->1->O O->P->26->N->23->22->23->24->27->28->Q->29->Q->30->32->35->34->A->33->31->R->O 169.0 227.3 206.7 均衡度a?max(Ck)?min(Ck)227.3?169?100%??100%?25.6%max(Ck)227.3

考虑到均衡性比较大,分析结果可知编号1较小，编号2偏大所以可以把编号2

中的一些点划分到编号1中，则

通过对最小生成树重新分三组后，得到以下最优路径： 编号 巡视路线 长度 1 2 3 O->2->5->6->L->19->18>J->13->14->15>I->16->17->K->21->20->25->M->O O->1->B->C->3->D->4->8->9->10->F->G->11->E->7->11->E->7>O O->P->26->N->23->22->23->24->27->28->Q->29->Q->30->32->35->34->A->33->31->R->O 191.6 218.2 206.7 均衡度a?max(ck)?min(ck)218.2?191.6??12.3%

max(ck)218.2综合考虑以上两种情况我们发现这两种情况的总巡视路线长度比较接近但

均衡度变化很大故我们选择第二种情况为最优巡视路线。巡视路线图如图6所示

8

编号 巡视路线 长度 1 2 3 O->2->5->6->L->19->18>J->13->14->15>I->16->17->K->21->20->25->M->O O->1->B->C->3->D->4->8->9->10->F->G->11->E->7->11->E->7>O O->P->26->N->23->22->23->24->27->28->Q->29->Q->30->32->35->34->A->33->31->R->O 191.6 218.2 206.7 图6

图7

6.问题二的解答

6.1模型的准备

由第二问的分析得知，我们至少要分4组。现在对已经得到的最小生成树T进行分解，使4个子图Gi分解结果尽量均衡。由于最小生成树上，边权接近，可略认为均衡度即各子图包含的顶点数接近，各子图包含的顶点尽量接近[(35+17)/4]=13个。

生成最小树划分为4组原则： 1：使各图中点权和尽量接近13. 2：分解后的各子图尽量为连通图。

9

3：分解点为O或尽量接近O。 4：生成的子图容易形成圈或接近圈。

依据以上原则对最小生成树分解为4组如图8所示

图8 组别 顶点编号 数量 1 A,B,C,R,Q,1,29,30,31,32,33,34,35 13 2 K,M,N,P,16,17,21,22,23,24,25,26,27,28 14 3 G,H,I,J,L,5,6,11,12,13,14,15,18,19,20 15 4 D,E,F,2,3,4,7,8,9,10 10 图9 6.2模型建立

6.2.1确定目标函数

此文在第一问的基础上分成了4组，且多了访问时间的限制。为使总巡视路线尽可能短且每组巡视路线尽可能均匀且访问时间在24小时以内，我们确立了三个目标函数

1:分成的四组回路中每组回路对应的权值w(Ck)最小

NN?1,城镇i与城镇j之间联通令xij??，则w(ck)???xijcij

i?1j?1?0,城镇i与城镇j之间不联通 10

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库灾情巡视路线的最优解决方案(2)在线全文阅读。