不确定条件下的应急物资配送选址-路径问题

2015-08-17王海军杜丽敬

系统管理学报 2015年6期

王海军，杜丽敬，胡蝶，王婧

（华中科技大学管理学院，武汉 430074）

当突发事件发生时，要快速启动救助行动，向受到危害的地区和人员运送充足的物资，而这种突发事件一般无法提前预见，因此，受到危害的地方通常缺乏充足的物资实施救助，那么就需要选择合适的物资供应点收集物资，来集中对这些需求点进行供货。有的突发事件会导致道路毁坏，使得应急物资无法顺利运到需求点，在这种情况下，如何有效地用车辆将应急物资运到每个需求点对救援起到关键的作用。因此，本文基于此背景研究应急物流系统中的选址-路径问题（Location-Routing Problem，LRP）。

目前，国内外学者对LRP问题研究较多［1-5］。Ozdamar［6］对应急物流定义进行了介绍。以总成本最小化为目标，Alumur等［7］建立了一个多目标LRP模型，确定了废物回收站的选址，对不同类别废弃物到这些不同回收站的路线做了安排。以成本最小化和社会影响最小化为目标，Caballero等［8］研究了多车型有容量限制的多目标LRP模型。Ozdamar［9］探讨了在自然灾害发生时，伤员运送救治与物资配送的问题，研究了灾区临时的医疗点选址、医务人员分配、应急物资分配以及车辆路径选择等问题，建立了一种确定型情况下的应急物流网络模型，并利用CPLEX软件对模型进行求解，目标是最小化物资送达及伤员救治的延误，但该文中将车辆当成一种物资进行分配，是整数变量，而不是0-1变量，且未考虑自然灾害应急物流系统中的不确定性。汪寿阳等［10］在国内提出LRP，并介绍了这一领域的重要研究成果，这才引起国内学者对集成物流管理系统的重视，开展LRP方面的研究。徐琴［11］考虑了在自然灾害发生后，城市道路毁坏造成交通拥堵情况下，建立LRP模型，其中应急运输时间是模糊数，目标是要总的应急救援时间满意度最大。曾敏刚［12］研究灾害发生后的选址路径问题，将该问题分为选址与路线安排2个子问题，并且建立了最小化运输成本和灾害损失的模型，用一个两阶段的启发式算法解决。文献［14-15］中介绍了求解LRP问题的相关启发式算法。

可见，学者们对于LRP的研究已经得出不少成果，但在应急物流的信息不确定性、对此种不确定信息的处理，以及求解算法方面还有不足，本文就基于此不足进行建模与求解算法的设计。在应急物流活动中，需求点的物资需求是不确定的，由于道路毁坏，车辆在道路上的运输时间也不确定，而由于应急物流对时间要求高，故需求点是具有一定时间窗的。在突发事件发生时，短时间内难以筹集到足够的资金，为了在有限的资金条件下达到更好的救援效果，本文基于机会约束规划方法建立一个带时间窗的LRP模型，目标是最小化救援的成本以及救援的时间，并提出基于整体的遗传算法来求解模型。

1 模型建立

1.1 问题描述

当自然灾害、突发公共事件等发生时，要快速从若干候选的应急物流配送中心中选出合适的配送中心，并且要在满足一定的时间与资源量的情况下，将物资从配送中心，按照一定路线运到应急物资需求点。本文研究自然灾害发生后，单一应急物资调配问题，应急物流网络如图1所示。文中仅研究陆地车辆运输，需要飞机、轮船等其他运输方式才能达到的受灾点不在考虑范围内。本文特点是受灾点应急物资的需求是高度不确定的，且具有较高的时间限制；另外，由于道路受损，车辆行驶时间也具有高度的不确定性。考虑到受灾点对应急物资需求的紧迫性，时间是考虑的目标之一；还由于短期内筹集到的资金有限，合理利用有关资金至关重要，故成本作为第2个要考虑的目标。

