136 运筹与管理 2015 年第 24 卷 [5] 面,Campos 等基于图论中的最短路算法, 以最大化总通行能力与行驶时间比为目标建立了应急疏散路 [6] 线决策模型, 并在核电站事故背景

Size: px

Start display at page:

Download "136 运筹与管理 2015 年第 24 卷 [5] 面,Campos 等基于图论中的最短路算法, 以最大化总通行能力与行驶时间比为目标建立了应急疏散路 [6] 线决策模型, 并在核电站事故背景"

坍宛丁
7 years ago
Views:

1 第 24 卷第 2 期运筹与管理 Vol.24,No 年 4 月 OPERATIONSRESEARCH ANDMANAGEMENTSCIENCE Apr.2015 基于情景分析的应急疏散车辆配置模型俞武扬 (1. 杭州电子科技大学管理学院, 浙江杭州 ;2. 浙江省信息化与经济社会发展研究中心, 浙江杭州 ) 摘要 : 在情景模式影响疏散点疏散人员数量及疏散最晚完成时间限制的条件下, 研究了避难所应急疏散车辆配置计划及各种情景模式下的车辆出车任务安排, 以疏散车辆出车安排为下层模型, 以期望疏散总时间最小化车辆配置计划为上层模型建立了车辆配置及出车任务安排的双层规划模型设计了结合 CPLEX 内置算法的模拟退火算法, 最后用算例进行了仿真研究关键词 : 情景分析 ; 车辆配置 ; 应急疏散 ; 双层规划模型中图分类号 :F016 文章标识码 :A 文章编号 : (2015) EmergencyVehicleDispositionModelBasedonScenarioAnalysis YUWu yang (1.SchoolofManagement,HangzhouDianziUniversity,Hangzhou310018,China;2.TheResearchCenterof InformationTechnology& EconomicandSocialDevelopment,Hangzhou310018,China) Abstract:Thispaperisconcernedwiththeemergencyvehicledispositionproblemandtheschedulingproblemfor emergencyevacuationindiferentscenario,whichinfluencetheevacueesquantityandthetimelimitationof evacuation.abi levelprogrammingmodelisestablishedinwhichschedulingproblem foremergencyevacuation asalower levelmodelandminimizesthetotalexpectationofevacuationtimeasaup levelmodel.asimulated annealingalgorithm embeddedwiththecplexalgorithm ispresentedandanumericalexampleisgiven. Keywords:scenarioanalysis;vehicledisposition;emergencyevacuation;bi levelprogrammingmodel 0 引言对于许多突发性灾害事件, 防止和减少人员伤亡的关键措施之一就是制定合理的应急疏散决策早在 20 世纪 60 年代已经有国外学者针对应急疏散决策的一般概念与研究框架进行了一定的探讨 [1] 此后随着近年来突发事件的频繁发生, 众多学者对应急疏散问题进行了多方面研究从模型研究的角度看可大致分为微观模型与宏观模型两大类, 其中微观模型着重于研究疏散个体的特性, 通过模拟各种可能因素对疏散个体选择疏散路径的影响并对人员疏散过程中的一些动力学特征进行研究如将行人视为相互作用的粒子考虑人员疏散影响的社会力模型 [2] ; 通过构造一系列规则通过元胞之间简单的相互作用来模拟应急疏散动态过程的元胞自动机模型 [3] [4] ; 考虑疏散个体在疏散过程中排斥作用的格子气模型等微观模型的优点是针对疏散个体直接建模, 表现疏散个体的思考能力和对环境刺激的响应能力, 结合不同的因素能对疏散过程中出现的典型动力学现象进行模拟和分析微观模型的缺点是这类模型主要是针对疏散者个体的研究, 当出现区域性突发事件需要应急疏散时, 很难为决策部门组织应急疏散决策提供有效的参考宏观模型一般是从区域疏散情况出发研究疏散方案, 可以为决策部门提供有效的参考宏观模型方收稿日期 : 基金项目 : 教育部人文社会科学青年基金资助项目 (10YJC630360); 杭州电子科技大学管理科学与工程省高校人文社科重点研究基地 (ZD ) 作者简介 : 俞武扬 (1974 ), 男, 博士, 副教授, 研究方向 : 物流建模与优化计算

