公路交通科技  2021, Vol. 38 Issue (6): 149−158

扩展功能

文章信息

姚佼, 邵楚薇, 鲍雨婕, 李宇航
YAO Jiao, SHAO Chu-wei, BAO Yu-jie, LI Yu-hang
基于双层规划模型的应急救援调度与路径选择集成优化
Bi-level Programming Model Based Integrated Optimization of Emergency Rescue Scheduling and Route Selection
公路交通科技, 2021, 38(6): 149-158
Journal of Highway and Transportation Research and Denelopment, 2021, 38(6): 149-158
10.3969/j.issn.1002-0268.2021.06.019

文章历史

收稿日期: 2020-09-14
基于双层规划模型的应急救援调度与路径选择集成优化
姚佼 , 邵楚薇 , 鲍雨婕 , 李宇航     
上海理工大学 管理学院, 上海 200093
摘要: 城市中突发事件发生后,为有效降低财产损失和人员伤亡,减少应急救援在调度和路径选择等环节的响应时间损失,保障应急救援任务顺利完成,需要对各类应急救援交通资源进行合理调度,并在起讫点间根据路网实时交通状态,动态选择行驶路径,减少其路段行程时间。在多目标应急救援调度和最优路径选择目标分析的基础上,提出了一种考虑不同类型应急车辆调度和最优路径选择的双层规划的集成优化模型。在上层模型中,主要考虑应急救援车辆的调度费用成本,通过最小化应急救援车辆的固定成本、容量成本和时间成本,来确定不同类型应急车辆的出救位置和相应出动车辆数;下层模型中,主要考虑应急救援车辆的路径在途行程时间,通过最小化动态路网下应急救援的路段行程时间和信号延误时间来确定救援通过的路径,并根据固定的时间间隔动态更新路网的交通状态,使救援车辆尽可能选择避开交通拥堵的路段行驶,从而更快速到达目的地。案例分析结果表明,基于双层规划的应急车辆调度和路径选择集成模型与仅考虑调度或路径选择的模型相比,总调度成本降低了2.67%,总在途行程时间减少了21.05%,路径选择中能有效降低通过沿线拥堵道路的比例,表明模型具有很好的适用性和实用价值。
关键词: 城市交通     应急救援调度     双层规划模型     应急车辆类型     路径选择     集成优化    
Bi-level Programming Model Based Integrated Optimization of Emergency Rescue Scheduling and Route Selection
YAO Jiao, SHAO Chu-wei, BAO Yu-jie, LI Yu-hang    
School of Business, University of Shanghai for Science and Technology, Shanghai 200093, China
Abstract: When emergency event occurs in cities, in order to effectively reduce property losses and casualties, reduce the response time loss of emergency rescue in the links of schedule and route selection, and guarantee completion of emergency rescue tasks, it is necessary to schedule various emergency rescue traffic resources reasonably, and select the driving route dynamically to reduce the travel time of the road section based on real-time traffic status of the road network between the starting and ending points. Based on the analysis of objective of multi-objective emergency rescue scheduling and optimal route selection, a bi-level programming integrated optimization model considering different types of emergency vehicle scheduling and optimal route selection is proposed. In the upper model, the scheduling cost of emergency vehicles is considered, in which the rescue location and the corresponding number of different types of emergency vehicles are determined by minimizing the fixed cost, capacity cost, and time cost of the emergency vehicles. In the lower model, the route travel time of emergency vehicles is considered, in which the rescue route is determined by minimizing the travel time and signal delay time of emergency rescue in dynamic road network, and the traffic status of the road network is dynamically updated according to the fixed time interval, so that the rescue vehicles can choose to avoid traffic congestion as much as possible to reach the destination more quickly. The result of case study shows that compared with the model only considering scheduling or route selection, the integrated model of emergency vehicle scheduling and route selection based on bi-level programming can reduce the total scheduling cost by 2.67% and the total travel time by 21.05%, which can effectively reduce the proportion of congested roads along the route, indicating that the model has good applicability and practical value.
Key words: urban traffic     emergency rescue scheduling     bi-level programming model     emergency vehicle type     route selection     integrated optimization    
0 引言

