客户分类下生鲜配送两级路径问题与算法研究

马艳芳，李保玉，杨屹夫，冯翠英

1.河北工业大学 经济管理学院，天津 300401

2.浙江工业大学 经贸管理学院，杭州 310014

随着人们生活水平的提高，对肉制品、水产品、牛奶、新鲜果蔬等生鲜产品的需求不断增加，冷链物流行业也在快速发展。国家发改委、交通运输部门等24部门于2019年发布了《关于推动物流高质量发展促进形成强大国内市场的意见》，文中强调巩固物流降本增效成果，增强物流企业活力，提升行业效率效益水平，畅通物流全链条运行。据统计，在生鲜运输过程中腐烂的水果和蔬菜价值每年高达700亿元，造成了巨大的经济损失[1]。因此，如何提高生鲜产品冷链物流的运输效率，降低物流配送成本，成为优化生鲜冷链物流系统的主要研究方向之一。

近年来，为降低生鲜产品高昂配送成本，学者们对其进行了广泛研究。马艳芳等[1]建立了基于冲突合作关系的生鲜选址-路径多主体优化模型，主导层以系统总成本最低为目标，从属层考虑运输相关成本最小化，并设计GAPSO算法求解模型。冯杰和史立[2]构建了有客户软时间窗约束和车辆里程约束的生鲜产品配送路径优化模型，并采用蚁群算法进行求解。李军涛等[3]针对冷链物流配送系统中总成本较高但车辆有效利用率低的问题，在考虑拥堵指数的基础上，构建多目标多车型路径优化模型，并提出自适应遗传模拟退火算法。Chen等[4]研究了冷链配送过程中具有一些实际约束的多隔间车辆路径问题，开发自适应大邻域搜索算法求解。Yao等[5]将生鲜海产品配送问题建模为多仓库车辆路径问题，以总配送成本最小为目标，采用蚁群算法求解。从以上文献中可以看出，目前生鲜产品冷链物流背景下的车辆路径问题研究较为丰富，但大多考虑单级车辆路径，能检索到的考虑两级车辆路径问题的文献还不多。

此外，由于生鲜产品的易腐性，顾客十分重视生鲜产品的质量和新鲜度。对于配送企业而言，若想获取客户信任，提高市场竞争力，不仅要关注物流配送成本，也需要考虑客户满意度[6-7]。客户满意度已成为配送企业竞争的重要考量因素[8]，这也促使学者们开始对如何提高客户满意度进行研究。李军涛等[3]验证了采用多车型配送、使用改进的自适应遗传模拟退火算法以及适当定价三种策略均可从不同程度上提高客户满意度。张惠珍等[9]通过综合考虑客户时间窗和食物新鲜度来提高客户满意度，并采用单亲遗传混合蚁群算法求解多目标车辆路径模型。夏扬坤等[10]研究了客户分级和客户需求依背包拆分的生鲜车辆路径问题，以降低物流配送成本并提高客户满意度。任腾等[11]构建在客户允许服务时间范围内以总成本最小为目标的冷链车辆路径优化模型，以满足企业经济和社会效益。户佐安等[12]以客户对服务时间和货物完好性的要求衡量客户满意度，建立以客户满意度最大和运输成本最小为目标的优化模型。可见，在生鲜物流市场竞争日益激烈的今天，配送企业若想稳固在竞争市场中的地位，在考虑经济成本的同时，客户满意度也不容忽略。且从以上文献中可以看出，目前对于车辆路径问题中客户满意度的研究较为丰富，但从客户分类角度提高客户满意度的文献较少。因此，本文考虑了客户分类，通过将客户按重要性进行分类以提高客户满意度。优先满足重要客户的期望时间窗，提高重要客户的期望时间窗满足率，这样，既保持了配送企业的优质客户资源，也提高了其整体客户满意度。

两级容量有限车辆路径问题（Two-Echelon Capacitated Vehicle Routing Problem，2E-CVRP）可视为两个车辆路径问题（Vehicle Routing Problem，VRP）的组合，VRP已是典型的NP难问题，可知2E-CVRP的求解难度更大。精确方法适用于求解小规模问题，对于复杂优化问题常采用启发式算法进行求解。启发式算法在求解VRP问题时展现出了优越的性能[1-5，9]，然而，单一的启发式算法具有一定的局限性。遗传算法（Genetic Algorithm，GA）具有较强的全局搜索能力，但容易过早收敛，易于陷入局部最优解，因而算法效率不高。模拟退火算法（Simulated Annealing，SA）局部搜索能力较强，但全局搜索能力较弱。综合两种算法的优缺点，将改进的遗传算法和模拟退火算法相结合，求解2E-CVRP优化模型。