车安排为下层模型, 以期望疏散总时间最小化车辆配置计划为上层模型建立了车辆配置及出车任务安排的双层规划模型设计了结合 CPLEX 内置算法的模拟退火算法, 最后用算例进行了仿真研究关键词 : 情景分析 ; 车辆配置 ; 应急疏

2 136 运筹与管理 2015 年第 24 卷 [5] 面,Campos 等基于图论中的最短路算法, 以最大化总通行能力与行驶时间比为目标建立了应急疏散路 [6] 线决策模型, 并在核电站事故背景下研究了疏散点与避难所的 k 条独立疏散路线 ;Konyeomewkewkul 等在飓风或洪灾情景模式下考虑避难所选址对待疏散人员应急疏散路线选择以及总疏散时间的影响, 建立了一个双层规划模型用于选择避难所以及相应的疏散路线, 设计了求解该模型的遗传算法 ;Yamada [7] 运用最小成本流模型对交通流疏散分配问题提出了最短路撤退计划方案, 该模型是以疏散者撤离至所选避 [8] 难所的行程总和最小化为目标函数 ;Yi 等考虑了受伤人员应急疏散应急物资调度以及医院救治伤员速率等多种因素, 建立了人员疏散与应急物资协同调度的网络流优化模型, 并设计了求解该模型的两阶段 [9] 蚁群优化算法 ; 张江华等在容量限制情形条件下研究了存在优先顺序的多源点应急疏散问题, 引入 k 最 [10] 短路概念设计了网络优化启发式算法以求解所建立的模型 ; 宋瑞等考虑利用公交车进行应急疏散情况下的公交车辆运行计划优化问题, 以最小化疏散总时间为目标建立了不确定需求情况下的选址路径优化 [11] 模型, 并设计了求解该模型的混合启发式算法 ; 霍良安等以展会应急疏散问题为背景, 研究了应急通道 [12] 设置对应急疏散情况下路网用户均衡影响的双层规划模型 ; 马浩博等在考虑灾害扩散的实时影响前提 [13] 下, 以最小化通过疏散路径所需的总时间为目标建立了应急疏散路径选择优化模型 ; 王永明等构建了非常规突发事件背景下具有时间限制的区域路网疏散能力评估与交通组织设计模型并且进行了仿真研究本文针对避难所车辆配置计划问题进行研究, 在考虑不同情景模式下所负责疏散点具有不同待疏散人员数量及疏散最晚完成时间限制情况下, 合理配置车辆并针对各种情景模式安排每一车辆的疏散出车任务以使期望疏散总时间最小化 1 数学模型 1.1 问题描述在许多自然灾害情况下需要将受威胁群众进行疏散, 设某个避难所负责所在地区的 N 个疏散点的群众疏散任务, 根据历史资料统计该地区共有 M 种情景模式需要对群众进行疏散, 不同情景模式下各疏散点待疏散人员数量及最晚疏散完成时间限制有所不同, 各种情景模式出现的概率可由统计数据给出该避难所需要从 H 种不同车型中选择配置一定数量的车辆以应对各种情景模式下的应急疏散任务, 每一辆车根据其车型不同具有不同的平均速度单位载人量以及配置所需单位成本, 避难所可用于配置应急疏散车辆的总可用资金具有一定的限制在给定避难所的车辆配置方案前提下, 可以通过合理组织安排车辆的多车次疏散出车任务使得各种情景模式下所需疏散时间最短, 为避免疏散时的组织混乱假设同一辆车只负责一个疏散点的应急疏散任务在满足现有的限制条件下, 如何合理配置所需的车辆以及每一车辆在各种情景模式下的疏散出车任务使得疏散所需期望总时间最短? 建模之前根据问题背景作如下假设 :a) 各种情景模式下各疏散点待疏散人员数量及疏散最晚完成时间限制已知 ;b) 各种情景模式出现的概率已知 ;c) 避难所至各疏散点的距离已知 ;d) 各种类型的运输工具属性已知 ( 平均速度单位载人量配置所需单位成本 );e) 可用于配置车辆的资金限额已知 1.2 参数和变量设置 1) 参数设置 N: 各疏散点组成的集合 ;H: 现有车辆的车型组成的集合 ;M: 所有情景模式组成的集合 ;C: 可用于车辆配置的资金限额 ;ξ i : 第 i 种情景模式,i M;p i : 第 i 种情景模式所对应的概率,i M;K X : 给定车辆配置方案 X 时运输车辆数量总和的集合 ;S ξ i n: 情景模式 ξ i 下疏散点 n 待疏散人员数,n N;T ξ i n: 情景模式 ξ i 下疏散点 n 最晚疏散时间限制,n N;d n : 疏散点 n 至避难所的距离,n N;h x (k) H: 给定车辆配置方案 X 时按序排列的第 k 辆车车型,k K X ;w(h):h 车型的运输车辆单位运载量 ( 以人为单位 ),h H;v(h):h 车型的运输车辆平均速度,h H;c(h):h 车型的运输车辆配置所需单位成本,h H 2) 变量设置 X h : 车型的车辆配置数量,h H;x kn : 第 k 辆车至疏散点 n 的出车次数 ;y kn : 当第 k 辆车负责疏散点 n 的疏散任务时则取值为 1, 否则取值为 0 说明 :h x (k) 是给定车辆配置方案 X 时按序排列的第 k 辆车车型, 例如 X={X 1,X 2,X 3 }={1,3,2}, 则