城市化进程的加剧,城市多种功能的聚集化,突发应急事件发生的概率不断上升,如何降低其发生后的人员伤亡和财产损失值得关注[1]。救援时间作为应急交通的关键参数,一直是应急交通管理的主要目标,相关的研究表明,路网应急交通产生前的车辆调度,及产生后在路网中路径选择对其影响尤为显著[2]。因此,如何将二者进行有效的集成,针对不同类型应急救援车辆,精准施策,进行有效的集成,对于降低突发事件的影响,减轻其发生后果的严重性,具有十分重要的意义。

对不同类型应急救援车辆的合理地调度,并对其在路网的行驶路径进行优化,一直是应急交通系统优化的研究热点和难点。关于应急车辆调度,Özdamar等[3]对自然灾害下应急救援中多阶段的救灾物资配送问题进行了研究,并结合拉格朗日松弛法对动态救灾模型进行分析求解;计雷[4]提出应急调度救援的本质是运输费用成本和时间成本,因此他将模型简化为多目标优化问题并求最优解;在应急交通的路径选择方面,Potvin等[5]以突发事件为背景,研究了应急救援车辆路径问题,并且解决一个考虑客户实时请求和车辆动态行驶时间的时间窗动态车辆路径问题;刘勇等[6]根据基本蚁群模型,进行了最优路径蚁群模型的改进研究,在蚁群算法的转移概率中引入路径权重,得到了应急救援的最优路线,同时结合调度路径优化问题进行了多方面的考虑。

双层规划模型综合考虑了上下两层目标的协调,从而可以取得整个系统的最优解。Calvete等[7]基于此,构建了以生产调度问题为核心的双层规划模型,上层模型的目标是将时间成本和费用成本最小化,下层模型将生产成本最小化,并结合蚁群算法对模型进行求解;杨忠振等[8]建立的配送选择与路径优化双层规划模型,证明其可以有效降低配送系统的总成本,提高了配送的整体效率。在应急救援交通的管控中,若单独从一个角度进行优化,会因为考虑不够全面,无法得到整体最优的决策方案。只有将调度与路径问题综合考虑, 彼此反馈,全面协调应急救援中的各个环节,才能针对应急救援城市道路的特点制订成熟的、实时的应急救援方案。本研究综合双层规划模型在生产调度、物流配送及路径优化等方面的效果,根据不同应急救援车辆类型,结合路网交通状态的动态变化[9],将应急救援的调度和路径选择进行集成,构建相应的双层规划模型,并进行求解。

因此,本研究的重点主要聚焦在:

(1) 基于城市应急救援事件发生后,针对不同应急救援车辆类型进行调度,以及动态路网下应急车辆最优路径选择问题,提出了基于双层规划的应急救援调度与动态路径集成优化模型。

(2) 采用基于非优势排序和精英策略的遗传算法和改进蚁群对模型进行求解。

(3) 通过实际的案例分析与验证,验证模型在减少应急车辆的调度成本、在途行程时间、降低路网拥堵程度等方面的实用性。

1 应急救援调度和路径选择的目标分析

应急救援的主要目标是尽可能降低突发事件造成的影响[10],同时让应急交通能在最短时间内抵达事故发生点。因此,应急救援主要从应急交通的调度和路径动态选择两方面进行考虑。其中,应急车辆的调度是一个涉及多因素的复杂问题[11],不仅要兼顾应急救援时间,还要考虑受到出救小区资源调度分配的公平性、路径费用、救援不及时造成的损失等多方面的影响。本研究考虑单应急救援请求点、多应急出救点、不同类型应急救援车辆(如消防车、救护车、公安警车、工程抢险车)[12],在应急调度阶段,将优化的主要目标分为3个:以最小的时间成本实现对应急救援请求点的响应、以最小的固定成本实现各出救小区的选择、以最优的容量成本限制求解各出救小区中不同类型应急车辆的调度数量;在路径选择阶段,则重点考虑应急车辆到达救援点的时间尽可能短[13-14],即不仅考虑救援路径沿线的交叉口数量,及信号延误时间,还需要加入救援路径上的动态交通状态的影响。

基于上述目标的分析,考虑将应急救援的车辆调度和路径选择结合,建立双层规划模型,进行集成优化,其中上层应急调度中的时间成本是在下层路径行程时间的基础上,考虑不同出救点的车辆数量计算得到,其固定成本反映了各个应急小区的车辆出动情况,也会影响下层的路径选择,从而最终影响行程时间,上下两层间的目标不断相互反馈,最终结果趋于最优解,模型的研究流程如图 1所示。

图 1 应急救援交通调度与路径优化集成的双层规划模型研究流程 Fig. 1 Flowchart of studying bi-level programming model of integrated traffic scheduling and route optimization of emergency rescue