表1总结了车辆调度问题中与生鲜配送、两级路径和客户分类相关研究。从表1中可以看出，目前关于VRP的研究已取得了较为丰硕的成果，但在生鲜冷链物流背景下的两级车辆路径研究较少，且少有研究在两级车辆路径中考虑客户分类，而考虑客户分类对配送企业维持优质客户资源，提高企业经济和社会效益具有重要意义。基于此，本文研究生鲜产品配送背景下考虑客户分类的两级容量有限车辆路径问题（Two-Echelon Capacitated Vehicle Routing Problem with Customer Classification，2E-CVRP-CC）。并设计两阶段启发式算法进行求解：第一阶段使用改进的GA-SA算法求解二级配送网络，第二阶段使用精确方法求解一级配送网络。最后，基于Set2、Set5两组基准算例集进行算法对比分析，证明算法的寻优能力，并测试算法的收敛性，然后结合实际案例模拟验证2E-CVRP-CC模型的适用性。

表1 相关文献特征Table 1 Characteristics of relevant literature

1 问题与模型

1.1 符号说明

集合：

设N(V,E)为生鲜产品运输网络，其中，V=D⋃S⋃C。

D：中心仓库，D={0}；

S：配送中心集合，S={1,2,…,s}；

C：客户集合，C={1,2,…,n}；

B：一级运输车辆集合，B={1,2,…,b0}；

K：二级运输车辆集合，K={1,2,…,k0}；

P1：由仓库和配送中心组成的节点集合，P1=D⋃S；

P2：由配送中心和客户组成的节点集合，P2=S⋃C；

指标和参数：

i/j：物流网络中节点的索引；

QS i：配送中心i∈S的容量；

QB：一级同质运输车辆的容量；

QK：二级同质运输车辆的容量；

FD：中心仓库的建设成本；

FS i：配送中心i∈S的建设成本；

FB：一级运输车辆的固定成本；

FK：二级运输车辆的固定成本；

a1：一级运输车辆的单位运输费用；

a2：二级运输车辆的单位运输费用；

d ij：节点i与节点j之间的距离，i,j∈V；

ρ：价值损耗系数，即单位时间内单位生鲜产品的价值损耗；

qi：客户i∈C的需求量；

：一级运输车辆b∈B在弧线(i,j)之间的装载量，i,j∈P1；

：二级运输车辆k∈K在弧线(i,j)之间的装载量，i,j∈P2；

/：二级运输车辆k∈K到达节点i/j的时间，

i,j∈P2；

：二级运输车辆k∈K从节点i驶向节点j的时间，i,j∈P2；

：二级运输车辆k∈K在客户点i∈C的等待时间；

：二级运输车辆k∈K在客户点i∈C的服务时间；

Tmax：二级配送网络中，每条路线允许车辆行驶的最长时间；

[ET i,LT i]：客户i∈C的期望时间窗；

ci：客户i∈C单位时间窗偏离量费用；

决策变量：

y i：0-1变量，如果配送中心i∈S开放，则为1，否则为0；

xijb：0-1变量，如果车辆b∈B通过弧(i,j)，则为1，否则为0，i,j∈P1；

y ijk：0-1变量，如果车辆k∈K通过弧(i,j)，则为1，否则为0，i,j∈P2；

zik：0-1变量，如果客户i∈C由车辆k∈K进行配送，则为1，否则为0。

1.2 客户分类

在运输过程中，生鲜产品价值随着时间而衰减，按时交付生鲜产品可以防止质量下降，并且能够提高顾客对于配送企业的可信度和满意度。优化模型考虑了顾客对于期望时间窗的要求，然而，带软时间窗的车辆路径问题容易降低客户满意度，且配送企业在提供配送服务时要权衡成本与效益。因此，为保持配送企业优质客户资源，将客户按重要性分为重要客户与普通客户两类，通过增大重要客户的时间窗偏离量惩罚程度，优先满足重要客户的期望时间窗，提高重要客户的期望时间窗满足率，进而提高整体客户满意度，形成一个考虑客户分类的2E-CVRP。

