基于NSGAII的带时间窗生鲜品配送路径优化

李善俊 陈淮莉

摘要：考虑到生鲜品的易腐性、高时效性和对运输环境要求高的特点，为减少生鲜品配送企业的配送成本，提高客户满意度，在车辆载重、时间窗、生鲜品保质期等约束条件下，提出将配送总成本最小化和生鲜品新鲜度最大化的多目标车辆路径优化模型。利用改进的非支配排序遗传算法（non-dominated sorting genetic algorithm Ⅱ，NSGA Ⅱ）对模型进行求解。求出满足配送总成本最小和生鲜品新鲜度最大的相对较优解，证明模型的有效性。该模型在大规模配送和客户地理位置分布较为分散的情况下，对生鲜品新鲜度的优化较为明显。

关键词：
生鲜品配送; 多目标优化; 非支配排序遗传算法（NSGA）; 带时间窗的车辆路径问题（VRPTW）

中圖分类号：
F252    文献标志码：
A

Optimization of fresh food distribution route with

time window based on NSGA II

LI Shanjun， CHEN Huaili

（Institute of Logistics Science & Engineering， Shanghai Maritime University， Shanghai 201306， China）

Abstract：
Considering the characteristics of fresh food perishability， high timeliness and high demand for transportation environment， in order to reduce the distribution cost of fresh food distribution companies and improve customer satisfaction， under the constraints of vehicle load， time window and shelf life of fresh food， a multi-objective vehicle route optimization model is proposed to minimize the total cost of distribution and maximize the freshness of fresh food. The model is solved by an improved non-dominated sorting genetic algorithm （NSGA II）. A relatively better solution satisfying the minimum total cost of distribution and the maximum freshness of fresh food is obtained， which proves the validity of the model. The optimization on the freshness of fresh food by the model is obvious under the condition of large-scale distribution and scattered distribution of customers.

Key words：
fresh food distribution; multi-objective optimization; non-dominated sorting genetic algorithm （NSGA）; vehicle routing problem with time window （VRPTW）

0 引 言

近年来，互联网的迅猛发展让生鲜企业的业务范围从线下延伸到了线上，生鲜电商企业迎来了飞速发展的黄金时期。鉴于生鲜品易腐烂、高时效性的特点，对生鲜品配送企业提出了比传统的物流配送更高的要求。生鲜品的配送是生鲜电商的重要组成部分，也是影响生鲜电商企业发展的最大的一块绊脚石。

国内外许多学者，对生鲜品配送问题做了广泛研究。TAGMOUTI等[1]考虑了服务成本、配送成本和逆向物流成本，构造了车辆路径优化模型，并重新设计了算法进行求解;TSANG等[2]提出了在生鲜品配送过程中采用多温带模型，并利用遗传算法减小运输过程中的食物腐败率;OSVALD等[3]研究了带配送时间窗和顾客时间窗的车辆路径优化问题，并设计了算法求解冷链配送问题;SONG等[4]研究了在冷藏车和普通车共同配送环境下，以消费者满意度最大为目标的生鲜品配送路径问题;WANG等[5]从低碳物流和环境保护的角度研究生鲜品配送问题，考虑碳排放成本，并利用改进遗传算法对模型进行求解，并研究了碳税政策对配送成本和碳排放的影响;TANG等[6]应用节约算法和蚁群算法对配送中心与超市之间的农产品冷链配送问题进行了研究;马帅[7]研究了生鲜食品的配送中心选址和配送路径优化问题;李嘉栋等[8]通过逻辑斯蒂方程来表示保质期与变质成本的关系，并对生鲜品的生产与配送进行了研究。范厚明等[9]考虑到生鲜品对时效性敏感的特点，有针对性地设计了时间窗和惩罚成本，构建了以总成本（包括车辆运输成本、时间窗惩罚成本和生鲜品变质成本）最小为目标的优化模型，并利用蚁群算法对模型进行求解;翟恒星[10]对O2O模式下的生鲜冷链配送优化和路径规划问题进行了研究，构建了一种新型的配送供应链模型，建立了实体店选址与配送为一体的数学模型，并利用基于字典顺序的求解方法对模型进行了求解;杨晓华等[11]针对生鲜电商的需求不确定性以及退货问题，提出了模糊环境下多周期生鲜闭环物流网络系统，并利用遗传算法和粒子群算法进行求解;陈久梅等[12]针对生鲜农产品多品种、小批量、易变质等特性，采用多隔室配送车辆对生鲜品进行冷链配送，并以配送成本最小为目标建立模型，采用粒子群算法对模型进行了求解。

