不确定环境下车辆配送路径鲁棒优化及求解算法*

赵 潇，夏绪辉，王 蕾，曹建华

(1.武汉科技大学 机械传动与制造工程湖北省重点实验室，武汉 430081；2.湖北文理学院 机械工程学院，湖北 襄阳 441053)

0 引言

车辆配送路径规划是供应链及物流、生产制造运作管理领域的基本问题，它对于提高物料流转效率起着至关重要的作用。因此，自车辆路径问题提出以来便受到国内外学者的广泛关注，时至今日仍然是该领域的热点问题之一[1-3]。其中，难点主要体现在两个方面。一是由于客观环境的不确定性，需求以及交通运输相关情况往往多变，由此可能导致当前方案的可行性降低，进而造成总体成本的增加或效率的降低；二是车辆路径规划问题一般属于NP-Hard问题，其求解效率随着问题规模的增加呈指数式骤然下降。配送路径优化是决定整个系统运作效率与成本的关键之一[4]。

目前，针对该类问题的研究已有大量研究成果[5]。但是，在不确定环境下，多数研究成果均是在随机规划与动态规划框架下完成[6]。在随机规划下，车辆路径问题中的随机因素，如客户需求或道路通行时间，通常被看作是服从某已知概率分布的随机事件。但是在现实条件下，不确定因素往往不会严格服务某一分布，而且，要准确获得或求出该概率分布信息基本难以实现。在动态规划框架下，按照配送阶段或路径路段可将运输问题划分为多个阶段，基于此可构建面向车辆路径问题的动态规划模型。该方面虽然直观易懂，但是，动态规划算法由于其天生存在的维数灾难问题使得其难以处理大规模的优化问题。因此，动态规划下的车辆路径问题其有效性也具有一定局限性。

针对上述两个难题，本文将研究在不确定环境下，特别是当需求信息或运输时间等不确定因素相关数据无法完全获知时，如何合理规划车辆配送路径，以实现运输成本的最小化这一为基本目标，同时控制配送或回收货物的延迟率，进而提高配送方案在不确定环境下的运作效率。

1 问题描述与模型构建

1.1 问题描述

为了模型构建的科学性和有效性，本文做出如下假设：

(1) 每一个需求点只能被一辆配送车辆所服务；

(2) 上游具备的库存总量可以满足下游所有客户的需求；

(3) 不考虑物资在配送中心以及运输过程中的装卸货时间；

(4) 物资运输的单位费用和配送中心的存储费用都是已知的；

(5) 产品的生产量都是已知的；

(6) 从供应商到配送中心以及配送中心到需求点的距离都是已知的。

假设当前在某一网络包含{1,…,n}需求点，其组成集合V={1,…,n}。假设任意两点之间的单位配送费用为cij，通行时间为tij，每个点的配送需求为di，且当前共有K辆具有相同运输能力C的运输车辆。在此，对于每一个车辆的配送任务而言，其可允许的总的配送时间上限假设为L，即如果假设每一辆车在初始时刻出发，那么它应在L时间到达最后一个目的地。通过L可反映不同配送需求点在时间上的要求。当车辆到达时间超出L时，还将接受βk的单位惩罚成本。

在上述背景下，要求完成所有配送需求的总成本最低。为此，涉及到的决策变量如下所示：

uki:车辆k服务完i点后剩余的物资数量或搭载能力，

wki:车辆到达最后需求点的时间。

1.2 鲁棒优化模型

现实条件下，由于外部环境的复杂性，获得关键参数(如需求或行程时间)的精确取值或者准确的概率分布往往是极其困难甚至是不可能的。由此可能导致基于传统模型得到的路径规划方案在现实中的可行性较低，甚至失效，即上述模型得到的方案在不确定环境下的鲁棒性较低。为此，本部分将研究对应的鲁棒优化模型，以提高在不能得到需求或行程时间准确值时的方案可行性。鲁棒优化是当前实现上述目标的主要方法之一，基于当前国内外相关研究成果[7-8]，本文将构建面向配送车辆路径规划的鲁棒优化模型。

假设各个配送点的需求是相互独立的，当不确定因素未知时，可假定其属于某一不确定集合。具体地，不确定因素有各配送点需求di和两点之间行程时间tij(不失一般性，假设任意车辆在任意相同两点之间的行程时间相同)，那么定义不确定集合U={Ud,Ut}，以及

(1)

(2)

Y3={y∈Rs|yTQy≤1}；

特别地，当Z满足以下条件时，不确定集合Ut分别可构成凸包集合、箱型集合及椭圆形集合等。

Z3={z∈Rs|zTQz≤1}。

基于上述定义，便可得到在不确定需求或行程时间参数下的配送车辆路径规划鲁棒优化模型(Robust Delivery Vehicle Routing Problem，RDVRP)。

(3)

(4)

(5)

(6)

(7)

(8)

(9)

ukj-uki+C(1-xkij)≥dj,∀k∈K,i,j∈V,d∈Ud

