考虑新鲜度约束的生鲜冷链配送路径优化研究

曹文彬 王婷

摘  要：随着生鲜市场交易规模日益增加，生鲜冷链配送中存在着“损耗高、保鲜率低、冷链流通率低、成本高”等一系列现实问题。因此可构建车辆使用成本、配送运输成本、配送制冷成本、碳排放成本、生鲜产品新鲜度和时间窗惩罚成本的生鲜冷链配送车辆路径优化模型，提出变邻域搜索改进遗传算法，并通过MATLAB软件对生鲜配送路径进行仿真得出配送总成本最优解，结果表明：变邻域搜索改进遗传算法（VNS-GA）求解的结果更加有效地避免了遗传算法出现局部最优解的情况，同时能降低总配送成本。

关键词：生鲜产品新鲜度;模糊时间窗;遗传算法;变邻域搜索

中图分类号：F252.14    文献标识码：A

Abstract： With the increasing transaction scale of fresh market， there are a series of practical problems in fresh cold chain distribution， such as high loss， low preservation rate， low circulation rate of cold chain and high cost. Therefore build vehicles using cost， distribution cost of transportation， distribution， refrigeration， carbon cost， fresh product freshness and time windows penalty cost of fresh cold chain distribution vehicle routing optimization model， provide VNS-GA and through the distribution path fresh simulation software MATLAB distribution total cost optimal solutions， the results indicate that the results of the VNS-GA is more effective to avoid the genetic algorithm local optimal solution， and reduce total distribution costs.

Key words： fresh product freshness; fuzzy time window; genetic algorithm; variable neighborhood search

0  引  言

随着人们工作节奏的不断加快和对生活品质要求的逐步提高，我国居民对选择蔬菜水果类生鲜产品送货上门的社区生活方式需求程度空前高涨。但是蔬菜水果类生鲜产品在配送过程中存在的“损耗高、保鲜率低、成本高”等问题仍未得到有效解决，因此研究如何以最小的成本将最新鲜的生鲜产品准时配送到用户手中的问题具有现实意义。

生鲜冷链物流配送路径问题是在传统车辆路径问题（VRP）上考虑生鲜产品时效性、易损耗的特性上进行的扩展和延伸。由于生鲜产品时效性强，Solomon等首次将服务时间窗引入了VRP问题[1]。李娜以硬时间窗为约束条件构建车辆配送成本最小的生鲜食品配送模型，并且通过改进蚁群算法来求解该问题[2]。由于现实配送过程中客户对不能在指定时间窗内送到并不会直接拒绝，因此马雪丽等以软时间窗为约束条件考虑食品生命周期服从负指数分布的损耗成本，构建供应商利润最大化为目标的易腐食品生产调度和路径优化联合的问题，并应用改进遗传算法进行求解[3]。对于生鲜产品易损耗的特征，Ghezavati V R等以生鲜农产品新鲜度和成熟度来构建零售商利润最大为目标的配送路径优化模型[4]。李桂娥以配送时间和卸货温度差对产品新鲜度影响来刻画生鲜货损成本，构建配送总成本最小为目标的生鲜产品冷链物流配送路径问题，并通过节约成本法进行求解[5]。刘炎宝等考虑生鲜产品新鲜度下降的惩罚成本，结合碳排放成本构建生鲜农产品冷链物流配送车辆路径优化模型，并采用禁忌搜索的改进遗传算法对其求解，结果验证了改进后算法比传统遗传算法得到结果更优，加快了收敛速度同时配送成本更低[6]。

国内外生鲜产品冷链物流车辆路径问题研究领域中，考虑生鲜产品新鲜度和时间窗共同约束的文献较少，研究不足，因此将新鲜度和时间窗惩罚成本囊括进配送目标函数更能丰富或完善该项研究。本文将重点研究如何以最小化配送成本将生鲜产品送到顾客手中，目的是在有效地降低配送成本的基础上提高人们对生鲜产品新鲜度的满意度。

1  生鲜冷链物流配送路径问题描述及建模

1.1  问题描述与假设