用最小成本流模型对交通流疏散分配问题提出了最短路撤退计划方案, 该模型是以疏散者撤离至所选避 [8] 难所的行程总和最小化为目标函数 ;Yi 等考虑了受伤人员应急疏散应急物资调度以及医院救治伤员速率等多种因素, 建立了

3 第 2 期俞武扬 : 基于情景分析的应急疏散车辆配置模型 137 h x (k)={1,2,2,2,3,3}, 表示第 1 辆车车型为 h=1, 第辆车车型为 h=2, 第 5 6 辆车车型为 h=3 另外给定车辆配置方案 X={X 1,X 2,,X H }, 则 K X ={1,2,, X h } 1.3 建立模型将所研究的问题分解成一个双层规划模型, 上层模型以可用配置资金为限制, 以所有情景模式的总期望为目标函数 ; 下层模型在给定情景模式及车辆配置方案前提下安排车辆的疏散出车任务, 具体模型如下 : 上层模型 : (P1) mine(x) = p i T(ξ i,x) (1) i M s.t. c(h) X h C (2) X h 0, 且为整数 (3) 说明 : 目标函数 (1) 中 T(ξ i,x) 为情景模式 ξ i 下根据车辆配置方案 X 进行最优车辆出车安排时所得最小疏散总时间, 而 E(x) 即为给定所有情景模式时疏散总时间的期望值 ; 约束条件 (2) 表示配置应急疏散车辆所需的总费用不超过可用资金总额 ; 约束条件 (3) 表示车辆配置数应为非负整数下层模型在给定情景模式以及车辆配置方案前提下求解每一车辆的疏散出车任务以最小化上层模型中的 T(ξ i,x) 下层模型 : T(ξ i,x) =min n Nk K X ( kn ) 2d n v(h (k)) x X (4) y kn 1, k K X (5) n N y kn 1, n N (6) k K X (P2) y kn x kn y kn M, k K X, n N (7) [w(h X (k)) x kn ] S ξi n, n N (8) k K X 2d n v(h k ) x kn T n, k K X, n N (9) x kn 0 且为整数,y kn {0,1}, k K X, n N (10) 说明 : 约束条件 (5) 表示每辆车最多只安排一个负责服务的疏散点 ; 约束条件 (6) 表示每一个疏散点至少有一辆车负责该点的疏散任务 ; 约束条件 (7) 建立了 0 1 变量 y kn 与非负整数变量 x kn 之间的内在关系, 其中 M 为充分大的正数 ; 约束条件 (8) 表示每个疏散点所到达车辆总载人次不低于疏散点待疏散人数 ; 约束条件 (9) 表示各疏散点所有到达的车辆完成疏散任务的最大时间不超过该疏散点的疏散时间限制 ; 约束条件 (10) 表示变量的约束 (P2) 为整数线性规划模型, 利用 CPLEX 软件的内置算法可对下层模型 (P2) 进行有效的计算 2 模型求解求解双层模型时, 下层模型是整数线性规划问题可利用 CPLEX12.4 内置算法进行求解, 而由于上层问题中 T(ξ i,x) 对于 X 是非线性的, 从而上层模型实际上是一个非线性整数规划模型, 一般的优化算法很难求解, 由于智能优化方法具有很强的全局搜索能力, 因此在对该模型求解时, 应用智能算法可以得到相对满意的解本文利用模拟退火算法求解上层模型, 算法流程如下 : 算法流程 : Step1 设置初始值, 令 T s :=100,r:=0.9,T end :=1; 生成初始可行解 : 令 Hset:=H, 任取 h Hset, 令 X h 为 [0,X up ] 之间的任意整数, 其中 X up :=?C/c h, 这里?x 表示不超过 x 的整数, 更新 Hset:=Hset\h, C:=C-c h X h, 重复这一过程, 直到 Hset= ; Step2 根据 X={X 1,,X H }, 得 K X ={1,2,, X h } 以及 h X (k),k K X 代入下层模型 (P2), 利

