双目标冷链物流车辆路径问题及其遗传蚁群求解

张 瑾， 毕国通， 戴二壮

(1. 河南大学计算机与信息工程学院，开封 475004；2. 河南大学商学院，开封 475004)

近年来，生鲜食品需求日益增多，实体超市与电商平台不断布局生鲜新零售，生鲜产品的易腐性要求对其进行冷链运输。除造成配送成本的增加以外，生鲜产品配送的时效会对其品质造成影响，从而影响消费者的购物体验。对冷链物流车辆路径问题进行合理优化，在满足企业市场定位的前提下有效控制配送成本、提高客户满意度，是提高企业市场竞争力的有效手段[1]。

冷链物流车辆路径问题是车辆路径问题(vehicle routing problem，VRP)在冷链物流的实际应用，可根据优化目标将相关研究文献分为单目标和多目标两种类型，后者相关研究相对较少。单目标相关文献中，缪小红等[2]考虑软时间窗限制，构建了以货损成本、惩罚成本与运输成本之和最小为目标的优化模型，利用改进的遗传算法求解最优配送路线，求解结果优于标准遗传算法；Zhang等[3]建立了包含运输、制冷、货损和惩罚成本在内的总成本最低的优化模型，考虑了时间窗、载重和不同食品单位体积的装载量约束，采用遗传算法求解，验证了该模型的可行性和合理性；杨珍花等[4]构建了冷藏车多车型混合配送优化模型，开发了混合模拟退火算法，并对比分析不同车型组合下配送成本的差异，表明提出的混合配送方案在总成本和碳排放方面具有优势；葛显龙等[5]考虑软时间窗约束，以生鲜配送损耗为可变成本，车辆启动费用为固定成本，建立了以总成本最小为目标的生鲜配送模型，表明所提模型可以有效缩短里程、节约成本；潘茜茜等[6]构建了运输成本、惩罚成本、货损成本、固定成本和碳排放成本最小的冷链物流配送路径优化模型，采用蚁群算法求解模型；钱光宇[7]构建了以碳排放成本和车辆使用成本、运输成本、制冷成本、货损成本最小为目标的生鲜农产品冷链配送路径优化模型，表明所建模型能够有效减少冷链配送过程中产生的二氧化碳；樊世清等[8]建立了含固定成本、运输成本、货损成本、惩罚成本和能耗成本在内的总成本最小为目标的农产品冷链物流车辆配送路径优化模型，采用改进的蚁群算法验证了模型的合理性和可行性；卢甲东等[9]考虑客户地理位置的相邻性以及交货时间相似性，构建了基于时空相似度的冷链物流分区配送模型，设计了问题求解的遗传算法。多目标相关文献中，Amorim等[10]针对易腐食品构建了配送成本最小化与产品新鲜度最大化的双目标模型，研究配送方案与成本-新鲜度之间的关系，表明这两个目标不能同时达到最优；Wang等[11]研究了易腐食品多目标带时间窗车辆路径问题，以总成本最低和新鲜度最大作为优化目标，提出一种基于Pareto可变邻域搜索的两阶段启发式算法，结果表明算法是有效的；梁承姬等[12]建立了包含运输成本、货损成本、时间成本等在内的配送成本最小化和客户满意度最大化的双目标冷链物流配送优化模型，运用改进的遗传算法进行求解，表明模型和算法是有效性的；张亚明等[13]建立基于时间和品质因素的顾客满意度约束的多配送中心冷链物流车辆路径模型，采用重心分区法和改进的精英单亲遗传算法求解，表明该模型更适合冷链物流配送最优路径选择；王勇等[14]考虑生鲜商品配送的物流成本和价值损失成本，构建使上述损失最小的配送优化模型，设计了基于K-means聚类的遗传-禁忌搜索算法，分析得到不同生鲜商品在配送过程中的最佳配送温度和包含不同配送单元的最佳聚类数；张倩等[15]构建了考虑配送成本、产品新鲜度及碳排放和需求不确定因素的配送模型，应用目标法和果蝇算法对问题模型进行求解，验证了模型及算法的鲁棒性。

通过对近年来冷链物流车辆路径问题相关文献进行研究，发现综合考虑总成本和客户满意度的多目标优化研究较少，其多目标问题的处理主要通过线性加权、权重迭代、优先级法及约束法等，主要思路是将目标函数转化为单目标进行求解，但这些方法对于确定参数的大小或优先级具有一定的主观性，需要决策者本身对每个目标都有比较明确的把握，且研究结果具有特殊性。基于此，将考虑软时间窗和车辆容量约束，构建以总成本最低和客户满意度最高为目标的双目标冷链物流车辆路径优化模型，采用ε约束法处理多个目标以避免问题处理时的主观性和特殊性，结合遗传(genetic algorithm，GA)和蚁群算法(ant colony optimization，ACO)各自优势，设计了模型求解的遗传蚁群算法(genetic-ant colony optimization algorithm，GA-ACO)。