2 模型描述

应急救援的调度与路径选择可以看作是一个双层规划[15],为降低研究的复杂性,本研究设计不同类型应急救援车辆的出动位置以交通小区为单位进行划分,并根据该交通小区相应半径范围内是否存在车辆的集合地(如救护车的出动是考虑小区内是否存在医院以及数量,消防车考虑小区内是否存在消防站及其数量,工程抢险考虑小区内是否存在市政抢险单位及其数量),来确定该出救小区是否能出动相应类型的应急车辆进行救援。

决策部门根据各类应急交通资源的所处交通小区的位置,以及已知应急救援请求点的需求,在允许的各类应急车辆数约束下确定最佳的应急车车辆调度方案;对于各类应急车辆在出救点和救援请求点之间的路径选择,考虑路网交通状态的变化,动态优化应急交通的出行路径[16]。以最优化应急救援交通调度评价函数和最优路径选择评价函数为目标[17],采用双层规划的建模方法[18],构建了动态的调度与路径选择的集成优化模型[19]

考虑研究问题的复杂性,模型的建立进行了如下的假设:(1)救援请求点、出救点所在交通小区的地理位置,以及需要各类应急救援交通的车辆数均已知,且不存在变化;(2)路网中所有路段均连通,且路段长度、道路通行能力等参数均已知;(3)应急救援交通车辆类型较多,本研究选取较为关键的3类应急救援车辆类型进行研究;(4)本研究出现的各类型应急救援车辆的速度已知而且固定,终点均为救援请求点,且不考虑完成救援任务后的返回;(5)相同类型的应急车辆在救援中假定同时出动,不考虑车辆出动顺序。

2.1 上层模型构建

上层主要从应急救援车辆调度过程中的固定成本、容量成本和救援时间成本3个方面进行分析,构建不同类型应急救援车辆的调度模型。具体而言:

目标函数:

(1)

约束条件:

(2)
(3)
(4)
(5)
(6)
(7)
(8)

模型中有两类符号, 决策变量和模型参数。

其中,决策变量:λp为出救小区p是否派出车辆进行救援,如果是λp=1,否则λp=0。

模型参数:P为所有备选出救小区的集合;P0为被选中作为出救小区的集合;xpk为出救小区p中救援车辆类型k(消防车、救护车、公安警车、工程抢险车等)的数量;fp为每个出救小区p救援的固定成本;K为所有参与应急救援的车型集合;βl为出救小区p中救援车辆类型k的车辆数容量限制系数;fβ为出救小区的容量限制成本,即不能出现某一个出救小区出动救援车辆数量过多,而其他救援小区出动救援车辆明显偏少、资源浪费的情况;l为不同类型应急救援车辆的数量;al为救援车辆类型l的权重;Tp为从p出救小区到事故发生点的最优行驶时间;ck(t)为救援车辆类型k从出救小区行驶到救援请求点,每分钟产生的费用;wpk为出救小区p中现有的救援车辆类型k的总数量;mk为救援请求点需要的救援车辆类型k的数量;B为应急救援小区的总固定成本上限。

在上层规划中,式(1)的目标函数为最小化应急车辆调度的整体费用成本(包括固定成本、容量成本和时间成本);式(2)的约束表示各出救小区是否参与救援的判断参数;式(3)的约束表示该出救小区中同一救援车辆类型的容量限制判断参数;式(4)的约束表示应急车辆出救小区中可自由调度的车辆总数不能小于实际参与调度的车辆总数; 式(5)的约束表示实际出救小区中调度的各类应急车辆总数等于救援请求点的车辆需求总量;式(6)的约束表示至少要选择一个出救小区进行应急救援;式(7)的约束表示选择应急车辆出救小区的总费用不能大于应急救援小区的总固定成本上限;式(8)为决策变量的取值约束。

2.2 下层模型构建

下层主要从应急救援车辆出动救援时的路段行程时间和信号延误时间两个方面进行分析,构建不同类型应急救援车辆的动态路径选择模型。该模型基于救援前制定的静态最优路径,并根据实时路网交通状态调整最优路径[20]。因此,本研究固定的时间间隔,采用马尔可夫过程对路网交通状态进行预测[21],不同类型应急车辆出动前,根据时变的路径信息,更新下一步的优化救援路径,直至到达救援请求点。

具体目标函数为:

(9)

