震后初期应急物资短缺情景下的定位-路径问题研究

盛虎宜, 刘长石, 鲁若愚

(1.电子科技大学 经济与管理学院，四川 成都 611731； 2.湖南商学院 工商管理学院，湖南 长沙 410205； 3.湖南商学院 移动商务智能湖南省重点实验室，湖南 长沙 410205)

0 引言

地震灾害具有突发性与强破坏性，经常造成严重伤亡与巨大财产损失。为有效开展抗震救灾工作、同时满足灾区群众的应急物资需求，应急物资应尽快配送到需求点。应急物流的实践工作证明有效保障灾后应急物资供应的关键在于合理进行应急设施定位分配(Location Allocation Problem, LAP)与科学规划应急物资配送路线(Vehicle Routing Problem, VRP)，而且二者相互依赖、相互影响，应将二者整体规划与优化，即研究震后应急物资配送的定位-路径问题(Location-Routing Problem, LRP)[1,2]。

学者们已经基于不同视角研究了应急物资不同配送情景下的LRP。部分学者综合考虑灾区路网存在损毁、受损路网动态恢复与应急物资动态需求等情况，分别以总配送成本最小、总配送时间最短为目标构建数学模型，并设计相应优化算法求解应急物资配送的LRP[3～5]。文献[6]考虑应急物资模糊需求与多式联运情景下的LRP，以总配送时间最短、应急物资短缺情景下受灾点的总损失最小为目标构建多目标的LRP数学模型，设计多目标遗传算法求解。文献[7]综合考虑震后多品种应急物资、多方式配送与公平分配等因素构建动态LRP数学模型。文献[8]研究了应急物资的中转运输问题，设计应急物资需求点的满意度函数，在此基础上构建基于时间满意度LRP数学模型，设计启发式模拟退火算法求解。文献[9]考虑了多阶段随机需求情景下应急物资配送的LRP，以总运输时间最短、系统总成本最小为目标构建LRP模型。文献[10]综合考虑灾区路网损毁、配送时间限制与配送路线可靠性等因素，构建震后应急物资配送的开放式LRP数学模型。文献[11]整体优化灾后应急中转点选择与医疗物资多方式联合配送路线。文献[12]综合考虑应急物资配送的多车型、开放式车辆路径与模糊需求等因素，以总运达时间最短、总配送成本最小为目标建立LRP模型。文献[13]在综合考虑应急物资覆盖率、仓库建设费用与配送费用等因素的基础上构建多目标LRP模型，设计数学启发式求解算法。文献[14]针对震后初期应急路网部分受阻、应急物资短缺与多方式配送的两层配送网络，以总配送时间最短、受灾点的应急物资满足率最大为目标构建LRP模型。文献[15]综合考虑应急物资模糊需求、部分道路损毁与车辆不确定行驶时间等因素，以总运输时间最短、总运输成本最小为目标构建LRP模型。文献[16]综合考虑应急路网可靠性、总配送成本与开放式路径等因素构建应急物资配送的LRP模型。文献[17]研究应急物资供应网络的动态LRP，以总运输时间最短、系统总成本最小为目标构建LRP模型。最近，还有文献[18]研究了震后灾区应急物流路网存在故障与救援时间限制条件下的LRP，文献[19]研究了车辆行驶时间随机与模糊需求情景下震后应急物资配送的LRP，文献[20]考虑了震后应急物资多方式供应的动态LRP，文献[21]研究了应急物资灾前预置与灾后配送联合优化的LRP，文献[22]设计了一种两阶段连续近似方法求解灾后应急物资配送的LRP。

已有成果从不同角度对应急物系统中的LRP进行了有益探索，为后续研究奠定良好基础。分析已有文献，发现如下研究缺口：①已有成果大多假设应急物资对每个需求点的重要程度相同，鲜少考虑灾害级别与应急物资短缺情景下需求点造成损失的难易程度；②震区道路遭受不同程度损毁，导致应急车辆行驶时间随机，相关研究文献不多。震后初期，灾区预置的应急救灾物资储备总量通常不能满足灾区的应急物资需求[23,24]。与此同时，震区道路遭受不同程度损毁，难以及时修复，灾区外部的应急物资在短时间内难以及时运达灾区。在地震灾害等特殊环境下，受灾群众身心相对脆弱。如果应急物资不公平分配，容易引发人们的公愤，甚至可能演变成为群体性事件，导致严重后果[7,26]。因此，本文基于公平与效率兼顾视角研究震后初期应急物资短缺情景下的LRP，为有效保障应急物资供应提供参考。

