基于道路改向和启发式搜索的交通疏散算法改进和研究

《基于道路改向和启发式搜索的交通疏散算法改进和研究》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、基于道路改向和启发式搜索的交通疏散算法研究和改进基于道路改向和启发式搜索的交通疏散算法研究和改进【摘要】本文建立了经典的有向图模型，并以最短路径选择算法为基础对交通疏散算法作一步步地改进。通过引入交通路网本身的一些特性，为了缩短疏散时间采用了道路改向和尽量避免交叉路口流量冲突的策略，同时利用交通图地理位置信息以人工智能中启发式搜索算法的思想从算法复杂度的层面算法作进一步地改进。最后结合实例分析算法改进的有效性。【关键词】路网模型，最短路径，道路改向，启发式搜索，流量冲突1引言我国处于世界上自然灾害最多的

2、东南亚、太平洋地区，也是少数几个灾害种类最多损失最严重的国家之一。同时其它灾难性突发事件，如毒气泄漏、核泄漏、恐怖袭击甚至战争等，也时刻威胁着人民生命财产安全。这些自然或人为的灾害的往往造成巨大的社会灾难。随着我国城市化进程的加快，各种灾害对城市乃至整个国家所造成的损失越来越大，城市灾害对城市发展的影响日益引起人们的关注。城市作为人口高度聚集的场所减少人员伤亡应是灾害应急管理的首要目标。在短时间内安全地大范围疏散转移高密集人群，实施科学的应急救灾策略，是减少灾害（事故）后果严重性的重要措施之一。交通疏散

3、道路规划是城市防灾综合减灾系统的重要组成部分。交通疏散道路规划主要以网络流优化为基础，传统的静态网络流没有刻画应急交通道路改向的重要特性，没有利用交通图地理位置信息的特性。同时，交通道路交叉口存在着一定的流量冲突可能，而传统的网络流优化没有刻画流量冲突的情况。因此，有必要在原有的传统网络流优化的基础上，建立基于道路改向的利用交通图地理位置信息的特性并尽量避免流量冲突的网络流模型，给出一种科学合理的疏散道路规划算法。2算法整体设计在本文的研究中，要获得是疏散道路规划算法，简单的说就是要给出人流从起点逃往终

4、点的路线并给予评价。显然逃生路线不是唯一的，因而7基于道路改向和启发式搜索的交通疏散算法研究和改进为了获得更好的疏散效果，需要优先将宝贵的道路流量资源分配给较短时间内从起点到达终点的道路，基于这一思想建立以下算法流程。图1算法整体设计流程3基础模型定义3.1路网模型科学合理的疏散道路规划算法必须依赖适当的路网模型，本文以经典的有向图模型为基础路网模型。图2有向图模型路网模型的基本定义：(1)图G(V，E)：路网系统。描述路网的基本要素有两大类点实体——节点和弧实体——路段(2)节点V：通常理解的节点就是

5、交叉路口,由三类节点构成：{start_V(起点),end_V(终点),V(普通节点)}(3)路段E:为四元素集合体（路段起点v,路段终点w,通过时间t,流量上限flow）。上图中（0，1，1，2）表示节点0到节点1通过时间为1单位，流量上限为2单位。(4)路段权重:7基于道路改向和启发式搜索的交通疏散算法研究和改进3.2离散时间疏散仿真模型在图1的流程图中，为了计算疏散时间建立离散时间疏散仿真模型。仿真模型通过离散时间模拟的方式来计算人数疏散完毕所需的时间，如下表所示:01234567803+1+1+

6、113+1+1+11+123+1+1+11+1133+1+11+113+1143+11+113+111353+1113+11+11361131+11+133731+11+1+1333+1831+1+1333+191+1+1333+1+11033+1+1+11133+1+1+1123+1+1+131表1离散时间模拟演示建立一个二维数组，其中纵坐标为离散的时间尺度，横坐标为节点信息，记录的是每个节点在该离散时刻存在于节点上的人数，其中0为起点，6为终点。如0—0上数据表示，0节点有6个单位从0点出发，1—1

7、上数据表示1节点在1时刻有2个单位存在。通过这种算法，模拟了整个疏散过程，并可得到多少时间可疏散完毕多少人的信息，表中为12的单位时间可疏散31个单位。疏散时间=最后一个单位到达终点时刻-疏散开始时刻。4算法的研究和改进4.1路网模型的研究和改进从图的角度看，交通图显然是一张有向图，即0->1和1->0表示是两条不同的路，但是交通图也存在着其不同于一般有向图的特殊之处，因此有必要结合这些特性对图2描述的经典有向图模型进行改进7基于道路改向和启发式搜索的交通疏散算法研究和改进4.1.1道路改向有别于经典的

8、有向图，交通图是可以进行道路改向的，即0->1的流量可通过改向变为1->0的流量。合理的道路改向可以充分利用道路资源，提高交通图的疏散效率，从而减少疏散时间，经研究以下算法流程可获得较好效果的改向策略。图3道路改向算法流程将有向图转化为无向图：只要将道路的双向流量求和就可实现。如AàB流量3，BàA流量4，那么转化后就是A—B总流量为7；将无向图转化为有向图：根据求得的道路信息结果分配流量。如结果为AàB流量6，既新图信息为AàB流量6，B