考虑公平性的面向多灾点需求应急资源调度

杜雪灵，孟学雷，杨 贝，汤 霖

(兰州交通大学 交通运输学院，兰州 730070)(*通信作者电子邮箱mxl@mail.lzjtu.cn)

0 引言

突发事件发生后，人们的正常生活受到影响，生存所必需的资源遭到破坏，需要制定相应的应急资源调度方案，在第一时间完成对事故发生点的资源供给，这种在应急条件下研究的资源调度问题被称为应急资源调度(Emergence Resource Scheduling, ERS)。在铁路突发事件发生后的应急指挥工作中，应急资源调度处于核心关键位置，制定正确合理的应急资源调度方案是重要的应急指挥工作之一。

关于单目标优化的应急资源调度问题，文献[1]基于时空网络的概念，以最小化运输成本为优化目标，解决了大规模、多商品、有时间窗的多模态网络流问题，提出了两种启发式算法，而实际救援过程中，商品数量和救援车数量是不确定的。文献[2]提出强震后初期搜救的主要目标是尽量减少死亡人数，并引入了动态优化模型，该模型可计算与响应相关的不同任务的资源性能和效率，求解算法为模拟退火算法。文献[3]考虑到救护车可能处于忙期的随机特性，建立了超立方体覆盖模型，该模型的目标是确定每一个时间群集的最小救护车数量和位置，在需求模式发生重大变化的同时满足覆盖要求，求解算法为禁忌搜索算法。文献[4]假设物资拥有量小于车容量，建立了动态车辆调度模型，目的是避免延误，提高设备利用率；但该模型对于现实的突发性灾害具有一定的局限性，没有将旅行时间和地点群集相结合进行优化。文献[5]以机会成本最小化为优化目标，建立了紧急救援资源调度模型，采用模拟退火算法求解模型，但该模型忽略了救援车辆需求的不确定性。文献[6]结合博弈论理论，建立面向多灾点需求的博弈调度模型，采用改进的蚁群算法求解，实现调度“虚拟成本”的最小化，“虚拟成本”的影响因素有灾情的严重程度、平均速度、响应时间和距离。文献[7]建立了多资源时间-成本调度模型，以满足资源需求量为前提，以时间为约束，使总调度成本最低，采用改进的进化规划算法验证模型；但该模型较简单，较难满足大规模突发事件的应急管理需求。文献[8]研究了高速公路应急救援的动态模式，目的是使总成本最小化，采用Dijkstra算法验证模型，但文中的救援时效矩阵是在假设速度一定，并将最短距离矩阵作为阻抗矩阵的情况下得到的，而实际救援过程中车辆速度会随路况发生变化。

关于多目标优化的应急资源调度问题，文献[9]设计了多时段动态应急资源调度问题的多目标优化模型，利用基于分解的多目标进化算法求解模型；但该研究假设车辆的数量和运输能力是不受限制的，对实际路网问题考虑较少。文献[10]建立了多约束整数线性规划模型，以并行方式分配多个应急资源，使应急响应时间最短、应急资源成本最小；但该研究提出的启发式算法忽略了响应时间的约束。文献[11]以未满足率最小化和未疏散人员数最小化为优化目标，构建了多目标鲁棒优化模型，采用结构化鲁棒模型的求解方法求解模型；而旅行时间、能力、需求等网络数据是不确定的，文中没有对网络结构进行优化。文献[12]研究了最短路线、最短时间及服务水平，以时间为约束建立模型，用改进的遗传算法、改进的蚁群算法分别求解；但两种算法在改进的过程中没有充分考虑到道路及交通情况对算法结果的影响。文献[13]考虑了评估灾害点的灾害情况和资源需求产生的误差，将灾害地区信息运用改进后的专家打分法量化成灾情因子，模型的目标是延误时间最小化、成本最小化，求解算法为逐步法，但专家打分法使得灾情因子具有一定的主观性。文献[14]研究了区域路网交通应急资源调度的优化，以总响应延迟时间和总预计响应时间加权之和最小为优化目标，在资源不确定的条件下建立模型，求解算法为遗传算法；但该研究以响应时间最短为主要目标，对资源调度成本考虑较少。文献[15]在确保满足救援能力需求的前提下，对设备调度问题进行了研究，目标是救援结束时间最小、调度费用最小，并设计了两阶段启发式算法。

