灾后带有时间窗的多目标选址-路径问题

陈贵景，孟献青，王振芳

(山西大同大学数学与统计学院,山西大同037009)

近年来,人为的或自然的灾害在不同的地区和国家频发，引起了巨大的人员伤亡和经济损失。灾后及时有效并且稳定的救援工作非常重要。应急物流管理主要包括两个方面[1]:一是服务设施点的选址问题(FLP)，二是救援物资从供应点到需求点的车辆路径问题(VRP)。事实上在应急物流中设施选址和车辆路径是密切联系的，即选址-路径问题(LRP)。与传统的运输物流相比，应急物流中的设施选址问题和车辆路径问题更具挑战性和复杂性[2]。文献[3]最早把设施选址问题和车辆路径问题结合在一起，到目前为止已有丰富的研究成果[4-5]。

灾后情况十分复杂，为了更接近实际的应急情况，多目标的LRP问题成为研究热点，Rath，Gutjahr[6]研究了在灾难救援中有中间配送站的选址路径问题，为需求点提供必要的物资，目标是最小化设施固定开设成本，这里包括车辆的采集和操作成本，最大化客户需求覆盖率;王海军、马士华等[7]提出了多目标的需求可分的选址-路径模型，优化地震后的救济物资分配问题，目标是最小化路径运输时间，最小化总成本包括分配中心的固定开设成本和车辆运输成本，最大化路径可靠性。Çağrı Koç，Tolga Bektaş，Ola Jabali，Gilbert Laporte[8]研究了带有时间窗的LRP问题，车队是不同性质的，目标是最小化总成本且需求不可分的。

从已有的文献可以看出，大部分学者都会把成本作为LRP问题的一个目标，事实上灾后两点间的距离和通过时间都会受到不同程度的影响都需要付出一定代价，所以距离和时间都可以理解为成本类型的目标。引入半时间窗约束，即物资到达需求点的时间不能迟于规定时间，从而提高紧急救援的时效性，另外灾后各类物资大量短缺，充足的救济物资显得非常重要，故除了成本作为其中一个目标外，物资的满足率作为第二个目标。突发事件发生后，运输网络一定会受到不同程度的破环和影响，为了找到更好的路径，把路径的运输能力作为第三个目标。

1 问题描述

通常情况下灾后的物资分布网络被描述成图G=(V,E) ，其中V是顶点集合，M={n+1,n+2,…,n+m}是候选分配中心的集合，假设M中的点没有需求，N={1,2,…,n}是受灾点集合。E={(i,j):i,j∈V,i≠j} 是有效弧集合，K={1,2,…,k}是车辆集合。考虑以下三个目标:(1)最小化总成本，包括分布中心开设的固定成本和车辆运输成本;(2)最大化需求点的最小物资满足率;(3)最大化最差路径的通过能力。其中每个弧上的通过能力用车辆通过的速度表示。

假设受灾点和候选分布中心是已知的且候选分配中心的容量是足够大的;运输网络中可用的弧和距离以及弧上车辆通常速度是已知的，比如可以通过先进的监测技术获得或者通过运输研究团体获得等;因为多种类型的救灾物资以体积计算，所以不同类型的救灾物资可以看成一种物资;灾后物资紧缺，假设需求点的对救济物资的需求量大于等于供应量。只考虑能通过车辆运输救灾物资的受灾点，忽略需要直升机等特殊运输手段才能服务的受灾点。

m是分配中心候选点数;n是受灾点数;k是车辆数;fj∀j∈M是开设分配中心j的固定成本;dij∀(i,j)∈E是弧(i,j)上的距离;vij∀(i,j)∈E是通过弧(i,j) 的运输速度;是弧 (i,j)上最大的运输速度;vk是车辆k的通常速度;Di,∀i∈N是受灾点i需求量;Q是运输网络中可用的救济物资量;ck∀k∈K是车辆k的单位运输成本;Lk∀k∈K车辆k的负载能力;si∀i∈N受灾点i的服务时间;tik∀i∈N,k∈K车辆k开始服务受灾点i的时间;bi∀i∈N服务受灾点i的最迟时间。

如果分配中心j开设xj∀j∈M为1，否则是0;如果在车辆k的路径上点i在点j的前面yijk∀k∈K,(i,j)∈E是1，否则是0;如果i在车辆k的路径上zik∀k∈K,(i,j)∈E是 1，否则是 0;qik∀i∈N,∀k∈K是被车辆k运送到i的救灾物资量;如果车辆k服务的最后一个点是受灾点i，则VFik∀i∈N,k∈K是1，否则是0。

2 模型

目标1最小化救济物资配送总成本minf1。在选址-路径问题中需要同时决定分配中心的个数和选址，给分配中心安排受灾点的任务，以及相应的车辆配送路径，所以救济物资的分配总成本包括分配中心开设的固定成本和车辆运输成本，

目标2希望灾后救济物资能及时有效的到达需求点，所以要考虑需求点对物资的满足率问题，希望受灾区域的救济物资满意度最大化且考虑到救济物资分配公平最大化，即优化满足率最差的点maxf2，