近年来，少数学者开始将生鲜配送与多目标车辆路径问题联合起来进行研究。侯宇超等[13]对配送过程中的配送成本、客户满意度和污染物排放3个目标进行了研究;丁欢[14]对客户满意度和配送中心选址进行了研究。然而，少有文献将生鲜品的新鲜度与多目标车辆路径问题联系到一起。基于此，针对带时间窗的多目标生鲜品配送路径优化问题（multi-objective vehicle routing problem with time window dealing with perishable products，MO-VRPTW-P），结合相关理论与方法，建立MO-VRPTW-P模型，并利用改进的（即带精英策略的）非支配排序遗传算法（non-dominated sorting genetic algorithmⅡ，NSGA II），求出满足配送总成本最小和生鲜品新鲜度最大的相对较优解，验证MO-VRPTW-P模型的有效性。

1 问题描述与MO-VRPTW-P模型的建立  基本的带时间窗的车辆路径问题（vehicle routing problem with time window， VRPTW）如下：一组车辆从配送中心出发，将货物运输给各个客户，并在运输任务完成后返回配送中心;每个客户的地理位置和需求量是已知的;配送车辆有最大载荷限制;要求在特定的时间段内交付货物给客户;要求合理的行车路线实现优化目标。

结合生鲜品运输的特点，本文将MO-VRPTW-P描述为：一个配送中心对多个随机客户点进行配送服务，在此服务过程中，从企业利益角度出发将配送总成本最小作为追求目标，从客户角度出发将生鲜品新鲜度最大作为追求目标，以期企业和客户的利益都得到满足。企业的配送总成本包括固定成本、运输成本、惩罚成本和产品变质成本。在配送过程中，每个客户都有不同的时间窗：早于时间窗到达的车辆，必须等待;晚到的车辆，会受到一定的惩罚。为表示生鲜品在运输过程中的新鲜状态，参考文献[15]，考虑生鲜品的质量随着运输时间ti加速递减的特点，令φ（ti）=etiln 2/Ti-1，这里φ（ti）为生鲜品的损耗比例系数，Ti 为客户i的生鲜品保质期。用β（ti）=1-φ（ti）=2-etiln 2/T 表示生鲜品的新鲜度。

由于MO-VRPTW-P较为复杂，为便于对现实问题进行研究，假设：（1）客户的地理位置、需求量和时间窗以及产品的保质期等信息已知;（2）所有的距离采用欧几里得距离表示;（3）客户点之间的配送时间等于欧几里得距离;（4）每个顾客只能接受一辆车的一次配送服务;（5）从配送中心出发的车辆必须返回原配送中心;（6）车辆的实际装载量不能超过其核定载荷;（7）生鲜品离开配送中心时处于最大新鲜状态。

模型参数：N={1，2，…，n}为全部客户需求点集合，0为配送中心;M 为车辆集合，m∈M; C为车辆最大载荷;si为服务客户i的时间;tij为从客户i到客户j的配送时间;dij为从客户i到客户j的距离;di为客户i的需求量;cm为车辆m的单位距离运输成本;ei为客户i时间窗起始时刻;li为客户i时间窗结束时刻;w（m）i为车辆m到达客户i的时刻;fm为车辆m的固定成本;Ti为客户i的生鲜品保质期;β为客户可以接受的最低新鲜度;β（ti）为客户i收货时的生鲜品新鲜度;q1为等待成本惩罚系数;q2为延误成本惩罚系数;q3为变质成本惩罚系数。

决策变量：x（m）ij=1， 车辆m从客户i到达客户j

0， 其他

y（m）i=1， 车辆m访问客户i

0， 其他  构建配送总成本最小和生鲜品新鲜度最大的双目标数学模型如下，其中除有特殊说明外，i∈N，j∈N，m∈M。

min f （1）=i，j，m（x（m）ijtijcm）+j，m（x（m）0jfm）+

q1i，j，m（x（m）ijmax （ei-w（m）i，0））+

q2i，j，m（x（m）ijmax （w（m）i-li，0））+

q3i，j，m（φ（ti）dix（m）ij）

（1）

max f （2）=Ni=0（β（ti）di）Ni=0di

（2）

s.t.

i（y（m）idi）≤C