上述文献的研究目标大多为成本最小[1,5-8,10,12-13,15]、死亡人数最少[2]、延误最小[4]、时间最短[10,12-13,15]、未满足率最小[11]等，对本文有着重要启发，但突发事件发生之初，供应点的资源量往往不能同时满足多个受灾点的需求，此时会造成距离供应点较远的受灾点获得的资源量较少甚至没有的情况，但很少有文献考虑到多个受灾点的公平性。本文结合“软时间窗”的概念，将救援公平性最大和调度总成本最小作为优化目标，构建了面向多灾点需求的多目标应急资源调度模型。

1 多目标应急资源调度模型

在实际生活中，某些铁路突发事件的波及范围较大且具有传播效应，在突发事件的影响下可能会产生多个救援需求点，本文从现实角度出发解决多资源供应点与多救援需求点之间的应急资源调度问题，设计建立多需求点与多供应点间的数学模型。供应点与需求点间的调度关系如图1。

图1 物资供应点与救援需求点的调度关系示意图

1.1 模型假设

为了增加本文所建立模型的可操作性，需要作如下假设：1)救援需求点和资源供应点的位置关系已知；2)应急所需救援物资数量可根据突发事件影响程度提前预估；3)应急所需救援物资量不随时间变化；4)假设救援车辆的目标行驶速度为v=100 km/h；5)为加大对时间延误的惩罚力度，本文假设迟到惩罚系数p=1 000。

1.2 模型基础

设：S1,S2,…,Si为供应点(i∈[1,m])，D1,D2,…,Dj为需求点(j∈[1,n])，模型参数定义如下：

si表示供应点Si(i=1,2,…,m)的物资储备量。

dj表示需求点Dj(j=1,2,…,n)对资源的需求量。

xij表示0- 1状态变量，供应点Si向需求点Dj提供救援资源时xij=1；否则，xij=0。

nij表示供应点Si为需求点Dj所提供的资源量。

ηj表示需求点Dj的资源满足程度。

lij表示供应点Si到需求点Dj的距离。

αij表示供应点Si到需求点Dj各路段的道路畅通程度(因道路拥挤等原因无法达到目标行驶速度)。

v表示车辆在路段上的目标行驶速度。

tj表示需求点Dj需要获得资源的目标时间。

cij表示供应点Si为需求点Dj所提供资源的单位成本。

p表示迟到惩罚系数。

1.3 模型建立

时间窗总体上可分为“硬时间窗”和“软时间窗”。“硬时间窗”是指必须在规定的时间段内对客户进行服务，超出规定时间后客户不再接受服务；“软时间窗”是指超过规定时间段后依然可以对客户进行服务，但超出规定时间的服务需因时间延误而接受相应的惩罚，迟到成本为迟到时间与迟到惩罚系数之积[12]。

铁路突发事件发生之初，资源在救灾环境中受到限制，应急资源的数量有可能不能同时满足所有需求点的需求。若只考虑救援效益或救援时间最优，则有可能忽略某些距离较远的受灾点，因此考虑每个需求点的公平性更为重要，本文以所有需求点的资源满足程度的方差来衡量救援的公平性。

综合考虑前文对问题的分析，本文设计建立以救援公平性最大和调度总成本最小为目标的应急资源调度模型：

(1)

[lij/(αij·v)-tj]

(2)

(3)

(4)

(5)

(6)

(7)

xij=0或1;i=1,2,…,m,j=1,2,…,n

(8)

nij≥0

(9)

该模型是一个多目标模型，式(1)、(2)为目标函数：式(1)表示所有需求点的资源满足程度的方差最小；式(2)表示调度总成本最低。式(3)～(9)为约束条件：式(3)表示需求点Dj获得的资源量不超过其实际需求量；式(4)表示供应点Si提供的总资源量不超过其自身存储量；式(5)表示每个需求点至少有一个供应点为其提供救援；式(6)为需求点Dj的资源满足程度的计算公式；式(7)为所有需求点的平均资源满足程度的计算公式；式(8)为“0- 1”整数约束；式(9)为非负约束。

2 算法设计

对于多目标问题的求解，多数学者青睐于启发式算法，主要包括：禁忌搜索算法[3]、进化规划算法[7]、模拟退火算法[2,5]、遗传算法[12,14]、蚁群算法[6,12]等；此外，还有Dijkstra算法[8]、并行分配算法[10]、逐步法[13]等。

本文构建的基于“软时间窗”的多目标应急资源调度模型是典型的多目标规划模型，需综合考虑两个目标函数。本文两个目标函数的量纲不同，方差的取值较小，很难将其统一量纲转化为单目标求解，而并列选择遗传算法可以对两个目标函数同时进行运算操作，故本文采用并列选择遗传算法求解。并列选择的基本思想是：根据目标函数的个数，将种群均等地划分为与目标函数个数相等的子种群，为划分后的各个子种群各自分配一个目标函数，并对其进行独立的选择运算，将各个子种群中适应度高的个体组成完整的种群，对这个完整的种群进行交叉、变异，生成下一代种群，如此循环可得到Pareto最优解。

