考虑碳排放的冷链多配送中心选址与路径优化

郜振华，朱兴伟

(安徽工业大学管理科学与工程学院 安徽 马鞍山 243032)

0 引言

生鲜产品本身的易腐性决定了冷链物流与其他物流不同，其时效性更为重要。顾客对产品本身新鲜程度的要求提高，对环保和碳排放问题的重视和关注，这些都给冷链物流带来挑战。因此，应合理有效规划冷链配送中心选址与路径。这与以往仅仅考虑路径问题不同，可以从整体上优化配送路径，降低选址成本和配送成本，提高配送的准时率，还能缩短配送里程，减低制冷成本与排放量，与此同时给顾客带来较高质量服务。

求解选址与路径优化问题有很多种算法，常用的有混合遗传算法[1]、蚁群算法[2，3]、混合免疫算法[4]等。国内外学者对冷链生鲜配送中心选址与路径问题进行不同研究，并且取得许多成果。Helena M[5]等人针对改善环境与经济效益的条件下，提出LDVRP模型，并且考虑在配送过程中的制冷排放，建立车辆路径模型；Okan Dukkanci[6]等人还提出了一种基于整数规划的算法和迭代局部搜索算法，从成本、燃料消耗和排放等方面分析若干参数对选址和路由决策的影响；Zhitao Xu[7]等人研究时变车辆速度和软时间窗的有能力的绿色车辆路径问题，将GVRP发展为一个包含燃料消耗计算算法的多目标混合整数非线性规划( MINLP )模型；张明亮等人[8]根据时间和产品的新鲜程度满意度建立多车型VRP模型；段砚等[9]、王旭坪等[10]研究在考虑碳规则下的冷链车辆路径优化问题，来减少在运输中的碳排放。

1 问题描述

本文研究的考虑碳排放冷链多配送中心选址及路径优化问题，具体为：某个生鲜电商的4个备选配送中心对N个客户进行配送；配送中心和客户点是已知的；客户软时间窗是已知的；冷藏车的相关数据是已知的。在符合文中给出的所有约束条件下，综合考虑最低成本、最大顾客满意度以及最低碳排放3个目标，对整体配送中心选址及路径方案进行优化求解。

为了科学研究的严谨性以及方便研究计算，本文对配送中心选址及配送车辆路径有着以下一系列基本假设：(1)配送车辆从配送中心出发到客户点，然后再回到配送中心形成一个闭环并且一条路线有一辆车配送。(2)一个客户点有且只能被一个配送中心和一辆车服务，并且一次性配送完成，避免二次配送。(3)配送中心只能对6公里内的客户点进行服务。(4)因为上班高峰期，凌晨5:30之后，时速从30 km/h降到20 km/h。(5)顾客不仅对车辆到达客户点的时间有要求，并且对农产品的新鲜程度也有着较高的要求。(6)为客户点服务的车辆有着统一容量、油耗、制冷成本，配送量不能超过车辆统一的容量。(7)每个客户点的需求量、坐标、能够接受的服务时间假设都是提前了解的，配送中心的固定成本和容量也是已知的。(8)车辆都是同时从配送中心出发的。

2 数学模型

2.1 符号及变量描述

文中涉及的符号及变量如表1所示。

表1 符号及变量描述

2.2 模型构建

2.2.1 成本目标函数

最低成本包括配送中心选址成本、配送成本、制冷成本3个部分组成。

(1)配送中心选址成本

配送中心选址是一个影响久远的战略决策，配送中心的选址直接影响到后来的车辆路径的设计，所以选址的重要意义显而易见。一个配送中心的成本通常包括租金c1、管理成本c2、制冷成本c3，改造成本c4，可以表示为

Cj=c1+c2+c3+c4

(1)

被选中的所有配送中心总选址成本

(2)

(2)配送成本

配送成本由于不同客户点的软时间窗不同，在配送车辆较少的前提下，选择最优的路径对提高顾客满意度、减低配送成本和碳排放都非常重要。配送成本包括制冷车辆的启动费和运输费，可以表示为

(3)

(3)制冷成本

本文将制冷成本与时间相联系，将制冷成本分为两个部分，一个部分为运输时的制冷成本，另一个则是为客户点卸货时(服务时间)的成本。可以表示为

(4)

2.2.2 顾客满意度

本文对顾客满意度研究从配送时间和产品的新鲜程度两个方面进行研究，并且以赋权的形式将这两种影响因素结合起来。

(1)送达时间的顾客满意度

