权衡预测时间和偏离度的消防车辆救援调度算法

陈友荣 卢俊杰 曾江波 孙 萍 诸燕平

1(常州大学信息科学与工程学院 江苏 常州 213164)2(浙江树人大学信息科技学院 浙江 杭州 310015)3(台州市消防救援支队司令部信通科 浙江 台州 318000)

0 引 言

伴随着我国社会经济发展，城市火灾的发生往往造成较大的经济损失和人员伤亡。在火灾发生后，消防中心接到报警信息，并根据国家出警标准进行消防车辆和其人员的调度派遣。而在车辆调度过程中，往往依靠人工经验进行调度，且不考虑道路的拥堵程度，车辆行驶时间较高且调度效率较低[1-2]，因此迫切需要一种消防车辆救援调度算法。

目前国内外学者在调度优化领域已取得一定成果。部分学者侧重于以救援时间短，经济损失小作为模型优化目标，研究多目标调度分配和调度优化集成问题，如：文献[3]和文献[4]为解决多发放点之间潜在的应急救援物资调度冲突问题，提出运输时间最短和成本最小的多目标优化模型，并采用改进蚁群进行求解。文献[5]和文献[6]针对应急资源分配问题，均以人员伤亡、经济损失和救援开支费用最小作为约束条件，建立一种在多出救点、多物资和多受灾点约束条件下的资源分配模型。文献[7]建立了以抢险救援工作结束时间最早和出救装备总调度费用最少的双目标优化装备调度模型，并借助贪婪算法对该模型进行分层序列求解。但是文献[3-7]未考虑灾情随时间动态变化情况下的调度问题。部分学者侧重于考虑救援时间和车辆行驶距离，研究车辆的调度算法[8]，如：文献[9]考虑避难点分配、路径规划和不确定通行能力等约束，建立不确定信息环境下救援优化模型，并提出基于逆向搜索最短路径和正向反推安全路径的求解方法。文献[10]提出基于风险并结合消防服务覆盖模型，采用进化算法解决消防定位和快速救援服务的问题。但是文献[9-10]没有以最小救援时间作为主要优化目标。同时部分学者侧重于研究消防人员调度问题，如：文献[11]针对并发火灾的消防力量调派，以并发火灾总体灭火救援效果最优为目标，应用线性规划理论建立消防力量供大于求时的优化部署模型，给出了消防力量供求关系不平衡时的优化部署方案。文献[12]引入了一种基于数学规划的滚动水平启发式算法，对不同位置设立不同权重来求解分配调度问题。但是文献[11-12]只是考虑消防车辆到达时间，没有考虑多消防车辆出警时的离规定救援时间的偏离度。

综上所述，目前国内外学者较少关注消防领域急需解决的问题——消防救援调度优化问题，已取的研究成果较少，可借鉴的算法较少，由此可见，应对火灾的消防救援调度优化问题仍有待解决。因此提出一种权衡预测时间和偏离度的消防车辆救援调度算法(Rescue scheduling algorithm of firefighting vehicle weighing forecast time and deviation degree，RSA)，即根据接警信息，确定火灾的受灾区域和其需要的车辆数，提出受灾区域所需消防车辆数量约束和消防中心拥有消防车辆数量约束，并根据路段期望通行时间计算当前路段路况权重。计算消防车辆到达各个受灾区域的平均调度预测时间及其离规定救援时间的偏离度，建立权衡预测时间和偏离度的消防车辆救援调度算法。采用修正的遗传算法求解该消防车辆救援调度模型，获得消防车辆的最优路线，通过精英保留策略在每一轮迭代中保留最优解，提高算法的收敛性，使用映射交叉操作保证调度错解尽可能地减少，在变异的不同阶段使用不同变异策略提高局部的搜索能力。修正的遗传算法能适应不同的受灾救援场景，获得消防车辆的最优调度方案，从而降低消防车辆的行驶时间，降低调度预测时间离规定最大救援时间的偏离度，实现救援调度的高效率和公平性。

1 数学模型

1.1 问题提出

研究消防车辆在应急火灾场景中的快速调度优化方法，解决的问题可描述为：一个城市有若干个消防中心，每个消防中心有多辆消防车辆，一辆消防车辆同一个时刻只可负责一个受灾目标的救援任务。当发生报警时，消防车辆根据调度预测时间最小和公平性原则进行调度分配。

1.2 假设前提

(1) 一个城市已知有若干个消防中心，并根据报警信息和国家出警标准，获知当前受灾区域位置和需要的消防车辆数。