另外，不同类别客户的单位时间窗偏离量费用c i是不同的，重要客户的c i值较普通客户更大，为保持企业优质客户资源并提高整体客户满意度，应尽量满足重要客户的期望时间窗。[0,Tmax]为配送中心点i∈S的硬时间窗约束，Tmax是二级配送车辆可允许行驶的最长时间。[ET i,LT i]为每个客户点i∈C的期望时间窗，如果顾客的期望时间窗未得到满足，则会施加惩罚成本。惩罚成本与客户满意度呈负相关关系，惩罚成本越高，说明未被满足的顾客期望时间窗越多，客户满意度也就越低。因此，可以用惩罚成本的高低反映客户满意度水平。

1.3 生鲜两级车辆路径问题

两级容量有限车辆路径问题（2E-CVRP）可描述如下：在生鲜产品物流配送网络中有一个中心仓库和多个期望客户，在中心仓库和客户之间有固定数量的配送中心。位于城区边缘位置的仓库通过大型同质冷藏运输车（一级配送车辆）向位于城区中的各配送中心运送生鲜产品，其中仓库和配送中心的地理位置已知，有装载量和数量限制的一级配送车辆从仓库出发，配送完成后返回仓库（一级配送网络）；在配送中心，生鲜产品被转移到小型同质冷藏运输车上（二级配送车辆），然后车辆从配送中心出发，通过规定的优化路线为指定的顾客服务，最终再返回配送中心（二级配送网络）。具体的物流网络结构图如图1所示。

图1 2E-CVRP物流网络示意图Fig.1 Logistics network diagram of 2E-CVRP

2E-CVRP在已知中心仓库和配送中心的容量和地理位置、各级配送车辆容量、顾客地理位置、需求量等条件下，规划各级配送车辆运输服务路径，从而使整个物流配送网络总成本最低。物流配送网络总成本包括仓库和配送中心的建设成本、车辆固定成本、车辆运输成本、生鲜产品损耗成本以及未满足顾客期望时间窗要求而产生的惩罚成本。其中，仓库和配送中心的建设成本主要包括场地租赁费、冷藏设备购置费、水电费以及员工工资等；车辆固定成本主要指驾驶员工资以及车辆折旧费用等；车辆运输成本主要包括电能消耗费用以及车辆维修费用等；损耗成本指生鲜产品在配送过程中因腐烂变质而产生的损失费用。问题假设如下：

（1）中心仓库有足够数量的存货，可以满足所有配送中心的需求；

（2）配送中心和客户的数量、地理位置已知，各级配送车辆固定成本已知；

（3）各节点间距离按欧式距离计算，各级配送车辆单位运输成本已知；

（4）各级配送车辆容量已知，各运输路径上车辆载重量不能超过其容量限制；

（5）配送途中交通状况良好，车辆均匀速行驶；

（6）客户需求和期望时间窗是独立且预先确定的；

（7）各级配送车辆离开并最终返回相同的起始节点位置；

（8）为减少生鲜产品损耗，一级配送车辆到达配送中心并卸下产品后，产品会立即被装载到二级配送车辆上，此时产品在配送中心的处理成本忽略不计；

（9）仅计算二级配送网络中生鲜产品的损耗成本。

1.4 数学模型

目标函数式（1）为最小化物流配送系统的总成本，包括仓库和配送中心的建设成本，一、二级配送网络中车辆的固定成本和运输成本，二级配送网络中生鲜产品的损耗成本以及因未满足顾客期望时间窗要求而产生的惩罚成本，分别如式（2）～（6）所示。其中，二级配送网络中生鲜产品的损耗成本Z4与车辆到达顾客节点的时间呈正相关，生鲜产品的价值损耗系数ρ由文献[13]提出，表示单位时间内单位生鲜产品的价值损耗。约束条件式（7）确保离开仓库的生鲜产品总量等于顾客总需求量；式（8）是一级配送车辆的容量约束；式（9）保证每个配送中心最多只能被一辆一级配送车辆服务一次；式（10）保证一级配送网络中每个节点的进出车辆相同；式（11）表明在仓库之间没有车辆路径；式（12）表示分配给各配送中心的生鲜产品数量不能超过其自身容量；式（13）是二级配送车辆的容量约束；式（14）保证每位顾客只能被一辆二级配送车辆服务一次；式（15）保证二级配送网络中每个节点的进出车辆相同；式（16）说明在配送中心之间没有车辆路径；式（17）是车辆载重量守恒约束，消除子约束，满足每位顾客的需求；式（18）和（19）确保所有车辆空车返回其原始仓库或配送中心；式（20）和（21）保证从仓库和配送中心发出的车辆总数不能超过其拥有的最大数量；式（22）是硬时间窗约束，也是二级配送车辆最长运输时间限制；式（23）计算二级配送车辆的等待时间；式（24）计算二级配送网络中，二级运输车辆到达节点j∈C的时间。