: (P1) mine(x) = p i T(ξ i,x) (1) i M s.t.

4 138 运筹与管理 2015 年第 24 卷用 CPLEX12.4 内置算法求解得到各种情景模式下的最优目标函数值 T(ξ i,x), 返回上层模型得到车辆配置方案 X 所对应的期望总时间 E(X), 令 bestex:=e(x),bestx:=x; Step3 根据当前解 X, 生成其邻域解 X : 先令 X :=X, 令 HX:=H,HX 0 :={h HX X h >0}, 任取 h HX 0, 令 X h 为 [0,X h -1] 之间任意整数, 任取 h HX\h, 令 X h :=?C r /c h, 这里 C r :=C- c h X h ; X\h Step4 计算解 X 对应的下层模型目标函数值 T(ξ i,x), 返回得到 E(X ); 若 E(X )<E(X), 则令 ( ) bestex:=e(x ),bestx=x,x:=x 转 Step3; 否则计算 Δz=exp E(X )-E(X), 产生随机数 ζ U(0,1), T 若 Δz>ζ, 则令 X:=X, 否则 X:=X; Step5 更新 T s :=T s r, 若 T s >T end 则转 Step3, 否则停止, 输出最优目标函数值为 bestex, 最优车辆配置方案为 bestx 说明 :Step4 中采用了 Metropolis 准则的邻域移动方法, 若新解的目标函数值小于当前解的目标函数值, 则进行无条件移动, 否则依据一定的概率进行有条件移动, 其中 U(0,1) 表示区间 [0,1] 上的均匀分布 s 3 数值例子算例. 设某避难所需要配置应急疏散车辆以应对各种情景模式下所负责的 N=6 个疏散点人员的疏散任务, 各疏散点到避难所的距离为 d n ={60,48,37,55,84,18}( 单位 :km); 已知现有车辆类型 H=4 种, 各车型的单位载客量 w(h)( 单位 : 人 / 辆 ) 平均速度 v(h)( 单位 :km/ 小时 ) 以及配置所需的费用 c(h)( 单位 : 万元 ) 见表 1 表 1 各车型车辆属性表车型 h=1 h=2 h=3 h=4 属性 w(h)( 人 / 辆 ) v(h)(km/ 小时 ) c(h)( 万元 / 辆 ) 避难所可供配置车辆的资金限额为 500 万元 ; 根据历史资料统计分析, 该地区共需考虑 5 种情景模式 ξ i, 该 5 种情景模式出现的概率 p i 与对应情景模式下各疏散点待疏散人数 S ξ i n 以及各疏散点对于疏散最晚完成时间的限制 T ξ i n 见表 2 表 2 疏散点情景模式数据表情景疏散点 N 1 N 2 N 3 N 4 N 5 N 6 情景概率 ξ 1 (40,160) (116,200) (70,150) (120,240) (36,360) (144,180) 0.1 ξ 2 (60,220) (96,240) (90,180) (112,200) (40,300) (136,210) 0.2 ξ 3 (50,190) (112,150) (80,200) (116,340) (36,240) (140,260) 0.45 ξ 4 (56,320) (108,240) (86,300) (100,180) (44,200) (130,320) 0.18 ξ 5 (60,180) (90,340) (76,210) (110,250) (50,200) (150,150) 0.27 说明 : 表中括号内第一个数表示对应情景模式下某疏散点待疏散人数 S ξ i n( 单位 : 人 ), 第二个数表示对应情景模式下该疏散点最晚疏散完成时间限制 T ξ i n( 单位 : 分钟 ) 利用上述算法结合 MatlabR2010b 编程, 求解下层模型 (P3) 时调用 CPLEX12.4 内置算法, 对上述算例进行了 10 次计算, 结果如下表 3 所示 : 表 3 算例 10 次求解结果示意表目标函数值出现次数

