疏散路径规的求解方法.pptVIP

* * 路网疏散路径规划 的求解方法 曾麦脉 人口应急疏散的两种研究方法： 2. 基于网络流的方法 把疏散队伍抽象为流，将问题建模为节点和边带容量限制的网络模型。从而将问题转化为网络流领域的研究。 主要用于区域范围内的人口疏散问题研究。 1. 基于微观仿真模型的方法 对单个人或者是交通工具的行为进行建模仿真来反映整个疏散的状态过程。 特点是体现个体特性，体现个体与周围环境之间的相互作用，计算量大，计算结果受到驱动个体行为的算法和程序的影响。主要用于建筑物内的疏散。 本讲的疏散路径规划就是采用第二种方法，将交通流建模为网络流问题来求解疏散问题。目标是在尽可能短的时间内将人员疏散出去。 建模方式： 边的建模：将路段建模为网络上的边，道路的宽度特性建模为边上的容量，通过路段所需的时间建模为通过时间。 节点的建模：将有一定量疏散人口聚集的地方建模为节点，包括源节点、目的节点和中间节点。节点的容量代表可以容纳的疏散人口。 具体的数量标准的确定、路段的取舍、节点所代表的范围的界定、初始人口数据的获取与建模等等规则，需要对实际区域进行分析和细致的探讨，这里不深入讨论。 已知条件： 在一个由节点和边组成的有向网络上，已知： (1) 节点和边上的容量限制； (2) 边上的通过时间； (3) 待疏散人口的数量及其他们所在的源节点； (4) 疏散的目的地节点。 包括已知条件、解的表达、优化目标和限制条件四个部分。 疏散路径规划问题的网络模型描述： 限制条件： (1) 在任何时刻，疏散者所在的路径上必须满足节点和边的容量限制； (2) 节点和边遵守先入先出的原则； (3) 有限的计算机计算能力和内存资源。 优化目标： 最小化疏散所需的时间。 解的表达： 疏散路径规划结果的表达包括一系列的条目，每个条目包括一条从源节点到目的地节点的路径、到达路径上各个节点的时间、本次通过这条路径的人口数量。 一个例子： 一种可行解： 16 N1(1)-N3(2)-N5(5)-N7(9)-N11(14)-N14(16) 3 N1 16 N2(0)-N3(3)-N4(6)-N6(10)-N10(15)-N13(16) 3 N2 15 N2(0)-N3(1)-N5(4)-N7(8)-N11(13)-N14(15) 2 N2 15 N1(0)-N3(1)-N5(4)-N7(8)-N11(13)-N14(15) 1 N1 15 N1(0)-N3(2)-N4(5)-N6(9)-N10(14)-N13(15) 3 N1 14 N1(0)-N3(1)-N4(4)-N6(8)-N10(13)-N13(14) 3 N1 5 N8(0)-N11(3)-N14(5) 3 N8 5 N8(1)-N10(4)-N13(5) 6 N8 4 N8(0)-N10(3)-N13(4) 6 N8 到达 时间 路径规划 节点ID（到达时间）-节点ID（到达时间）- … 疏散 数目 源节点 求解以上疏散路径规划的两类方法： 2. 启发式算法 如：CCRP算法。它不能保证得出的是最优解，却能够在次优解的前提下获得计算性能上改善。 1. 线性规划方法 需要借助时间扩充图将时间过程规避掉，转化为最小代价流问题(Minimum cost flow theory)。由于计算量过大，主要用于小型网络，如小型建筑物内的疏散。 时间扩充图(Time expended Graph)的例子： 最小费用流问题(Minimum cost flow theory)： Minimize Subject to for all for all 其中： 代表每单位流的费用 代表从i到j的容量上限 代表节点i的网络流。如果 0，说明是源节点，如果 0，说明是目的节点；如果 =0，说明是中间的转运节点。 将最小费用流问题应用到时间扩充图时，单位流量的费用 是分段函数。 多项式时间算法（Polynomial Algorithms） Geometric improvement approach (2) Scaling approach (3) Dynamic programming approach (动态规划) (4) Binary search 2. 网络简化算法（Network Simplex Algorithms） 在初始生成树的基础上不断改进生成树结构直到最优。 最小费用流的求解算法： CCRP 算法： CCRP： Capacity constrained routing planning