考虑时效与公平性的震后应急物资动态配送优化研究

曲冲冲，王　晶，黄　钧，何明珂

(1.北京工商大学商学院，北京　100048;2.中国科学院大学工程科学学院　100049;3.北京物资学院物流学院　101149)

1　概述

大规模地震严重威胁人民生命和财产安全。加强震后应急物资保障是应对突发自然灾害条件下提高救援效率的关键。震后物资保障需要将大量的应急物资运输到受灾区域，应急物资运输的响应速度和分配策略是救援工作开展的重点任务。同时，根据受灾区域的破坏程度，合理选择运输工具和稳定的配送中心是保证救援工作有序开展的前提。

震后应急配送中心选址和物资运输分配问题是国内外学者广泛研究的课题。震后应急救援物流不同于一般的社会性物流，其活动开展具有不确定性、突发性、时间约束较强、经济性较弱等特点。宫华等[1]从外围物资集散的中心选址、救灾物品的分配满意度等方面进行了研究。沈晓冰等[2]在分析震后应急物资的配送特点和应急配送中心的选址问题的基础上，建立了一个综合考虑应急物流运作效率和运输路径选择的多目标优化模型，对震后救援效率和路径选择进行研究。刘长时等[3-4]在对震后应急物资运输道路规划问题进行研究时，通过建立多种运输方式、多运输周期的LRP模型，对应急物资开展运输的时间进度进行讨论；在对震后灾民的非理性攀比因素进行研究时，通过构建一个静态的运输-分配优化模型，对静态条件下的震后救援工作的开展进行了讨论。王海军等[5]通过建立一个双目标的OLRP模型，对配送中心的选址和应急物资的运输安排进行了讨论。 Sheu[6]对台湾震后救援工作开展的研究中，通过递推机制对配送中心和受灾地区进行分组分析。Najafi等[7]在对多目标、多线程、多种物资开展震后运输和救助伤员的研究中，通过设计时间优化算法对救援工作有序开展提供建议。Yi Wei等[8]对研究震后响应活动中的协调后勤支援及疏散作业的综合作业定位分配模式进行了研究。Haghi等[9]通过对震后受伤人员的救治路径和健康中心布局规划研究，提升了救助覆盖的全面性。Arora等[10]在对公共卫生事件下开展物资、药品分配的研究的基础上，认为政策因素和距离因素对物资分配的公平性有一定的影响。Altay[11]认为提升救灾效率和公平分配物资对伤员救治和灾后区域恢复有着积极的促进作用。Liu Cong等[12]认为将救援工作从时间上划分成若干个时段可以提升震后救援的效率。

对应急物资配送中心选址、运输路径选择和物资分配公平性开展研究时，众多文献是通过建立数学模型进行分析的。李孟良等[13]在研究震后多式联运问题时，对未满足灾区应急物品需求的最小惩罚系数进行了讨论，提出了基于鲁棒优化的联运调配模型。郑斌等[14]针对震后物资供不应求的状况，通过设计一种混合遗传算法结合汶川地震案例对物资的运输时间规划、物资分配方式进行了分析。Abounacer等[15]设计了一种启发式算法—ε-约束方法，旨在确定实际所需的分配中心数量、位置和救援作业时间规划。张伟等[16]在讨论考虑运输时间、运输距离和道路复杂程度对路径选择影响的问题时设计了一种多目标非线性整数规划模型。Mahmoudabad等[17]提出了一种基于动态风险和动态损伤烈度网络的混沌理论解决突发情况下信息中断时救援路径选择和物资分配的问题。王旭坪等[18]在借鉴前景理论的基础上，通过构建风险感知函数，从道路运力、物资流动、决策过程等方面建立了物资调配的系统动力学模型。Haghani和Oh[19]通过交互式启发算法解决救灾物资分配和带时间窗问题的多模态网络流问题。Najafi等[6]用成本分析的方法提出了多目标、多模式、多商品、多周期的随机模型为震后物资分配提供指导。

