交通网络中疏散路线设计与调度方案数学建模论文 - 毕业论文(4)

Kj?

?Nij?

2Dij

??Si

?ni?[]?1

x?

?Nij

1?V??12Vf?s.t.?K V?V(1?)f?2

KJ

??ni?CijNij?K?

Dij?

?

?Cij?[ni]?Nij?

?Dij??pi?xj?2??qi?yj?2,1?i?69,1?j?26?

5.2.4基于Warshall—Ford 算法的最短疏散路径模型

为了找到集结点与现在间的最短路径，采用Warshall—Ford 算法求疏散处与避难处的最短路径。 可以将问题分解，先找出最短的距离，然后在考虑如何找出对应的疏散路线。如何找出最短路径呢，这里还是用到动态规划的知识，对于任何一个疏散处而言，i到j的最短距离不外乎存在经过i与j之间的k和不经过k两种可能，所以可以令k=1，2，3，...，n，在检查dij与d(ik)+d(kj)的值；在此d(ik)与d(kj)分别是目前为止所知道的i到k与k到j的最短距离，因此d(ik)+d(kj)就是i到j经过k的最短距离。所以，若有dij>d(ik)+d(kj)，就表示从i出发经过k再到j的距离要比原来的i到j距离短，自然把i到j的dij重写为d(ik)+d(kj)，每当一个k查完了，dij就是目前的i到j的最短距离。重复这一过程，最后当查完所有的k时，dij里面存放的就是i到j之间的最短距离了。

minz???AijDij

i?1j?12669?2669???Aij?69?i?1j?1?69st??Aij?1,1?j?26 ?i?1??0Aij??

5.3模型的求解

本文利用Matlab2014a进行求解，程序见附录，具体步骤如下：

1、求解Si，整理附表2中的数据，利用GM（1,1）灰色模型法评估每处人数，将每处人数转化为所需用于疏散的车辆数；

2、根据Floyd-Warshall算法，利用Matlab编程得到69列疏散处距离26行避难处的最短距离Dij。

3、将69出疏散处进行编号根据以及建立的模型中的约束条件和目标函数，利用Lingo11求得全局最优解。

4、最终利用Matlab搜寻法得到，每个避难处所接受的疏散处不超过5处，才能解决道路阻塞以及人员疏散时间过长的问题，此时的分配方案如附表5。

5.3.1 疏散区域人口规模求解

根据题目所给出的沙坪坝地区地图，利用GM(1，1)灰色模型法估测人口规模，从灰色系统的建模，关联度以及残差辨识的思想出发，得出疏散处总户数与年份之间的关系，并得出所需车辆数。其中，商业楼与住宅楼群不同，人数更为密集，每楼标准建筑面积约为4.2万平米，地下2层，地上18层，标准层面积2500平米，内部敞开式的建筑，大约10平米/人，能估算出一栋20层的大厦可容纳的人数约为2000，一小区式住宅应有4000-8000人。在模型中假设每户为标准型，有三位住户，共有55165户，即有165495人。每辆用于疏散的车辆为标准公交车型，车身长度x>9米，按照国家标准是8人/平方米，每辆公交车容量（50人/车），共需3308辆。

根据MATLAB编程计算，得到结果如下：

表1:疏散处所需车辆关系表

疏散处编号 所需车辆 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 11 72 128 57 18 23 60 51 41 48 24 18 22 22 22 41 53 27 54 疏散处编号 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 所需车辆 24 21 30 59 29 49 11 24 66 28 21 39 36 240 220 55 55 11 30 疏散处编号 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 所需车辆 26 55 90 54 39 42 147 22 59 17 71 42 61 18 13 8 28 44 48 疏散处编号 58 59 60 61 62 63 64 65 66 67 68 69 所需车辆 31

9 59 36 163 34 56 25 34 66 22 37 5.3.2 最短疏散路径模型的求解

设A=(aij)n?n为赋权图G?(V,E,F)的权矩阵，当vivj?E时，aij?F(vivj)，否则取aii?0,aij???(i?j)，dij表示从vi到vj点的距离，rij表示从vi到vj点的最后路中一个点的编号。

①赋初值，对所有i,j,dij?aij,rij?j,k?1.转向②

②更新dij，rij对所有i,j，若dij?dik?dkj?dij ，则令dij?dik?dkj,rij?k，转向③

③终止判断。若dii?0,则含有一条含有顶点vi的负回路，终止；或者k?n终止；否则令k?k?1，转向②

其中可由最短路径rij得到避难处至1,2,3,4处疏散处的最短路径矩阵见附表6所示。并用Matlab编程得到各个路径之间的距离，再使之在地图的道路上标出各自的距离，其中各点坐标表示如下图：

图2:疏散处与避难处坐标分布图

5.3.3道路阻塞模型的求解及最终调度方案的确定

利用Matlab7.14对格林希尔兹速度-密度线性模型导出公式 Q=VfK2V2（K-）=KJ(V-)进行图像绘制，得到交通量与交通密度、速度与交通VfKj量之间的关系图像，分别为图3和图4：

图3：交通量与密度之间的关系 图4：速度与交通之间的关系

观察图像，可知：当K=62辆/km时，交通量最大，此时车速V=38.7km/h 根据5.3.1人口估摸评估得到的所需车辆数和5.3.2最短路径矩阵求得的最短距离，由交通密度公式K=

ni可算出各疏散处到对应避难处间的交通密度，对比Dij交通量最大时的交通密度，小于62辆/km则按实际交通密度计算，即情况一，反之则按照62辆/km交通密度计算，即情况二。

最终通过计算结果取整可得最优疏散方案，其中到达某避难处的道路阻塞密度如下表3所示

表2: 至某避难处的道路阻塞密度

避难处 道路阻塞密度 重庆七中 62 金城广场 62 卫校 62 工商管理学院 40 体育馆 62 土湾小学 62 欣阳广场 62 人民医院 27 红槽房小学 62 南开小学 62 实验中学 62 沙坪公园 49 南开中学 62 重庆八中 23 天星小学 62 征兵大楼 62 火车站 62 农民工服务中心 62 三峡广场 62 沙坪坝站 62 红槽房中学 62 滨江小学 62 邮政招待所 62 树人景瑞小学 34 避难处 道路阻塞密度 避难处 道路阻塞密度

5.3.4验证疏散路线方案性能的讨论 本文定义了两个评价原则：

原则一：将某疏散处所有人员运送到避难处所需时间≦60min； 原则二：保证道路阻塞密度不超过负荷峰值，且尽量接近于最优值； 现依据问题分析中两个评价原则，先对所得方案性能进行评价。