综上，本文主要研究选择合适数目与位置的配送中心以及合理安排车辆路线2个问题，在高度不确定的条件下，以较低的成本尽可能快地将应急物资配送到受灾人员手中。

图1 应急物流网络LRP示意图

模型假设：

（1）有若干候选应急物流配送中心，容量有限。

（2）每个应急物流配送中心有若干个不同类型的运输车辆，车辆有容量限制。

（3）每个应急物资需求点只由1辆车提供服务，并具有一定的时间窗限制。

（4）每辆车属于一个应急物流配送中心，从该中心出发，运送完物资以后回到该中心。

（5）需求点的物资需求量是不确定的，是随机变量，服从正态分布。

（6）由于道路可能毁坏，故车辆运输时间是随机变量，服从正态分布。

1.2 变量与符号说明

A｛r|r=1，2，…，n｝——需求点集合

B｛i|i=n+1，n+2，…，n+m｝——候选配送中心集合

S=｛A｝∪｛B｝——应急物流网络中所有节点集合

V｛k|k=1，2，…，K｝——运输车辆集合

Fi——候选配送中心i（i∈B）处的固定建设费用

Wi——候选配送中心i（i∈B）的最大容量

dab——点a（a∈S）与点b（b∈S）之间距离

Ck——车辆k（k∈V）的固定运营成本

Qk——车辆k（k∈V）的可用容量

qr——需求点r（r∈A）处的需求量，服从正态分布

tab——车辆k（k∈V）从a（a∈S）到b（b∈S）的行驶时间，服从正态分布

tr——车辆在需求点r（r∈A）处的服务时间

LTr——需求点r（r∈A）处最迟必须得到服务的时间

Tbk——车辆k（k∈V）到达点b（b∈S）的时间，Tbk=Tak+tabzabk+ta，当b∈B时，Tbk=0

C——单位距离车辆行驶成本

xi——1，如果被选作配送中心；0，否则

yik——1，车辆k（k∈V）分配到配送中心i（i∈B）；0，否则

zabk——1，车辆k（k∈V）从节点a（a∈S）到b（b∈S），且a≠b；0，否则

1.3 模型建立

约束条件中含有随机变量，且必须在观测到随机变量实现之前做出决策的问题，可以用机会约束规划方法解决［13］。一般采用的原则是：允许决策在一定程度上不满足约束条件，但该决策要保证约束条件成立的概率不小于某一置信水平。这里将物资需求和车辆运输时间的约束处理成机会约束条件。模型如下：

目标式（1）使得物资到达需求点的时间总和最小；式（2）使应急物流总成本最小，包括应急物流配送中心固定成本、车辆运输成本以及车辆运营成本。约束式（3）表示每车物资配送量小于车辆容量的概率不小于α1；式（4）表示物资配送量小于应急物流配送中心的容量的概率不小于α2；式（5）表示物资到达时间满足时间窗的概率不小于α3；式（6）表示选上的配送中心可以发车；式（7）表示未选上的配送中心无车辆发出；式（8）表示车辆只能分给选上的配送中心；式（9）表示每辆车只从它被分到的配送中心发出；式（10）表示车辆不在配送中心之间来往；式（11）表示每辆车从一个点驶入，也要从该点驶出；式（12）表示物资需求点一定有且只有1辆车服务；式（13）表示车辆行驶时间具有先后；式（14）～（16）是0-1变量。

2 模型求解

2.1 双目标处理

由于该模型中，成本目标和时间目标是存在冲突性的，而在实际的应急物流过程中，响应阶段不同，决策者对于成本和时间的要求也不同，从而导致了两者的重要程度不同，故本文采用加权的方法对成本和时间目标予以权重，根据灾害发生的不同时间，决策者可以根据经验和实际状况来赋权，如应急物流响应初期，时间的权重大，而在响应后期，成本的权重可以增大，将双目标问题转化为单目标问题，增强了决策的柔性。

对双目标LRP模型的目标做以下处理：