1 冷链物流车辆路径问题模型

研究带容量和软时间窗约束的双目标冷链物流车辆路径问题，由一个配送中心服务多个客户，配送车辆具有容量约束，所有车辆均从配送中心出发，客户服务完成后返回配送中心，优化目标是在保证完成客户需求的前提下最小化总成本及最大化客户满意度。

1.1 模型假设

所研究问题的前提条件如下：①仅有一个配送中心，所有冷藏车都由配送中心出发并最终返回配送中心；②所有冷藏车都是同质的；③每个客户点仅有送货需求，没有取货需求；④每个客户的需求量和位置都是已知和固定的；⑤每个客户由且仅由一辆车提供服务；⑥每个客户都有期望时间窗和可接受时间窗；⑦冷藏车在运输途中匀速行驶，仅在客户点处停留；⑧仅配送一种生鲜农产品，货损比例已知；⑨冷藏车运输过程中车厢内外温度恒定。

1.2 参数说明

模型中相关重要参数定义如下：K为所需车辆总数；dij为客户i和客户j的距离；qi为客户i的需求量；tj为客户j卸货需要的时间；p为单位质量农产品的价格；v为配送车辆行驶速度；Mweight为车辆额定载重；λ为使用每辆冷藏车的固定成本；λ0为冷藏车单位距离运输成本；λ1为运输过程单位时间内的制冷成本；λ2为卸货时单位时间内的制冷成本(通常λ2≥λ1)；λ3为运输过程单位时间内的货损率；λ4为卸货时单位时间内的货损率(通常λ4≥λ3)；λ5为早到时单位时间惩罚成本；λ6为迟到时单位时间惩罚成本；[ETi,LTi]为客户i最佳服务时间窗；[AETi,ALTi]为客户i可接受时间窗；M为无穷大的惩罚成本。

决策变量定义为

(1)

(2)

1.3 模型建立

综合考虑成本和客户满意度两方面因素，优化目标为

(3)

式(3)中：minC表示最小化总成本C；maxS表示最大化客户满意度S。

1.3.1 成本因素分析

总成本主要包括固定成本、运输成本、制冷成本、货损成本和惩罚成本。

(1)固定成本：指安排车辆完成客户需求所产生的固定费用，包括车辆保养、维护、折旧损耗以及员工工资等费用，记为C1，计算公式如式(4)所示：

C1=λK

(4)

(2)运输成本：指冷藏车完成配送所需的燃油费用，通常与运输距离成正比，记为C2，计算公式如式(5)所示：

(5)

(3)制冷成本：包括运输途中车厢温度恒定的制冷成本和卸货过程中车门开启产生热交换的制冷成本，记为C3，计算公式如式(6)所示：

(6)

(4)货损成本：主要包括运输途中和卸货时产生的货损成本，记为C4，运输时车厢温度恒定，卸货时产生热交换引起车厢温度升高，导致运输和卸货时货损率不同，计算公式如式(7)所示：

(7)

式(7)中:ri表示离开客户i时车厢内货物重量。

(5)惩罚成本：在配送车辆未在客户定义的最佳时间窗内到达时产生，将其定义为无穷大的数M。任一客户i具有一个最佳服务时间窗[ETi,LTi]和可接受时间窗[AETi,ALTi]，若配送车辆在[ETi,LTi]之内到达客户i，不会产生惩罚成本；若在[ETi,LTi]之外、[AETi,ALTi]之内到达客户i，会产生一定的惩罚成本；若在[AETi,ALTi]之外到达，客户i将拒绝接受服务。客户i的惩罚成本P(ti)与车辆到达时间ti之间的关系如图1所示，其函数关系定义为

图1 惩罚成本与车辆到达时间关系Fig.1 Relationship between penalty cost and arrival time

(8)

由此可得所有客户的总惩罚成本C5，计算公式为

(9)

1.3.2 客户满意度分析

客户满意度主要依据时间窗进行定义，若在[ETi,LTi]之内到达客户i，则其满意度为100%；若在[ETi,LTi]之外，[AETi,ALTi]之内到达客户i，其满意度会有一定的降低；若在[AETi,ALTi]之外到达客户i，其满意度为0，不再接受服务。客户i的满意度S(ti)与车辆到达时间ti之间的关系如图2所示，函数关系定义为