$:={h HX X h >0}, 任取 h HX 0, 令 X h 为 [0,X h -1] 之间任意整数, 任取 h HX\h, 令 X h :=?$

5 第 2 期俞武扬 : 基于情景分析的应急疏散车辆配置模型 139 从表 3 可知,10 次计算所得最优目标函数值为分钟, 平均目标函数值为分钟 ; 最优解为 X=[0,0,4,7], 总配置费用为 490 万元在车辆最优配置方案下, 各种情景模式的出车安排 x kn 见表 4 表 4 最优配置方案下各种情景模式出车安排表疏散点 N 1 N 2 N 3 N 4 N 5 N 6 车辆号 k=1 (0,0,0,0,0) (0,0,0,0,0) (0,0,0,0,1) (0,0,0,0,0) (0,0,0,0,0) (1,1,1,1,0) k=2 (1,0,0,0,0) (0,0,0,0,0) (0,2,1,0,0) (0,0,0,0,0) (0,0,0,1,0) (0,0,0,0,0) k=3 (0,0,0,0,0) (0,0,0,0,0) (1,0,0,0,0) (0,0,0,0,0) (0,0,1,1,1) (0,0,0,0,0) k=4 (1,0,0,0,0) (0,0,0,0,0) (0,2,0,0,0) (0,0,0,0,0) (0,0,1,0,1) (0,0,0,0,0) k=5 (0,0,0,0,0) (0,1,0,0,0) (0,0,0,2,0) (0,0,0,0,0) (0,0,0,0,0) (2,0,2,0,2) k=6 (0,0,0,0,0) (0,1,0,0,0) (0,0,0,0,0) (1,0,0,1,1) (0,0,0,0,0) (0,0,0,0,0) k=7 (0,0,0,0,0) (0,0,1,0,2) (0,0,0,0,0) (1,0,0,0,0) (0,1,0,0,0) (0,0,0,2,0) k=8 (0,0,0,1,0) (0,0,0,0,0) (1,0,1,0,0) (0,0,0,0,0) (0,0,0,0,0) (0,2,0,0,1) k=9 (0,0,0,0,0) (0,0,0,1,0) (0,0,0,0,0) (0,1,2,0,1) (1,0,0,0,0) (0,0,0,0,0) k=10 (0,0,0,0,1) (1,0,1,0,0) (0,0,0,0,0) (0,1,0,1,0) (0,0,0,0,0) (0,0,0,0,0) k=11 (0,1,1,0,0) (1,0,0,1,0) (0,0,0,0,1) (0,0,0,0,0) (0,0,0,0,0) (0,0,0,0,0) 说明 : 表 4 中括号内 5 个数字分别代表 5 种情景模式下, 每一车辆对各疏散点的出车次数, 如 k=2 行 N 3 列处 (0,2,1,0,0) 表示第 2 辆车在 ξ 2 情景模式下对 N 3 进行 2 次疏散出车任务, 在 ξ 3 情景模式下对 N 3 进行 1 次疏散出车任务, 而在其它情景模式下对 N 3 无疏散出车任务 4 小结本文研究基于应急疏散情景模式的避难所应急疏散车辆配置问题, 假设各疏散点待疏散人员以及最晚疏散完成时间限制由情景模式决定, 在考虑各种情景模式前提下, 寻求最优的车辆配置方案以使得总的期望疏散时间最小化模型的假设具有较强的现实意义, 可为涉及类似的应急决策问题时为决策者提供一定的借鉴作用通过建立双层模型将车辆配置问题分解成两个子问题, 上层模型给定可行的车辆配置方案, 下层模型根据所给定的车辆配置方案就各种情景模式安排最优疏散出车任务以最小化疏散总时间, 下层模型的目标函数值作为参数反馈至上层模型模型的建立过程考虑了求解的因素, 通过变形与约束条件增维降低了模型求解的难度, 设计了一种结合 CPLEX 内置算法的模拟退火算法以求解该双层规划模型, 最后以一个算例说明了模型与算法的有效性参考文献 : [1] GreenLV,KolesarPJ.Improvingemergencyresponsivenesswithmanagementscience[J].ManagementScience,2004,50 (8): [2] HelbingD,MolnarP.Socialforcemodelforpedestriandynamics[J].Phys.Rev.E,1995,51(5): [3] KirchnerA,SchadschneiderA.Simulationofevacuationprocessesusingabionicsinspiredcelularautomatonmodelfor pedestriandynamics[j].phys.a,2002,312: [4] MuramatsuM,NagataniT.Jammingtransitionofpedestriantraficatacrossingwithopenboundaries[J].Phys.A,2000, 286: [5] CamposVBG,SilvaPAL,NetoPOB.Evacuationtransportationplanning:amethodofidentifyingoptimalindependent routes.surcharovlj.proceedingsofurbantransportv:ryantransportandtheenvironmentforthe21stcentury[c]. Southampton:WITPress,2000: [6] KongsomsaksakulS,YangC,ChenA.Shelterlocation alocationmodelforfloodevacuationplanning[j].journalofthe easternasiasocietyfortransportationstudies,2005,6: [7] YamadaT.A networkofapproachtoacityemergencyevacuationplanning[j].internationaljournalofsystemsscience, 1996,27(10): [8] YiW,KumarA.Antcolonyoptimizationfordisasterreliefoperations[J].TransportationResearchPartE.2007,43: [9] 张江华, 刘治平, 朱道立. 多源点突发灾害事故应急疏散模型与算法 [J]. 管理科学学报,2009,12(3): [10] 宋瑞, 何世伟, 章力. 紧急疏散情况下的公交车运行计划优化研究 [J]. 交通运输系统工程与信息,2009,9(6): [11] 霍良安, 黄培清, 程云龙. 基于疏散效率的展会应急优化问题研究 [J]. 工业工程与管理,2011,16(4): [12] 马浩博, 季建华, 何冰. 大规模人流多出口应急疏散预案的优化与研究 [J]. 系统管理学报,2011,20(2): [13] 王永明, 周磊山, 刘铁民. 非常规突发事件中的区域路网疏散能力评估与交通组织方案设计 [J]. 系统工程理论与实践,2011,31(8):