约束条件:

(10)
(11)
(12)
(13)
(14)

模型主要包含两类符号, 决策变量和模型参数。

其中,决策变量:ωijp为车辆是否从p出救小区出发,从i点前往j点,如果是ωijp=1,否则ωijp=0;μpk为救援车辆类型k是否从p出救小区出发,进行救援,如果是μpk=1,否则μpk=0。

模型参数:Tp为从p出救小区到事故发生点的在途行程时间;Tc为不同类型救援车辆在交叉口(路网拓扑中的节点)的延误时间,具体的延误时间计算参考经典的交叉口延误模型[22]tij为应急车辆从节点i行驶到节点j的行程时间;fZtl)为表示路径交通状态参数;Δtc为交叉口等待的时间差;kijtl)为时间间隔Δtl路径ij的交通状态影响值。

在下层规划中,式(9)目标函数最小化应急车辆路段行程时间的在途行程时间(包括路段行程时间和信号延误时间);式(10)的约束表示应急车辆从每个出救小区至救援请求点,均得到一条最优路径; 式(11)的约束为交通状态影响值的求解;式(12)约束为应急车辆路径的连续性限制,如果救援车辆从一个节点进入,也应从同一个节点离开;式(13)和(14)均为变量取值的约束。

3 模型求解

本研究上下层模型分别建立在NSGA-II算法和改进蚁群算法的基础上,结合全局搜索进行最终结果的求解。首先,从下层应急车辆最优路径选择着手,筛选出符合条件的最优路径,然后,将结果代入上层应急车辆调度中,由此,得到所有类型应急车辆最优路径结果均相同的双层规划最优解;由于某一类型的应急车辆出动救援,路网交通状态可能发生变化,因此需不断更新下层路径选择最优解,并将更新结果反馈给上层调度模型;如此循环往复多次,如果在一定的迭代次数内,全部类型的应急救援车辆均已出动,且当前上层调度的费用成本和下层路径选择的时间成本的总最优解均不发生改变,则终止计算,输出当前上、下层的最优解[23],作为双层规划模型的最优解。具体的模型求解流程如图 2所示。

图 2 调度和路径优化集成的双层规划模型的求解流程 Fig. 2 Flowchart of solving bi-level programming model of integrated traffic scheduling and route optimization

4 案例分析与验证

选取江苏省苏州市工业园区相关实际路网,模拟高峰时段辖区内第五元素网球场突发火灾的紧急救援交通调度和路径优化进行案例分析研究。

根据相关的信息统计,路网共有36个路段节点,55条相交路段。

根据苏州的实地建筑分布情况,以及该交通小区半径范围300 m内是否存在医院、公安派出所和消防站,明确消防车、救护车、警车等各类应急车辆的出救小区位置。据此根据实地的调查,案例路网中存在5个应急车辆不同类型的出救小区,具体的分布如图 3所示。

图 3 案例路网及各类型应急车辆的出救小区分布 Fig. 3 Road network of case study and distribution of emergency vehicles' rescue zones

结合火灾发生时间段(工作日上午8时—9时)的路网交通状态等相关信息,确定应急救援分配和应急车辆动态最优路径选择,并根据前述的双层规划模型和求解算法,进行仿真验证。

基于历史统计数据,进行相关的参数标定,相应参数设置如下:

(1) 需求点和出救小区:发生火灾的救援请求点用节点19#表示;根据附近公安派出所、消防站和医院的相应位置,确定应急车辆出救小区重心的分布,确定各类应急车辆的出救起始节点,标记为节点1#,3#,12#,21#和33#,并根据实际数据,调查各出救小区各类应急车辆的可供应量,如表 1所示。

表 1 各出救小区的应急车辆资源分布 Tab. 1 Distribution of emergency vehicle resources in each rescue zone
救援请求点救援出救小区 消防车/辆 警车/辆 救护车/辆
e1 8 4 3
e2 0 3 2
e3 5 2 0
e4 3 5 1
e5 0 8 6

(2) 道路网络配置参数:统计案例路网的相关静态参数,调查相应道路的交通量,各路段相关参数如表 2所示。