（3）

ix（m）ij=ix（m）ji

（4）

m ix（m）ij=m jx（m）ij=1

（5）

m ix（m）0i=m jx（m）j0=1

（6）

w（m）i=w（m）i-1+si-1+t（i-1）i

（7）

β（ti）≥β

（8）

x（m）ij∈{0，1}

（9）

y（m）i∈{0，1}

（10）

式（1）表示配送总成本最小，配送总成本包括固定成本、运输成本、等待成本、延误惩罚成本和变质成本;式（2）表示生鲜品运达时其平均新鲜度最大;式（3）为车辆载荷约束;式（4）表示到达客户与离开客户的车辆相同;式（5）表示所有客户均得到服务且仅被一辆车服务;式（6）保证从配送中心出发的车辆必须返回该配送中心;式（7）表示车辆m到达客户i的时间;式（8）保证生鲜品新鲜度满足客户的最低新鲜度要求;式（9）表示车辆m是否从客户i到达客户j，若是则x（m）ij=1，否则x（m）ij=0;式（10）表示車辆m是否访问过客户i，若是则y（m）i=1，否则等于y（m）i=0。

2 帕累托最优和NSGA II

2.1 帕累托最优

在求解单目标问题时，可以在所有的候选解中选出最好的解作为最优解。然而，在多目标优化问题中，因为各目标相互冲突，所以最优解不一定只有一个。由于不能简单地进行比较，通常能够求得不比其他任何解差的解，这种解成为帕累托最优解或者非支配解，同时帕累托解的目标变量集合称为帕累托前沿。

2.2 NSGA II

本文主要采用NSGA II，其整体过程与普通遗传算法大同小异，都要经历编码、种群初始化、选择、交叉、变异、迭代等过程，与普通遗传算法稍有不同的是：在初始化种群之后的步骤中，其在计算个体适应度环节进行了快速非支配排序和拥挤度比较，并且在算法选择时引入保存精英策略，保证了个体的多样性。首先阐述NSGA II的两个核心步骤，即快速非支配排序和拥挤度比较。

2.2.1 快速非支配排序

首先定义2个变量wp和sp，wp表示解p被支配的数量，sp表示解p支配的解的集合，w=0表示该解为非支配解。如图1所示：对于一个有多个目标函数且均为求解其最小值的问题（本文中的目标函数f （2） 为求其最大值，为便于计算，将其倒置，转化为求其最小值问题），图中每个点都表示一个解;对于c点而言，由于a、b两点的目标函数f （1） 、f （2） 所对应的值都优于c点，因此c点被a、b两点支配，wc=2，同理sb={c，d，e}。寻遍解集中的所有点，计算出所有点所对应的w值和s值，将w=0的点划入F1（帕累托第一前沿），然后删去w=0的点;重新遍历计算各点所对应的w值和s值，将新的w=0的点划入F2（帕累托第二前沿）;以此类推，直到所有的点都被划分到对应的前沿中，得到F1F2…（符号表示优先）。

2.2.2 拥挤度比较

通过快速非支配排序方法可以对所有的解进行排序，将解归属到不同的帕累托前沿，帕累托前沿越小，解的优先级越高。若两个解都属于同一个帕累托前沿，则需对解进行进一步处理，称这个过程为拥挤度比较。以图2中的a点为例（假设a、b、c均处于同一个帕累托前沿），以a点左右邻近的两个解为顶点构造矩形，矩形的平均边长作为a的拥挤距离。当两个解属于同一个帕累托前沿时，优先选择拥挤距离大的解，这样可以保证种群的多样性。当两个解属于不同的帕累托前沿时，帕累托前沿越小，解的优先级越高。

2.3 编码

编码是设计遗传算法的第一步，也是遗传算法在解决实际问题中极为关键的步骤。所谓编码就是将求解问题的解空间映射到编码空间（即搜索空间）的过程，它对搜索过程影响很大。本文染色体编码采用自然数编码，每个基因代表一个客户，在客户序列中插入“0”表示配送中心，并在首尾处插入“0”以表示车辆从配送中心出发最终又回到配送中心。这种编码方式的优点在于可以非常方便地将信息输入染色体中，无须额外的解码和计算。例如染色体{0，5，7，9，0，3，1，0，2，8，4，6，0}代表3条路径：0-5-7-9-0、0-3-1-0和0-2-8-4-6-0。

2.4 种群初始化

