基于改进NSGA-II的冷链物流多目标车辆路径优化

杨 亮,向万里,王 丽,王超然,朱 亮

(兰州交通大学 a.交通运输学院;b.兰州交通大学 现代物流研究所，甘肃 兰州 730070)

生鲜产品的质量受物流配送时间影响较大，配送不及时则会导致物流企业亏损，以及顾客满意度变化。如何科学有效的规划冷链物流行驶路径、减少成本、提高客户满意度，成为学者关注的重心[1]。Bortolini[2]提出以运营成本、碳足迹和车辆服务时间为优化目标的生鲜食品配送优化模型。李善俊[3]以配送成本最小和生鲜品新鲜度最大为优化目标进行求解。

然而，传统算法经常陷入局部最优、无法收敛的情况，本文构建多目标冷链物流优化模型，设计I-NSGA-II算法求解物流配送问题，通过算例验证多目标优化模型的合理性。

1 问题描述

配送问题描述：1个配送中心和n个客户点的冷链物流优化，在配送过程中结合生鲜产品的特点，假设客户点的需求、地理位置、配送时间窗已知，从物流企业角度出发考虑如何减少配送总成本、提高客户满意度。

2 冷链物流多目标车辆路径优化模型

2.1 模型假设

为了更好地建立多目标车辆路径优化模型，假设有如下条件：① 每辆车载重不能超过车辆最大载重；② 每辆车均需从配送中心出发，配送任务完成后必须返回配送中心；③ 每个客户点只需要执行一次配送任务；④ 配送时间满足客户点的要求，早到或晚到都会有惩罚；⑤ 不考虑道路拥堵状况；⑥ 配送总成本包括车辆使用成本、运输成本、时间惩罚成本、制冷成本、碳排放费用、生鲜货损成本。

2.2 符号说明

优化模型中常用的数符号及含义见表1。

表1 符号定义

2.3 配送成本

1)车辆使用成本。车辆的固定使用成本是一个常数，仅与配送所需的车辆数量有关。x0jk表示从配送中心到客户j出发的车辆，车辆固定成本C1可通过式(1)计算，即

(1)

2)运输成本。运输成本是指车辆随着行驶距离变化产生油耗而造成的成本，文中采用单位行驶距离成本与行驶距离的关系，计算冷藏车的运输成本C2，即

(2)

3)时间惩罚成本。客户对生鲜产品的配送提出的要求比普通货物配送更高，而软时间窗对时间要求较为宽松，能极大地优化资源配置，在软时间窗约束下，如果配送车辆到达时间早于客户i的左时间窗ETi，则会产生早到惩罚φ1；在规定的[ETi,LTi]到达则不会产生惩罚；迟于LTi则会产生晚到惩罚φ2。时间惩罚成本函数如图1所示，其中ET'i表示车辆早到时间，LT'i表示车辆晚到时间。

图1 时间惩罚成本函数

配送车辆的时间惩罚成本为C3，即

(3)

4)制冷成本。运输时制冷成本受车辆行驶时间影响，而卸货时由于冷藏车门打开，外部空气进入车厢，造成车厢内部温度变化，为了保持车厢内部恒定温度，车辆制冷机功耗增加，成本也会随之变化，所以模型将车辆的制冷成本分为2个过程产生的成本：运输过程中产生成本、卸货产生成本。

运输制冷成本为T1，即

(4)

只考虑对顾客点服务时间的卸货制冷成本T2，则

(5)

式中：t0i表示开始服务客户i的时间；yjk表示客户j由第k辆车服务。

总制冷成本为C4，即

C4=T1+T2.

(6)

5)碳排放费用。碳排放费用是指车辆在行驶过程中随着距离和载重的变化而产生的CO2排放成本，采用碳排放费用=碳税*碳排放量[4]的计算方法，综合考虑车辆载重、油耗计算产生的费用C5，即

(7)

(8)