图2 客户满意度与车辆到达时间关系Fig.2 Relationship between customer satisfaction cost and arrival time

(10)

总体客户满意度S依据每个客户的需求量占整体的比重分配相应的权重：

(11)

1.3.3 模型构建

根据上述分析，构建模型如式(12)～式(21)所示：

minC=C1+C2+C3+C4+C5

(12)

(13)

s.t.

(16)

(17)

(18)

(19)

(20)

AETi≤ti≤ALTi

(21)

式(12)为目标函数，即使综合成本最低；式(13)为目标函数，即使客户满意度最高；式(14)～式(21)为约束条件，其中式(14)、式(15)为决策变量取值约束；式(16)表示为车辆容量约束；式(17)、式(18)保证每个客户能且仅能被一辆车服务；式(19)表示配送中心共发出K辆冷藏车；式(20)表示每辆车从配送中心出发，最后返回配送中心；式(21)指每辆车都要在可接受时间窗内到达。

2 求解冷链物流车辆路径问题的遗传蚁群算法

由于所设计模型源于经典的属于NP(non-deterministic polynomial)难题的VRP问题，传统算法难以在有限时间内获得精确解，适宜采用智能算法。考虑蚁群和遗传算法是当前公认的较为常用且具有良好性能的智能优化算法，蚁群算法具有正反馈机制、局部寻优能力强，但存在搜索时间过长且会因信息素累积而陷入局部最优解；遗传算法具有较好的全局搜索能力，却过于依赖初始种群并因缺少反馈机制而存在冗余迭代。结合二者的优缺点，在ACO中引入GA的交叉算子和变异算子，设计遗传蚁群算法以求解该问题。首先通过ACO生成初始解，然后对其实施交叉操作和变异操作，以增加种群多样性，从而提高算法收敛速度和解的质量。

2.1 蚁群算法求解初始解

2.1.1 种群初始化

首先利用蚁群算法对种群进行初始化，得到初始种群，过程如下。

Step1将种群中每只蚂蚁的起始点设为配送中心并将其编号记为0，对于每只蚂蚁，在n个需求点中随机选取一个地点作为其第一个访问点，并记录到路径禁忌表中。

Step2构建解空间。对每只蚂蚁k(k=1,2,…,m)，按照状态转移规则选择每个待访问的地点，并修改禁忌表，直到全部蚂蚁访问完所有地点。

为了避免算法过早收敛，状态转移按照确定性选择和伪随机比例选择相结合的方式进行。确定性选择规则为

(22)

式(22)中:q0为初始化参数，且q0∈[0,1]；q为[0,1]区间内的随机数；τij(t)为启发函数，表示在t时刻的边(i，j)上的信息素大小；α为信息启发因子，表示信息素的相对重要性；ηij(t)表示从客户i到客户j的启发程度，且ηij(t)=1/dij；β为期望启发因子，表示能见度的相对重要性。

当q>q0时，采用伪随机比例选择，如式(23)所示：

(23)

式(23)中:Fk(k=1,2,…,m)为蚂蚁k待访问的需求点集合。

2.1.2 种群适应度计算

使用蚁群算法生成初始种群后，需要计算初始种群的适应度，获得当前最优解。由于研究目标为双目标，为求得种群的适应度，采用ε约束法处理双目标函数。ε约束法是一种处理多目标优化问题的有效方法，主要思想是先对其中一个目标函数f1(x) 进行寻优，寻得最优值ε，并将此值作为f1(x)的约束条件，在其不小于ε的条件下，寻找另一目标f2(x)的最优值，获得一组帕累托解。逐渐增加ε的值，并以此为约束求得f2(x)的最优值，通过多次求解，逐渐求得多组在f1(x)不同值情况下f2(x)的帕累托解。

由于成本受诸多因素影响，较难进行人为控制，而客户满意度的大小则可以依据企业的经营目标进行控制，因此将客户满意度作为约束。先对客户满意度进行寻优，寻得最优值ε，并将此值作为约束条件，在其不小于ε的条件下，寻找总成本的最优值，然后逐渐减小ε的值，并以此为约束求得总成本的最优值，获得帕累托解。种群适应度计算流程如下。

Step1分配配送路线。

Step2计算每条染色体的适应度。

Step3计算客户满意度。

Step4求解给定客户满意度情况下当前最优适应度和全局最优适应度，若当前最优适应度大于全局最优适应度，则将当前最优适应度作为全局最优适应度，并记录当前编码方式和路线分配方式。