2 求解算法

本文建立的2E-CVRP-CC模型属于NP难问题，包含两级配送网络：一级配送网络从中心仓库出发将生鲜产品运输至各配送中心，二级配送网络从各配送中心出发将生鲜产品配送给终端客户。文中设计两阶段启发式算法求解该模型：第一阶段求解二级运输路径，由于涉及客户数目相对较多，采用求解效率较高的改进GASA启发式算法，又由于配送企业将客户按重要性分为重要客户和普通客户，故为区分两类客户，在算法设置数据时，将不同类别客户的时间窗偏离量费用ci赋予不同的数值，其中重要客户的时间窗偏离量费用为c1，普通客户的时间窗偏离量费用为c2，且c1>c2，这样保证了能够优先满足重要客户的期望时间窗。

2.1 第一阶段：改进的GA-SA算法求解二级网络

第一阶段求解配送中心与顾客之间的车辆路径问题，可视为单层VRP。对于2E-CVRP而言，其重点在于第二级配送网络的车辆路径规划，二级路径的优化可以节约大量物流系统成本，因此为二级配送车辆规划合适的运输路线至关重要。为了更好地求解二级物流网络车辆路径问题，本阶段采用改进的混合启发式算法（GA-SA），即在算法的迭代过程中，首先使用遗传操作，然后使用模拟退火操作，以增强找到的最优解。

遗传算法（GA）最早由John Holland提出，是一种模拟达尔文进化理论和自然界优胜劣汰机制进行全局最优解搜索的启发式算法[14]。GA将问题的求解过程转化成类似生物进化中染色体基因的交叉、变异等过程，通常包括选择、交叉、变异等基本操作。然而，单一的启发式算法都有一定的局限性，像GA在求解大规模复杂优化问题时，存在局部搜索能力较弱、容易过早收敛、易于陷入局部最优解的缺陷。

基于单一解的模拟退火算法（SA）可以突破爬山算法的局限性，克服局部最优陷于停滞的问题，该算法由Kirkpatrick等[15]提出，以一定的概率接受较差解，从而加强跳出局部最优的能力。此外，刘兰芬和杨信丰[16]证明了将GA和SA结合的遗传模拟退火算法的有效性。因此，综合借鉴两种算法的思路，将改进的GA-SA算法作为第一阶段算法。

2.2 解的表示与初始解

初始解的生成方式有随机生成和启发式生成两种。采用启发式生成的初始解更为优良，但个体较为集中，易使算法陷入局部最优。为保持个体多样性，且利于改进的GA-SA算法搜索到全局最优解，本算法采用随机方式生成初始种群，以使初始种群尽可能地均匀分布在整个解空间。

本阶段研究配送中心与客户之间的配送路径问题，用三个向量表示一个完整的解，第一个矢量为车辆向量，第二个矢量为配送顺序向量，第三个矢量为车辆所属配送中心的向量。二级配送网络编码解码中包含有编号为{1,2,…,n}的n位客户、编号为{1,2,…,s}的s个配送中心以及编号为{1,2,…,k}的k辆二级运输车辆。

假设有2个配送中心，编号为1,2；可支配二级运输车辆4辆，编号为1,2,3,4；需要服务的客户数为15位，编号为1,2,…,15，则配送方案编码如下：

可以看出，二级配送网络中，车辆1和车辆4从配送中心1出发，车辆2和车辆3从配送中心2出发。客户编号对应的车辆向量值表示服务该客户的车辆编号，车辆向量对应的顺序向量值表示车辆服务客户的先后顺序。如车辆1服务客户3,4,8，对应配送顺序为2,13,3，对应配送中心1，即车辆1从配送中心1出发先后服务客户3,8,4。因此，解码后得到的四条车辆路线表示如下：

2.3 适应度函数

2E-CVRP-CC模型以物流配送系统总成本最小为目标，考虑到二级配送网络中顾客期望时间窗和车辆容量约束，对违反约束的染色体添加一个足够大的惩罚值，以免生成不可行解。而当满足客户时间窗和二级车辆容量约束时，目标函数如下所示：

适应度函数的确定要结合求解问题本身而定，根据适应度值判断个体的优劣，并以此进行选择操作。2ECVRP-CC模型是一个最小化组合优化问题，目标函数值越小，对应的个体适应度就越大，解就越优良。因此，本算法选用目标函数值加惩罚函数值的倒数作为适应度函数[17]，具体公式为：