(0,0,0,0,0) (0,0,0,0,1) (0,0,0,0,0) (0,0,0,0,0) (1,1,1,1,0) k=2 (1,0,0,0,0) (0,0,0,0,0) (0,2,1,0,0) (0,0,0,0,0) (0,0,0,1,0) (0,0,0,0,0) k=3 (0,0,0,0,0) (0,0,0,0,0) (1,0,0,0,0) (0,0,0,0,0) (0,0,1,1,1)

km

4484.5 2007 2 11 793.9km 2 12 697.3km 2 13 145.9km 2 14 418.7km 7 24 2 15 2 16 513.4km 2 2 17 39.5km N - 90 12 2 18 234.1km 90 90 2007 2006 32 2 19 266.5km 90 80 50 2 20 10km 9 3000 MP4 2 21 307.3km

136 运 筹 与 管 理 2015 年 第 24 卷 [5] 面,Campos 等 基 于 图 论 中 的 最 短 路 算 法, 以 最 大 化 总 通 行 能 力 与 行 驶 时 间 比 为 目 标 建 立 了 应 急 疏 散 路 [6] 线 决 策 模 型, 并 在 核 电 站 事 故 背 景

136 运筹与管理 2015 年第 24 卷 [5] 面,Campos 等基于图论中的最短路算法, 以最大化总通行能力与行驶时间比为目标建立了应急疏散路 [6] 线决策模型, 并在核电站事故背景