式中：FCij表示客户i到j的碳排放量；ρ0表示载重为0时的油耗；ρ*表示满载时的油耗；Qij表示从客户i到客户j的载重量；w表示碳税。

6)生鲜货损成本。在只考虑配送时间对货损成本的前提下，本文采用文献[5]中生鲜损耗系数的计算办法，来描述冷链产品随时间变化产生货损成本变化，则整个配送环节中产生的生鲜损耗成本C6为

(9)

式中：T表示冷链货物的保质期；r∈(0,1)是时间敏感因子。

2.4 客户满意度

本文主要研究冷链物流配送中软时间窗对客户满意度的影响，如果配送时间在客户左时间窗之前到达，客户满意度为1；如果在客户期待时间窗到达，客户满意度则会随着到达时间呈线性递减趋势；若配送时间迟于顾客要求的右时间窗则客户满意度为0。客户对配送时间的满意度函数Ui为

(10)

2.5 模型建立

冷链物流的车辆路径模型以最小成本Z1(车辆使用成本、运输费用、时间惩罚成本、制冷成本、碳排放费用、生鲜货损成本)、最大客户满意度为目标进行求解。模型如下：

minΖ1=C1+C2+C3+C4+C5+C6，

(11)

(12)

(13)

(14)

xijk=0 ∀i=j,∀i,j∈N0,∀k∈K，

(15)

(16)

(17)

(18)

(19)

(20)

(21)

(22)

(23)

式(13)表示容量约束，式(14)表示每辆车只能访问客户后必须离开，式(15)表示每个节点不能访问自己，式(16)、式(17)、式(18)表示每个客户只能有1辆车进行服务且不能重复访问客户点，式(19)表示所有车辆必须从配送中心出发进行配送，式(20)表示每辆车必须返回配送中心，式(21)、式(22)、式(23)均为决策变量。

3 I-NSGA-II算法设计

3.1 遗传算法

3.1.1 编码、解码

染色体编码采用自然数编码的方式，将1，2，3…，n个客户随机排列，如5-4-6-2-1-3，表示6个客户点的随机分布。上述编码方式必须对染色体进行解码操作，算法按照染色体编码中基因的顺序，在不违反车辆载重约束的条件下，将客户的需求插入路径，若超过车辆载重则将该客户放入下一辆车的路径，0代表配送中心。例如上述6个客户的需求分别为：6、5、7、9、8、3 t，车辆最大载重为20 t。在使每一个车辆尽可能装满的前提下，解码后的路径为：第一辆车路径：0—5—4—6—0；第二辆车路径：0—2—1—3—0。

3.1.2 交叉

采用遗传算法顺序交叉的方法对染色体进行操作，首先，随机选取[a,b]长度的染色体片段，交换父代和母代[a,b]部分基因片段，从b点以后基因起删除重复基因；最后，重组基因。例如：父代1：13|2486|75，父代2：86|4573|12，交叉3-6位置的点，得到父代1：4573|13248675，删除重复基因得到交叉后的父代1：4573|1286；同理得父代2交叉后的结果为：2486|5731。

3.2 NSGA-II算法

NSGA-II算法运行速度快、收敛性好，是解决多目标优化问题的算法之一[6]，算法步骤和遗传算法均需执行编码、解码、交叉等操作。与遗传算法不同的是，NSGA-II需要通过快速非支配排序、拥挤度距离计算，选择解空间更好的个体进入下一代，保证种群的优良性状。算法中种群进化的步骤如图2所示。

图2 NSGA-II种群进化策略

3.2.1 快速非支配排序

作为NSGA-II算法的重要步骤，快速非支配排序根据个体解的水平对种群实现分层，指引算法搜索向最优Pareto解集的方向进行。定义2个变量：np表示支配个数，Sp表示被p支配个体集合。如图3所示，对于求解多个目标且求解均为最小值的问题，图中每一个点都表示一个解。对于c点而言，a、b点f1，f2值均优于c点值，因此c被a，b两点支配，np=2，Sb={c}。遍历解集中所有点，记录np和Sp，将np=0的点记为第一非支配层F1，将其所有个体赋予非支配序值rank=1(rank是个体i的非支配排序值)，将F1中的个体从种群中除去；接着循环寻找下一支配层中np=0的点，直到种群中所有个体都分层为止，得到F1≻F2≻F3≻…(≻表示优先)。