两个目标函数随迭代次数变化的曲线如图2。由图2可知，两个目标函数在迭代计算过程中都是逐渐趋于最优的，没有存在相背离的情况。

具体求解过程如下。

步骤1 生成初始染色体。对模型中的0- 1决策变量xij采用长度为1位的二进制编码，对非决策变量nij采用实数编码，根据编码方式，在集合S、D中随机选取i、j，由随机函数生成变量xij、nij的值，由此生成初始染色体Pi=[xij|nij],i=1,2,…,N，N为种群规模。

图2 目标函数随迭代次数变化示意图

步骤3 通过选择得到每个子种群中适应度高的个体，将这些个体组成完整的种群，对这个完整的种群进行交叉、变异，生成下一代种群，并去除种群中不满足约束条件的个体，得到新的种群。具体步骤如下。

1)选择。本文算法中染色体选择采用适应度值比例方法(也可称为轮盘赌方法)，其选择概率为：

(10)

其中fi为群体中第i个个体的适应度函数值。

r∈[0,1]是一个随机数，若r∈(0,pi]，则选择个体i。

2)交叉。在本算例中，对于采用二进制编码的0- 1决策变量xij，交叉操作采用单点交叉，即在二进制编码中，随机选择一个点，以这个点为界限，相互交换变量。

对于采用实数编码的非决策变量nij，其需要交叉的染色体数由交叉概率决定，若交叉概率为pc，则每次需对pc·N的染色体进行交叉。r∈[0,1]是一个随机数，若r

(11)

其中：Pm为第m个染色体，Pn为第n个染色体，k为交叉的位置，a为区间[0,1]内的随机数。

3)变异。需变异的染色体数由变异概率决定，若变异概率为pm，则每次需对pm·N的染色体进行变异。r∈[0,1]是一个随机数，若r

(12)

其中：Pmax是基因Pik的上界；Pmin是基因Pik的下界；f(g)=r′(1-g/Gmax)2，r′是一个随机数，g是当前迭代次数，Gmax是最大进化次数。

4)根据模型的约束条件，判断种群中个体的可行性，删除种群中不满足约束条件的个体，通过随机生成的方法，补充染色体，使其总数保持为N，形成新的种群。

步骤4 终止。累计循环计算的次数，如果次数小于预先设定的迭代次数，转步骤2；否则，终止计算，转步骤5。

3 算例分析

结合本文设计的模型，通过以下算例对其进行验证。

算例1 设某地区因地震灾害，出现5个受灾点需要救援，现有8个资源供应点，需求点Dj(j=1,2,3,4,5)的物资需求量分别为D1=3 000，D2=1 800，D3=2 200，D4=2 000，D5=2 500，每个需求点需要获得物资的目标时间tj=1 h (j=1,2,3,4,5)，供应点Si(i=1,2,3,4,5,6,7,8)现有物资量分别为S1=800，S2=1 500，S3=1 300，S4=800，S5=1 600，S6=1 400，S7=1 500，S8=1 100，供应点Si到需求点Dj的距离如表1，供应点Si为需求点Dj提供资源的单位成本如表2，供应点Si与需求点Dj之间各路段的道路畅通程度如表3。

表1 算例1中供应点到需求点的距离lij km

表2 算例1中供应点为需求点提供资源的单位成本cij 元

根据上述算法，初始可行解的染色体为P=[0 1 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 1 0 0 1 1 0 0 0 0 1 0 0 1 0 0 1 | 0 800 0 0 0 1 500 0 0 0 0 0 0 1 300 0 0 0 0 0 0 800 0 0 0 0 1 600 0 0 900 500 0 0 0 0 1 500 0 0 1 000 0 0 100]，此时，目标函数Z1=0.05,目标函数Z2=9 534 356(元)。

一般遗传算法种群大小的取值范围是20～100，种群取值较小时，会降低种群的多样性，可能会引起早熟现象，种群较大时，会降低运行效率，本文设置种群大小N=100；交叉概率一般应取较大值，但若取值较大的话，会破坏种群中的优良模式，若取值较小，产生新个体的速度较慢，一般取值范围是0.4～0.99，本文取交叉概率pc=0.8；变异概率的一般取值范围是0.000 1～0.1，取值较大虽能产生较多的新个体，但也可能破坏掉很多较好的模式，取值太小的话，变异操作产生新个体的能力和抑制早熟现象的能力就较差[16]，本文变异概率pm=0.05，迭代次数为1 000。利用Matlab软件工具编程求解算例，其结果如表4～5所示，目标函数Z1=0.000 133 7,目标函数Z2=10 370 889(元)。