已知客户最佳时间窗[Sta2Sta3]，如果配送车辆到达客户点时间在[Sta2Sta3]，则顾客满意度为100%；客户可接受服务时间[Sta1Sta4],假若配送车辆到达客户点的时间点在[Sta2Sta3]之外，在[Sta1Sta4]之内客户满意度随着时间变化而变化；如果配送车辆到达客户点的时间在[Sta1Sta4]之外，客户满意度则直接为零。客户满意度与配送车辆送达时间函数表达式

(5)

顾客送达满意度为

(6)

(2)产品新鲜程度的顾客满意度

产品的新鲜程度考虑到是因外部因素导致其新鲜程度的变化，因此，产品的新鲜度跟配送车辆到达客户点的时间有关，其函数表达式为F(t)=e-σti。产品新鲜程度的顾客满意度可以表示为

(7)

2.2.3 碳排放

碳排放量的消耗是燃油所直接造成的，车辆的这部分燃油消耗与客户节点配送的车辆在运输货物所行驶路程中的排放量以及车辆上货物制冷所消耗燃油的碳排放。

(1)车辆在运输货物所行使路程中的排放量

D*=∂1×φ(Qab)×dab

(8)

(2)车辆在运输货物所行使路程中制冷的排放量

D**=∂2dabQab

(9)

2.3 模型构建

综上所述，考虑的碳排放的冷链多配送中心选址及路径优化三目标模型为

(10)

maxS=εs1+θs2

(11)

minF=D*+D**

(12)

约束条件除了公式(5)之外，还有

(13)

(14)

(15)

(16)

(17)

xabk∈(0,1),a≠ba,b=1,2,…,n+m,k=1,2,…,l

(18)

xj∈(0,1),j=1,2,…,n

(19)

yji∈(0,1),j=1,2,…,n,i=1,2,…,m

(20)

式(13)表示每个客户点只能被一个配送中心服务，而且客户点也只能被一辆车配送。式(14)表示每辆车最多服务一个配送中心。式(15)表示每辆配送车都从配送中心出发，完成配送任务后再返回配送中心。式(16)表示在选择配送中心为客户点进行配送的时候，只有那些被选择的配送中心才能对客户进行配送。式(17)由于配送车辆载量有限，所有每条线路上客户点全部需求之和不能超过车辆的载量限制。式(18)、式(19)、式(20)为决策变量。

3 算法设计与测试

本文选用标准NSGA-III[11]作为基础算法进行求解，设计了改进的NSGA-III算法，记做I-NSGA-III。在I-NSGA-III中，考虑到需求解模型的复杂性，采取实数编码；同时使用基于进化阶段的自适应方法作为个体交叉率与变异率的调整方法过程并且采用模拟二进制交叉，增加算法的空间搜索能力，为算法后续操作的多样性奠定基础。

3.1 I-NSGA-III的算法求解过程

采用I-NSGA-III的算法求解考虑碳排放的冷链多配送中心选择及路径优化模型的流程如图1所示。

3.2 编码

标准NSGA-III算法所采用的编码规则并不适用于本文提出的考虑碳排放的冷链多配送中心选址及路径优化模型求解，本章提出的INSGA-III算法采用实数编码规则。首先，与其他常见的编码方法相比，实数(浮点数)编码方法能够表示范围较大的数，同时降低算法计算的复杂性，具有较高的精度和鲁棒性，适用于处理复杂的多约束优化问题。

3.3 初始种群

初始种群的优劣会直接影响算法迭代的执行效率，所以初始种群的生成方法和种群规模在一定程度上影响了帕累托解集的质量。而标准NSGA-II算法中的初始种群是随机生成的，并没有做太多的筛选限制。所以，本文在随机生成初始种群的基础上加入了筛选条件，通过对初始种群的配送中心的容量和辐射范围的限制，在一开始就将不满足条件的染色体直接淘汰，从而大大提高了初始种群的质量。

3.4 模拟二进制交叉算子

初始NSGA-III算法采用的单点交叉，本文I-NSGA-III进化产生新解过程是采用模拟二进制交叉，对于两个父体x1与x2，按照式(21)生成两个子个体x′1与x′2。

图1 I-NSGA-III算法流程图

(21)

其中，γ为随机变量，其在解的每一维上都需要重新生成，即

(22)

其中，μ是均匀分布于区间(0,1)上的随机数，η是交叉参数，其值为一常数。

3.5 自适应的交叉与变异

采用基于进化阶段的自适应方法作为个体交叉率与变异率的调整方法[12]。自适应交叉率与变异率的模型的两个部分如下。