种群初始化是遗传算法的开端，一个好的起点对问题的求解至关重要。本文随机生成n个客户点，并在首尾处插入“0”，如（0，i1，1，…，i1，n，0），根据车辆最大载荷和时间窗要求初始化染色体。当考虑车辆载荷约束时，若rj=1di1-j≤C且r+1j=1di1-j>C，则在第i1，r个客户与第i1，r+1个客户之间插入0，或者将客户向前或向后移动一个位置再插入0;同理，当考虑时间窗约束时在第i1，r个客户与第i1，r+1个客户之间插入0，或者将客户向前或向后移动一个位置再插入0;重复以上步骤，直到产生足够的种群数量。

2.5 选择操作

本文中的选择操作主要存在于两个过程中。第一个选择操作是算法刚开始，与普通遗传算法一样，在生成子代的过程中采用锦标赛选择法，从父代中选择个体进行交叉和变异，生成新的子代。第二个选择操作就是NSGA-II的核心部分，在第2.2.1节和第2.2.2节中已详细介绍。

2.6 交叉算子

为避免交叉过程中产生不可行解，提高算法的收敛效果，并且保留优良基因，采用最大保留交叉方法。首先，从两个父代染色体中分别选择一段基因作为保留区域。此过程中，要确保两个基因段长度相同并且有相同的起始序列，为防止交叉后生成的染色体出现基因段缺失，选择的基因段包含的配送中心（即编码基因为0）数也必须一致。两个父代染色体P1、P2分别删去对方染色体保留区域的客户基因，最后按顺序覆盖对方非保留区域的基因，并生成两个子染色体。如染色体P1=017506380240， P2=034207180650，若P1的保留区域为0638，P2的保留区域为0718，则p′ 1=056307180240，p′ 2=042706380150。显然，从路径中删除部分客户，不会违背车辆载荷约束和时间窗约束，因此生成的子染色体一定是可行的。

2.7 变异算子

在一条染色体上选择两个变异点，变异点之间的区域称为变异段，将变异段进行逆转变异，生产新的个体。如染色体p=0123‖456‖7890，变异后生成p′=0123‖654‖7890。

2.8 终止条件

当迭代次数达到设定最大迭代次数1 000时终止。

3 实验仿真与分析

案例数据主要来自国外著名学者Solomon对VRPTW的研究数据集。目前，国外关于VRPTW的研究，大多以Solomon的数据集为参照。在Solomon研究的VRPTW中，一共设计了6类问题，即R1、R2、C1、C2、RC1、RC2，其中R类（random）表示客户的地理位置是随机均匀分布的，C类（clustered）表示客户的地理位置是聚集分布的，RC类表示客户的地理位置是混合分布的。在此基础上，又将R、C、RC类分为1类和2类：1类表示调度范围较小，在配送路径上有较少的客户对象;2类表示调度范围较大，即要服务的客户数量比较多。本文所使用的数据来自Solomon的R103中的100组数据，由于Solomon公开的研究数据均无量纲，故下文所有数据均无量纲。由于Solomon的数据集中只包括客户坐标、时间窗开始时刻和结束时刻、服务时间和客户需求量，不包括本文中的另一个重要参数——生鲜品的保质期Ti ，因此为便于研究，特在选择的客户时间窗结束时刻li的数据的基础上，随机加减50生成保质期Ti。算法通过MATLAB 2016a在配置為Intel（R） Core（TM）i5-5200U CPU @2.20 GHz，运行内存为8 GB，操作系统为WIN8.1的计算机上运行。实验设置种群规模为100，交叉概率为0.8，其他参数见表1。

圖3是在NSGA II下本文模型的初始迭代收敛结果，图中实心圆表示帕累托前沿，空心圆代表新生成的个体适应度。图4为经过迭代计算得到的最终的帕累托最优解集。需要指出的是，由于多目标优化目标大多相互冲突，因此最终的结果是一个无法进行简单比较的帕累托最优解集，在不对目标函数增加权重的情况下，可以认为帕累托最优解集中的任何一个解都不比其他的解差。在此基础上，从帕累托最优解集中随机选择一个解进行车辆路径分配，并绘制车辆路径图，见图5。根据图5 的结果，对得到的车辆路径规划进行甘特图绘制，以方便生鲜品配送企业进行调度和作业，见图6。