其中，z i为第i条染色体对应的目标函数值，P1和P2分别表示违反客户时间窗和二级车辆容量约束时产生的足够大的惩罚成本（当未违反约束时，P1,P2=0，此时目标函数值由公式（25）计算），f i表示第i条染色体的适应度值。

2.4 遗传操作

轮盘赌选择：选择算子以适应度作为衡量标准，对群体进行优胜劣汰操作，使得适应度越高的个体被遗传到下一代种群的概率也越大。然而，这种方法容易导致适应度高的个体大量繁殖，从而造成算法的搜索范围过于局限。因此，将轮盘赌选择算子结合精英保留策略，根据适应度值和精英策略，从父代和子代染色体中产生新一代染色体。

精英保留策略：遗传算法中，后代染色体通常由父代染色体复制而来。采用精英保留策略进行选择操作时，每一代种群中较好的一部分个体作为精英个体（精英染色体数目为种群规模×精英率），直接保留到下一代，从而保证迄今为止最优的个体不会被交叉、变异等遗传操作破坏。

部分匹配交叉：交叉算子决定算法的全局搜索能力，是遗传算法中的一种重要算子。它模拟生物自然进化过程，将选择算子得到的两条染色体互相交换部分基因，从而形成新个体。本文选用部分匹配交叉策略，通过随机选择两个交叉点确定交叉区域，然后交换两组基因的位置并进行冲突检测，如图2所示。具体步骤如下：

步骤1根据基于个体适应度值的自适应交叉率选择父代染色体1和2，然后随机选择两个不同的位置作为交叉点。自适应交叉概率更新公式如下所示：

其中，Pc为交叉率，Pcmax和Pcmin分别为最大交叉概率和最小交叉概率。f为个体的适应度值，fmax和favg分别为染色体适应度值的最大值和平均值。

步骤2将两条父代染色体位于交叉区域内的基因进行互换。

步骤3做冲突检测。本问题中，一个完整的解有三个向量，其中车辆向量和配送中心向量允许出现重复基因，而对于顺序向量，每位顾客的配送顺序唯一，故顺序向量中不允许出现重复基因，因此，要对顺序向量中交换的两条父代染色体进行冲突检测。其方法是，根据交换的两组基因建立一个映射关系，如图2所示，以2↔3这一映射关系为例，可以看到父代染色体交换基因后，染色体1存在两个基因2，这时将其通过映射关系转变为基因3。以此类推，直至两条染色体中的基因没有冲突为止。

图2 部分匹配交叉算子Fig.2 Partially-matched crossover operator

单点变异：变异算子决定算法的局部搜索能力，通过改变染色体中部分基因的位置，形成新的染色体，维持种群的多样性。改进GA-SA算法采用单点变异算子，随机选择父代染色体中的两个变异位置，交换两个变异位置上的基因，得到一条新的后代染色体。

2.5 模拟退火操作

SA状态函数：在算法迭代过程中，完成遗传操作后，将遗传操作得到的最优解作为模拟退火操作的初始解，然后使用状态函数生成新解。本算法中，状态函数采用互换操作，随机选择每个向量中的四个位置，然后分别将第一个位置和第三个位置、第二个位置和第四个位置的基因进行互换，从而完成对初始解中车辆向量、顺序向量和配送中心向量的更新操作。

Metropolis准则：对种群不断进行遗传操作的进化过程是一个优胜劣汰的除差过程，不断进化使得种群多样性逐渐降低，这样也导致算法容易陷入局部最优解。因此，引入模拟退火算法中的Metropolis接受准则，以一定的概率接受较差解，从而使算法避免陷入局部最优和过早收敛，具有全局优化能力。Metropolis接受准则公式为：其中，T为当前温度，f1和f2分别为当前解和新解的二级网络配送成本。

2.6 第二阶段：精确方法求解一级网络

第二阶段求解中心仓库与配送中心之间的车辆路径问题，同样可视为单层VRP。由于一级网络涉及节点数目不多，可利用精确方法快速得到最优解。根据第一阶段所求结果，首先计算各配送中心需求量，然后根据一级车辆容量为各配送中心安排车辆，得到一级路径优化方案。最终，得到2E-CVRP-CC模型的最优解。综上，本文所提出的两阶段启发式算法流程图如图3所示。

图3 两阶段启发式算法流程图Fig.3 Flowchart of two-stage heuristic algorithm

3 实验结果与分析