2.2 遗传算法优化

2.2.1 交叉操作

染色体按照概率Pc(0≤Pc≤1)进行交叉，交叉方式采用部分映射交叉。将父代染色体两两分组，每组按照如下方式进行交叉。

Step1判断是否进行交叉操作。生成一个随机数，若随机数小于Pc，则该组染色体进行交叉操作，否则重新生成随机数，并判断下一组染色体。

Step2若进行交叉操作，则生成小于染色体长度的两个随机整数r1和r2，对应两个进行交叉操作的位置，对之间的染色体进行交叉。

Step3消除染色体冲突。由于交叉后可能存在重复标号和有的位置被覆盖，因此需要消除染色体冲突。采用部分映射的方法消除冲突，通过寻找冲突位置原始染色体对应的编号以取代被替换掉的编号。

Step4验证交叉后染色体是否符合要求，若符合则作为新的染色体进行下一步操作，否则舍去。

2.2.2 变异操作

染色体按照概率Pm(0≤Pm≤1)进行变异操作，变异方式采用以下策略。

Step1遍历每条染色体，每次生成一个随机数，若随机数小于Pm，则该染色体进行变异操作，否则判断下一条染色体是否进行变异操作。

Step2若进行变异操作，则随机选取该染色体的两个点，并将其对换位置，产生新的染色体。

Step3验证变异后染色体是否符合要求，若符合则作为新的染色体进行下一步操作，否则舍去。

2.3 更新信息素

所有蚂蚁完成一次路径分配后，按照式(24)、式(25)对路径上的信息素进行更新。

τij(t+1)=(1-ρ)τij(t)+Δτij

(24)

(25)

(26)

式(26)中：Lk为第k只蚂蚁经过路径的长度；Q表示蚂蚁循环一次所释放的信息素总量。Q过大时，会使信息素过于集中在某一路径，从而使算法早熟；Q过小时，路径上信息素浓度增长缓慢，从而使算法收敛速度慢。因此，对信息素总量Q采用分段函数进行优化：

(27)

式(27)中：ite为当前迭代次数；ite1、ite2、ite3为设定的一定迭代临界值。

算法伪代码如下。

Begin

Step1：初始化参数；

Step2：按照转移概率选择下一地点；

Step3：修改禁忌表；

If遍历完所有蚂蚁

计算适应度，更新已知最优解；

Else

选择下一只蚂蚁，跳转至Step2；

Step4：更新已知最优解；

Step5：进行交叉操作；

Step6：进行变异操作；

Step7：计算适应度，更新已知最优解；

If满足循环结束条件

输出最优解；

Else

更新信息素和迭代次数，清空路径记录表，跳转至Step2；

End

3 算例分析

以文献[6]中配送案例作为算例，研究单配送中心和20个门店的生鲜物流配送优化问题。实验设备采用联想PC机，操作系统为Windows 7 64位旗舰版，Intel i5 2450M CPU，2.5 GHz频率，6 GB内存，采用MATLAB R2014a作为仿真平台，分别采用遗传算法、蚁群算法和遗传蚁群算法进行求解，通过对比分析验证模型及算法的有效性。

3.1 算例描述

假设各配送点之间的距离均为欧氏距离，配送中心位置、各门店位置、客户时间窗、客户需求量和服务时间等详细信息如表1所示，所用参数值如表2 所示。

表1 某生鲜农产品配送中心配送数据Table 1 Data of a fresh agricultural products distribution center

表2 所需参数值Table 2 Parameter values

3.2 算法迭代次数分析

为了确定算法的最佳迭代次数，验证算法的稳定性，设置不同的迭代次数以求解在不同客户满意度情况下三种算法的最低成本。由于企业大都追求较高的客户满意度，分别选取100%、90%和80%三个较有代表性的满意度，并求解相应总成本。

在客户满意度为100%的情况下，三种算法不同迭代次数的求解结果如表3所示。

表3 客户满意度为100%时三种算法不同迭代次数最优解Table 3 Optimal results of three algorithms and iterations when customer satisfaction is 100%

客户满意度为100%时三种算法求解结果与迭代次数关系如图3所示。

图3 客户满意度为100%时三种算法求解结果与迭代次数关系Fig.3 Results of three algorithms and iterations when customer satisfaction is 100%

在客户满意度为90%的情况下，三种算法不同迭代次数的求解结果如表4所示。

表4 客户满意度为90%时三种算法不同迭代次数最优解Table 4 Optimal results of three algorithms and iterations when customer satisfaction is 90%