1 模型构建

1.1 问题描述

震后，需在规定时间内将物流中心的应急物资配送到需求点。为明确本文适用范围，提出如下假设：①震后初期应急物资短缺，难以满足灾区需求；②灾区路网存在不同程度的损毁情况，应急车辆行驶时间具有不确定性；③应急物流中心可以征调到足够的运输车辆，车辆具有不同类型与容量；④应急物资运达需求点具有时间期限。决策问题：在公平与效率兼顾的前提下如何合理规划应急物资配送方案？

1.2 符号说明

参数：B{b|b=1,2,…,m}为应急物流中心集合；gb为物流中心b拥有的应急物资数量；V{r|r=1,2,…,k}为应急车辆集合；qr为车辆r的容量；C{i|i=1,2,…,n}为需求点集合；di为需求点i的应急物资需求量；si为需求点i的应急物资实际分配量；N=B∪C为应急物流网络内的所有节点集合，i,j∈N；tijr为车辆r从节点i行驶到节点j的随机时间；l为应急物资配送时间期限。

决策变量：βbi为需求点i(i∈C)被分配给物流中心b(b∈B)则为1，否则为0；xijr为车辆r(r∈V)从节点i(i∈N)行驶到节点j(j∈N)则为1，否则为0。

1.3 应急物资公平分配

已有部分学者从不同视角探讨了灾后应急物资的公平分配问题，分别以单个需求点最大缺货量最小[1]、需求点的累计满足率最大[7,14]、应急物资短缺情景下受灾点的总损失最小[10,16,24]为目标构建数学模型进行应急物资公平分配。文献[23,25]基于公平理论与前景理论构建应急物资公平分配的多目标数学模型，文献[27]通过在负效用函数中引入灾民需求未满足的比例量化了灾后资源严重短缺情况下的应急物资公平分配效果。最近，有学者基于公平与效率兼顾的视角探讨了应急物资分配问题[28～30]，分别以需求点未满足的需求量之和最小表示应急物资分配的公平性、以总配送延误时间最小表示应急物资配送的效率性[34]。本文综合参考上述文献方法，综合考虑应急物资短缺、灾害级别、需求点的易损性等因素，设计需求点损失函数，具体如下：

(1)

其中，1/Dγ表示归一化处理，γ≥1。

以单个需求点的最大损失最小为目标来衡量应急物资分配数量的公平性，即

(2)

1.4 LRP模型

以单个需求点的最大损失最小为应急物资分配的公平性衡量指标、以总配送时间最短为应急物资配送的效率性衡量指标，建立LRP模型如下：

式(3)为公平目标，最小化单个需求点的最大损失；式(4)为效率目标，最小化总配送时间。约束式(5)表示灾区应急物资短缺；约束式(6)表示分配给某一物流中心的所有需求点的应急物资实际分配数量总和不能超过该物流中心的拥有数量；约束式(7)表示要把所有物流中心的应急物资全部分配；约束式(8)表示分配给某一车辆的所有需求点的应急物资实际分配数量之和不超过该车辆的容量限制；约束式(9)表示车辆行驶路径连续性约束；约束式(10)表示子巡回消除约束；约束式(11)表示车辆只能分配给一个物流中心；约束式(12)表示车辆从上一个节点行驶到下一个节点的时间计算方法；约束式(13)表示车辆到达需求点的时间不能超过时间期限；约束式(14)表示变量取值约束。

1.5 车辆随机行驶时间计算

(15)

关于灾后应急车辆随机行驶时间的研究成果屈指可数。文献[2]与文献[20]对行驶在震后灾区损毁道路上的车辆随机行驶时间进行了模拟仿真。文献[15]认为行驶在灾区损毁道路上的车辆随机行驶时间服从正态分布。文献[31]研究了汶川地震之后的灾区道路损毁程度量化问题，将灾区道路损毁程度ϑij分为5个级别。即：ϑij>0.3表示节点i与j的之间的道路完全损毁、0.2<ϑij≤0.3表示严重损毁、0.1<ϑij≤0.2表示中度损毁、0.01<ϑij≤0.1表示轻微损毁、0.01≥ϑij表示基本无损毁。文献[32]分析了道路损毁程度与地震烈度、地形、地质的关系。本文参考并拓展了以上方法，根据需求点j的地形yj与道路损毁程度指标ϑij等因素，计算车辆r从节点i行驶到节点j的行驶时间tijr为

