一种应急疏散最短路径的数学建模方法.pdf

电信息技术 一 种应急疏散最短路径的数学建模方法 榻家裕 清远市人防 民防 指挥信息保障中心 摘要 针对城市应急疏散的路径选择 运用数学方法讨论了最短路径的建模问题 使用模糊概念和图论分 析方法分别对应急疏散路径规划优化中的路径权值量化和结点约束图转化进行分析 给出相应的解决方法 并结 合简单例子说明了解决问题的步骤与方法 关键词 应急疏散 模糊概念 权值量化 最短路径 数学建模 0 引言 城市在发生重大灾害性事件时 必将面临市区人 员疏散问题 目前 对人员应急疏散规划的研究 理 论上主要包括数学分析和仿真 2种方法 国外有学者 提出用最大流方法进行路径选择 目的是在路网同行 能力许可的范围内 最大饱和度地从最优路径将疏散 者从危险区域疏散至安全区域 亦有运用最小代价流 问题进行疏散路径分配 即最短路撤退规划 S E P方 法 目的是将全部人员疏散至指定区域路径总行程 的最小化 影响较大的是 C o v a等提出的基于车道的 网络流模型 l 它针对复杂网络计算应急疏散的最优 路径 模型将研究对象抽象为一个最小费用流的优化 问题 本文从数学分析建模的角度介绍一种应急疏散 路径优化的方法 1 路径权值量化 道路网络 中路径权值的量化是进行路径优化分 析的前提 一般情况下 可将道路长度作为路径权值 在实际疏散过程中影响路径权值的因素很多 如疏散 路面状况 疏散人群结构状况 疏散易发生事故状况 疏散指挥人员配备及设施指示情况等 因此 应将诸 多因素加以考虑而得到一个更客观的路径权值 但各 因素间存在很大的不确定性与模糊性 难以找到统一 的定量计算公式 而模糊概念则为处理客观事物中 存在概念外延不确定的情况提供了一种解决方法 1 1 路径量化分析 由以上分析可知 影响路径权值的因素除长度可 30 确定外 其他因素都需采用模糊隶属度来表示 因此 路径权值可看作由长度和其他影响因素 2部分组成 x 2 x 3 x 4 X 5 a L o n g x 1 b F u z z x 2 X 3 x 4 X 5 1 其中 L o n g x 1 表示距离函数 F u z z x 2 x 3 x 4 x 5 表示与路面状况 疏散人群结构 疏散易发生事故状 况 指挥人员配备及设施指示情况相关的模糊综合函 数 a b为常系数 假设道路为理想路径 则式 1 右边第二项为 0 路径权值即为道路长度 设理想疏散用时为 人群 疏散速速为v 则有 t o L o n g x 1 v 设实际情况下疏散的实际时间t 则 t t o t 若将t 看理想状况疏散路径长 L o n g x 1 为所用 时间 则有 L o n g x L o n g x 1 V f 可见 实 际情 况 的 路径 长 度 可 看作 理 想 长度 L o n g 1 延长了1 f 其值由F u z z x 2 X 3 X 4 X 5 决 定 假 设 对 各 种 客 观 因 素 进 行 模 糊 综 合 评 价 F u z z x 2 x 3 x 4 x 5 得到的结果是 O 1 的一实数 且 F u z z x 2 X 3 x 4 X 5 与L o n g x 1 之比值与该实数为 线性关系 则有 F u z z x 2 x 4 L o n g x 1 c F u z z x z x 3 x 4 即 x 4 r 2 a L o n g x 1 b c F u z z x 2 X 3 x 4 L o n g x 1 一 式 2 中 令 a b c 1 则有 x 2 x 3 x 4 x 5 L o n g x 1 1 F u z z x 2 3 1 2 路径量化算法 根据模糊数学原理 构建模糊综合评价函数需要 3个要素 1 因素集 定义为 U 路面状况 人群结构 易发事故状况 人 员指挥及设备指示 U 1 U 2 U 3 U 4 2 1评价集 对事物好坏程度评价的集合 定义为 V 很 好 较 好 一 般 较 差 很 差 v 2 v 3 1 5 3 1单因素评判矩阵 为 R i1 2 l 2 1 2 r 4 1 r 4 2 3 4 5 3 r 2 4 5 3 4 5 r 4 3 5 假 设 因 素 集 上 的 因 素 模 糊 子 集 A 以 l a 2 a 3 a 4 0 a i 1 评价集 上的因 素模糊子集B 6 5 根据模糊概念的 综合评价关系有 B 找 出B 中元素 的最大值 b 作为综合评价的结 果 并作归一化处理 令 O 2 5 j 1 b b J 1 2 5 I 1 b b F u z z x 2 X 3 X 4 0 5 6 b b 3 4 b 将式 4 代入式 3 得到非理想 晴况下的路径权 值 若对某道路因素集的每个因素对照评价集进行 评价 路面状况 很好 较好 一般 较差 很差 的比例分别为 2 5 3 0 3 0 1 0 5 单因素评价矩阵中因素 1的评判结果 假设疏散中对 路面状况 最为关注 令 A 0 4 0 1 5 0 1 5 0 3 故 B 艘 0 1 6 0 2 1 0 2 4 0 2 2 0 1 7 最大值为 O 2 4 说明该路段的 路面状况 综合 评价为 一般 所以 F u z z x 2 x 3 x 4 0 5 0 2 5 3 1 0 2 5 若道路的实际长度为 3 0 0米 则综合评价后长为 x 2 x 3 x 4 3 0 0 x 1 0 2 5 3 7 5 2 结点约束转化及最短路径算法 理想化的应急疏散最短路径与实际最短疏散路 径一般情况下是不相同的 因为实际的疏散线路必须 遵循一定的疏散规则 如某路 口不能左转 某道路不 能逆行等 理论上 这类 问题都可以归结为结点有约 束的最短路径求解问题 通过特定的步骤将其转化为 无约束最短路径求解问题 是进行数学建模的关键网 一 般的解决步骤为 1 根据路径网给出的拓扑关系建立结点间的连 通关系表 如表 1 所示 表的第一列为前序结点 第 一 行为后续结点 结点间直接相连的结点用 表 示 其余的不填 表 1 结点连通关系表 1 2 3 4 5 1 2 3 4 5 2 0 1 5 年 第 3 6 卷 第 2 期 自动化与信息工程 3 1 2 根据路径网络给出的限制条件 得到约束结 点及对应的点对 如图 1中约束结点及对应点对可以 表示为 4 5 1 a 结点有约束路径图 b 结 点无约 束有 同路 径 图 图 1 结点有约束路径图与结点无约束有 向路径 图的转化 3 1 从表 1 中依次取出前序结点f 后续结点 若f 关系为 且 不是约束点 则f 与 有向相 连 若 f 为约束结点 但 f 的前序结点与后续结点 不 构成步骤 2 确定的点对 则f 与 有向相连 若 为 约束结点 且f 的前序结点与后续结点I 构成步骤 2 确定的点对 则设虚设点f 且虚设点 与 有向 相连 当有多个虚设点时 f 的下标序号递增 路径权值量化后道路网络拓扑如图 1 a 所示 4 据此建立如表 1 所示的结点连通关系表 根据步骤 3 的方法 可将结点有约束的最短路径求解 问题图 1 a 转化为结点无约束的有向 图最短路径 求解 问题 图 1 C o 而后者的求解通常可以用 Di j k s t r a 及 F lo y d算法 解决 3 结语 本文对应急疏散最短路径规划 中路径权值量化 和结点约束转化的问题进行分析并给出了相应的解 决办法 对城市应急管理部门具有一定的参考价值 但是 人员疏散的实际情况往往 比较复杂 要对 目标 区域环境进行各方面的综合评价与建模才能作 出更 优化的疏散路径算法 参考文献 1 C o v e T J J o h n s o n J P A n e t wo r k flo w mo d e l f o r l a n e b a s e d e v a cu a t i o n r o u t in g J T r a n s p o r t a t io n R e s e a r ch P a r t A 2 0 0 3 3 7 1 5 7 9 6 0 4 2 陈玉敏 龚健雅 基于模糊数学的多因素道路网权值确定算 法 J 武汉大学学报 信息科学版 2 0 0 7 3 2 1 0 9 2 8 9 3 1 3 王锐 城市防空人 口疏散问题研究 D 郑州 解放军信息工程 大学 2 0 0 4 4 F r e d B u ck le y Ma r t y L e w i n t e r 图论简明教程 M 李慧霸 王 风芹 译 E 京 清华大学出版社 2 0 0 8 A M a t h e ma t ica l M o de ling M e t ho d o f t he Sho r t e s t Eme r g e ncy Eva c ua t io n Ro ut e Xua n J ia y u C iv il A ir De f e n s e C o mma n d I n f o r ma t i o n S e cu ri t y C e n t e r o f Q in g y u a n C i t y Abs t r a ct F o r t h e ch o i ce o f t h e ci t y e me r g e n cy e v a cu a t i o n r o u t e we d i s cu s s e d t h e mo d e li n g p r o b le m o f t h e s h o r t e s t p a t h b y u s in g ma the ma t ica l me t h o d W e a n a ly z e d t h e we ig h t q u a n t iz a t io n o f e me r g e n cy e v a cu a t io n p a t h p la n n in g o p t imiz a t io n a n d c o n s t r a in t e d n o d e g r a p h t r a n s f o r m a t io n b y u s in g f u z z y co n ce p t an d g r a p h an a ly s is m e t h o d r e s p e ct iv e ly g a v e t h e co r r e s p o n d in g s o lu t io n s a n d s h o we d t h e s t e p s o f s o lv in g p r o b le ms in co mb in a t io n wit h s o me s imp le e x a mp le s F in a lly we illu s t r a t e d a ct u a l u s e v a lu e an d d e f icie n cy o f t h e me t h o d Ke y W o r