(2) 消防中心出发时，消防车辆中存在救援的消防人员，从而实现消防人员的调度。

(3) 车辆移动路径只考虑出发达到目标火灾现场时的距离长度，不计算救援总任务完成后的返回距离。

1.3 模型建立

一个城市有若干个消防中心，一个消防中心有若干辆消防车辆。当发生火灾时，首先根据道路的相关拥挤情况将消防中心中的消防车辆分配给火灾救援点，以尽可能地满足受灾需求以及救援的高效率，其次针对多个火灾点引入救援时间偏离度，尽可能保证其救援公平性，从而实现火灾救援的高效率与救援公平的平衡。但是算法仍需要解决以下二个问题：一是如何建立权衡预测时间和偏离度的消防车辆救援调度模型；二是如何求解上述模型，从而获得最优方案，从而降低车辆到达灾区时间和离规定救援时间的偏离度。具体模型建立如图1所示。

图1 消防车辆调度示意图

由于消防中心的消防车辆数量固定，因此消防中心拥有消防车辆数量约束为：

根据式(4)计算所得的行程时间比值，通过对比同一路段的相邻两个时间段车辆通行速度预测路段是否处于拥堵减轻或加重，获得当前路段路况权重。

当城市中出现多起或重大火灾等突发事件时，困于消防力量的有限性，不能在规定救援时间内满足所有受灾区域的消防调度需求，则考虑让所有受灾区域的消防车辆分配尽可能公平，即到每一个受灾点的车辆救援调度时间距离规定的救援车辆抵达时间的偏离程度尽可能小，则：

式中：ω表示救援时间偏离度；ωv表示车辆v的调度预测时间的偏离值；tv表示车辆v的调度预测时间；V表示受灾区域所需要的消防车辆数量；μ表示规定消防车辆到达受灾区域的最大救援时间，通常为5～8分钟。

则建立权衡车辆调度预测时间和偏离度的优化模型为：

minaT/Tyu+βω/ωyu

s.t. 式(1)-式(7)

a+β=1

(8)

式中：a表示车辆调度预测时间因子；Tyu表示车辆调度预测时间阈值；β表示偏离度因子；ωyu表示偏离度阈值。

2 模型求解

由于多火灾点的消防车辆调度问题是NP-Hard问题，目前国内外学者通常采用人工智能算法进行求解。而遗传算法相较于粒子群算法，蚁群算法和模拟退火具有较高的鲁棒性和较强的搜索能力等特性，更适合求解较为复杂的调度优化问题，因此采用遗传算法求解消防车辆救援调度模型，具体求解过程如下。

2.1 消防车辆的调度模型求解

当遗传算法被应用到调度问题中，一个有效的调度序列被称作染色体，每个染色体都有自己的适应度值。遗传算法以迭代的方式运行，每次迭代代表了种群的一代。每一代种群染色体包括上一代的幸存者和新的经过交叉、变异和选择后而新产生的比较优秀的染色体。不同的染色体是否被选择是由它们的适应度值来决定的，适应度越值大，被选中的概率越大。重复这种选择机制，直至满足给定条件为止。

2.2 染色体编码设计

改进遗传算法采用自然数编码，在消防调度中，拟设定一个城市有j个消防中心，有V个消防车辆以及k个受灾区域，编写长度为V的染色体编码。如图2所示，第一行代表已被调度消防车辆编号，第二行代表消防车辆所出发的消防中心点，第三行代表受灾区域。例如第一列(1，1，2)代表1号消防中心派遣车辆编号为1的消防车辆前往2号受灾区域。依次循环类推，形成对每一辆消防车辆的调度指示。

图2 编码结构

2.3 种群初始化

种群的初始化就是依据编码规则给出种群的初始解。通常使用常用的随机数生成器和修正的方法获得符合约束条件式(1)-式(2)的初始种群，作为有效初始解。初始化染色体的具体程序流程如下：

步骤3如果集合S中元素个数小于V，则向集合S中添加0元素，使集合S中元素个数等于V。随后从中随机抽取V个不重复的元素，将其放置在第三行中。获得符合约束条件式(1)和式(2)的车辆编号不重复的车辆调度序列。

2.4 染色体适应度评价

算法目标函数是最小化消防车辆调度预测时间和救援时间偏离度，则令染色体的适应度函数为：

FitnessC(i)=1/(aT/Tyu+βvar/vyu)

(9)

其中，适应度函数值越大，则该调度方案越优，反之越差。