首先，选用经典基准案例进行测试，验证提出的两阶段启发式算法求解2E-CVRP的性能；其次，使用模拟数据进行案例分析，证明2E-CVRP-CC模型的合理性和适用性以及算法的有效性。所有算法都在Dell Inspiron 14计算机上使用Matlab R2016a运行，具体配置为2.50 GHz Intel Core i7-6500U处理器，操作系统为Windows 10 64位。

3.1 算例参数设置

两阶段启发式算法涉及的主要参数有，种群规模，迭代次数，最大、最小交叉概率，变异概率，初始温度，终止温度，降温速度和内循环迭代次数等。通过一定的实验测试和文献参考[1，3]，算法参数设置如下：种群规模取80，迭代次数取1 000代，Pcmax=0.85,Pcmin=0.5,Pm=0.1,T0=2 000,T=20，降温速度q取0.95，内循环迭代次数设置为100代。另外，结合帕累托定律，规定顾客总数的前20%为重要客户（若重要客户数n为非整数，则进行向上取整处理）。

为了测试所提出算法解决2E-CVRP-CC问题的效果，使用2E-CVRP的两组基准案例进行测试，分别是Perboli等人[18]提出的Set2算例集和Hemmelmayr等[19]提出的Set5算例集。前者包含21个算例（只考虑Set2a和Set2b），包括21～50位客户；后者包含9个算例（只考虑b系列），包括100或200位客户。两个案例包含信息有：中心仓库和卫星（配送中心）的数量及位置，一、二级车辆数量及容量，客户位置和需求。两个算例集均可在https：//www.univie.ac.at/prolog/research/TwoEVRP下载。

3.2 算法对比分析

为分析两阶段启发式算法的性能，将本文算法求解基准案例的结果与前人的求解结果进行对比分析。同时，为了使求解结果更具有可比性，此处去除了目标函数（1）中的生鲜损耗成本、顾客时间窗惩罚成本以及仓库和配送中心的建设成本，以使所提出算法的目标成本与各案例所包含成本相匹配。

表2为Perboli的Set2算例集求解结果，前两列是各案例名称以及目前已知最优解[18](BKS)，3～6列是各算法得到的最优结果，最后一列“Gap”表示本文算法求得的最优结果(Best)与BKS的差距，计算公式为Gap=100%×(Best-BKS)/BKS。

表2将算法与Hemmelmayr等[19]（ALNS）、Perboli等[18]（Math-Heuristics）、Zeng等[20]（GRASP+VND）和许维胜等[21]（Multi-start）四篇文献中所用算法进行对比分析。可以看出，ALNS和GRASP+VND算法性能整体表现良好，而Multi-start和Math-Heuristics算法与最优结果相差较多。相比而言，两阶段启发式算法在6个算例中求得最优解，且E-n33-k4-s2-13算例求得的最优解优于目前已知最优解BKS，可见本算法性能与整体表现良好的ALNS和GRASP+VND算法相差不多。另外，求解结果均值565.42最接近于最优解BKS均值556.72，且与最优解BKS的差距均值仅为1.54%。由此可见，在与其他四种算法的比较中，本文提出的两阶段启发式算法可以在一定程度上较好地解决2E-CVRP问题。

表2 Set2算例集求解结果与比较Table 2 Solution results and comparisons of Set2

表3为Hemmelmayr的Set5算例集求解结果，Set5算例集包含100或200位客户，属于2E-CVRP问题的大规模算例，将本文算法与文献[22]的HCC和BSHV算法、文献[23]的STS和EDTS算法进行对比分析。

表3中记录了各算法运行五次的最优结果和均值，每个案例的最优结果和均值加粗强调，且最优解在五次运行测试中至少被检索一次。可以看出，两阶段启发式算法性能优于STS和EDTS算法，与HCC算法最优结果和均值的差距分别为8.5%和9.94%，与BSHV算法最优结果和均值的差距分别为8.67%和10.49%。由此可见，提出的两阶段启发式算法对于大规模问题能求得其近似最优解。

表3 Set5算例集求解结果与比较Table 3 Solution results and comparisons of Set5

综上，结合Set2算例集和Set5算例集可以看出，提出的两阶段启发式算法对于小规模问题均能找到最优解，对于中大规模问题能求得其近似最优解，且与其他算法差距不大，因此本算法具有一定的竞争力。

3.3 算法收敛性分析

