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

所以

?w(c)?min

i142：均衡度a最小:

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

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

?4??w(ci)?min?1 ?

?mina?maxw(ci)?w(cj)?maxw(ci)?

6.2.2确定约束条件

在加权图G中，将顶点集V划分为V1 , V2, V3，V4,则G的三个子图为G[V1], G[V2],

G[V3], G[V4]需满足一下几个条件：

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

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

?V14i?V(G)

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

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

?x?1,i?N?ij?j?1?4:每个组在巡视的过程中，往返的时间不能超过24小时即：

w(ci)?24 aiT?bit?V6.2.3综上所述得到问题二的最优化模型为

?4??w(ci)?min?1 ?

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

11

??O?Vi，i?1,2,3,4?4???Vi?V(G)?1?p s.t??xij?1,j?N;

?i?1?p??xij?1,i?N?j?1?w(ci)?aiT?bit??24V?

6.3问题二的解答

根据我们确定的分组原则把最小生成树大致分成四组，在Lingo中依次求出每组的最优哈密尔顿回路（详见附录2）。再依据均衡度的大小进行调整，最后得到的结果为近似最优解。

通过对最小生成树分三组后，得到以下最优路径如图10：

编号 巡视路线 O->C->B->34->35->32->30->Q->29->R->31->33->A->1->O O->P->28->27->26->N->24->23->22->17->16->17->K->21->25->M->O O->M->25->21->K->18->I->15->14->H->12->G->11->G->13->J->19->L->20->25->M 路程 136.5 154.3 203.9 153.4 行走 时间 等待 时间 总时间 1 2 3 4 3.90 4.41 5.83 4.38 18 18 18 15 21.90 22.41 23.83 19.38 O->2->3->P->4->8->E->9->F->10->F->9->E->7->6->5->2->O 图10

时间均衡度a1?23.83?19.38?100%?18.67#.83203.9?136.5路径均衡度a2??100%?33.06 3.9

最佳巡视路线图为：

12

图12

7.问题三的解答

7.1模型的建立

7.1.1确定目标函数

在问题三中， T , t和V同二没有改变，在巡视人员足够多的情况下要求求出巡视的最短时间。分析的，在人员足够的情况下，我们给每个镇（乡）或村都分派一名巡视员 。每个巡视员所走的路线该点与O点之间的最短路径，巡视时间为往返时间加上访问点权时间。对他们巡视时间进行比较，当巡视时间最长的巡视员返回时，其他巡视员都已近返回。所以巡视时间最长的即为要求的最短时间，因此我们确定的目标函数为：

min(maxKi)?max2Soi?ki V7.1.2确定约束条件

13

巡视人员从O点出发径直走向i点，在这个过程中Soi为两点之间权值最小值：

2(n) minSoi,Soi,?,Soi

??若巡视员访问某点权的时间Ki与maxKi之差大于一小时，则可考虑访问一个村。若大于两小时以上则可考虑访问多个村或镇，但附加访问的村或镇所用的时间Ki仍小于maxKi则

0?maxKi?Ki?1?Ki'?Ki,?K'?K?1,1?maxKi?Ki?2ii???Ki'?Ki?aiT?(maxKi?Ki?aT)t ?maxKi?Ki?2???Ki'?maxKi

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

min(maxKi)?

max2Soi?ki V0?maxKi?Ki?1?Ki'?Ki,?K'?K?1,1?maxKi?Ki?2ii???Ki'?Ki?aT?(maxKi?Ki?aT)t ?maxKi?Ki?2???Ki'?maxKi

7.2模型的求解

首先我们通过Dijkstra算法算出O点距离其它52各点的权值最小值，通过

比较发现点H距离O点最小权值最大，H又恰好为一个镇，综上二者可知从O点

2S2?77.5?2?6.43 径直访问H点所用的时间最长，最长时间为KOH?oi?k?V35所以在人员足够多的情况下，完成巡视的最短时间为6.43

1

6 11 55.9 21 39.6 31

2 9.2 12 67.3 22 49 32 3 14 13 64.1 23 39 33 4 34.9 14 72.7 24 44.3 34 5 17.5 15 69.9 25 31.8 35 6 27.2 16 60.3 26 20.6 36

14

7 34.5 17 53.5 27 28.4 A 8 49.7 18 52.9 28 22.2 B 9 49.5 19 46.2 29 20.8 C 10 65.9 20 38.3 30 35.7 D

22.1 30.2 23.7 27.8 36 0 E F G H I J 41.7 55.1 62.7 77.5 61.1 54.3 P Q R 10.1 28 12.9 16.3

K 43.7 11.9 L 39 11.5 M 19.8 22.2 N 31.1

图13：Dijkstra算法算出O点距离其它52各点的权值最小值

通过Matlab编程求解（详见附录3,4 ）在上述条件下求得共需要29组巡

视人员最优的巡视方案如下： 编号 巡视路径 1 O,2,5,6,7,E,9,F,10,F,9,E,7,6,5,2,O 2 0.2,5,6,L,19,J,13,14,13,J,19,L,6,5,2,O 3 0,c,0 4 O,2,5,6,7,E,9,F,9,E,7,6,5,2,O 5 O,2,5,6,7,E,11,G,11,E,7,6,5,2,O 6 O,2,5,6,7,E,9,F,12,H,12,F,9,E,7 ,6,5,2 ,O 7 O.M,25,21,K,18,I,18,K,21,25,M,O 8 O,2,5,6,L,19,J,19,L,6,5,2, O 9 O,2,5,6,L,19,J,19,L,6,5,2,O 10 0,2,3,2,0 11 O,2,3,D,4,D,3,2,O 12 O,2,5,6,5,2,O 13 O,2,5,6,7,E,8,E,7,6,5,2,O 14 O,2,5,6,7,E,9,E,7,6,5,2,O 15 O,M,25,21,K,17,K,21,25,M,O 16 O,M,25,21,K,18,K,21,25,M,O 17 O,2,5,6,L,19,L,6,5,2, O 18 O,P,26,N,23,22,23,N,26,P,O 19 O,P,26,N,23,N,26,P,O 20 O,53,29,53, O 21 O,53,29,Q,30,Q,29,53,O 22 O,53,31,32,31,53, O 23 O,1,A,33,A,1,O 24 O,1,A,34,35,34,A 25 O,2,5,6,7,E,11J,19,20,25,M,O 26 O,2,5,6,7,E,9,F,12,G,13,J,19L,6,5,2,O 27 O,M,25,21,K,18,I,15,I,16,17,K,21,25,M O 28 O,P,26,N,24,27,26,P,O 29 O,1,B,1,O,P,28,P,O 图14

15

停留地点 12 14 C F G H I J K 2,3 D,4 5,6 7,8 E,9 M,17 25,21,18 L,19 P,22 26,N,23 R,29 Q,30 31,32 1,A,33 34,35 11,20 12,13 15,16 24,27 B.28 所需时间 4.765714286 5.154285714 2.657142857 5.148571429 5.582857143 6.428571429 5.491428571 5.102857143 4.497142857 2.8 4.994285714 3.554285714 4.84 5.828571429 6.057142857 6.022857143 5.64 5.8 6.228571429 4.188571429 5.04 3.725714286 5.354285714 4.057142857 4.471428571 4.391428571 4.585714286 3.802857143 4.314285714

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