表3 算例1中供应点到需求点各路段的道路畅通程度αij

表4 算例1中由并列选择遗传算法得到的供应点与需求点的0- 1状态变量值xij

表5 算例1中由并列选择遗传算法得到的供应点为需求点提供的资源量nij

此外，采用标准粒子群优化(Particle Swarm Optimization, PSO)算法对该算例在同一台计算机上进行计算。其结果如表6～7所示，目标函数Z1=0.002 186 3,目标函数Z2=10 918 259(元)。与PSO相比，并列选择遗传算法的方差减小了93.88%，成本减少了5%。

算例中：需求点D1由于距离供应点较远，突发事件发生之初，供应点现有的资源量无法同时满足所有需求点，初始可行解中为需求点D1提供的资源量较少，这有悖于科学规划、公平合理的宗旨，不利于社会和谐。出于现实意义的考虑，为距离较远的需求点提供救援虽然会增加成本但也是必需的。运用本文设计的模型生成的资源调度方案(如表4～5所示)可使所有需求点的资源满足程度方差趋近于0，即公平性趋近最大化；与此同时也可使成本的增加量控制在可接受范围内，从而使得调度总成本最小。

表6 算例1中由PSO算法得到的供应点与需求点的0- 1状态变量值xij

表7 算例1中由PSO算法得到的供应点为需求点提供的资源量nij

算例2 再考虑8个受灾需求点，5个资源供应点的情形，需求点Dj(j=1,2,3,4,5,6,7,8)的物资需求量分别为D1=2 000，D2=1 500，D3=1 800，D4=1 000，D5=1 200，D6=1 700，D7=2 200，D8=1 600，每个需求点需要获得物资的目标时间tj=1h(j=1,2,3,4,5,6,7,8)，供应点Si(i=1,2,3,4,5)现有物资量分别为S1=1 500，S2=2 600，S3=1 800，S4=2 800，S5=2 500，供应点Si到需求点Dj的距离如表8，供应点Si为需求点Dj提供资源的单位成本如表9，供应点Si与需求点Dj之间各路段的道路畅通程度如表10。

表8 算例2中供应点到需求点的距离lij km

采用本文设置的并列选择遗传算法求解(算法参数设置与算例1相同)，其结果如表11～12所示，目标函数Z1=0.000 148 7,目标函数Z2=9 258 380(元)。

此外，采用文献[15]中设计的两阶段启发式算法对该算例进行计算。其结果如表13～14所示，目标函数Z1=0.001 47,目标函数Z2=9 272 364(元)。与两阶段启发式算法相比，并列选择遗传算法的方差减小了89.88%，成本减少了0.15%。

表9 算例2中供应点为需求点提供资源的单位成本cij 元

表10 算例2中供应点到需求点各路段的道路畅通程度αij

表11 算例2中由并列选择遗传算法得到的供应点与需求点的0- 1状态变量值xij

表12 算例2中由并列选择遗传算法得到的供应点为需求点提供的资源量nij

表13 算例2中由两阶段启发式算法得到的供应点与需求点的0- 1状态变量值xij

算例1和算例2的计算结果均可表明：采用本文设置的并列选择遗传算法，可使得所有需求点的资源满足程度的方差更小(即公平性更大)、调度总成本更低，计算结果更优。

表14 算例2中由两阶段启发式算法得到的供应点为需求点提供的资源量nij

4 结语

本文从现实角度出发解决多资源供应点与多救援需求点之间的铁路应急资源调度问题，结合“软时间窗”的概念，将公平性最大和调度总成本最小作为优化目标，以所有需求点的资源满足程度的方差来衡量救援的公平性，建立多需求点与多供应点间的数学模型，运用并列选择遗传算法求解，并设计了算例。该算例结果表明：1)该模型有很强的实用性，在铁路突发事件发生之初、总资源量不足时，有效避免了距离较远的受灾点获得的资源量较少甚至没有的情况。2)本文中模型所选用的并列选择遗传算法计算效率高，对该问题的求解有很强的适应性。3)本文所设计的模型与方法可为铁路应急资源调度提供有价值的决策支持，对于铁路应急指挥工作有很强的借鉴意义。此外，在将来研究中将增加对于铁路突发事件发生之初的实际资源需求量快速测算的研究，使模型更加完善。