众多文献设计的目标函数通常考虑救援成本和时间效率，对受灾点物资需求满足程度与分配公平性考虑较少。本文在解决多时段、多种运输方式共同参与的应急物资保障问题的过程中兼顾时效性与公平性，在综合物资运输与配送的两阶段、多时段的动态救援特点和多种运输方式共同参与的基础上，建立了保证救灾物资运输时效性和实现灾区物资分配公平的最优的应急物资配送中心选址与运输配送路径优化模型。针对此模型设计了一种带精英策略的非支配排序的遗传算法，结合九寨沟地区震后灾难情景对模型进行实证研究，通过结合Pareto前沿面分析，验证了模型和算法的有效性，为震后应急物资保障提供了理论指导与决策支持。

2　模型建立

2.1　问题描述

震后应急物资保障工作是依托于物资集散地、应急物资配送中心和受灾点之间的相互联系展开的。灾区所需的大批量、多批次、多品种的物资需要从灾区外围的救灾物资集散地通过公路和直升飞机向灾区周围的临时救灾物资存放地应急物资配送中心进行分配中转，这是应急物资运输的第一阶段；再由临时配送中心通过公路运输向灾区进行分配，这是应急物资运输的第二阶段。在两个阶段中根据不同时段的道路状况、运输装备性能开展的运输路线调整和应急物资配送中心的备选工作是该阶段的重点。两阶段划分示意图如图1所示：

图1　灾后应急物资运输系统示意图

震后救灾物资主要的供应模式是区域储备仓库和外围物资集散地整合物资-区域应急物资配送中心分配中转-受灾点，受到运输车数量和车辆的负荷装载能力、路况、环境、救援人员数量变化等一系列客观因素的制约以及随着震后救援工作不断深入，对灾区实际状况逐渐了解，需要对较长时间的救援工作进行时间细分，通过多时段的动态救援满足灾区的物资供应。

通过将应急物资保障分为若干时段，可以及时的调整救援工作，从而保证救援工作的高效率运作。同时要兼顾物资运输的时效性和物资分配的的公平性。

2.2　模型构建

2.2.1模型假设

针对特定条件下救灾物资的配送特征，作出如下假设：

(1)备选配送中心都是不易受到余震以及其他次生灾害影响且距离受灾区域距离较短的的交通枢纽区域点，可以长时间进行救灾作业。

(2)应急物资从区域储备仓库和外围集散地还未运输到区域应急配送中心时，受灾区域储备的物资可以满足自身的最低需求；区域应急配送中心向受灾点运输的应急物资数量可以满足所有受灾点的最低需求。

2.2.2符号说明

(1)参数

W：救援物资种类的集合(w∈W)

I：应急物资集散点的集合(i∈I)

J：应急物资配送中心的集合(j∈J)

K：受灾点的集合(k∈K)

Ξ：需要决策的时段的集合(ξ∈Ξ)

M=

T(ξ)：决策时段ξ重新决策的时刻

qwi(ξ)：ξ时段下集散点i供给物资w在的量

dwk(ξ)：受灾区域k在ξ时段对物资w的实际需求量

Pijm(ξ)：在ξ时段下从集散点i到配送中心j通过运输方式m单次最大运输量

Tijm(ξ)：在ξ时段道路未修复情况下，从集散点i到配送中心j通过运输方式m所需要的时间

Pjk(ξ)：ξ时段下从配送中心j到受灾点k的单次最大运输量

Tjk(ξ)：ξ时段道路未修复情况下，从配送中心j到受灾点k所需要的时间

ITijm：从集散点i到配送中心j通过运输方式m发车的时间间隔

θw：受灾点人均需求救灾物资w的最少量

LTkw(ξ)：ξ时段下受灾点k对救济物资w供应满意度最大时，所能够接受的最长等待时间

STkw(ξ)：ξ时段下受灾点k对救济物资w供应不满意度最大时，所能接受的最短等待时间

N(ξ)：ξ时段下允许配送中心运营的最多数量

PDkw(ξ)：ξ时段下进行下一时段(ξ+1)决策时，受灾点k接收救灾物资w必须等待的时间

Tkw(ξ)：ξ时段下受灾点k完全接受救灾物资w的时刻

QKw(ξ)：ξ时段下计划分给受灾区域K的救灾物资w的总量

Θ：可用车辆总数

Ω：一个大数

(2)决策变量

