基于双层规划模型的应急救援调度与路径选择集成优化

姚 佼，邵楚薇，鲍雨婕，李宇航

(上海理工大学 管理学院，上海 200093)

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个方面进行分析，构建不同类型应急救援车辆的调度模型。具体而言：

目标函数：

ck(t)。

(1)

约束条件：

(2)

(3)

(4)

(5)

(6)

(7)

λp={0,1}。

(8)

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

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

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

2.2 下层模型构建

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

具体目标函数为：

(9)

约束条件：

(10)

(11)

(12)

(13)

(14)

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

模型参数：T′p为从p出救小区到事故发生点的在途行程时间；Tc为不同类型救援车辆在交叉口(路网拓扑中的节点)的延误时间，具体的延误时间计算参考经典的交叉口延误模型[22]；tij为应急车辆从节点i行驶到节点j的行程时间；fZ(Δtl)为表示路径交通状态参数；Δtc为交叉口等待的时间差；kij(Δtl)为时间间隔Δ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

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

表2 案例路网的相关参数Tab.2 Parameters of road network of case study

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

表3 救援请求点各类应急交通需求分析Tab.3 Analysis of emergency traffic demand at rescue request point

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

表4 不同类型应急救援车辆调度成本分析Tab.4 Analysis of scheduling cost of different types of emergency vehicles

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

表5 应急调度车辆的容量限制分析Tab.5 Analysis of capacity limitation of scheduling emergency vehicles

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

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

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

5 结论

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

表6 应急救援调度与动态路径选择集成的双层规划模型结果分析Tab.6 Analysis of result of bi-level programming model of integrated emergency rescue scheduling and dynamic route selection

表7 双层规划模型与单独考虑调度或路径选择模型的费用时间对比Tab.7 Comparison of costs and time of bi-level programming model with models only considering scheduling or route selection

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

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