(10)

di≤uki≤C,∀i∈V,d∈Ud

(11)

xkij∈{0,1},∀(i,j)∈V,k∈K,

(12)

wk,uki≥0,∀k∈K

(13)

(14)

(15)

目标函数1旨在最小化总成本，包含所有车辆的运输配送成本以及惩罚成本，其中(wk-L)+={wk-L,0}。约束条件4和5保证每个需求点都被服务一次。约束条件6保证运输网络内的流量平衡，即在任意需求点，车辆进出守恒。约束条件7表示每一辆车都从车辆或配送中心出发。约束条件8表示任意车辆的服务路径不存在子回路。约束条件9表示当车辆到达时间超出L时，还将接受βk的单位惩罚成本，其中同时时间信息无法准确获取，但属于由约束15定义的不确定集合。约束条件10和11保证车辆剩余的货物或搭载能力必须满足该需求点的需要，且该需求信息无法准确获取，但属于由约束14定义的不确定集合。约束条件12到13是对决策变量的限制。

基于现有研究成果，模型RDVRP都为0～1混合整数线性规划问题。为保证路径规划方案的鲁棒性，可取模型RDVRP的鲁棒对应模型，即考虑在最坏情形下的不确定因素取值，此时，约束9以及10和11可改写为：

(16)

(17)

(18)

基于此，得到的优化模型便可计算在最大配送需求以及最长行程时间下的规划方案，因此该方案在不确定环境下具备较高的鲁棒性。

2 面向大规模配送问题的免疫遗传算法

配送车辆路径优化问题属于NP-Hard问题，虽然模型RDVRP可通过现有一些软件直接求解，如Cplex等，但是面对大规模决策问题时，这些软件求解效率往往较低[5]。为此，本部分将研究具有较高求解效率的启发式算法，以提高鲁棒优化模型的可行性。

免疫遗传算法(Immune genetic algorithm, IGA)是免疫算法和遗传算法的结合体[9-10]。免疫遗传算法主要包含7个模块：抗原识别，初始抗体产生，抗体适应度评估，记忆细胞分化，抗体促进和抑制，抗体生产和种群更新。目标函数被看着抗原，而候选解被看做抗体。可行解与最优解间的近似程度是用抗原和抗体间的相关关系来描述的，抗体差异化的计算是保持种群多样化的一种基本手段。

(1)初始抗体编码

在基本遗传算法和免疫遗传算法中，抗体都需要通过编码来表示基因型，编码方法通常包括二进制编码、实数编码等。一般来说，二进制编码比实数编码具有更强的搜索能力，但实数编码在变异操作中可以保持更好的种群多样性，并且不需要解码，可以有效地提高算法的精度和运算速度。因此，在本文配送车辆路径优化问题研究中，实数编码方法将被用来对抗体进行编码。设置初始变化区间[m(i),n(i)]，φ(i)表示第i个决策变量在区间[0，1]中对应的实数，g(i)表示基因。初始变化区间和实数区间满足线性变化关系，

φ(i)=m(i)+g(i)(n(i)-m(i))。

通过匹配初始区间和实数区间，可以获得一系列基因，并且这些基因按顺序同问题解决方案(g(1),g(2),g(3),...,g(p))的编码相关联。

(2)多样性评估

为了有效地克服算法过早收敛的弊端，基于近似向量距离的个体选择概率方法将被运用到本文。抗原、细胞B和抗体分别表示目标函数、最优解ki和候选解。第M个抗体由非空免疫系统集K和抗体在集合K上的距离组成，其中抗体的向量距离：

(19)

依据公式(19)，抗体密度为：

(20)

因此，个体选择概率可以表达为：

(21)

集合K中相似抗体数量越多，抗体i被选中的可能性越低。反之，集合K中同抗体i基因相似的抗体数越少，抗体i被选中的可能性越高。这种选择概率使得具有有效进化基因的低适应性个体能够获得生殖(再生)的机会。然而，这种个体选择的概率只同每一个抗体的适应度相关，没有考虑个体抗体之间的编码相似性。因此，欧几里得距离将被引用以应对这一问题。抗体φ1,φ2,φ3,...,φn和φ1,φ2,φ3,...,φn间的欧几里得距离可以定义为：

(22)

欧几里得距离越大，2个抗体之间的相似度越低；d=0表示2个抗体是相同的。在引入欧几里得距离后，抗体密度的选择概率可以表示为如下：

(23)

(3)免疫操作

在选择操作过程中，以P值作为选择概率进行抗体群体的选择，并且轮盘赌法被用来确保好的个体可以继承到下一代。

变异操作是指在一个或多个位点上以一定的概率改变基因的值。变异本身是一种局部随机搜索机制，与选择算子相结合的它可以保证免疫遗传算法的有效性。本文算法将随机选择一组个体进行变异操作以产生更好的个体：

Mi,G=Xi,G+H(Xr1,G-Xr2,G)