本研究以一个生鲜冷链物流配送中心，多个顾客需求点来考虑生鲜产品配送服务车辆路径问题。在顾客新鲜度和时间窗要求等约束条件下构建配送总成本最小化的生鲜冷链物流配送路径优化模型，并基于生鲜冷链物流配送特征，进行如下假设：

（1）仅有一个配送中心，且可使用车辆有限，车辆均为同一类型，且已知其最大载重;

（2）配送车辆从配送中心发出，独立完成配送任务后回到配送中心处，配送车辆从配送中心出发最后返回配送中心，均要符合配送中心的工作时段;

（3）顾客需求独立不可分割，且需求量不大于车辆的最大载重;

（4）每一条路线上只安排一辆车，避免车辆浪费;

（5）每辆配送车辆可以服务多个顾客节点，但是每个顾客只能由一輛车进行配送;

（6）服务系统允许缺货，一旦缺货，需求就流失;

（7）生鲜产品从储存到配送处于恒温下，不考虑温度对产品变质的影响，新鲜度仅与时间相关;

（8）车辆配送过程中行驶速度被假定是不变的。

1.2  相关参数表示

1.3  配送成本分析

（1）车辆使用成本

车辆单次使用成本包括车辆单次损耗折旧费用和人工费用的总和。

C=c*Z                                            （1）

（2）配送运输成本

假设需求点处的坐标位置是提前已知的，但是在现实中道路并不是呈直线状态，为了研究方便假设距离为直线距离，并且采用欧几里得直线距离表示，定义D为从i到j的直线距离，如式（2）所示。生鲜配送运输总成本如式（3）所示。

d=                                         （2）

C=c*d*X                                        （3）

（3）制冷成本

生鲜产品为了更好地维持新鲜度需要在配送过程中将采用冷藏车进行配送，冷藏车将从生鲜配送中心出发直到最后一个需求点完成服务都会产生制冷成本。本文将生鲜产品配送过程中的总制冷成本分为配送过程中制冷成本和卸货过程中制冷成本，如式（4）所示。

C=c*d*Z+y*st*c                                  （4）

（4）碳排放成本

生鲜配送过程中自身油耗加上制冷效果，排放的CO2比普通货物配送产生的CO2要多，冷链配送过程主要涉及到的碳排放，是由车辆油量燃烧产生的，而车辆油量燃烧又与运输距离相关。本文计算配送过程中将以碳排放成本以单位距离碳排放成本和行驶距离乘积为结果。

C=cd                                          （5）

（5）生鲜产品新鲜度惩罚成本

由于生鲜产品新鲜度函数随时间推移会发生变化，因此本文分析生鲜产品新鲜度随时间变化的函数如式（6）所示。

ft=2-e， β>0， 0≤t≤                                      （6）

其中：β为新鲜度衰减系数，β值越大，代表新鲜度衰减速度越快。t=0时，ft=1，代表生鲜产品从配送中心送出时生鲜的新鲜度最佳。t=时生鲜产品新鲜度衰减到0，表示生鲜产品失去全部食用价值。如图1表示生鲜产品新鲜度与时间的关系。

图1中表示，当配送车辆到达配送点时，生鲜产品新鲜度f，假设顾客期望的生鲜产品新鲜度为f，最低能接受生鲜产品新鲜度为F，因此若当配送车辆到达配送点时，生鲜产品新鲜度f>f，则满足顾客满意度为100%，对产品或公司增加了好感度，则会产生相应的激励成本，随着用户对生鲜产品的要求能力越高，单位激励成本φ值越大;当配送车辆到达配送点时，生鲜产品新鲜度F

W=φmaxe-e， 0+φmaxe-e， 0                        （7）

（6）配送时间窗不准时惩罚成本

本文将研究模糊时间窗的情况，假设顾客预约配送服务的时间为s，e，如果在预约服务时间窗内配送，则不会产生顾客不满意惩罚成本。但是在实际的配送过程中，不合理的配送安排或者交通拥堵都可能导致车辆在与顾客预约的时间之前或者之后到达，这就会降低顾客满意度。设S代表顾客能接受的最早服务时间，E代表顾客能接受的最晚服务时间，在S，s或E，e时间范围内，顾客满意度随着与指定时间的差距增大而减小。当配送车辆在S，E时间范围外到达，则顾客不满意惩罚成本为无穷大。顾客对配送时间滿意函数如图2所示。