文中提出两阶段启发式算法求解2E-CVRP-CC模型，其中第一阶段求解二级配送网络使用改进的GASA算法，第二阶段求解一级配送网络使用精确方法。为探究改进的GA-SA算法求解2E-CVRP-CC问题的能力，记录其求解基准案例的二级配送网络时每次迭代的运行结果并绘制出迭代图，选取四个不同的案例迭代图进行收敛性分析。

选取Set2算例中顾客数量为32的E-n33-k4-s3-17、E-n33-k4-s4-5、E-n33-k4-s7-25、E-n33-k4-s14-22四个案例，收敛曲线如图4所示。可以看出，算法结果在100代以内快速下降，500代左右算法已收敛到最优结果附近，500～800代之内算法下降趋势减弱并逐渐收敛于最优结果。

图4 四个基准案例收敛曲线Fig.4 Convergence curves of four classic benchmarks

4 模拟案例

4.1 单中心仓库

为验证2E-CVRP-CC模型的合理性和适用性，本案例拟选用1个中心仓库，3个备选配送中心，以满足50位客户的需求。中心仓库和备选配送中心的位置、容量和建设成本如表4所示。客户位置、需求量和时间窗信息如表5所示，其中时间窗以上午9点为基准点，单位为小时，由于版面限制，此处只列出前15位客户相关信息。

表4 中心仓库和备选配送中心信息表Table 4 Information sheet for central warehouse and alternative distribution centers

表5 部分客户信息表Table 5 Information sheet for some customers

本例中使用的部分参数设置如3.1节所示。根据实际情况和社会经验，使用的其他参数设置如下：一级车辆容量为200 kg，固定成本200元/辆，单位运输费用为0.53元/km；二级车辆容量为60 kg，固定成本为100元/辆，单位运输费用为0.3元/km，行驶速度为30 km/h，最长行驶时间Tmax为6 h；可用一级车辆数为3辆，可用二级车辆数为7辆。单位时间内单位产品的价值损耗系数ρ为0.5元，车辆在客户点的服务时间与货物重量有关，单位重量产品的服务时间为0.02 h。另外，由前文可知，顾客总数的前20%为重要客户（表5中编号加粗者为重要客户）。重要客户单位时间窗偏离量费用c1为0.5元，普通客户单位时间窗偏离量费用c2为0.1元。

基于上述数据，运用前文提出的两阶段启发式算法求解本案例，运行算法30次，选择其中最佳优化结果。结果显示，第一阶段算法求出的二级配送网络选择开放编号为S1和S2的配送中心，使用二级车辆数为7辆，相关经济成本为4 840.49元。第二阶段算法根据开放的配送中心和二级路径优化方案求解出一级运输路径，使用一级车辆数为2辆，相关经济成本为30 402.71元。解码后，一、二级网络路径优化方案如图5。

图5 一、二级网络路径优化方案Fig.5 Primary and secondary network path optimization scheme

表6展示了两阶段启发式算法求解2E-CVRP-CC模型的最佳优化结果。结果显示，2E-CVRP-CC模型的物流配送网络总成本为35 243.20元。从表6中可以看出，车辆1至车辆7的载重量均接近满载状态，这说明运输车辆不仅满足了容量限制，而且车辆利用率较高。从运输成本看，7辆车的运输成本均不高，这是由于客户间距离较近造成的。从时间窗惩罚成本看，每辆车都有一定的惩罚成本，其原因是一些客户的期望时间窗没有得到满足。对于10位重要客户而言，其中8位客户的期望时间窗得到满足，重要客户时间窗的满足率达到了80%。这说明，对客户按重要性进行分类处理，通过增大重要客户时间窗偏离量费用，可以提高重要客户的时间窗满足率，进而提高了整体客户满意度，并使配送企业稳定了优质客户资源。从损耗成本看，除车辆固定成本、中心仓库和配送中心的建设成本外，损耗成本在总成本中占比最高。这表明，在满足客户时间窗的前提下，尽可能减少生鲜产品的损耗费用，可以使整体目标达到最优。

表6 二级网络最优结果Table 6 Optimal result for the second echelon network

4.2 多中心仓库

为验证提出的两阶段启发式算法对于求解多中心仓库的生鲜配送两级车辆路径问题的性能，本案例拟选用3个备选中心仓库，5个备选配送中心以满足100位客户的需求。将本文算法求得的最优结果与标准粒子群算法（PSO）、蚁群算法（ACO）、遗传算法（GA）和模拟退火算法（SA）求解结果进行对比分析，每种算法的种群大小为80，最大迭代次数为1 000，运行算法30次，选择其中最佳优化结果。