(16)

其中，M表示山区、P表示平原。决策者可以根据实际经验合理确定ε、η、σ、φ、ξ、ψ的值。

2 混合启发式算法

分层序列法能有效求解多目标优化问题，核心思想是将所有目标按照重要性程度排序，首先求出前序目标的最优解，再使用前序目标最优解依次求出后序目标的最优解[23,33]。遗传算法具有随机化搜索、多点并行搜索与鲁棒性等特性，已经被广泛应用于各研究领域[7,14]。因此，针对模型特点，本文采用分层序列法的思想设计二阶段混合启发式求解算法，第一阶段进行应急物资分配，第二阶段采用遗传算法规划应急物资配送方案。

2.1 应急物资分配算法

步骤1初始化。输入di、gb、γ、δi的值，令当前迭代次数iter=1，z1=∞，最优分配方案Sbest=φ。

步骤4算法结束判断。如果iter等于最大迭代次数，算法结束，求得z1与Sbest；否则，iter=iter+1，转步骤3。

2.2 遗传算法设计

步骤1种群初始化。将目标函数z2及约束条件对应于抗原，问题的解对应于抗体。设定群体规模为E，随机生成一组抗体作为遗传算法的初始抗体群W。

抗体由3个子串组成。子串1为实数编码，长度为m×n，表示物流中心b对需求点i的配送量∂bi。子串2为自然数编码，长度为n，表示为需求点服务的车辆序号r。子串3为实数编码，长度为n，表示车辆到达需求点的时间Tir。

(17)

而且fitness(w)的值越大，抗体w与抗原的亲和力Q(w)越大，表明该抗体越优。

步骤4抗体促进与抑制。①根据抗体编码特征，定义抗体w的浓度为

(18)

②根据种群的亲和力类型总数κ，设定抗体浓度阀值为κ/E。③选择亲和力较高而且浓度较低的抗体进行促进。④当抗体的浓度达到阀值时，随机生成超浓度规模数量的ω条新抗体替换旧抗体进行抑制。

步骤5遗传操作。采用精英选择和轮盘赌选择方法进行遗传操作。另外，抗体的子串1与子串3采用文献[7]设计的算术交叉方法，子串2采用顺序交叉与逆转变异方法。

步骤6终止条件。算法迭代maxgen次后结束，得出最优z2。

3 算例分析

采用文献[16]中汶川地震之后的帐篷配送数据作为基础构造算例，具体如下：①需求点汶川(V1)、绵竹(V2)、北川(V3)、青川(V4)、茂县(V5)、都江堰(V6)、安县(V7)、平武(V8)、彭州(V9)、江油(V10)与德阳(V11)的帐篷需求量、易损性如表1；②物流中心成都(V12)、绵阳(V13)与广元(V15)的拥有应急物资数量如表2；③各物流中心拥有大型卡车、中型卡车、小型卡车的行驶速度与容量如表3；④应急物流网络图中的剑阁(V14)表示转运点，节点之间的链路表示可用道路，可用道路越粗表示该道路允许车辆行驶的速度越大，一共有4种类型的可用道路：快速通行道路(限速80KM/小时)、中速通行道路(限速60KM/小时)、缓慢通行道路(限速40KM/小时)、难以通行道路(限速20KM/小时)，如图1。⑤采用百度地图里面的推荐路线距离计算方法求得应急物流网络中节点之间的距离，如表4。⑥限于篇幅，需求点j的地形yj、节点i至节点j之间的道路损毁程度指标ϑij等不再一一详细描述。

程序采用Matlab 2013a编程，参数设置：maxgen=1000、γ=1.5、l=24小时，ε=4、η=3、σ=2、φ=3.5、ξ=2.5、ψ=1.5、ζ=5。