客户满意度为90%时三种算法求解结果与迭代次数关系如图4所示。

图4 客户满意度为90%时三种算法求解结果与迭代次数关系Fig.4 Results of three algorithms and iterations when customer satisfaction is 90%

在客户满意度为80%的情况下，三种算法不同迭代次数的求解结果如表5所示。

表5 客户满意度为80%时三种算法不同迭代次数最优解Table 5 Optimal results of three algorithms and iterations when customer satisfaction is 80%

客户满意度为80%时三种算法求解结果与迭代次数关系如图5所示。

图5 客户满意度为80%时三种算法求解结果与迭代次数关系Fig.5 Results of three algorithms and iterations when customer satisfaction is 80%

通过GA、ACO和GA-ACO三种算法在不同客户满意度下求得的最低成本进行对比后得到以下结果。

(1)在收敛速度方面，当客户满意度分别为100%和90%时，GA和ACO在迭代进行到500次时收敛，GA-ACO在迭代进行到400代时即收敛；当客户满意度为80%时，三种算法均在500代时收敛至最小值。表明GA-ACO收敛速度快于GA和ACO，能够在迭代次数较少时收敛，获得最优值。

(2)在求解结果方面，在相同迭代次数下，GA-ACO求解结果均优于GA和ACO；在求解精度方面，GA-ACO最终求得的最优解优于GA和ACO求得的最优解。

由于市场竞争激烈，客户满意度是企业竞争的关键因素，大都追求较高的客户满意度，因此，为提高求解效率和求解精度，设置GA-ACO的最大迭代次数Max_iter=400，GA和ACO最大迭代次数Max_iter=500。

3.3 算例求解

为了获得帕累托解，首先将客户满意度的初始值设为100%，并依次递减5%，分别用三种算法求解不同满意度下的最低成本，每种算法分别运行20次，取最优结果作为该算法求得的最终结果。三种算法求得的解如表6所示。

表6 GA、ACO和GA-ACO求解结果Table 6 Solution results of GA, ACO and GA-ACO

三种算法在不同客户满意度下求得结果的对比图如图6所示。

图6 GA、ACO和GA-ACO求解结果Fig.6 Solution results of GA, ACO and GA-ACO

通过对三种算法求解结果(表6、图6)对比发现，GA-ACO算法求解结果较GA和ACO更加优秀，在相同客户满意度条件下求得的总成本最低，表明设计的GA-ACO算法在相关问题求解上是有效的，并且优于GA和ACO。

对表6中数据进行分析表明，在客户满意度为100%时，总成本最高；当客户满意度降低至95%时，GA求得总成本降低8.9%，ACO求得总成本降低14.4%，GA-ACO求得总成本降低13%，降幅均较大；当客户满意度为80%，同客户满意度为95%时相比，GA求得总成本降低6.3%，ACO求得总成本降低1.2%，GA-ACO求得总成本降低2.2%，表明客户满意度在由95%降至80%时，总成本降幅较小；而当客户满意度低于80%时，总成本基本保持稳定，不再降低。这是由于客户满意度降低时虽然运输成本会降低，但是违反时间窗约束的惩罚成本会增加，当客户满意度低于一定值时，惩罚成本会很高，减少的运输成本并不能抵消增加的惩罚成本，因此总成本并不会降低。前述数据分析结果也进一步表明，对于逐步关注客户满意度的市场经营环境来说，由于100%的客户满意度要求过高，80%～95%的客户满意度在企业制定营销战略时是较好的选择。

4 结论

研究了带容量和软时间窗约束的双目标生鲜农产品冷链物流车辆路径问题，构建了以总成本最小和客户满意度最高为优化目标的双目标优化模型，采用ε约束法求解双目标函数，结合遗传算法和蚁群算法各自的优点，在蚁群算法中引入遗传算法的交叉和变异算子，设计了遗传蚁群算法。为验证模型与算法的有效性，对实际算例进行求解，并将其结果与遗传算法、蚁群算法求得结果进行对比。结果表明本文模型符合实际需求，所设计的遗传蚁群算法收敛速度和求解结果均优于遗传算法和蚁群算法。

但假设较为理想，如仅配送一种生鲜农产品、需求点之间距离为欧氏距离、车厢内外温度恒定、车辆匀速行驶等，与实际中的情况还存在一定的差异。在将来的研究中，可以考虑配送多种生鲜农产品、各需求点之间的实际距离、客户需求量不定、车厢外温度变化及道路交通情况和车辆抛锚等对车辆行驶造成的影响等实际因素，从而使研究内容更加符合现实中冷链物流企业的需要。