表2是基于测试实例R103的数据，分别采用NSGA和NSGA II计算的结果。从计算结果可知，虽然用NSGA得到的总成本4 198.67略优于用NSGA II得到的总成本4 205.25，但用NSGA得到的新鲜度0.712 8明显劣于用NSGA II得到的新鲜度0.918 1，证明了NSGA II算法和MO-VRPTW-P模型的有效性。

为探讨模型的适用性，将本文中提出的考虑配送总成本最小和生鲜品新鲜度最大的MO-VRPTW-P模型与传统的不考虑生鲜品新鲜度的VRPTW模型进行对比，分析两种配送策略在客户数量分别为25、50和100的情形下配送企业的总成本和生鲜品的新鲜度，并利用传统遗传算法对VRPTW模型进行求解，结果见表3。

分析表3可得出结论：

（1）VRPTW策略下的配送总成本略低于考虑生鲜品新鲜度的MO-VRPTW-P策略下的配送总成本，但MO-VRPTW-P配送策略对生鲜品新鲜度的优化较为明显。在9组对比数据中，VRPTW策略下的配送总成本比MO-VRPTW-P策略下的低1.27%～5.02%，但可以发现，MO-VRPTW-P策略对生鲜品的新鲜度最低优化3.30%，最高优化14.43%，这说明对于注重服务水平的生鲜电商配送企业来说，使用MO-VRPTW-P策略只需略微提高配送成本就能够达到很好的配送效果，提高服务质量。

（2）客户订单数量越多，生鲜品新鲜度的提升效果越明显，即MO-VRPTW-P模型优化效果越好。如算例中，大规模客户环境R1_100相比于小规模客户环境R1_25， R1_100的新鲜度优化率为14.43%，R1_25的新鲜度优化率为5.48%，因此本文提出的MO-VRPTW-P模型更加适合大规模客户订单环境。

（3）对比分析客户地理位置随机分布的R类算例和客户地理位置聚集分布的C类算例，客户地理位置较分散，其优化效果越明显。在同样的订单量环境下，R类的优化效果比C类的明显，如同样是50个客户，R1_50的新鲜度优化率为8.58%，C1_50的为4.51%，可能是因为客户地理位置越分散，配送时间就越长，对生鲜品新鲜度的影响就较大，因此本文提出的MO-VRPTW-P策略更适合客户地理位置较为分散的配送场景。

4 结束语

本文利用改进的非支配排序遗传算法（NSGA II），考虑了企业实际配送过程中可能会出现的延时配送、货物变质等实际情况，考虑了固定成本、运输成本、等待成本、延误惩罚成本和变质成本，更加符合实际情况。通过测试实例，证明了带时间窗的多目标生鲜品配送路径优化（MO-VRPTW-P）模型的有效性，求出了满足配送总成本最小和生鲜品新鲜度最大的相对较优解。同时通过对MO-VRPTW-P模型的适用性讨论，提出本文模型较为适合的配送场景，即适合大规模客户订单和客户地理位置分布较为分散的配送场景。该研究可为生鲜电商配送企业决策提供参考。由于该模型只考虑了一个配送中心和单品种运输，所以还有进一步的提升空间。

参考文献：

[1] TAGMOUTI M， GENDREAU M， POTVIN J-Y. Arc routing problems with time-dependent service costs[J]. European Journal of Operational Research， 2007， 181：
30-39. DOI：
10.1016/j.ejor.2006.06.028.

[2] TSANG Y P， CHOY K L， WU C H， et al. An intelligent model for assuring food quality in managing a multi-temperature food distribution centre[J]. Food Control， 2018， 90：
81-97. DOI：
10.1016/j.foodcont. 2018.02.030.

[3] OSVALD A， STIRN L Z. Vehicle routing algorithm for the distribution of fresh vegetables and similar perishable food[J]. Journal of Food Engineering， 2008， 85（2）：
285-295. DOI：
10.1016/j.jfoodeng.2007.07.008.

[4] SONG B D， KO Y D. A vehicle routing problem of both refrigerated- and general-type vehicles for perishable food products delivery[J]. Journal of Food Engineering， 2016， 169：
61-71. DOI：
10.1016/j.jfoodeng. 2015.08.027.

[5] WANG Songyi， TAO Fengming， SHI Yuhe. Optimization of location-routing problem for cold chain logistics considering carbon footprint[J]. International Journal of Environmental Research and Public Health， 2018， 15（1）：
86-102. DOI：
10.3390/ijerph15010086.