由于顾客对配送服务窗早到和迟到均会产生不满意的情绪，降低生鲜电商企业的信誉，所以对早到和迟到都做惩罚因素，本文假设顾客对早到的厌恶程度比迟到的厌恶程度更大，因此早到的单位时间惩罚成本θ1小于迟到的单位时间惩罚成本θ，因此配送不准时产生惩罚成本如式（8）所示。

W=θmaxs-t， 0+θmaxt-e， 0                               （8）

1.4  模型构建

通过对相关成本进行分析后得到生鲜冷链物流配送总成本的模型如式（9）所示。

MinZ=c*Z+c*d*X+c*d*Z+y*c*st+C*d

+φmaxe-e， 0+φmaxe-e， 0+θmaxs-t，0+θmaxt-e，0

約束条件如下：

0≤Z≤Q， i=1，2，…，N+1， k=1，2，…，k                                  （10）

x=1， i=1，2，…，N                                        （11）

y=K， x=1， i=1，2，…，N， k=1，2，…，k                                （12）

W=   i=1，2，…，N                                 （13）

W=    i=1，2，…，N                                  （14）

t=t+g+*x， i=1，2，…，N+1， k=1，2，…，K， j=1，2，…，N+1                          （15）

t≤wt， j=1，2，…，N                                           （16）

x=y， x=y， i，j∈1，2，…，N， k=1，2，…，K                             （17）

式（9）表示配送总成本最小，包括车辆使用成本、运输成本、制冷成本、碳排放成本、新鲜度和时间窗惩罚成本;式（10）表示在车辆k的最大容量，也就是确保每一次配送中心出来的货物数量会满足顾客的需求。式（11）表示每一条路线上只有一辆车，也就是每一个顾客最多由一辆车配送服务。式（12）表示车辆从配送中心处出发配送结束后又回到配送中心。式（13）表示生鲜产品惩罚成本只要是指车辆到达顾客的时间是早于顾客期望新鲜度时间点t或者介于顾客期望新鲜度时间点t和最低能接受新鲜度时间点t之间。式（14）表示时间窗惩罚成本只要是指车辆到达顾客的时间是早于s或者晚于e。式（15）表示在配送车辆k路线上需求点j的到达时间等于需求点i的到达时间加上g服务时间再加上需求点i到j的路上行驶时间。式（16）表示配送车辆K在路线上需求点j到达时间必须小于等于每天的工作时间。式（17）表示到达每个需求点的车只有一辆。

2  变邻域改进遗传算法求解

遗传算法（Genetic Algorithm，GA）最早是由美国的John Holland提出，是一种模拟生物自然进化现象的全局性随机搜索算法。该算法通过借鉴达尔文的物种进化理论，采用选择、交叉、变异操作模拟自然界遗传机制，是一种基于种群的优化方

法[7]。变邻域搜索算法（Variable Neighborhood Search，VNS）最早是由Mladenovi和Hansen提出的一种局部搜索方法，主要包括随机扰动、局部搜索和邻域变换等三个过程[8]。其主要思想是通过改变邻域结构以提高局部搜索能力，避免过早陷入局部最优。因此本文结合GA和VNS各自优势，提出一种优化方法变邻域遗传搜索算法（Genetic Algorithm-Variable Neighborhood Search，VNS-GA）。针对每代种群，VNS-GA首先将GA搜索到的最优解作为VNS的初始解，然后通过不同的邻域结构进行局部搜索。与传统GA算法相比具有较好的全局和局部搜索能力。

（1）编码与解码

本文的遗传算法使用整数编码的方式，假设现有3辆车，8个需求点的编码方式为0，1，2，3，0，4，5，6，0，7，8，0表示调用了三辆车进行配送即含有三条子路径，0表示配送中心，即第一辆车的配送路线为0-1-2-3-0;第二辆车的配送路线为0-4-5-6-0;第三辆车的配送路线为0-7-8-0。