式中：a和b分别为时间与成本的权重；minT和minC分别为最小时间与最小成本，是在该模型的目标分别为最小化时间与最小化成本的单目标时，得到的最小目标值，将其代入式（17），再运行双目标模型程序time和cost是程序运行得到的当前解，即是要求的双目标模型的解。

2.2 遗传算法设计

遗传算法的实质是模拟生物界遗传规律和生物进化论，采取并行随机搜索的优化方法。遗传算法的概率搜索机制增加了搜索过程的灵活性，运算速度较快，不受函数约束条件的限制，且采用多种机制保证搜索过程不陷入局部极值，例如，通过调整交叉和变异概率消除早熟的现象，它可以很好地将全局和局部搜索结合起来，因此，本文采用遗传算法求解。

2.2.1 编码设计染色体利用配送中心、应急物资需求点以及应急运输车辆号来编码，用的是自然数编码的方式。染色体编码方式如表1所示。

表1 染色体编码方式

染色体第1段有n个基因位，n指需求点个数，1个需求点与1个车号对应，表示需求点与车辆的分配关系，由1～k的自然数，随机生成1个，表示每个基因位，k为车辆数量，或者说线路的条数；第2段同样是n位，是由1～n的随机自然数排列成，表示路线中需求点排列的顺序；第3段是k位，是1～r的自然数，r是候选配送中心数量，表示每辆车属于哪个应急物流配送中心，染色体总长为n+n+k。

举例说明，若候选配送中心有3个，需求点有15个，可用车辆数量是3，则有如下的染色体：2-1-1-3-2-3-1-2-1-3-2-1-1-2-3-15-3-4-11-1-5-9-8-2-7-10-13-14-12-6-1-1-2，根据上文，染色体有4段，共15个需求点，那么染色体的第1段就有15位，为2-1-1-3-2-3-1-2-1-3-2-1-1-2-3，1个需求点与1个车号对应，可见1，2，3都出现了，说明3辆车都用到，关系如表2所示。

表2 需求点与车辆对应的关系

同理，第2段也有15位，为15-3-4-11-1-5-9-8-2-7-10-13-14-12-6，每一位表示1个需求点，数字顺序表示需求点接受服务的先后，因此，需求点15是第1个接收到物资，接着是需求点3，依次类推。因此，车辆行驶经过的路径为车1：3→9→2→7→13→12，车2：11→1→5→8→14，车3：15→4→10→6，接着，车的数量是3，那么染色体第3段就有3位，为1-1-2，表示3辆车与应急物流配送中心的关系，如表3所示。

可见，应急物流配送中心1和2出现了，表示选择它们作为物流中心，1，2号车属于应急物流配送中心1，3号车属于应急物流配送中心1。

表3 车辆与应急物流配送中心关系

上述分析表示应急物流配送中心与车辆的分配关系，车辆与物资需求点的分配关系。初始种群是随机生成的，根据候选应急物流配送中心的数量及车辆数量等，染色体每个基因位随机生成一个自然数，如果满足配送中心与车辆容量约束，即可得到一个初始的染色体，按照这种方法得到初始种群。

2.2.2 约束条件处理采用罚函数的思想来处理约束：如果有染色体不满足约束，就给它一定惩罚值，将惩罚值在目标函数上体现，同时也在适应度函数值上体现，即在目标函数增加一个极大的数，使得适应值减小，减少选中的概率。在本文中，有应急物流配送中心容量、车辆容量以及时间窗的约束，对这些约束增加一个惩罚值。

每个需求点的需求量qr满足正态分布N（μ，σ），且彼此独立，则也服从正态分布

则约束式（3）可转化为

η服从正态分布，当

时，约束才成立。φ—1（α1）可以查正态分布表得到。

令

则约束式（3）转化为H1（X）≤Qk。

在目标中加入f（1）=M1max｛H1（X）—Qk，0｝，M1是很大的数，同理对约束式（4）进行处理，为H2（X）≤Wixi。在目标中加入

M2是很大的数，时间窗式（5）为

则目标就转化为