Qijwm(ξ)：ξ时段下计划采用运输方式m从物资集散点i运输到配送中心j物资w的数量

ϑj(ξ)：ξ时段下计划分配给配送中心j进行运输物资的车辆数目

Qjkw(ξ)：ξ时段下计划从配送中心j运输到受灾点k的救灾物资w的量

2.2.3数学模型构建

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

Qijwm(ξ)≥0,i∈I,j∈J,w∈W,m∈M

(13)

uijmw(ξ)=(0,1),i∈I,j∈J,w∈W,m∈M

(14)

(15)

(16)

(17)

Tjk(ξ),k∈K,w∈W,(j,k)∈Ak(ξ)

(18)

(19)

Qjkw(ξ)≤Ω·zjkw(ξ),j∈J,k∈K,w∈W

(20)

(21)

(22)

zjkw(ξ)=(0,1)

(23)

目标函数(1)表示在ξ时段下，各种应急物资配送到灾区的加权时刻最短，进而保证应急物资的时效性。目标函数(2)表示最大化所有受灾点各种物资满意度的最小值，保证救援物资分配的公平性。约束(3)表示在ξ时段下计划运输物资到配送中心的总量等于该集散点物资总供应量；约束(4)表示受灾点物资最小满足率；约束(5)表示配送中心的最大承载量；约束(6)表示在不同运输方式下，将救灾物资从集散点运输到配送中心所需时间表达式；约束(7)表示第一阶段物资运输时间函数表达式；约束(8)表示受灾点完全接收救灾物资时刻的函数表达式；约束(9)表示ξ时段下只有选择某个配送中心时，才会把物资运输到该配送中心。约束(10)表示救灾物资只能向运转的配送中心运输救灾物资；约束(11)表示配送中心开始运转后，任何阶段都不会关闭；约束(12)表示可以运转的配送中心小于等于初始设定的最大数目限制；约束(13)表示非负约束；约束(14)、(15)表示0-1约束。约束(16)表示配送中心接受物资的量与输出给灾区的量均等；约束(17)表示各个受灾点的物资接收量总和等于配送中心运往灾区的量；约束(18)表示通过公路运输从配送中心到受灾点的时间函数表达式；约束(19)表示由于物资的供不应求，运输到受灾地区的物资总量小于灾区实际需求量；约束(20)表示只有选择为某个受灾点服务时，才会输送物资到该点；约束(21)表示受灾点接受的救灾物资只能来自于已经开启运转的配送中心。约束(22)表示受灾点接受的物资只能来自于一个配送中心。约束(23)表示0-1约束。震后应急响应时间满意度通过以下线性时间满意度函数表达式描述：

在第一阶段中，公路运输与直升飞机运输共同参与到应急物资的输送工作，救援车辆从集散点到配送中心的出发时刻根据物资运输方式的不同可以分为以下两种情况：

i.当运输方式为公路运输且当前时段没有救援车辆向灾害地点运输救灾物资。

ii.运输方式为公路运输，且在下一时段开始

决策时，当前时段的运输工作已经完成。

i.当运输方式为公路运输时，且下一时段救援工作开始时，当前时段的车辆仍在途中。

ii.运输方式为直升飞机时，由于受到航线的限制，下一时段的车辆发出时刻是当前时段车辆返回的最早时刻。

(24)

(25)

同时由于灾后救援物资需求具有持需时间长、多时段等特点，本文将救援过程细化成若干时段，目标函数考虑各个时段配送方案的设计与评价，保证在任意时段下救援物资配送的时效性与公平性。模型可转化为：

s.t.(1)-(25)

3　算法设计

为了实现灾后应急物资运输与分配的时效性与公平性，构建了包括多时段动态的配送中心选址和应急物资配送路径优化的多目标规划模型，并设计了一种基于Pareto最优解基础上改进的带精英策略非支配排序的多目标遗传算法，将精英策略引入到模型中，提升了算法了运算效率和准确率。通过基因交叉、多点变异将父代种群与子代种群组合，保证优良的种群个体在进化过程中不会被丢弃，进一步提高优化结果的精度。通过对所有个体的分层存放，迅速提高种群水平。

3.1　初始化参数