（2）种群初始化及适应度函数

本文初始种群采用随机生成的方式生成，以保证个体的多样性。适应度值用来衡量种群中个体质量的优劣，染色体对应的路径方案的成本越低，该路径方案对应的解适应度值越高。本文模型的目标函数是降低路径方案的生鲜产品冷链物流配送总成本，因此本文所设计的算法中将目标函数的倒数作为适应度函数。成本越低，解的适应度值越高。

（3）选择算子

本文选擇轮盘赌法作为选择算子。轮盘赌选择算子思路如下：

第一步：将种群中的每个个体代入适应度值函数，计算适应度值f和种群所有个体的适应度值之和F。

第二步：计算种群中每个个体被选择的概率，计算公式如式（18）。

p=                                                 （18）

第三步：计算选择累计概率，组成轮盘，计算公式如式（19）。

P=p                                               （19）

第四步：生成0至1间的随机数n，当n

第五步：进行种群规模次轮盘赌选择，生成新的下一代的种群。

（4）交叉算子

交叉算子在遗传算法中有助于提升算法的全局搜索能力，为了避免交叉过程中可能产生重复个体。本文交叉算子首先生成两个点作为交叉区间的两个端点，将序列中进行互换的基因序列放到另一个染色体的前方，从左往右遍历序列，删除互换基因序列中与原序列中重复的基因，删除重复元素后得到交叉后的两个新个体，如图3所示。

（5）变异算子

变异算子决定算法的局部搜索性能。本文选择Swap算子作为变异算子，在种群中随机选择的一个个体中随机选择要变异的两个基因位置，将两个位置的基因交换得到新的个体，如图4所示。

（6）邻域结构

本文采用的邻域结构有2种：逆序变化、互换变化。具体过程如图5所示。

（7）设定终止条件

本文算法采用的终止条件是设定最大进化代数，当迭代次数达到这个最大进化代数时算法停止运行。

通过上述描述，归纳变邻域搜索遗传算法的主要步骤如下：

Step1：编码与解码。通过参数编码将实际的解空间映射为遗传算法处理的遗传空间，通过解码将遗传空间转化成实际的解空间;

Step2：设置算法参数。包括种群规模、交叉概率、变异概率和最大终止次数，确定适应度函数;

Step3：种群初始化。随机产生一定数目的初始解，其数目应适中，保证个体多样性;

Step4：计算个体适应度。根据个体对应的目标函数值来计算其适应度大小，采用轮盘赌方式选择适应度大的个体遗传给下一代;

Step5：对选择的每个个体，按一定的概率进行交叉、变异等操作不断产生子代;

Step6：对当前代最优解进行VND邻域搜索，得到邻域最优解，若搜索到邻域解优于当前最优解，则进行替换，否则在下一邻域结构中继续搜索，直到全部邻域结构均未找到优于当前最优解则结束本次搜索;

Step7：回到步骤Step4直至满足终止条件时停止进化。

3  算例分析

参考M生鲜电商企业的一个生鲜配送中心为城区配送各个生鲜需求节点的历史数据，随机产生各个需求点的配送需求q，且单个生鲜节点的需求量不超过生鲜电商配送中心车辆的最大核定载重量。假设车辆最大载重量Q=300kg，配送车辆每天早上6：00发车，每个客户点的服务时间小于30分钟，若车辆超过顾客期望时间窗则支付无穷大时间惩罚成本M，配送生鲜产品不能达到顾客最低能接受的新鲜度惩罚成本无限大。模型中相关参数取值和算法中相关参数表如表1所示。

随机选取某生鲜电商配送中心附近的20个需求节点，为了便于计算顾客节点之间的空间距离，生鲜电商配送中心和各个需求点形成横纵x，y坐标点分布如图6所示。

通过整理上述坐标和随机生成的各个生鲜超市节点需求量以及时间窗得到所有需求节点的相关信息如表2所示，生鲜超市节点的序号从1～20表示，生鲜电商配送中心序号为0的节点。