目标3最大化可用路径的通过能力。灾后原有的路径都受到或多或少的影响，此时我们考虑到路径的通过能力，希望最大化通过能力最差的可用路径，这里每个可用弧上(i,j)∈E的通过能力用车辆通过的速度vij来表示，则每条路径的通过能力为每条弧上的速度和。车辆的速度在区间(0,]上随机产生。则第三个目标为maxf3，

约束条件:

约束(4)(5)是时间窗约束，这里M是一个较大的正数，只要求不迟于某个给定的时间。约束(6)说明从分配中心配送到受灾地点的救济物资的总量不能超过相应物资的可用总量。约束(7)保证被车辆k运送到受灾区的所有救济物资的体积不能超过车辆的负载能力。约束(8)～(9)保证决策变量是0～1变量和非负变量。

车辆路径中为了避免子回路有相应的子回路消除约束，这里采用Dror等[9]在1994年提出的约束。设di为点i的出次:。约束中k表示车辆的数量，

3 模型的求解

很多实际问题都需要同时优化多个目标，有时这些目标经常相互竞争或者相互矛盾，为此介绍帕累托最优解的概念。

(1)帕累托占优，考虑所有的目标，如果解x1至少与x2相等，且至少有一个目标值比x2好，则称解x1占优解x2，记为x1＞x2。通常情况下对于极小化问题(f1,f2,…,fw)，如果则x1＞x2。

(2)帕累托最优解，x1是帕累托最优解(或非劣解)当且仅当没有任何解x2满足x2＞x1。

(3)帕累托前沿，如果x1是帕累托最优解(非劣解)，则f(x1)={f1(x1),…,fw(x1)}称为非劣向量。所有非劣向量的集合称为帕累托前沿或成为非劣前沿。

对于多目标的优化问题常见的解决方法见[10-13]。引用遗传算法用文献[13]来解决提出的带有半时间窗的多目标路径选址问题。下面介绍具体过程:

①初始种群。

根据该LRP问题的特点，假设每个染色体有三个子串

其中g=1,2,...,NP，NP是种群里染色体数，t是种群的代数，初始种群t=0，子串是车辆的排列，子串是从m个分布中心中任意选出k个的排列，子串是n个需求点的排列。那么可以看出和在一起就是一个车辆分配决策，中的第一个基因代表的车辆是停在中的第一个基因代表的分布中心，以此类推。和共同决定了在车辆路径中的物资供应量。每一个都可以计算出相应的目标函数值。具体见文献[7]。在运输过程中根据点与点之间的距离以及不同车辆的速度计算运输时间(忽略分布中心的分配时间)加该点的服务时间如果大于等于bi，对该路径的运输能力进行惩罚，即运输能力更新为:bi(运输能力)/(运输时间+服务时间)。

② 变异过程。

③交叉过程。

④选择过程。

采用加权的方法进行排序，随机选取λ1∈(0.1,0.3],λ3∈[0.3,0.5)。因为满足率小于1，与总成本和总路径速度相加时容易丢失，故随机选取λ'∈[500,1000]，然后设λ2=λ'×N。

(5)遗传算法的具体步骤。

S1随机产生规模为NP的初始种群X0；

S2通过变异过程得到变异种群Vt，通过交叉过程得到实验种群Ut；

S3混合Xt和Ut得到规模为2NP的种群Rt；

S4计算Rt中每个染色体的目标函数值；

S5确定λ1,λ2,λ3的得到F=λ1(-f1)+λ2f2+λ3f3，并进行排序；

S6选取前NP个做为下次迭代的种群。直到T大于规定的最大迭代次数。

4 算例

参数设置:NP=5×(m+n)，变异概率pm=0.7，交叉概率pc=0.7。候选分配中心个数m和受灾点个数n的组合是

每个点的坐标在平面上随机产生，且假设从i点到j点的距离和从j点到i点的距离相等。分配中心的固定开设成本(元)在(0，3000]内随机产生。受灾点的需求量在区间(0，80]上随机产生(m3)。各弧上大、中、小型车辆的通过速度分别在区间[20,80]上随机产生,不同个数的受灾点需要大中小型车辆个数见表1。假设灾难发生的时刻是零时刻,则每个需求点被服务的最迟时间(小时)是在(0,100]内随机产生。表2给出有关车辆的参数,表3是计算结果,图1(3～10)例子的近似帕累托前沿。

表1 所需车辆数

表2 车辆的参数

表3 计算结果

图1 用遗传算法得到的近似帕累托前沿(3～10)

5 结论与展望

提出一个带有半时间窗的多目标非线性选址-路径模型,即物资到达需求点的时间不能迟于规定时间来提高紧急救援的时效性,其中受灾点可以被访问多次即需求可分的,另外灾后各类物资大量短缺,充足的救济物资显得非常重要,故除了成本作为其中一个目标外把物资的满足率作为第二个目标。突发事件发生后,运输网路一定会受到不同程度的破环和影响,为了找到更好的路径,把路径的运输能力作为第三个目标。最后采用加权排序的遗传算法解决随机产生的若干算例。多次运行结果显示,对于本文的问题加权排序的遗传算法表现稳定有效。

灾后的情况非常复杂,具有高度的不确定性比如需求、运输时间、路径通过速度等,因此模型中加入随机优化或者鲁棒优化的方法是未来研究的一个方向。另外解决该问题的方法还可以尝试模拟退火或者非劣排序的遗传算法等。