将本文的公平分配方法(BW)与文献[23]的优先考虑应急物资归属地的分配方法(GS)、文献[25]的比例分配方法(BL)比较，各需求点的分配数量(FP)、需求点损失(SS)如表5所示。按照文献[23]的应急物资归属地方法(GS)，成都配送中心必须优先考虑都江堰(V6)、彭州(V9)的应急物资需要，绵阳配送中心必须优先考虑北川(V3)、平武(V8)、江油(V10)的应急物资需要，广元配送中心必须优先考虑青川(V4)的应急物资需要。然后，如果各配送中心还剩余应急物资，再考虑其他属地需求点的需要。值得注意的是，GS方法容易导致具有优先分配权的需求点应急物资满足率达到100%，而受灾比较严重的汶川(V1)、茂县(V5)竟然没有优先权，甚至没有同等对待。这种情况下，容易引起灾区群众的不满，引起公愤，极端情况下可能发生应急物资哄抢等社会事件，导致严重后果(例如2010年海地地震之后发生了灾民哄抢应急物资的事件)。震后应急物资分配应“以人为本”，综合考虑公平、效用与易损性等因素，尽可能避免社会事件。

图1 应急物流网络图

表1 需求点的帐篷需求量与易损性

表2 物流中心拥有的应急物资数量

表3 配送车辆数据

车辆类型大型车中型车小型车容量(个)800600400行驶速度(km/小时)806040

表4 节点之间的距离(KM)

从表5可知，BW方法计算得到的需求点损失(SS)最大值为0.0037，最小值为0.0008，总损失为0.0208；BL方法计算得到SS最大值为0.0057，最小值为0.0004，总损失为0.0243；GS方法计算得到SS最大值为0.0124，最小值为0，总损失为0.0338。从公平性视角来看，BW方法求得的最大SS的值最小，SS的值在需求点之间的跨度最小，优于其余2种方法；BL方法次之，GS方法第三。从总损失最小的角度来看亦如此。说明了本文设计的应急物资分配方法同时兼顾了应急物资分配的公平性与效用性。决策者在进行应急物流规划时，应综合考虑灾害级别、应急物资效用、需求点优先级别、灾区群众的心理多种因素，制定科学、公平、合理的应急物资分配方法。

表5 需求点的应急物资实际分配数量与损失

最优应急物资配送路线如图2所示。一共使用了大型卡车11辆、中型卡车18辆、小车卡车1辆，应急物资总配送时间为207.328小时。配送时间较长的需求点主要是汶川、茂县、平武，原因是通往这些需求点的道路难以通行，致使配送车辆行驶非常缓慢。从而可知：①影响应急物资配送时间的关键在于灾区是否存在高可靠连通性的应急路网；②为满足灾区群众需要，对路网损毁特别严重、车辆难以通行的需求点应空投应急物资；③应及时开展灾区损毁道路的抢通工作，使损毁道路尽快恢复，配送车辆可以正常通行。

图2 应急物资配送路线

在各种参数不变的前提下，通过扩展上文算例(算例1)的规模参数a、b形成算例2至算例4，采用本文的二阶段混合启发式求解算法(TSHHA)与文献[12]的混合遗传算法(HGA)分别求解各个算例，结果如表6所示。其中，a表示配送中心数量，b表示需求点数量。从表6可知，TSHHA的求解时间随着LRP规模增大有所增长；TSHHA在程序运行时间方面略胜HGA。说明TSHHA能够在较短时间内有效求得应急物资配送方案。

表6 不同问题规模的LRP求解结果

4 结论

震后初期，由于外界的应急物资难以及时运达各配送中心，灾区存在应急物资短缺情况，应急物资应该公平配送。本文基于公平视角研究震后初期应急物资短缺情况下的LRP，综合考虑灾区路网不同程度损毁、车辆行驶时间难以准确计算、灾害级别、需求点受灾指数与易损性等因素，以单个需求点的最大损失最小作为应急物资分配的公平性衡量指标、总配送时间最短为应急物资配送的效率性衡量指标，在此基础上建立应急物资公平配送的LRP模型，并设计两阶段混合启发式求解算法。基于汶川地震之后的帐篷配送算例分析结果表明，该算法运行效率较高，能够迅速求解出规定期限内的震后应急物资配送方案。

进一步的研究将考虑应急车辆动态调度、应急车辆协作救援等问题。