(24)

其中，Xi,G是从优秀个体集里随机选择的个体。Xr1,G和Xr2,G是从当前种群中随机选择的个体。Mi,G是变异操作后生成的染色体。H是调整因子，其迭代公式如下：

(25)

randk，k={1,2}，服从[0,1]均匀分布。θ1是一个固定参数，表示调整后的控制参数的概率。Hu,G和Hl,G都是固定参数，分别代表控制参数H的上下界。Hi,G和Hi,G+1表示第i个个体变异过程中的调整因子。

综上所述，免疫遗传算法的步骤如图1所示。

图1 算法流程图

3 案例分析

3.1 案例背景

企业A是本地的大型连锁超市，其主要业务是向本地区分销配送某些商品。然而，随着配送业务量的扩大，配送成本逐渐增加，延迟配送现象时有发生。因此，有必要研究配送车辆的配送网络问题。在假设已知环境下，配送中心与需求点之间的需求、配送时间、最大配送时间等相关数据分别如表1、表2、表3所示。该问题中共包含40个分销点配送需求点，其中有5个需求点，如图2所示。目前拥有5辆型号一致的配送车辆，每辆车的配送上限为5t。

图2 供应链空间分布情况

表1 配送中心/超市到分销点的平均配送需求量

表2 配送中心/超市到分销点的平均运输时间

表3 配送中心/超市到分销点的最大配送时间

3.2 算法效果分析

基于上述数据，本文将通过免疫遗传算法对选择模型进行求解。所有的数值实验均在Windows 10.0系统MATLAB中完成。种群的最大数值设置为40，最大迭代次数设置为500，个体交叉的概率为0.75。

由图3、图4可以看出，GA效率快于IGA。但是，IGA在解的最优性上显然好于GA。如图5所示，Cplex所使用的精确算法在在迭代约400次后达到收敛状态，即相对于IGA效率较低。为进一步验证IGA解的可靠性，如表4所示为当问题规模为50，90，130时各算法性能差异。通过对比可以发现，IGA在求解时间上的优势非常明显，解的质量虽然随着问题规模的增加下降明显，但相对于GA来说依然保持着较大优势。

图3 免疫遗传算法的平均及最优适应度曲线

图4 免疫遗传算法与遗传算法目标函数收敛对比

图5 Cplex收敛曲线

此外，通过改变个体交叉概率(0.5、0.7、0.9)，研究其对免疫遗传算法的影响。图6表明，在种群规模为20时，随着交叉概率的增加，其对应的适应度值和最佳解的质量亦增加。最后，为了验证不同种群大小对算法表现的影响，本文分别计算了种群数量为20、30、40、50、60下算法的适应度值，具体见图7。从图7可以发现，当种群规模是40时，效果是最好的。

图6 不同交叉概率下免疫遗传算法的适应度曲线

图7 不同种群大小下免疫遗传算法的适应度曲线

3.3 方案效果分析

为验证鲁棒路径优化方案效果，本部分将通过对比一般随机优化模型下得到的方案加以分析。

如图8、图9、表4、表5所示，传统配送路径方案和鲁棒配送路径方案在局部存在一定差别。特别是如图中椭圆标注区域中距离配送中心较远地带。在鲁棒优化中，这些需求点在保证配送成本尽可能低的前提下，相对均为地分配给了配送中心，以保证配送的及时性。而传统模型对配送及时性未做考虑，因此导致椭圆区域内的需求点以配送总距离最短分布，此时有些配送中心服务对象较多，有些较少。如图10、图11所示，通过对比配送延误比发现，鲁棒优化模型在各个问题规模下相对传统模型均较低，且低幅随着问题规模的增加而增大。这表明在本问题中，鲁棒优化模型可以较好的保证各个需求点配送的及时性，能更好的满足各个点的配送需求。

表4 算法效果对比

表5 模型结果对比

图8 鲁棒优化模型所得方案

图9 传统风险中性模型所得方案

图10 不同规模下配送成本对比

图11 不同规模下配送延误对比

4 结论

本文提出了不确定环境下随机因素数据不完全时的车辆配送路径鲁棒优化模型以及求解算法。构建了基于鲁棒优化的车辆配送路径规划模型以及确定型的鲁棒对等式。同时，为了提高该模型在大规模问题下的可行性，提出了基于免疫遗传算法的求解算法。通过算例分析发现，鲁棒优化模型可显著提升在不确定环境下的配送及时率，相比一般随机优化方法，配送延误可降低28.6%。提出的免疫遗传算法在算法效率上显著优于一般遗传算法，且对比CPLEX等精确求解方法具有明显优势。

然而，路径规划问题属于典型NP-Hard问题，随着问题规模的增加，其求解难度急剧增大，因此，研究面向大规模问题的鲁棒路径优化问题将是下一步的主要工作。

DOI:10.1016/j.ejor.2018.07.039.

DOI:10.1016/j.cor.2018.02.006.