2.5 选择操作

遍历计算父代种群中所有染色体的适应度值，将适应度最优的染色体直接存入下一代新种群。随后从父代种群中随机选择2个染色体进行两两比对，选择适应度较优的染色体，直至下一代新种群染色体数量与父代种群染色体数量一致。

2.6 交叉操作

算法使用部分映射交叉算子产生下一代染色体。由于染色体的三维构造特殊性，在进行交叉操作时需要将消防车辆与消防中心出发点进行绑定。使用映射交叉方法可以避免染色体出现异常解，保证染色体都满足约束式(1)-式(2)。随机选择两个父代染色体，随机选择基因段的两处位置，以此为起止位置，交换基因，并根据映射关系进行修正。具体步骤如下：

步骤1在[0,1]范围内产生一个随机浮点数，若其值小于预先设定的交叉概率，则进行交叉操作，从下一代新种群中随机选择一对染色体，跳到步骤2。反之，不进行交叉操作，退出。

步骤2产生两个小于染色体长度的随机正整数r1和r2，作为两染色体交叉段的基因起止位置。对基因起止位置中，第一行和第二行的基因数据进行交换，第三行保持不变，并获得根据两个染色体的交换基因位置，建立一一映射关系。

步骤3检查交叉后两个染色体中是否存在重复的消防车辆调度编号。如果存在重复的数字编号，则选择交叉段外的重复基因，根据已获得的基因映射关系，替换成对应映射基因，若替换后仍存在重复冲突，则继续寻找和替换成当前基因对应的映射基因，直到染色体中不存在重复基因。

具体实例如图3-图4所示，随机选择两个整数1和3，在父代染色体1和父代染色体2中都以此为起止位置，选择需要的交叉基因段为[2 3 4,1 2 2]和[4 5 2, 3 1 2]，对其进行交叉得到两个原始子代，获得映射关系1↔1，2↔4，5↔3。交叉后原始子代1中出现数值为5的重复冲突，原始子代2中出现3的重复冲突，选择交叉段外的重复基因，根据已获得的基因映射关系，替换成对应映射基因，若替换后仍存在重复冲突，则继续寻找和替换成当前基因对应的映射基因，直到染色体中不存在重复基因，最终消除冲突获得子代。

图3 染色体交叉

图4 重复项消除

2.7 变异操作

在基本遗传算法的基础上，采用了移位变异操作和非均匀变异两次变异操作，改善遗传算法的局部搜索能力，维持群体的多样性，防止出现早熟现象。具体步骤如下：

步骤1在[0,1]范围内产生一个随机浮点数，若其值小于预先设定的变异概率，则对该染色体进行变异操作，并获知当前迭代次数，跳到步骤2。反之，则不进行变异操作。

步骤2如果当前迭代次数不大于20(取经验值)，则采用非均匀变异方法，即根据2.3节中第三行序列的步骤2和步骤3，重新对该染色体的第三行序列进行初始化，退出，结束变异操作，否则跳到步骤3。

步骤3重复执行K-1次操作：随机指定两个基因位置，交换其基因码。退出，结束变异操作。

由于染色体在初始化时即已满足约束条件式(1)-式(2)，在后续的选择、交叉、变异操作中，对染色体的基因仅在位置上发生变换，不做数值的随机变换，因此新生成的染色体仍满足约束条件式(1)-式(2)，不需要对染色体进行修正。

3 算法实现

如图5所示，本文模型主要使用遗传算法进行计算求解，在算法初始阶段，获取模型必要数据以及设置算法初始参数，其具体步骤如下所示：

步骤2经百度地图开源平台获取车速、道路拥堵等参数，更新RCW值，计算各个消防中心预计抵达灾区所需时间，并根据对各个消防中心车辆进行三维度实数编码。

步骤3初始化Mc个满足式(1)-式(2)的车辆调度染色体；初始化车辆调度种群中染色体个数为Mc，车辆交叉概率为Pc，变异概率为Pm，迭代次数rc=0，最大迭代次数为Rc，初始化Mc个满足式(1)-式(2)的车辆调度染色体。

步骤4以车辆调度预测时间和救援时间偏离度最小作为染色体适应度，通过式(9)计算每个车辆调度染色体的适应度值，更新最优车辆调度染色体。

图5 算法模型求解流程

步骤5将当前车辆调度最优的染色体放入下一代种群，随后重复执行Mc-1次以下操作，直至下一代种群与当前种群规模大小一致：随机选择两个染色体，选择其中适应度较好的染色体放入当前选择种群。