本文采用Matlab R2018a软件进行编程，根据上述实例的具体数据分别对传统遗传算法和变邻域搜索改进后的遗传算法进行求解，得到该算例分别在两种算法情况下的车辆最优路径如图7所示，最优车辆配送路线、配送成本及行驶距离如表3所示。

从表3中可以看得出变邻域遗传算法求解出来的最优车辆路径总成本和行驶路径为972.4元和206.21km，而传统遗传算法求解出来的最优车辆路径总成本和行驶距离为1 112.6元和232.64km。在两种不同规模需求点配送情况下变邻域遗传算法求解的总成本比传统算法求解的结果分别减少了12.6%和11.4%。由此可见变邻域遗传算法对M生鲜电商公司配送周边生鲜需求点的冷链物流配送路径求解结果比传统遗传算法配送路径总距离更短、配送总成本更低，为了更好地体现各项成本之间的差异，需要对上述配送路径的各项成本具体的分析如表4所示。

从表4中可以看出对时间窗而言，算法中的惩罚成本都是最小的，即车辆配送的时效性比较好，顾客满意度比较好。对于配送车辆运输成本应用改进后遗传算法求解得到的结果比传统遗传算法降低了11.4%。为了保证生鲜产品新鲜度高，变邻域遗传算法改进后生鲜产品新鲜度惩罚成本较传统遗传算法成本降低了33%。制冷成本应用变邻域遗传算法求解得到的结果比传统遗传算法降低了11.4%。

由此可见变邻域遗传算法求解出来的配送总成本和行驶路径长度均小于传统遗传算法的求解结果，从各项成本具体分析可见，变邻域改进后遗传算法求解后，生鲜新鲜度惩罚成本、运输成本等降低幅度明显，表明在降低配送总成本的基础上可以更好地满足顾客要求，有利于生鲜企业长期发展，同时验证了生鲜冷链物流配送路径优化模型的可行性和有效性。

4  结  论

本文以车辆固定成本、运输成本、制冷成本、碳排放成本、生鲜产品新鲜度和时间窗惩罚成本之和最小化为目标，构建生鲜冷链物流配送路径优化模型，并结合变邻域搜索对遗传算法改进的模型进行求解。以M生鲜电商公司一个配送中心、20个需求配送点为案例，将传统遗传算法求解结果与变邻域搜索改进后遗传算法求解结果进行对比，结果表明变邻域搜索改进后的遗传算法有效降低了生鲜产品冷链物流配送总成本，同时在顾客指定时间窗内减少了生鲜产品新鲜度的损耗，提高了顾客满意度。因此本文所建模型和求解算法对于生鲜产品冷链物流配送路径问题具有适用性和有效性，为生鲜冷链物流发展提供支持。

参考文献：

[1]  Solomon M M， Desrosiers J. Time Window constraint routing and scheduling problems[J]. Transportation Science， 1988，22（1）：1-13.

[2] 李娜. 不确定需求和配送时间窗约束下的供应链优化[J]. 计算机仿真，2015，32（4）：424-428.

[3] 马雪丽，王淑云，刘晓冰，等. 易腐食品二级供应链生产调度与配送路线的协同优化[J]. 工业工程与管理，2017，22（2）：46-52.

[4]  Ghezavati V R， Hooshyar S， Tavakkoli-Moghaddam R. A Benders' decompose tion algorithm for optimizing distribution of perishable products considering postharvest biological behavior in agri-food supply chain： a case study of tomato[J]. Central European Journal of Operations Research， 2017，25（1）：29-54.

[5] 李桂娥. 生鮮农产品冷链物流配送路径优化研究[J]. 物流科技，2019，42（10）：68-72.

[6] 刘炎宝，王珂，杨智勇，等. 考虑碳排放与新鲜度的冷链物流配送路径优化[J]. 江西师范大学学报（自然科学版），2019，43（2）：188-195.

[7] 孙琦，戢守峰，刘旭. 基于变邻域搜索算法的物流配送系统集成优化研究[J]. 工业技术经济，2016，35（8）：46-55.

[8] 张晓楠，范厚明，李剑锋. 同时配集货定位—路线问题的变邻域分散搜索算法[J]. 计算机集成制造系统，2015，21（9）：2535-2548.