(1)当非支配解个数小于10时，个体交叉概率与变异概率的模型为

(23)

(24)

(2)当非支配解的个数不小于10时，该情况下的个体交叉率模型不变，而变异率的模型为

(25)

当中PC、Pm分别是个体交叉率和变异率，N是迭代次数，L是个体编码的长度。N1、N2、β都是调节参数。

3.6 基于参考点的选择机制

标准的NSGA-III算法结构与标准NSGA-II算法相似，最大区别就是在与NSGA-III算法采用的是基于参考点对个体进行选择，而标准NSGA-II采用的是拥挤距离对个体进行选择，这使得NSGA-III在对3个及3个以上目标函数进行求解时不仅提高种群的多样性还降低计算代价。

3.7 算法有效性检测

为验证所提模型及方法的可行性和有效性，本文设计了算法测试。实验在MATLAB R2019a软件上实现，系统为Windows10专业版，处理为Intel(R) Core(TM) i5-4210U CPU @ 1.70 GHz～2.40 GH，运行内存8 GB的笔记本电脑上进行测试。

3.7.1 多目标算法评价指标

IGD为二元评价指标[13],通过计算真实帕累托前沿中所有解与算法求解出非支配解的平均欧式距离，从而评估解集的收敛性与多样性。IGD值越小，表示解集越逼近真实帕累托前沿且分布均匀，解集的收敛性与多样性佳。计算公式为

(26)

其中d(x*,X)表示解x*ep*到X中的最小欧式距离，|P*|表示P*内解的个数。

3.7.2 算法测试

为了评估基于模型的多目标I-NSGA-III算法的性能,本文选取4组测试函数: DTLZ1、DTLZ2、DTLZ3、DTLZ4分别对NSGA-II算法、NSGA-III算法、I-NSGA-III算法进行20次测试，表1为得到的评价指标IGD的均值，不仅可以评价算法的收敛性还能体现算法的多样性。设置种群为500，交叉概率为0.5，变异概率为0.05，分别测试M(目标函数的数量) 为3的实验，这是因为本文中模型的目标函数个数是3个。其结果如表2所示。

从表2中可以看出，I-NSGA-III在测试函数DTLZ1-4上的IDG值比较小。因此，可以说明I-NSGA-III算法求解时的多样性和收敛性更为优秀，同时也说明I-NSGA-III在解决三目标问题的优越性。

表2 IGD对比表

4 实例分析

4.1 已知条件

某企业欲在4个备选配送中心之中选择选性开放N个，对22客户点进行配送，备选配送中心与客户点散点图如图2所示，客户点的需求点，最佳时间，可接受时间，服务时间如表3所示，配送中心成本参数如表4所示，其他参数如表5所示。

图2 备选配送中心与客户点的散点图

表3 需求点的需求点和服务时间窗以及服务时间

表4 配送中心相关数据

4.2 运算结果

文采用I-NSGA-III算法对考虑碳排放的冷链多配送中心选址与路径模型进行求解，通过MATLAB R2019a软件上得帕累托解集，如图3所示。

如图3帕累托解集所示，可以清楚看出配送中心开放策略有3种且方案解分布广泛，说明了I-NSGA-III算法在求解时多样性。目标函数D与目标函数S成反比，目标S与目标F成反比，正是因为目标函数中存在反比例关系，才能求出帕累托解，而不是出现最优解。如果不对目标函数进行加权处理，就可以认为帕累托解集之内任意一个解都不比其他解差。因此，可以从图3帕累托解集中任意选出一个解得到其方案是开放第1和第3备选冷链配送中心，其配送路线如图4所示，成本为5570.97元，顾客满意度为0.87，碳排放为49.67 kg。

表5 实例相关参数汇总

图3 帕累托解集

图4 路径图

5 结论

本文在考虑到碳排放基础上，研究综合客户满意度的冷链多配送中心选址与路径优化问题。综合考虑成本、顾客满意度、碳排放3个目标，构建本文问题模型，采用改进的I-NSGA-III算法求解，并且对I-NSGA-III与NSGA-II和NSGA-III进行测试函数测试对比，结果显示I-NSGA-III求解时更具有多样性和收敛性。最后从实例求解的结果可以得知，在现有情况下随着开放第1和第3配送中心更能达到最高顾客满意度和一个较低碳排放量。本文可以为生鲜电商提供一些方案，企业若适当提高成本，既可以降低碳排放，又可以获得较高的顾客满意度。