步骤6令当前操作序号i=0，从当前选择种群中选择染色体ic，随机生成[0,1]范围内的一个浮点数f。如果f

步骤7随机生成[0,1]范围内的一个浮点数f。当f

步骤8i=i+1；如果i≤Mc，跳到步骤7，否则rc=rc+1，如果rc≤Rc，跳到步骤5，否则获得所有车辆的调度方案，即派往每一个受灾区域的车辆数量和到达所有受灾区域的时间。

4 算法仿真分析

4.1 仿真参数

实验主要根据杭州市主城区的消防中心实际位置数据，采用Python语言和其编译软件Pycharm2019进行仿真实验，其中道路中各路段的距离长度、车辆行驶速度、深夜通行时间均可通过百度地图开源API获得。在杭州市区范围内选择了10个消防中心作为实验出发起点。受灾场景1为2017年杭州十五家园小区火灾，当时出动艮山、湖滨、景芳消防中队共9辆消防车辆。受灾场景2为2020年4月杭州萧山区湖头陈花园发生火灾，当时由湘湖、萧山、滨江共3个消防站共出动7辆消防车辆。受灾场景3为2016年杭州艮山西路汽配仓库的大火灾，共调配52辆消防车辆进行救援。受灾场景4为考虑同时发生上述3种实际场景的情况。后续受灾场景为在杭州市范围内随机产生多个受灾坐标点进行仿真实验，其中受灾场景8-10为受灾区域的消防车辆需求数较多的实验场景。在实验仿真中，各个消防中心的车辆数由浙江消防网所公布的数据模拟生成。同时设置以下参数：车辆调度模型的种群大小为100，模型的终止迭代次数均为100，车辆调度预测时间因子a为0.3，偏离度因子β为0.7，车辆调度预测时间阈值Tyu为69，偏离度阈值ωyu为42，规定消防车辆最大救援时间μ为8。可通过改变参数的大小来影响模型在求解过程中对于救援时间和救援公平的倾向性。

其次，实验生成如表1所示的10种受灾场景，其受灾区域个数不同，受灾车辆需求数不同，受灾区域位置在杭州百度地图中随机生成。例受灾场景编号4中受灾车辆需求数为[9,7,52]，其数组长度3代表受灾区域总个数，数组中其值对应各个受灾区域的车辆需求数，如第一个受灾区域需要9辆消防车辆，第二个受灾区需要7辆消防车辆，第二个受灾区需要52辆消防车辆。

表1 受灾区需求表

4.2 算法参数和效果分析

为验证RSA在火灾仿真场景下的性能，令RSA-1代表Pc=0.95，Pm=0.08的RSA，RSA-2代表Pc=0.85，Pm=0.05的RSA，RSA-3代表Pc=0.75，Pm=0.03的RSA，RSA- 4代表Pc=0.99，Pm=0.1的RSA，其中Pc表示交叉概率，Pm表示变异概率。现选择4.1节中其他仿真参数和表1内的10类受灾场景，并20次循环计算每一个RSA的收敛代数和最优适应度值，取其平均值作为仿真结果值。如表2和图6所示，4种不同参数情况下的RSA均能求解得到一致的最优适应度值，但其收敛能力存在一定差异，相较于其他3类RSA，RSA-1算法最早完成收敛的迭代次数最小，其收敛速率最快。因此RSA选择Pc=0.95和Pm=0.08。

表2 不同参数下RSA适应度比较

续表2

图6 不同参数下RSA的最早完成收敛迭代次数对比图

现选择4.1节中仿真参数和表1内的编号1受灾场景，获得RSA的收敛图。如图7所示，RSA在第35次迭代收敛到最优适应度值，是收敛的。

图7 受灾场景1的RSA收敛图

在云端软件上采用Java语言和其开发软件Myeclipse软件，调用RSA，实现百度地图调度、消防车辆路径显示等功能，从而实现消防车辆调度平台。其消防车辆实际移动路径如图8所示。当发生受灾场景1时，当时由杭州艮山、湖滨、景芳共派遣9辆消防车辆进行救援，但等到第一辆车到达现场时，已经过了15 min，不符合规定消防车辆到达受灾区域的救援时间要求。而基于RSA进行调度，由艮山、湖滨、景芳消防中队最早抵达十五家园社区的车辆调度预测时间分别只需要7 min、17 min、12 min，较好实现消防车辆的救援调度。

图8 车辆调度地图