设该遗传算法的种群规模popsize，最大迭代次数为max gen，交叉概率Pc，变异概率Pm。

3.2　染色体编码

通过矩阵编码策略描述每个时段配送中心到受灾点的指派关系zjkw(ξ)和分配量Qjkw(ξ)。每个受灾点在每个时段内的需求满足情况是通过列向量基因位表现在染色体上。在每个列向量中第一个基因位是通过在1到|J|的整数内随机产生，表示配送中心到受灾点之间的指派关系。第二基因位到第(w+1)位是在[1，dwk(ξ)]的整数内随机产生，表示在每个时段下配送中心向受灾点运送的不同物资的具体的数量。因此，染色体编码的总长度为(1+w)×(1+ξ)。

假设受灾点的数量是16个，即K={k|1,2,3,4,5,6,7,8,…14,15,16}，受灾点对应急物资的需求种类为2种：食品和生活用品。救援分为3个时段，即Ξ={ξ|1,2,3}。配送中心候选地点有8个，即|J|=8,选从中选出4个点作为开放的配送中心。因此，可以得出以下染色体编码，见图3。

图3　染色体矩阵编码示意图

图3矩阵含义：选择2，5，6，8物资配送中心进行运营为16个受灾地点运输生活用品和食品。当ξ=1时，物资配送中心5为灾区1和灾区15服务，向灾区1运送24单位和40单位的应急物资。同时向灾区15运输27单位和33单位的应急物资。

配送中心所属车辆的数量是其向受灾点运输物资的数量来决定的，具体的运算公式为：

3.3　种群初始化及适应度函数计算

为了使初始种群中染色体数量尽可能丰富，在满足约束条件的基础上随机均匀产生各基因位上的值，使得每个受灾点K都能够得到救援。在遗传算法程序设计上，对各个受灾点救援次数进行跟踪，对于观测到救援次数偏少的受灾点将随机选择种群中没有对其进行救助的个体，随机将若干个基因位设置为其对应的受灾点序号。

3.4　带精英策略的非支配排序解集构造

非支配解排序的流程如下：

对于种群中每一个个体i，设都有两个参数ni和Si，ni是指种群中支配个体i的解的个体数量，Si是指被个体i支配的解的个体集合。

步骤1：找出种群中所有ni=0的个体，表示个体i支配其他个体，将他们存入当前非支配集合Z1中；

步骤2：非支配集合Z1中的每一个个体j，遍历其所支配的个体集合Sj中每一条染色体t，令nt=nt-1。若nt=0，将个体t存入集合H。

步骤3：Z1作为第一级非支配个体的集合，在Z1中的解得个体都是最优的。令其非支配序rank(i)=1，在此基础对集合H作上述分级操作，直到所有的个体都被分级，同时赋予相应的非支配排序。

3.5　拥挤度与比较算子

拥挤度的计算是确保种群多样性的一个重要因素，计算步骤如下：

(1)每个点的拥挤度id置为0；

(2)根据每个优化目标，令边界上的两个个体拥挤度为无限大，即od=ld=∞；

(3)对种群中的其它个体的拥挤度进行运算：

其中，id表示i点的拥挤度，fji+1表示i+1点的第j个目标函数值，fji-1表示i-1点的第j个目标函数值。

个体i与另一个体j进行比较，只要有以下一个条件满足，则个体i胜利。

(1)个体i所处的支配层优于个体j所处的支配层，即ranki

(2)若种群中有两个个体有相同等级(处在相同的非支配层)，且个体i比个体j有一个更大的拥挤距离，即irank=jrank且id>jd。

3.6　精英策略与遗传操作

将父代种群与其产生的子代种群混合后进行非支配排序，可以有效的避免父代种群中的精英个体流失。通过轮盘选举对个体进行选择操作，采用单点、多点交叉和基因互换进行变异操作。设计算法的流程图如图2。

图2　带精英策略的非支配模型遗传算法流程

4　算例分析

4.1　算例介绍与参数设置

根据四川九寨沟地震区域的灾难情景，选取8个应急物资配送中心(编号为1～8)，以及16个受灾点(编号1～16)同时选取2中主要的应急物资(选取食品和生活用品)。震后救援初始阶段选择4个应急配送中心开放运营。九寨沟县各应急物资配送中心的仓库容量如表1，主要受灾点的物资需求量见表2。