表 2 案例路网的相关参数 Tab. 2 Parameters of road network of case study
节点编号 道路
长度/m
交通量/
(veh·h-1)
节点编号 道路长度/
m
交通量/
(veh·h-1)
节点编号 道路
长度/m
交通量/
(veh·h-1)
节点编号 道路
长度/m
交通量/
(veh·h-1)
(1, 2) 1 218 1 431 (9, 12) 273 1 124 (18, 25) 894 829 (27, 28) 1 713 920
(1, 5) 261 1 247 (10, 11) 626 473 (19, 20) 335 737 (27, 30) 382 435
(2, 3) 1 400 989 (10, 13) 225 1 266 (19, 23) 562 762 (28, 29) 1 233 820
(2, 6) 189 792 (11, 14) 230 1 260 (20, 24) 584 (20, 24) (28, 32) 355 1 393
(3, 4) 766 1 024 (12, 13) 479 704 (21, 22) 909 (21, 22) (29, 36) 898 1 053
(3, 7) 214 627 (12, 21) 1 021 1 387 (21, 26) 992 (21, 26) (30, 31) 340 293
(4, 8) 259 917 (13, 14) 615 681 (22, 23) 662 (22, 23) (30, 33) 760 580
(5, 6) 1 197 887 (14, 15) 694 1 230 (22, 27) 1 125 (22, 27) (31, 32) 751 510
(5, 9) 403 1 032 (14, 22) 1 173 772 (23, 24) 321 587 (31, 34) 464 374
(6, 11) 384 721 (15, 16) 339 883 (24, 25) 1 211 480 (32, 35) 570 1 060
(7, 8) 764 632 (15, 19) 686 722 (24, 28) 1 118 990 (33, 34) 417 550
(7, 17) 597 739 (16, 17) 400 670 (25, 29) 809 800 (35, 36) 1 323 798
(8, 18) 582 957 (16, 20) 689 764 (26, 27) 943 533
(9, 10) 524 700 (17, 18) 779 732 (26, 33) 1 311 525

(3) 应急资源需求信息:根据《突发事件应急管理》中规定的生产安全事故等级标准,判断该突发性火灾的规模属于较大规模的突发事件。已知该火灾发生时消防车辆、救护车辆和警车均需到达现场进行应急救援。查询应急管理部对火灾现场应急处置措施,及较大火灾对这3类应急车辆的的需求量,整理得到救援请求点应急车辆的需求量如表 3所示。

表 3 救援请求点各类应急交通需求分析 Tab. 3 Analysis of emergency traffic demand at rescue request point
救援请求点 消防车/辆 警车/辆 救护车/辆
Z 12 15 8

(4) 应急车辆调度时间成本:根据公安部相关火灾损失统计和损失计算方法[24],并参考《江苏省医疗服务项目价格手册》,计算不同类型应急救援交通的调度时间成本相关参数,如表 4所示。同时,结合表 2中的相关的路径长度,计算不同类型应急救援车辆路径选择的路段行程时间,结合表 4中的行驶费用,最终计算出各类应急救援车辆的调度时间成本。

表 4 不同类型应急救援车辆调度成本分析 Tab. 4 Analysis of scheduling cost of different types of emergency vehicles
车辆类型 行程费用mk/(元·min-1) 行驶速度vk/(km·h-1)
消防车 15 75
警车 12 40
救护车 10 60

(5) 调度容量限制成本:通过上述参考文献,计算每个出救小区出动车辆的固定成本为300元,进而求得不同类型应急救援车辆调度的固定成本;根据应急车辆出动所花费的时间,判断不同类型应急救援车辆出发的时间间隔为5 min,以此为固定的间隔时间更新路径交通状态信息,并计算不同类型应急救援车辆沿线路径的交叉口处的信号延误时间。每种应急车辆调度的容量成本情况如表 5所示,结合模型可计算应急车辆调度的容量成本。

表 5 应急调度车辆的容量限制分析 Tab. 5 Analysis of capacity limitation of scheduling emergency vehicles
容量限制类型 β1 β2 β3
费用/元 100 75 50

结合上述的双层规划的模型参数,进行求解。上层应急车辆的调度为整个双层规划模型的主程序,先假设每个出救小区到救援请求点的行驶时间仅考虑最短路径长度,在迭代完成时,将不同应急出救小区选择和各类型应急车辆的调度方案导入到下层模型下层根据上层的初始方案进行计算,并考虑到每条路径的交通状态,更新路网交通状态,分别为初始、5 min和10 min的路网交通状态。

通过计算求得各个出救小区到救援请求点的最优路径,同时将最优路径行驶的时间结果返回到上层的调度模型中,上层模型再次调整调度方案,重复迭代此过程,直至得出最终的出救小区选择、车辆出动数量及路径优化方案。