五种算法最优结果对比如表7所示。从表7中可以看出，本文算法的最优解相较于PSO而言，可使总成本降低4.22%，重要客户时间窗满足率提高37.5%；相较于ACO而言，可使总成本降低2.42%，重要客户时间窗满足率提高18.75%；相较于GA而言，可使总成本降低1.29%，重要客户时间窗满足率提高12.5%；相较于SA而言，可使总成本降低0.61%，重要客户时间窗满足率提高6.25%。因此，相较于其他四种算法而言，本文算法得到的结果最优。

表7 五种算法最优结果对比Table 7 Optimal results of five algorithms

算法迭代效果对比如图6所示。本文采用两阶段启发式算法求解该问题，第一阶段使用改进的GA-SA算法求解二级网络，第二阶段使用精确方法求解一级网络。为保证算法对比的统一性，其他四种算法和本文算法保持一致，即第一阶段分别使用PSO、ACO、GA和SA求解二级网络，第二阶段求解一级网络均使用精确方法。因此，图6的算法迭代对比图表示各算法求解二级网络成本的迭代过程。从图6中可以看出，五种算法都可以得到最优结果，但GA-SA求得的结果最优。另外，从收敛速度看，GA-SA在450代左右已收敛到最优值附近，在580代左右已逐渐收敛于最优值；而PSO、ACO和GA均在600代左右才开始收敛于最优值附近；SA在300代左右收敛于最优值附近，在600代左右逐渐收敛于最优值，虽然SA的收敛速度优于GA-SA，但其求得的最优值劣于GA-SA求得的最优值。

图6 算法迭代对比图Fig.6 Comparison figure of five algorithms iteration

因此，由上述的对比分析可知，本文提出的算法对于求解多中心仓库的生鲜配送两级车辆路径问题是可行且有效的。

5 结语

本文研究了生鲜产品冷链物流背景下的两级容量有限车辆路径问题，考虑了客户分类，将客户按重要性分为重要客户和普通客户两类，以物流配送网络总成本最小为目标建立了优化模型。设计两阶段启发式算法求解该模型，第一阶段使用改进的GA-SA算法求解二级配送网络，第二阶段使用精确方法求解一级配送网络。GA-SA算法改进如下：（1）采用随机方式生成初始种群，以使初始种群尽可能地均匀分布在整个解空间，保持种群的多样性；（2）将轮盘赌选择机制结合精英保留策略，保留优秀个体；（3）采用部分匹配交叉算子结合自适应交叉概率，维持种群多样性，增强算法的全局搜索能力；（4）GA和SA两种算法的结合避免算法易于陷入局部最优解，弥补单一启发式算法的局限性。

为验证提出的两阶段启发式算法求解2E-CVRP的能力，选取Perboli提出的Set2算例集和Hemmelmayr提出的Set5算例集，共30个基准案例，分别将所提出算法与四种算法进行对比分析。结果表明，本文算法对于小规模问题均能找到最优解，对于中大规模问题能求得其近似最优解，且与其他算法差距不大。具体而言，对于Perboli提出的21个中小规模基准案例，两阶段启发式算法在6个算例中求得最优解，另有1个算例求得更优解，整体求得结果与最优解的差距Gap均值仅为1.54%。对于Hemmelmayr提出的9个大规模基准案例，本文算法性能优于STS和EDTS算法，与HCC算法最优结果和均值的差距分别为8.5%和9.94%，与BSHV算法最优结果和均值的差距分别为8.67%和10.49%。另外，对算法的收敛性进行了测试分析，结果表明，算法在前期就能快速收敛于最优值附近，且在不同算例中表现稳定。

为探究提出的2E-CVRP-CC模型与算法的适用性，基于模拟数据进行了案例分析。最终的结果分析表明：（1）车辆载重量均接近满载状态，说明运输车辆不仅满足了容量限制，而且车辆利用率较高；（2）对客户按重要性进行分类处理，通过增大重要客户时间窗偏离量惩罚程度，可以提高重要客户的期望时间窗满足率，进而提高整体客户满意度并维持配送企业优质客户资源；（3）本文提出的两阶段启发式算法对于求解多中心仓库的生鲜配送两级车辆路径问题也是可行且有效的。

综上，本文可为生鲜配送的两级车辆路径问题提供决策支持，对保持企业优质客户资源，提高企业配送效率和客户满意度具有一定参考价值。但是，本文也存在一定的局限性，比如只从经济角度考虑了物流配送系统总成本最小，而未考虑运输过程中的实时路况，以及各级网络的多车型混合配送问题，未来可就此进行进一步的研究。