表1　应急物资配送中心库存容量

表2　主要受灾点的物资需求如下

图3　Pareto前沿面解的分布图

带精英策略的遗传算法的参数设置如下：种群规模popsize=400,最大迭代次数maxgen400，交叉概率pc=0.92，变异概率为pm=0.01。

4.2　运算结果分析

通过Matlab2017a编程，在2.9 GHz Intel Core i5，8 GB内存，macOS操作系统的计算机上进行运算。算法终止时，所有解收敛到Pareto前沿面上，得到140个Pareto解，Pareto最优解分布见图3。表3是从中抽取的5组(A-E)典型Pareto解。

4.3　结果对比与分析

为了保证算法运算的稳定性与可操作性，文章根据不同种群数量和算法迭代次数设计了4组参照组。表4是参照组1、2、3、4各主要指标的具体数值以及不同种群数量和迭代次数下的解数量和运算时间，各参照组Pareto前沿面结果如图4。

表3　典型Pareto解

表4　各参照组主要指标及运行时长

通过对结果的分析我们可以得出以下论：

(1)通过带精英策略的非支配排序的遗传算法的运算，我们得出不同参数下的Pareto前沿面解集，证明了模型和算法的有效性。

(2)Pareto解的运算时间与种群数量和迭代次数有关。伴随着种群数量和迭代次数的不断增加，Pareto解的数量呈现着递增趋势，通过参照组的对比分析，种群规模越大，迭代次数越多，得到的结果就更加丰富，分布也更加均匀。

(3)通过表4发现，在迭代次数相同的情况下，种群数量越多，Pareto解的集合也就越多，但消耗更多的运算时间；在种群规模相同的情况下，迭代次数越多，Pareto解的数量更加丰富，同时消耗更多的运算时间。Pareto解的数量和种群规模以及迭代次数在一方面条件确定的情况下存在着正相关的关系。

图4　各参照组Pareto前沿面解的分布图

通过图4三个参照组的对比可以发现，公平性目标与时效性目标存在着悖反现象。从Pareto前沿面的参照图来看，救灾物资的时效性目标波动较小，其分配物资的公平性目标波动较大。从图3可以看出，当公平性目标越大，时效性目标略微增加时，公平性目标则大幅度降低。同时灾区需求的增加会使公平性目标受到损失。

在救援的初级阶段，决策者更多的关注时效性目标，在救援的后期阶段，决策者更多的关注公平性目标。通过Pareto前沿面的分析，为救援决策者根据在不同阶段对决策目标的偏好提供了更多的选择。

5　结语

震后应急物资的分配与运输是震后救援保障工作的重要环节，配送中心的选址的稳定性与物资保障效率的提升对于减少财产损失、保证生命安全有着重要意义。震后物资运输与配送过程包括将应急物资从区域储备仓库和外围物资集散地运输到区域应急配送中心、区域配送中心配送到各个受灾点两个阶段。但是应急物资保障具有持续时间长、需求紧迫性强和物资相对短缺的特点，因此将物资分配时效性与公平性，多时段、多种运输方式共同参与的应急物资保障策略有机的结合起来，综合考虑震后应急物资的运输与分配特性，建立了一个考虑时效性-公平性的震后配送中心选址和物资动态分配的多目标规划模型。基于模型设计了一种带精英策略的非支配排序的遗传算法，通过非线性混合整数规划结合Pareto前沿面对时效性-公平性双目标动态救援模型进行求解。通过算法对实际案例的求解分析，发现模型可以产生有效的Pareto最优解和前沿面，准确反映了时效性目标和公平性目标的悖反现象，通过数学模型的计算将时效性与公平性的关系通过数学结果对模型和算法的有效性进行了验证，为今后进一步研究该问题奠定了基础。

在构建的模型中，救援过程涉及的相关系数的是确定的数值，但是在实际的运输过程中是随机变化的。如道路安全系数、车辆的安全性能、运输时间受道路清障的影响等因素，这些带有随机参数的目标函数模型是未来研究的方向。