图3 快速非支配排序算法

3.2.2 选择

选择的目的是保留优良的个体进入下一代，以防止解的收敛效果不佳。首先对父代Pt和新子代Qt组合而成的种群Rt进行非支配排序，按非支配排序值从小到大排序，将整层个体放入Pt+1，如果某一层出现Pt+1超过种群最大数目N时，计算拥堵距离，按拥堵距离从大到小放入Pt+1，直到满足种群数目N。

3.3 改进的NSGA-II

NSGA-II算法在收敛速度过快的同时，会出现过早收敛、分布性不佳、局部最优等问题；为保证种群多样性，提高算法收敛性能，通过C-W算法构建初始种群，利用M-变异算子、C-进拥堵距离计算的方法来提高算法的性能。

3.3.1 初始解构造

NSGA-II算法的解集对初始种群依赖性很大，改进算法通过C-W节约算法来提升解的可依赖性，构建得到NSGA-II-CW算法。C-W节约算法将n个客户点与配送中心相连，形成k条路径；通过节约值的大小顺序将客户i和客户j合并，形成0—i—j—…—0的路径。C-W节约算法的步骤如下：

首先，计算节约值的大小，算法中距离节约值可通过式(24)计算，即

s(i,j)=d0i+d0j-dij，

(24)

排序寻找最大距离节约值对应的客户i和客户j，判断要合并的路径是否满足时间窗约束，满足则合并至一条配送路径。其次，判断路径合并后是否满足车辆载重，若满足则继续判断是否存在只有1个客户点的路径，更新最大距离节约值；否则重新选择客户。当1条路径有2个或3个以上客户时，计算不同位置点的节约值，在节约值最大的位置插入新客户，例如：0—3—4—5—0有4个位置可以插入，分别计算0—i—3—4—5—0、0—3—i—4—5—0，0—3—4—i—5—0，0—3—4—5—i—0，选取节约值大的位置插入，最后，判断是否满足时间窗，直到满足车辆载重量为止。

3.3.2 改进变异算子

变异算子将父代的1个或多个基因点进行交换，如：父代为：123456，对第二个位置进行变化得：153426。

通过改进变异算子，构建M-变异算子，结合C-W算法得到NSGA-II-CW-M算法。M-变异算子可以避免种群出现过早收敛的情况，保证性状更好的个体进入种群，增加种群的多样性，在算法中局部搜索更好的解集。变异过程为：随机选择父代个体进行循环变异操作，对产生的新个体进行解码操作，根据支配关系判断变异后的子代是否可放入种群。若产生的新个体与父代个体形成支配关系时，变异个体替换被选择的父代个体；无任何支配关系时，则将新个体与种群中的其他个体比较。与种群中其他个体比较有无支配关系时，若形成支配关系，则直接放弃，继续变异操作；若新个体不支配种群中的个体，则将产生的变异个体放入子代，结束变异。流程如图4所示。

图4 改进变异算子流程

3.3.3 改进拥堵距离计算

拥堵距离计算可以使非支配排序边缘上的个体在下一代个体中更具有选择优势，拥堵距离是指计算同一支配层中，个体i相邻的个体i+1和i-1之间的距离。已有的计算距离方式存在将选择后的个体放入下一代解集时，易出现分布性不佳、局部最优的问题，针对该问题对拥堵距离计算进行改进，得到C-拥堵距离计算。改进前拥堵距离计算步骤：

Step1:初始化拥堵距离，令d=0；

Step2:对同一层级的个体按目标函数m排序；

Step3:令最大、最小个体的拥堵距离为d1=dend=inf；

