动态系统最优的疏散路线与出发时间综合优化模型.docx

文章编号: 100124098 (2009) 0620073205动态系统最优的疏散路线与出发时间综合优化模型高明霞1 , 贺国光2(1. 兰州交通大学, 甘肃 兰州 730070;21 天津大学, 天津 300072)摘 要: 疏散是应急管理的重要内容。区域性疏散涉及到大批车辆的集体性出行, 为保证疏散的安全、有序,有必要在疏散规划中合理规定源点车辆的分批次出发时间和路线安排。以往大量研究将疏散路线和出发时 间的优化描述为动态网络流优化问题。但在这些模型中, 交通流的一个重要特征却没有得到合理反映, 即路 段走行时间等路网特征的变化不但与时间有关, 还依赖于路段或路网的交通负荷。本文提出了一个动态系 统最优的疏散路线与出发时间综合优化模型, 其中采用基于加载仿真的非解析式子表示流量传播约束, 通 过其反映路段走行时间随道路负荷变化的实际。设计了基于加载仿真的启发式算法, 并给出了一个数值算 例。关键词: 应急管理; 动态系统最优; 启发式算法; 疏散路线与出发时间中图分类号: u 491文献标识码: a总结了常用于疏散问题的动态流模型, 并分析了这些模型在区域性疏散中的应用潜力。文献5 采用动态最快流模 型, 在不考虑疏散目的地容量限制的情况下, 对分批次车 队的疏散路线和出发时间进行了优化。动态流模型对疏散 问题的描述很直观, 其认为车辆走行速度等路网特征或者 是固定常数或者是随时间动态变化的 ( t im e2dep enden t)。 但是交通流的一个重要特征却没有得到反映, 即车辆走 行速度的变化不但和时间有关, 还依赖于道路的交通负 荷 (f low /den sity2dep enden t) , 路上车辆稀少时车速较高, 而随着车辆的增多密度增大, 车辆运行速度会随之降 低。本文从道路上车辆的走行速度依赖于道路交通负荷 这一交通流的重要特征出发, 建立了一个动态系统最优的 疏散路线与出发时间综合优化模型, 将问题所在时间段离 散化后, 通过优化在各个时段内沿不同路径出发且走行的 车辆个数, 使包括源点等待时间和路上走行时间在内的疏 散总时间最小化, 其中采用一个基于加载仿真的非解析式 子表示流量传播约束。根据模型的最优性条件提出了一个 启发式算法, 算法通过不断迭代、模拟车辆的出行调整过 程来逼近最优解。1 引言随着各种灾害的频发, 应急管理越来越受到重视。应 急疏散作为保护受灾人群生命安全的主要手段, 是应急 管理的重要内容。其中区域性疏散常见于影响范围大、易 扩散的灾害性事件应急处置, 需要将整个区域内的人群、 车辆全部疏散至安全出口或目的地。一般情况下, 疏散期 间由疏散源点产生的交通出行量占整个疏散出行量的绝 大部分。所以, 为提高疏散效率, 有必要在疏散规划中合理 规定源点车辆的分批次出发时间和路线, 安排其有序疏 散。以往研究中关于疏散路线与出发时间的优化, 大多 采用动态网络流模型, 通过优化流在网络中移动的时空 轨迹来确定最优方案。文献1 将出发时间与疏散路线的 优化问题描述为最快流问题, 给出了在树形网络中寻找最 省时疏散方案的算法。文献2 对常用于疏散问题的动态 流模型及算法进行了研究, 对描述疏散方案优化的最快转 运问题, 给出了多项式算法。文献3 分别采用动态最快流 模型和字典序的动态最快流模型, 对分批次车队的疏散路 线与出发时间进行优化, 并结合仿真软件对疏散方案进行 评价。文献4 从建筑物等狭小空间疏散的应用角度, 系统收稿日期: 2009204212作者简介: 高明霞( 1979) , 女, 宁夏中卫人, 兰州交通大学交通运输学院讲师, 博士, 研究方向: 交通系统工程; 贺国光, 男, 湖南人,天津大学系统工程研究所教授, 博士生导师, 研究方向: 交通系统工程, 智能交通系统。系 统工 程2009年74kf ld lm in( l + +(f ) )(2)2 模型2. 1相关符号及变量用顶点表示路网中的交叉口、疏散源点及终点, 用弧 表示相邻交叉口或交叉口与源点或终点之间的路段, 将疏 散路网表示为有向网络 g = v , a , 其中 v 为顶点集合, a 为弧集合。设问题所在时间段为0, t , 将其划分为 krspsrsprr ss p p rs l= 1其中 ls + 代表时段 l 内出发的车辆在源点的等待时间。模型以沿各动态路径 ( 出发时间和路径组合) 出发且走行 的车辆数与其平均疏散时间乘积的总和作为总体疏散时 间的某种度量, 把对其的最小化作为目标。此时总疏散时 间虽然不能由目标函数直接得出, 但是却隐含在模型的解 中。模型的约束条件如下:个大小为 的小时段, 即 t = k .符号和变量:为叙述方便, 定义以下 u rsp ,klkaua = k , a(3)k: 时段编号, 表示车辆行驶在路网上的时刻所属时段, k = 1, 2, , k ;l: 时段编号, 表示车辆的出发时刻所属时段, l= 1, 2, k ;ks, k e: 第 k 个时段 (或时段 k ) 的开始时刻和结束时刻,k s = (k - 1) , k e = ks + ;ls , le: 第 l 个时段 (或时段 l) 的开始时刻和结束时刻,ls = ( l- 1) , le = ls + ;r , s: 疏散源点和终点的集合;r, s: 疏散源点和终点, rr , ss;d rs: r、s 之间总的疏散需求, 即位于 r 需去往 s 的车 数;p rs: r、s 之间路径的集合;rr ss p p rs1lk v rsp ,v klka k , aa =(4)rr ss p p rs1lk1x a = 0, a(5) (6)(7)x k =x k - 1 +uk - v k , k , aaaaav kb = uc , i, kkbb ( i)ca ( i) f rsp =ld rs , r, s(8)p p rs1lk(u lka lka lkalrsp , v rsp , rsp ) =g (f rsp : r, s, p , l)(9)(10) rsp , r, s, p , ld llkarsp =aa 1kklka =所有变量均大于等于 0,(11)0, 1rsp式(3)、式 ( 4) 为定义性约束; 式 ( 5) 给出了路网的初始条件; 式 (6) 为路段的状态方程, 式 (7)、式 ( 8) 为守恒约束, 分 别表示节点通过车数和源点总需求的守恒; 式 ( 9) 为流量 传播约束, 表示动态的路段车流量 (包括流入和流出) 和决 策变量之间的关系; 式 (10) 给出了路径走行时间与决策变 量之间的关系; 式 (11) 为非负约束。2. 3 基于加载仿真的流量传播描述流量传播约束描述了车流如何随着时间沿其走行路 线变化, 若不考虑走行速度和道路负荷之间的关系, 式 ( 9) 可以用一个线性方程代替。但是由于车辆走行速度是随着 道路负荷动态变化的, 车流随时间沿其路径的变化情况取 决于整个路网的交通状态, 而路网的交通状态又和整个规 划时间段内做出的决策 f 有关。式 ( 9) 中函数 g ( ) 表示的 是一个动态、非线性的复杂过程, 很难用解析的数学式子 描述。采用一个基于路段走行时间函数的加载 ( ne tw o rk load ing) 仿真模块来描述式 ( 9) 表示的关系, 其中用式 ( 12) 所示的修正 g reen2sh ie ld s 公式6 推算路段走行时间, 其 中 v f 、vm in、v、k、k j 分别代表自由流速度、最小速度、当前速 度、当前密度和阻塞密度, 走行时间由路段长度除以走行 速度 v 得到。基于这一走行时间函数的流量传播描述, 能 够保证路段上车流量和走行时间的一致性、因果性, 并在 一定条件下能满足先进先出7- 8 。lf rsp : 时段 l 内由 r 出发去往 s 且沿路径 p 走行的车辆数;f : (f l sp : r, s, p , l) 的集合;rd rsp (f ) : 在 f 决定的交通状态下, 在时段 l 内由 r 出l发去往 s 且沿路径 p 走行的车辆花在路上的平均走行时间;kx a: 第 k 个时段的初始时刻行使在路段 a 上的车辆数;kkv a: 时段 k 内进入 (离开) 路段 a 的车辆数;ua ,u lkalkarsp , v rsp : 时段 l 内由 r 出发去往 s 且沿路径 p 走行的车辆中, 在时段 k 内进入 (离开) 路段 a 的车辆数;lkarsp : 021变量, 若时段 l 内由 r 出发去往 s 且沿路径 p走行的车辆在时段 k 初行驶在路段 a 上则取1, 其他情况取0;a ( i)、b ( i) : 以节点 i 为起点和终点的路段集合。2. 2模型构造疏散路线方案优化的目标是使整体疏散时间最短, 即 从疏散开始至所有车辆都到达安全地点的时间最省, 该目 标可以直观地表示为m in t(1)式 (1) 虽然直观简便, 但是无法和决策变量建立联系,为了使模型便于求解, 以式 (2) 代替式 (1) 作为模型的目标 函数: k v = vm in + (v f - vm in ) (1 -)(12)k j第6期高明霞, 贺国光: 动态系统最优的疏散路线与出发时间综合优化模型75为简便起见, 只根据式 (12) 计算每个时段初始时刻和结束时刻的走行时间, 其它时刻的路段走行时间通过式(13) 表示的线性插值计算:v lm ay larsp =rsp (k , m )(24)klalairsp (k , m ) , j rsp (k , m ) 分别代表车流 ussp 在时段m 内离开路lka段 a 的最早时刻和最晚时刻, b rsp (k ) 代表车流 u rsp 离开路lalkat -k sd a ( t) = d a (k e ) - d a (k s ) k+ d a (k s ) ,- k段 a 的过程所在的时间跨度, y la在时段m 内离开路段 a 的车数。 根据以上分析, 墩给定的 f =的加载步骤如下:rsp (k , m ) 表示车流 u rsp 中lkaesk s t k e , a, k(13)根据模型特点, 需要记录 u lka , v lka 来表示路段上车流(f lrsp : r, s, p , l) , 具体rsprsp的动态性。此外, 在同一个时段内出发的车辆, 即便是路径相同也很难在同一个时刻到达或离开沿途的路段, 设 sla ,s tep 1 令 k = 1, x 1 =0, a;rspaelalrsp 分别表示车流 f rsp 进入路段 a 的最早和最晚时刻, 则车s tep 2 根据式 (12) 计算 d a (k s ) , d a (k e ) , a;流 f l 在路段上的动态性可以用 u lka , v lm a , sla , ela , m , ks tep 3 根据式 (16) 计算 u lkarsp , 根据式 (12) (15) 计算rsprsprsp rsp rsp来描述。假设车流 f l在时段 l 内是均匀地离开源点, 则有la larspsrsp , ersp , r, s, p , l, a.a 为 p 的第一条路段否则a 是 p 的第一条路段 否则ls ,s tep 4 根据式 ( 17) ( 24) , 由 (u lka , sla , ela ) v lm a ,slarsp =( )14rsp rsp rsp rspsla2pla2p+d a2p (srsp ) ,le ,rsp m , r, s, p , l, a.k kk+ 1s tep 5 由式 (3)、式 (4)、式 (6) 分别计算 ua , v a , x a ;s tep 6 若 k = k , 停止; 否则, 令 k = k + 1, 返回 s tep 2。elarsp =( )15ela2pla2p+d a2p (ersp ) ,rspf lk = l 且 a 为 p 的第一条路段k l 且 a 为 p 的第一条路段, 或k = l 但 a 不是 p 的第一条路段k l 且 a 不是 p 的第一条路段rsp ,3 算法3. 1算法思路及步骤上述模型从本质上来说是关于出行过程的优化模型, 只是此处所针对的是疏散出行。由于出行过程达到系统最 优时, 出行者不能通过单方面改变出行时间或路径使系统u lkarsp =0,v lka2p,rsp(16)其中 a2p 为路径 p 上位于 a 前面的路段。为了描述流量的传播, 还需追溯车流 u lka 在时段 k 内进入路段 a 的过程所rsp9的总费用更低 。对此处问题而言, 达到系统最优时每对od 之间所有被使用的动态路径 ( 路径和出行时间组合) 具有相等且最小的边际疏散时间, 而未被使用的动态路径 其边际疏散时间大于或等于最小值。由此提出一个启发式 算法, 对决策变量赋初值后, 通过不断迭代、调整来逼近最 优解。调整过程主要是将每对od 之间边际疏散时间较大 的动态路径的承载车流量, 调配至边际疏散时间较小的动 态路径; 调整的目标是使每对od 之间被使用动态路径的 边际疏散时间相等且最小, 而未被使用的动态路径其边际 疏散时间皆大于或等于最小边际疏散时间。当达到一定收 敛标准时, 算法停止。在的时间跨度, 这一时间跨度不一定等于时段 k 的长度。设 slalarsp (k ) , ersp (k ) 分别表示车流 u rsp 在时段 k 内进入路段 alka的最早时刻和最晚时刻, 其值取决于 sla , ela 与时段 k 的相rsp rsp对关系, 并不一定等于 k s 和 k e.由此流量传播描述即为根据 u lm a- p la- pla- p(m ) , ersp (m ) , d a- p (m s ) , d a- p (m e ) , m 确定rsp, srspu lka la larsp , srsp (k ) , ersp (k ) , k 的过程, srsp (k ) , ersp (k ) 根据 srsp , erspla lala la由下面的公式计算:k s ,t,k e ,t keslalarsp (k ) = m (srsp , k )(18)(19)令 crsp (f ) 表示在 f 对应的路网状态下, od 对 r、s 间lelalarsp (k ) = m (ersp , k )的出发时间 l 和路径 p 的组合 (p , l) 的边际疏散时间, 则算法步骤如下:v lm arsp , l, m 可由下面的公式确定:ilalalarsp (k , m ) = m(srsp (k ) +d a (srsp (k ) ) , m ) , k , ms tep 1 初始化, 令 i= 1, 为 f i = (f l : r, s, p , l) i 赋rsp(20) k , m(21)一组可行的初始值;s tep 2 根据加载模块, 由 f i = (f l sp : r, s, p , l) i 确定j lalalarsp (k , m ) = m(ersp (k ) +d a (ersp (k ) ) , m ) ,r(uk ) , (v k ) , (x k ) , a, k , 并计算边际疏散时间 cl (f ) ,a i a i a irspib lalalalalarsp (k ) = ersp (k ) + d a (ersp (k ) - srsp (k ) + d a (srsp (k ) , k(22) r, s, p , l;s tep 4调 整, r, s, 记:m in(f )= m in crsp (f ) i:lcrsu lka larsp j rsp (k , m ) - irsp (k , m ) lalka,u rsp 0lm inp p rs , 1 l k , (p rs ) i = (p , l) : crsp (f ) - (f )lacrsb rsp (k )0,y larsp (k , m ) = , p p rs , 1 l k , 令: (f l =(f l -u lkarsp ) i+ 1rsp ) irsp =0(f llm inrsp ) i crsp (f ) i - crs(f ) i ,(p , l) |(p rs ) i , p rs ,(23)p系 统工程2009年76(rs ) i(f l= (f l ) +, (p , l) (p ) , 其中, ( )算例以一个数值算例说明模型的应用, 图1所示为由某城 市一化工厂附近的疏散路网简化后的网络, 节点1、节点2、 节点3代表疏散源点, 节点17代表疏散终点, 设d 1, 17 = 1000rsp i+ 1 rsp irs irs i4i (p rs ) i i(f l ) cl (f ) - cm in (f ) , = .f lf l=iirsp i rsprsrsp rspp p rs, l(p , l) | (p rs) iks tep 5 收敛性判断, 若 i (f l -rsp ) i+ 1rr ss l= 1 p p rs(veh ) , d= 1500 (veh , d 3, 17 = 1200 veh 。)( )2, 17(f l ) i , 停止计算, 否则令 i= i+ 1, 返回 step 2 ( , , rsp i为简便起见, 令所有路段的 v f = 30 (km /h ) , vm in =为给定参数)。3. 2关键步骤 边际疏散时间的计算边际疏散时间的计算是算法的一个重要步骤, 对于点 对 r、s 间的出发时间 l 和路径 p 的组合 (p , l) , 在 f 对应的5 (km /h ) , k = 140 (veh /km /lan )。令 = 0. 01, = 0. 532, j= 2, = 5 (m in ) ,以时刻0为疏散开始时刻, 将本文的算法用 c + + 实现, 得疏散方案如表1所示, 表中所列数字为每个小时段内沿不同路径出发的车辆数。网络中三对od路网状态下, 其边际疏散时间 cl (f ) 包括边际等待时间之间共有37条路径 但按照表 的方案 只有, 14条路径被作,1rsp和边际走行时间, 其中边际等待时间与决策变量的取值无关, 等于实际等待时间; 边际走行时间由其包含路段的动 态边际走行时间累加得到。设路径 p 由路段 a1 , a2 , , am为疏散路线。采用加载仿真模块将疏散方案对应的车流加载到路网, 得疏散时间为45分钟。5 结束语本文立足于疏散规划, 充分考虑交通流的重要特征, 提出了一个动态系统最优的疏散路线与出发时间综合优 化模型, 通过优化分批次车队的疏散路线与出发时间, 使 总疏散时间最小化。根据模型最优性条件设计了一个启发 式算法, 并在数值算例中进行了应用。此类疏散方案可以 作为应急预案纳入长期规划, 也可以作为实时管理系统的 初始计划, 以提高实时管理的效率。虽然模型和算法的有 效性在算例的应用中得到了验证, 但算法在大型复杂网络 中应用的效率还需进一步检验, 这也是下一步要做的工 作。组成, 则 clrsp (f ) 按下式计算:clrsp (f ) =t1 + ca1 ( t1 ) + ca2 ( t2 ) +cam ( tm ) (25)+其中, t1 = ls +( le - ls ) , ti+ 1 = ti + d a ( ti) , i = 2, , mi1。ca ( ti ) 为路段 a i 在时刻 ti 的边际走行时间, 表示时刻-iti 路段 ai 上新进入一辆车对整体走行时间的贡献, 包括该车自身的走行时间和其对其他车辆走行时间的影响, 此处只考虑位于同一路段上车辆之间的影响, 对于 ti =k s 或 k ,k e , k , ca ( ti ) 根据式 ( 26) 计算, 对于 k s ti ke ,ica i ( ti ) 通过线性插值计算。5d a ( t)ca ( t) =d a ( t) +t x a ( t)(26)5xa ( )图1 算例的疏散网络第6期高明霞, 贺国光: 动态系统最优的疏散路线与出发时间综合优化模型77表1算例的疏散方案som e evacua t ion p rob lem s a . p roceed ing s of th ef if th annua l a cm 2s iam sym po sium on d iscre te a lgo r ithm s c . a r ling ton, v irg in ia, u n ited s ta te s,1994: 433 441.l in p. a dynam ic ne tw o rk f low op t im iza t ion fo r la rge2sca le em e rgency evacua t ion d . h ong kong: c ity u n ive r sity of h ong kong, 2006.h am ach e r h w , t jand ra s a. m a th em a t ica l m ode l2 ing of evacua t ion p rob lem s: a sta te of th e a r t a . sch reck cnbe rg m , sh a rm a s d. p ede st r ian and evac2ua t ion dynam icsc . sp r inge r, 2002: 227 266.34卢兆明等. 基于 g is 的都市应急疏散系统j .公共安全 (学术版) , 应急救援, 2005, 8: 35 40.中国56j ayak r ish nan r , e t a l. a dynam ic t raff ic a ssignm en tm ode l w ith t raff ic2f low re la t ion sh ip sj . t ran spo r ta2t ion r e sea rch: p a r t c , 1995, 3 (1) : 51 72.n ie x j , e t a l. d e lay2funct ion2ba sed link m ode ls:th e ir p rop e r t ie s and com p u ta t iona l issue sj . t ran s2po r ta t ion r e sea rch: p a r t b , 2005, 39: 729 751.c a rey m , ge y e. a lte rna t ive cond it ion s fo r a w e ll2beh aved t rave l t im e m ode l j . t ran spo r ta t ion sci2ence, 2005, 39 (3) : 417 428.c a rey m , s r in iva san a. conge sted ne tw o rk f low s:t im e2va ry ing dem and s and sta r t2t im e po licie s j . e u rop ean jou rna l of o p e ra t iona l r e sea rch , 1988, 36:227 240.78参考文献:1m am ada l s, e t a l. t h e evacua t ion p rob lem , dynam icne tw o rk f low s, and a lgo r ithm s a . s ic e a nnua lconfe rence in f uk u i c . f uk u i u n ive r sity, j ap an ,2003: 2807 2811.h opp e b , t a rdo s e. po lynom ia l t im e a lgo r ithm s fo r92syn thet ica l o p t im iza t ion m odel of o p t ima l eva cua t ion routesan d d epa r ture t im e cho ice in a d ynam ic sy stemga o m ing2x ia1 , h e guo 2guang2(1. l anzhou j iao tong u n ive r sity, l anzhou 730070, c h ina;2.t ian jin u n ive r sity, t ian jin 300072, c h ina)a bstra c t: a s an im po r tan t p a r t of em e rgency m anagem en t, th e reg iona l evacua t ion p roce ss indeed invo lve s m ovem en t ofp eop le by veh icle s, w h ich m ay gene ra te m any t raff ic t r ip s du r ing lim ited t im e. e ff icien t too ls a re needed to e stab lish evacua2 t ion rou t ing p lan s th a t iden t ify rou te s and dep a r tu re sch edu le fo r each g roup of veh icle s to en su re safe ty and o rde r. m any re sea rch w o rk s h ave de scr ibed th e op t im iza t ion of th e evacua t ion p rob lem a s a ne tw o rk f low p rob lem and u sed ne tw o rk f lowa lgo r ithm s to p roduce o r ig in2de st ina t ion rou te and dep a r tu re sch edu le of evacua t ion veh icle s in each o r ig in. h ow eve r, lit t