求解过程,上层调度的求解中运用MATLAB编写相关的应急车辆调度优化函数,运用NSGA-II算法求解,设置遗传变异算子参数(种群规模50,迭代100次,交叉概率0.8,变异概率0.2);下层的路径选择,根据案例的相关数据,通过MATLAB仿真软件,运用改进的蚁群算法求解,参数设置为m=200,NCmax=100,α=0.5,β=1,ρ=0.1,最终求解仅考虑调度或路径优化,以及本研究基于双层规划的调度和路径选择集成的结果,如图 4所示,双层规划模型计算求得的调度成本、行程时间等参数如表 6所示。

图 4 双层规划模型与单独考虑调度或路径选择模型的结果对比 Fig. 4 Comparison of results of bi-level programming model with models only considering scheduling or route selection

表 6 应急救援调度与动态路径选择集成的双层规划模型结果分析 Tab. 6 Analysis of result of bi-level programming model of integrated emergency rescue scheduling and dynamic route selection
方案 车辆类型 出救位置 出救数量/
配送路线 出救点固定成本/元 容量限制成本/元 救援时间成本/元 在途行程时间/min 信号延误时间/min
双层规划 消防车 E1 5 1-5-9-12-13-14-15-19 100 75 279.40 3.73 3.00
E2 0 3-7-17-16-20-19 0 0 0.00 2.43 2.00
E3 5 12-13-14-15-19 100 100 205.86 2.75 1.50
E4 2 25-18-17-16-20-19 100 75 92.62 3.09 2.00
E5 0 33-34-35-32-28-24-20-19 0 0 0.00 3.92 3.00
救护车 E1 0 1-2-6-11-14-22-23-19 0 0 0.00 5.23 3.00
E2 1 3-7-17-16-20-19 100 50 30.42 3.04 2.00
E3 0 12-13-14-22-23 0 0 0.00 4.02 1.50
E4 1 25-24-23-19 100 100 32.66 3.27 1.00
E5 6 33-34-35-32-28-24-23-19 100 100 298.98 4.98 3.00
警车 E1 4 1-2-6-11-14-15-19 100 100 334.15 6.96 2.50
E2 1 3-7-17-16-20-19 100 50 58.64 4.89 2.00
E3 2 12-13-14-15-19 100 100 123.52 5.15 1.50
E4 5 25-24-23-19 100 100 326.43 5.44 1.00
E5 3 33-26-21-22-23-19 100 50 308.66 8.57 2.00
上层调度成本 1 100 900 2 091.34
下层路径时间 52.55 31.00

为进一步验证本研究所采用的双层规划模型对基于紧急车辆调度各路径优化研究的有效性,对仅考虑调度模型中,采用Dijkstra最短路径分配法对路径进行选择;在仅考虑路径选择的模型中,采用全有全无分配法对以调度方案进行选择,最后将3种情况下的费用成本和时间成本进行了对比分析,具体结果如表 7所示。

表 7 双层规划模型与单独考虑调度或路径选择模型的费用时间对比 Tab. 7 Comparison of costs and time of bi-level programming model with models only considering scheduling or route selection
方案 固定成本/元 容量成本/元 时间成本/元 总成本/元 路段行程时间/min 信号延误时间/min 在途行程时间/min
本研究双层规划模型 上层调度选择后的总成本 下层路径优化后的行程时间
1 100.00 900.00 2091.34 4 091.34 52.55 31.00 83.55
仅考虑调度的 1 100.00 900.00 2 203.38 4 203.38
仅考虑路径优化 71.33 34.50 105.83
优化比例/% 0.00 0.00 5.09 2.67 26.32 10.14 21.05

从中可以看出,与仅考虑调度或路径选择的应急车辆模型相比,由于双层规划模型将调度和路径优化集成,能够根据下层道路情况的变化更新最优路径的选择,同时反馈给上层调度,更新调度方案,上下两层相互反馈,可以有效提高应急救援的整体效率,优化资源分配,故上层调度模型总成本降低了2.67%,下层路径选择后的在途行程时间减少了21.05%,具体的对比分析示意如图 5所示。此外,与仅考虑调度或路径优化的模型相比,基于双层规划的集成模型克服了重复选取同一条路径的缺陷,降低路段的压力,避免拥堵结果的产生。因此,基于双层规划的应急车辆优化研究模型所得到的方案要更优越,实用性更高。