Step4:求解其他个体的拥堵距离，即

(25)

Step5：对不同的个体重复Step2～Step4的操作，得到个体i的拥堵距离。

为了体现种群中个体分布的合理性，加强算法的收敛性，引入C-拥堵距离计算方式，定义如下:

(26)

其中，

(27)

N=

(28)

式中：M表示目标函数向着最优的方向前进；N表示让个体分布更加合理。M值越大个体的目标函数越优，收敛得越快；N值越大个体分布性更合理。综合这2个参数后，整合进C-拥挤距离计算方法中，得到I-NSGA-II算法。算法流程如图5所示。

4 算例分析

为验证改进算法的有效性，选取VRPTW数据集中C101中50个客户点，算例数据见表2。设计合理的物流配送路径，满足所有客户的货物需求，以及配送成本最小和客户满意度的目标。算法中种群数200，迭代次数500次，交叉概率0.9，变异概率0.3。根据市场调研得出以下参数：货物价格p2=250元/kg，时间敏感因子r=0.8，保质期T=30 000，运输制冷成本s3=0.2，卸货制冷成本s4=1，车辆最大载重200 kg，车辆的固定成本s1=730元/辆，油耗价格s2=2元/km，早到等待惩罚φ1=0.1元/min，晚到惩罚φ2=10元/min，车辆载重量为0时油耗ρ0=0.2 L/km，满载油耗为ρ*=1 L/km，碳税ω=2.61，p1=2。

表2 客户点坐标、需求、时间窗

改进算法通过C-W节约算法构建的初始解为7辆冷藏车的配送路径，初始解的配送成本为70 372.36，客户满意度为35.78。解码得到的配送路径如图6所示。

图6 C-W节约算法构造初始解

通过计算得到NSGA-II、NSGA-II-CW、NSGA-II-CW-M、I-NSGA-II算法最优解集分布图。NSGA-II-CW算法改进后的Pareto前沿分布较NSGA-II算法更好，算法有效搜索初始解构造的解空间；而未改进的NSGA-II算法表现较差，解集较为集中，易陷入局部最优解中。NSGA-II-CW与NSGA-II-CW-M比较，淘汰部分相似个体，为物流企业提供多种选择方案，保证了在配送成本最小的同时，顾客满意度最大。I-NSGA-II算法较NSGA-II算法性能提升明显，克服传统算法陷入局部最优解的问题。

在多目标函数条件下，Pareto解集中的任何一个解都是最优解，如图7所示。改进的算法得到的最优解集，客户满意度最大为45.57，最小为36.16；成本最大值为23 750，成本最小值为22 033.58。当客户满意度最大时使用7辆车对客户进行服务，最小时需要5辆车进行服务。

图7 改进前后Pareto前沿解分布对比

通过上述实验结果对比，通过对拥堵距离、变异算子的改进，得到的Pareto前沿解收敛性较好，解的多样性得到了保证，避免了传统算法中的早熟现象，证明了改进算法的有效性。

本文同时对多个算例进行了分析，分别选取C102、R01数据集中50个客户点，得到改进前后的算法前沿面如图8所示。NSGA-II算法解集分布较差，改进后的NSGA-II算法Pareto前沿解收敛、分布结果更好，进一步证明了算法的有效性。

(a)R101实验

5 结语

本文以配送成本最小、顾客满意度最大为目标对冷链物流配送路径优化进行了研究，提出了该问题的多目标模型。模型在考虑碳排放的同时，考虑冷链物流运输过程中生鲜产品的损耗，通过I-NSGA-II算法对模型求解。改进的算法构造良好的初始解，确保解空间可以更加趋于最优解集，避免出现局部收敛、早熟等问题。通过改进变异算子、拥堵距离计算，调整种群搜索方向，保持了种群的多样性。最后通过实验证明了本文所提算法的有效性，显著提升了收敛效率，对传统算法存在的问题也得到了一定的改进。