4.3 算法性能比较

通过节4.2可知，参数为Pc=0.95，Pm=0.08的情况下，可较快地寻找到算法最优解。经过多次实验发现惯性因子为0.8，学习因子为1.47的粒子群算法计算的解较优，发现初始温度Tinit=200，降温系数k=0.97，重复降温次数150的模拟退火算法计算的解较优。因此选择该参数和4.1节中其他仿真参数，循环20次计算10个不同受灾场景下较优参数下的RSA、SA、PSO和就近优先的救援算法(Traditional nearest priority rescue，TNPR)的车辆平均调度预测时间和救援时间偏离度，取其平均值作为仿真结果值。其中，TNPR算法是传统救援算法，即根据救援点位置，选择调度所需距离最小的消防中心进行救援调度，直至满足所有救援点的需求。

首先，比较RSA、SA、PSO和TNPR算法的车辆平均调度预测时间。如图9所示，RSA的车辆平均调度预测时间较小，且都小于SA、PSO和TNPR算法的车辆平均调度预测时间。这是因为染色体编码设计中使用了三维矩阵，而PSO在处理多维、多峰值的调度分配问题时容易出现早熟问题，从而导致寻优效果较差，其适应度值较低。SA在重复迭代计算过程中容易出现较差解，从而影响后续的求解，导致无法寻找到全局最优解。TNPR算法采用比较简单的就近原则，即贪心策略，其在较为简单的受灾场景1和2中，其最优解质量与其他算法相差不大，但在受灾场景3-10中，需要车辆数量或救援点数量较多，其解质量变差。RSA在染色体的编码设计和初始化阶段对随机解集进行条件约束，并在变异操作中混合两种变异方法，使得算法具有更好和更稳定的寻优能力，因此其最优适应度值最优。

图9 车辆平均调度预测时间对比图

比较RSA、SA、PSO和TNPR算法的救援时间偏离度。如图9和表3所示，受灾场景1-7对消防车辆的需求较少，其周围消防中心均能满足实际受灾需求，RSA其平均调度时间均小于20 min，且RSA的救援时间偏离度略小于SA、PSO和TNPR算法的救援时间偏离度。受灾场景8-10对消防车辆的需求较多，消防车辆较难在规定救援时间内到达所有受灾点，导致偏离度大大增加。但是由于RSA考虑消防调度公平性，将车辆调度预测时间距离规定救援时间的偏离度加入到适应度函数，并能寻找到权衡预测时间和偏离度的最优解，因此RSA的救援时间偏离度小于SA、PSO和TNPR算法的救援时间偏离度。

表3 救援时间偏离度对比表

由于TRNN算法只是简单选择调度所需距离最小的消防中心，不含有迭代优化的思想策略，仅需对消防中心和道路距离组合进行降序排序，其运行所需时间较小，与SA、PSO和RSA没有可比性。因此比较SA、PSO和RSA的运行时间。如图10所示，SA受降温系数影响较大，容易陷入局部最优解，短时间内无法寻找到全局最优解，导致其运行时间最长。PSO在解空间随机搜索过程中产生较多的不满足预设约束的无效解，而通过重新初始化的手段往往无法保证新解的质量，从而导致其运算时间较大。RSA在模型中会产生少量异常解，且通过染色体修正保证解的质量不会大幅度变差，从而在保证寻找到全局最优解的情况下提高了收敛速度，降低了算法迭代次数，因此RSA的运行时间最短。

图10 算法运行时间比较图

5 结 语

本文提出一种权衡预测时间和偏离度的消防车辆救援调度算法(RSA)。首先，获得各个消防中心及受灾区位置，需要的车辆数等主要信息。其次，根据百度地图开源平台获得出发点距离受灾点的各路段通行时间，通过对比过往通行时间重新评估各路段通行时间，并建立消防救援调度优化模型。随后采用修正的遗传算法求解，即对染色体进行三维实数编码并使其满足预先设定的约束条件，通过精英选择、保存历史最优染色体、映射交叉、非均匀变异、移位变异等方法获得最优救援调度方案。最后基于仿真实验参数，比较了在不同火灾场景下的RSA、PSO、SA和TNPR算法性能。

总之，RSA考虑了多目标情景下的消防救援调度，选择最优参数下的修正遗传算法，相比于粒子群算法和模拟退火算法，加快了其收敛速度，并保证其救援方案为最优解。而在后续的研究中将考虑一种计算复杂度更低的启发式算法，求解救援调度问题。