2.2.3 适应度函数由于本文的目标函数是最小值，故要最大化适应度函数，通过如下方式得到：适应函数值=A/目标函数值，这里A是个常数。目标函数U=minZ，则适应度函数f（x）=1/U。

2.2.4 遗传操作本文遗传操作有选择、交叉、变异3种。随机生成一个初始的种群，再经过预定的代数进化，优化后的结果就是适应值最佳的染色体代表的结果。

（1）选择方法。本文使用精英法与轮盘法两种方法。

（2）交叉方法。文中染色体含有选址与路径两类信息，因此，不能将染色体框架成整体直接交叉，而要分别对选址与路径基因实施交叉。由于路径基因中需求点只能显示1次，故路径基因用部分匹配交叉的方法，而选址基因则是双点交叉法。

（3）变异方法。进行基因变异操作时，同样要将选址与路径基因分开进行。由于选址与路径基因不同，这里将选址基因用对换变异法，路径基因用逆转变异法。

（4）停止准则。本文采用停止准则为算法的遗传代数达到程序设置的最大迭代数，则停止运算。

3 算例分析

3.1 运算结果分析

用Solomon的RC题目的RC208部分数据作为算例。方法为：从RC208的100个数据中随机选3个作备用的配送中心，随机生成1～100中的3个数，将原数据库中的这3个编号的需求点坐标视为备用应急物流配送中心的坐标。同理得到20个需求点。

参数设置为车辆单位运输成本C为9元/km，赋予时间和成本的权重a、b分别为0.6和0.4，3个置信水平为95%，其他数据信息如表4～8所示。

表4 候选配送中心信息

表5 运输车辆信息

表6 需求点的数据

表7 各点之间的运输时间μ表

表8 各点之间的运输时间σ表

使用MATLAB软件编程，设置迭代次数为1 000次，初始种群数为200，交叉概率pc=0.8，变异概率pm=0.2。对算例计算50次，平均计算时间为278.55 s，计算效率较高，得到结果比较稳定，均是选择配送中心1和2；对运算结果进行统计分析得到，目标函数的平均值为1.045 1，最差解和最优解的目标函数值分别为1.054 6和1.034 9，与平均值的偏差仅为0.91%和0.98%，说明算法的鲁棒性较好；最优目标值1.034 9对应的最小应急物流成本为61 821元，最小应急物流时间为575 m。得出模型目标值收敛图如图6所示，结果表示的选址和路径分配如表9所示。

选出1和2作为应急物流配送中心，运输车辆3，4，5，10属于应急物流配送中心1，运输车辆1，2，6，7，8属于应急物流配送中心2，也得出了每个车辆配送需求点的顺序。

图6 目标值收敛图

表9 车辆路线结果

3.2 敏感性分析

下面对运算结果进行敏感性分析，改变模型中置信水平的取值，应急时间和应急成本的权重，得出的运算结果也不同，结果变化如表10所示。

表10 不同置信水平及权重下的运算结果

由图7可见，当时间权重增加，应急总时间呈下降趋势，应急总成本呈上升趋势。由表10可见，当置信水平一定，随着时间的权重增大，选出的配送中心的数量是递增的，这是由于多设置一些配送中心，能够使得应急物资尽快送达需求点处，图中当置信水平增加到90%，配送中心由1个增加到2个，由于配送中心固定成本较大，故总的应急成本也增大。

图7 应急时间与成本随权重变化趋势图

当时间和成本的权重一定，而置信水平增大时，表示要求物资送达需求点的时间满足时间窗的概率越大，故应急时间越短，同时也表示物资运送量满足配送中心容量与车辆容量的概率越大，因此，选中的配送中心个数越多，且启用的车辆个数也增多，导致应急总成本越大，配送中心增多，能够快速地响应需求点对物资的需求，从而使得应急时间也变短。

由此可见，置信水平和时间成本权重的取值是非常重要的，决策者应该在应急过程的不同阶段根据实际状况对参数赋予合适的值，这样得到的方案结果是可行有效的。