图 5 模型的调度成本和路径行程时间对比 Fig. 5 Comparison of scheduling costs and route travel time of models

5 结论

本研究从不同类型应急救援车辆的调度和动态路径选择的集成出发,从调度的固定成本、容量成本和时间成本,以及路径选择的路段行程时间和信号延误时间等多个角度着手,构建了基于双层规划模型的不同类型应急车辆调度和路径选择集成优化模型,进而采用全局搜索,结合NSGA-II算法和改进蚁群算法对模型进行了求解。最后通过相关的案例,对模型的效果进行了分析对比,结果表明:本研究的集成优化模型与仅考虑调度或路径选择的模型相比,在调度成本和路径选择的在途行程时间等方面有较好的改进,具有较好的实用性和应用价值。

但应该注意的是,为了简化运算,研究的案例是基于固定时间的进行路网更新,而现实中路网的变化更为复杂,部分路段的变化情况可能被错误预估。因此,面对不同类型应急车辆救援,可在本研究模型的基础上进一步调整,如针对不同类型车辆的出动优先性也可在后续进一步深入研究。

参考文献
[1]
刘波, 李砚. 应急物资车辆调度的鲁棒双层优化模型[J]. 系统工程, 2016, 34(5): 77-81.
LIU Bo, LI Yan. Robust Bilevel Optimization Model for Vehicle Routing of Emergency Commodities[J]. Systems Engineering, 2016, 34(5): 77-81.
[2]
AFSHAR A, HAGHANI A. Modeling Integrated Supply Chain Logistics in Real-time Large-scale Disaster Relief Operations[J]. Socio-Economic Planning Sciences, 2012, 46(4): 327-338.
[3]
ÖZDAMAR L, EKINCI E, KVÇVKYAZICI B. Emergency Logistics Planning in Natural Disasters[J]. Annals of Operations Research, 2004, 129(1/2/3/4): 217-245.
[4]
计雷, 池宏, 陈安, 等. 突发事件应急管理[M]. 北京: 高等教育出版社, 2006.
JI Lei, CHI Hong, CHEN An, et al. Emergency Management[M]. Beijing: Higher Education Press, 2006.
[5]
POTVIN J Y, XU Y, BENYAHIA I. Vehicle Routing and Scheduling with Dynamic Travel Times[J]. Computers & Operations Research, 2006, 33(4): 1129-1137.
[6]
刘勇, 刘念, 刘孙俊. 一种基于免疫蚁群混合算法的TSP求解模型[J]. 四川大学学报, 2010, 42(3): 121-126.
LIU Yong, LIU Nian, LIU Sun-jun. A TSP Solving Model Based on Immune Ant Colony Hybrid Algorithm[J]. Journal of Sichuan University, 2010, 42(3): 121-126.
[7]
CALVETE H I, GALÉ C, OLIVEROS M J. Bilevel Model for Production-distribution Planning Solved by Using Ant Colony Optimization[J]. Computers & Operations Research, 2011, 38(1): 320-327.
[8]
曾庆成, 杨忠振, 蒋永雷, 等. 配送中心选址与车辆路径一体优化模型与算法[J]. 武汉理工大学学报, 2009, 33(2): 267-270.
ZENG Qing-cheng, YANG Zhong-zhen, JIANG Yong-lei, et al. Optimization Model and Algorithm of Coordinated Distribution Center Location and Vehicle Routing[J]. Journal of Wuhan University of Technology, 2009, 33(2): 267-270.
[9]
YI W, ÖZDAMAR L. A Dynamic Logistics Coordination Model for Evacuation and Support in Disaster Response Activities[J]. European Journal of Operational Research, 2007, 179(3): 1177-1193.
[10]
WANG H, DU L, MA S. Multi-objective Open Location-routing Model with Split Delivery for Optimized Relief Distribution in Post-earthquake[J]. Transportation Research Part E: Logistics and Transportation Review, 2014, 69(1): 160-179.
[11]
GU F, LIU H L, WANG Q. Relay Node Deployment for Wireless Sensor Networks Using Evolutionary Multi-objective Algorithm[J]. International Journal of Sensor Networks, 2019, 31(3): 189-197.
[12]
张凯敏. 面向紧急救援交通的路径级信号控制策略研究[D]. 上海: 上海理工大学, 2018.
ZHANG Kai-min. Study on Route Signal Control Strategy for Emergency Traffic[D]. Shanghai: University of Shanghai for Science and Technology, 2018.
[13]
刘杨, 云美萍, 彭国雄, 等. 应急车辆出行前救援路径选择的多目标规划模型[J]. 公路交通科技, 2009, 26(8): 135-139.
LIU Yang, YUN Mei-ping, PENG Guo-xiong, et al. A Multi-objective Programming Model of Route Choice of Emergency Vehicles before Travel[J]. Journal of Highway and Transportation Research and Development, 2009, 26(8): 135-139.
[14]
PAL P, TRIPATHI S, KUMAR C. Clustered Heterogeneous Wireless Sensor Network Infrastructure for Reliable and Efficient Path Planning of Mobile Nodes in Remote Area[J]. International Journal of Sensor Networks, 2019, 31(4): 199-215.
[15]
YAO J, ZHANG K, YANG Y, et al. Emergency Vehicle Route Oriented Signal Coordinated Control Model with Two-level Programming[J]. Soft Computing, 2018, 22(13): 4283-4294.
[16]
杨莉. 物流中心选址和布局规划的两阶段双层规划模型及解法研究[D]. 西安: 长安大学, 2006.
YANG Li. Research on Two-stage Bi-level Planning Model and Solution Method of Logistics Center Location and Layout Planning[D]. Xi'an: Chang'an University, 2006.
[17]
喻德旷, 杨谊. 多受灾点应急救援车辆调度的优化遗传算法[J]. 计算机系统应用, 2016, 25(11): 201-207.
YU De-kuang, YANG Yi. Optimized Genetic Algorithm for Vehicle Scheduling Problem in Emergency Rescue of Multiple Disaster Areas[J]. Computer Systems & Applications, 2016, 25(11): 201-207.
[18]
潘根安. 基于禁忌遗传算法的区域路网双层优化模型[J]. 系统管理学报, 2012, 21(4): 571-576.
PAN Gen-an. Bi-level Bi-level Optimization Model of Road Network Based on Genetic Algorithm and Tabu Search[J]. Journal of Systems & Management, 2012, 21(4): 571-576.
[19]
李孟良, 王喜富, 孙全欣, 等. 基于鲁棒优化的应急物资多式联运调配策略研究[J]. 铁道学报, 2017, 39(7): 1-9.
LI Meng-liang, WANG Xi-fu, SUN Quan-xin, et al. Research on Allocation Strategies of Multimodal Transportation for Emergency Resources Based on Robust Optimization[J]. Journal of the China Railway Society, 2017, 39(7): 1-9.
[20]
杨春霞, 秦家鹏, 王庆, 等. 基于多车道加权融合的短时交通流预测研究[J]. 公路交通科技, 2021, 38(1): 121-127.
YANG Chun-xia, QIN Jia-peng, WANG Qing, et al. Study on Short-term Traffic Flow Prediction Based on Multi-lane Weighted Fusion[J]. Journal of Highway and Transportation Research and Development, 2021, 38(1): 121-127.
[21]
郭海锋, 蔡华波, 朱超, 等. 基于马尔可夫过程的路网交通状态预测方法[J]. 浙江工业大学学报, 2017, 45(4): 421-426.
GUO Hai-feng, CAI Hua-bo, ZHU Chao, et al. Prediction Method of Road Network Traffic State Based on Markov Process[J]. Journal of Zhejiang University of Technology, 2017, 45(4): 421-426.
[22]
周荣贵, 钟连德. 公路通行能力手册[M]. 北京: 人民交通出版社, 2017.
ZHOU Rong-gui, ZHONG Lian-de. China Highway Capacity Manual[M]. Beijing: China Communications Press, 2017.
[23]
郑斌, 马祖军, 周愉峰. 震后应急物流动态选址-联运问题的双层规划模型[J]. 系统管理学报, 2017, 26(2): 326-337.
ZHENG Bin, MA Zu-jun, ZHOU Yu-feng. Bi-level Model for Dynamic Location-transportation Problem for Post-earthquake Relief Distribution[J]. Journal of Systems & Management, 2017, 26(2): 326-337.
[24]
贾宜普. 我国火灾损失统计工作的发展、现状及对策初探[J]. 消防科学与技术, 1998, 17(3): 33-34.
JIA Yi-pu. Preliminary Study on Development, Current Situation and Countermeasures of Fire Loss Statistics in China[J]. Fire Science and Technology, 1998, 17(3): 33-34.