肖智豪，胡志华，朱琳
（上海海事大学物流研究中心，上海 201306）
冷链物流配送作为一项特殊的运输方式近年来备受关注。一方面是由于冷链配送车辆相比普通车辆需额外控制货舱温度，此举会产生更高的能耗和更多的碳排放。据国际能源署的统计结果表明，交通运输行业的碳排放量占全球总排放量的20%以上，而交通运输行业产生的碳排放有70%以上来自于公路运输［1］。为实现碳中和、碳达峰的总目标方针，节能减排对冷链物流企业尤为重要。另一方面，由于人们生活水平的提高，对于生鲜食品的需求也日益增加，这要求物流企业对生鲜进行合理的冷藏运输，否则会发生损毁、腐烂等情况。据联合国粮食及农业组织调查显示，全球有1/3 的食物消耗都是由于浪费或者损耗造成的，其中50%为生鲜食品［2］。因此，如何在保证客户满意度的同时，达到节能减排和减少货损的目标是当前冷链物流企业所面临的巨大挑战。
目前国内外很多学者都致力于冷链车辆路径问题的研究：殷亚等［3］对混合蝙蝠算法的单多点变异设定选择机制，提出了一种改进混合蝙蝠算法求解以成本最小、客户满意度最大的多目标生鲜配送最优路径选择模型；
方文婷等［4］针对蚁群算法阶段初期收敛速度过慢的问题，设计了一种结合A*算法和蚁群算法的混合蚁群算法，以求解冷链配送路径问题；
Song 等［5］则设计了一种改进人工鱼群算法求解以固定成本和能耗最小为目标的多车型冷链车辆路径问题；
为了改变目前冷链物流配送过程中成本最小化模型的应用现状，Zhao 等［6］设计了一种基于多目标启发式函数的改进蚁群算法。
随着研究的进一步深入，许多学者都将交通时变纳入到冷链车辆路径问题的考虑范围之内。考虑交通时变的车辆路径问题也被称为时间依赖型车辆路径问题（Time-Dependent Vehicle Routing Problem，TDVRP），最早由Malandraki 等［7］提 出，是车辆路径问题（Vehicle Routing Problem，VRP）的变式，属于组合优化中的NP（Nondeterministic Polynomial）-hard 问题，采用启发式算法可以高效求解该类问题。反映交通时变的行驶时间依赖函数可分为Malandraki 模型［7］和Inchoua 模型［8］：Malandraki 模型考虑将每天的时间划分为多个小段，每一段的行程时间固定，每个时段内的行驶时间按照当前的路况呈阶梯式分布；
Inchoua 模型用行驶速度代替行程时间，每个时间段内的行驶速度呈阶梯式分布，通过路径长度和行驶速度计算行驶时间，从而行驶时间连续变化。现有对冷链时间依赖型车辆路径问题的研究中，Osvald 等［9］、白秦洋等［10］、杜琛等［11］考虑了Malandraki 模型；
赵志学等［12］、付朝晖等［13］、任腾等［14］考虑了Inchoua 模型。
结合以上分析可知有关冷链时间依赖型车辆路径问题的研究已经形成了一定的成果，但还存在如下3 个问题：1）反映时变的两类行驶时间依赖函数和真实路况之间存在一定误差，其主要原因在于Malandraki 模型并不满足先进先出（First-In-First-Out，FIFO）准则，而Inchoua 模型虽然可以满足FIFO 准则，但由于其行驶速度跃迁变化，和实际情况之间存在较大差异；
2）对于车辆行驶过程中油耗量的评估，以往的研究中学者们多采用负载估计法［15］描述载重量和油耗的关系，但该方法按载重量比例估算油耗，和真实值之间存在一定误差；
3）目前很多学者都考虑采用基于随机邻域搜索一类的元启发式算法来求解同类型的车辆路径问题，尽管该类算法的求解速度快，但是搜索随机性较强，从而导致搜索精确度较低，难以满足求解现有复杂路径优化问题的要求。
针对以上3 个问题，本文另考虑了一种连续型行驶时间依赖函数，车速在不同时段之间连续变化，以更加真实地反映城市交通拥堵状况，同时还采用综合油耗模型来衡量冷藏车行驶过程中的实时燃油消耗量，以准确反映车辆行驶时间和载重量对于行驶油耗的影响；
此外，以总成本最小为目标建立数学优化模型，并为获得良好的求解效果，本研究从自适应大邻域搜索（Adaptive Large Neighborhood Search，ALNS）的角度出发对该模型进行求解。ALNS 算法能够采用不同的算子对可行解进行指导性的破坏和修复，并在此基础上增加了对算子作用效果的衡量，使算法能够选择好的算子进行搜索，从而获得良好的局部寻优的能力，目前已被广泛应用于车辆路径问题［16-19］中；
但该算法全局搜索的能力较弱，容易陷入局部最优。因此将本文设计的破坏-修复大邻域搜索算子融入人工蜂群（Artificial Bee Colony，ABC）算法之中，以进一步提高算法的全局搜索能力。
1.1 问题描述
本研究以连续型行驶时间依赖函数为基础，综合考虑车辆行驶油耗成本、制冷成本、货损成本、碳排放成本等其他成本。问题具体表述为：多辆同类型的冷藏车从同一配送中心出发，按一定顺序向同一城市中不同位置的客户点提供送货服务，在完成配送任务后返回配送中心。每个客户具有不同的需求，且不超过冷藏车的最大载货量。所有车辆最大载货量相同，且配送车辆的行驶速度受交通拥堵的影响而连续变化。每个客户都有时间窗要求，提前或者延迟到达都会产生惩罚费用。另外对问题还做出如下假设：
1）配送中心的库存量满足所有客户点的需求，且配备足够多的冷藏车为客户点提供配送服务。
2）任意两个客户点之间的最短距离是提前计算好的，在配送过程中不会改变，只有车辆行驶速度和行驶时间会受路况影响而改变。
3）车辆行驶速度只受到早晚交通车流量高峰期的影响，不考虑行人、气候等因素。
4）车辆行驶油耗不会受到驾驶员主观因素的影响而变化。
1.2 符号定义
给定一个有向完全图G=(N，A)，N={0，1，…，n}为所有节点的集合，0 表示冷链物流中心，N{0}表示需要服务的客户集合，A={(i，j)，i∈N，j∈N，i≠j}表示任意两节点之间的最短路径集合。配送中心一共有K辆冷藏车，k=1，2，…，K。Qmax表示车辆最大装载重量，车辆从客户i到客户j的行驶过程中搭载的货物重量为Qij。客户i的需求为qi(i∈N)。dij表示客户i到客户j之间的距离。vf表示自由流速度，vc表示拥堵速度，vc∈(0，vf]。tki表示车辆k到达客户的所需要的时间，表示客户i期望被服务的时间窗要求表示客户i接受服务的时间，tij表示车辆从顾客i到顾客j的通行时间。zk为0-1 变量，车辆k被使用则zk=1，否则zk=0；
yki为0-1 变量，yki=1 表示车辆k服务客户i，否则yki=0；
xkij为0-1 变量，如果车辆k途径客户i到达客户j，则xkij=1，否则xkij=0。
1.3 车辆行驶时间计算
连续型时间依赖函数考虑车辆行驶速度受一天内早晚高峰的影响而平滑改变，如图1 所示。
图1 接近真实路况的连续型时间依赖函数Fig.1 Continuous time dependent function close to real road conditions
将一天的时间分为多个时段，时段集合为H，每一时段h∈H，不同时段间的速度连续改变，因此可用线性函数表示每段时间内的速度：
其中：Vh(t)表示在时段h中和时间t线性相关的速度函数；
Vh表示时段h的初始速度；
th表示时段h的初始时间；
(Vh+1-Vh)/(th+1-th)表示车辆在时段h的加速度，后文简化为αh表示。
本文还考虑两级速度函数［20］以计算经历速度拐点的过渡路段所耗行程时间，并对两级速度函数进行改进以更好适应连续型时间依赖函数。若某一车辆在从客户i到客户j的行驶过程中从时段h进入时段h+1，假设车辆离开上一个客户点i的时间为x，时段h的终止时间为y。两个客户位置间的距离为dij，tij(x，vh)表示车辆在客户i和客户j之间的行驶时间。车辆在时段h+1 中行驶的距离为：
考虑车辆均匀变速的理想情况下，通过构建一元二次方程求解变速行驶时间，并忽略车辆减速时的折返效应，则在时段h+1 中的行驶时间为：
因此tij(x，vh)计算公式如下：
1.4 目标成本分析
本文考虑车辆实际配送过程中所产生的行驶油耗成本、制冷成本、碳排放成本、货损成本，此外还考虑了固定成本和时间惩罚成本，各项成本分析和计算公式如下。
1.4.1 行驶油耗成本
车辆在运输过程中会产生燃油消耗，不同载重量会产生不同的油耗。为更好地体现时间对油耗的影响，本文采用综合油耗模型求解。该模型由Barth 等［21］提出，本文在此基础之上进一步改进以适应连续型时间依赖函数。相关的参数及其取值参照文献［20］，如表1 所示。
表1 车辆参数定义与取值Tab.1 Definition and value of vehicle parameters
载重Q（kg）货物的冷藏车以恒定车速v（m/s）行驶d（m）距离所产生的油耗量F（L）为：
考虑连续型时间依赖行驶函数的油耗计算可分为两种情况。
第一种是车辆行驶路段中不包含速度函数的拐点，相应油耗计算公式如下：
第二种是包含速度函数拐点的过渡路段，相应油耗计算公式如下：
综上所述，行驶油耗成本，也即车辆运输成本C1为：
1.4.2 制冷成本
本文考虑配送中心派发同类型车辆提供服务，车厢整体劣化程度及车辆性能参数均保持一致，且卸货过程中只打开一次车门，故而制冷成本可近似看作与时间呈正线性相关。冷藏车一般配备独立的制冷机组以保证车厢内部恒定低温，而制冷机组在制冷过程中会产生燃油和制冷剂的消耗，因此制冷成本C2包括燃油消耗成本和制冷剂消耗成本。
制冷机组的燃油消耗又可分为运输时产生的燃油消耗成本和卸货时产生的燃油消耗成本。令θ1和θ2分别表示运输过程和卸货过程中产生的单位热负荷燃油消耗量，Gt为车辆在行驶过程中产生的单位时间热负荷。燃油消耗成本的计算公式如下：
同理，制冷剂消耗成本也可分为运输时产生的制冷剂消耗成本和卸货时产生的制冷剂消耗成本。令ϑ1和ϑ2分别表示运输过程和卸货过程中产生的单位时间制冷剂消耗成本，则制冷剂消耗成本为：
1.4.3 碳排放成本
本文考虑碳税以衡量碳排放成本。碳税政策正逐渐成为许多国家激励减排的有效工具，其是指将二氧化碳排放带来的环境成本转化为企业生产经营成本。冷藏车燃油消耗一部分来自发动机引擎，一部分来自制冷机组。由Barth等［22］可知，车辆的碳排放量和燃油消耗量呈线性正相关性，因此可以根据式（8）和式（9）计算车辆行驶过程中的碳排放量，根据式（11）计算冷藏车制冷所产生的碳排放量。令ω表示每单位体积的油耗所产生的二氧化碳排放量，Pt表示单位体积二氧化碳所需支付的碳税。故碳税成本C3的计算公式如下：
1.4.4 货损成本
冷链货物具有易损、易腐等特性。由于冷藏车制冷机组能够将温度控制在相对安全的范围内以适宜冷藏货物的存放，因此考虑货损成本仅与运输时间和卸货时间有关。货损成本C4主要包括运输过程中的货损成本和卸货过程中产生的货损成本。Pg为货物单价，δ1为单位时间运输货损率，δ2为单位时间卸货货损率。运输过程中生鲜产品的自然呼吸作用会导致新鲜度下降，从而导致货损，相应的成本计算如式（13）：
卸货过程中，由于冷藏车车厢门开启而产生热交换，也会导致生鲜产品新鲜度下降，相应的成本计算式如下：
1.4.5 其他成本
1）固定成本C5。C5为使用冷藏车完成某一路径上客户的配送而产生的固有费用，包括车辆的折损费用、维修费用、保养费用、驾驶员薪资等，与参与配送的冷藏车数量成正比，可以表示为：
其中Fk表示单位车辆所产生的固定成本。
2）时间惩罚成本C6。C6客户通常要求冷链货物在规定时间范围内送达，超出该规定时间范围送达货物会降低客户满意度，因此本文考虑软时间窗惩罚成本，提前或者延迟交付货物都会产生惩罚费用。令μ1和μ2分别表示提前交货和延迟交货所产生的单位时间惩罚成本，则时间惩罚成本可表示为：
结合上述分析，以行驶油耗成本C1、制冷成本C2、碳排放成本C3、货损成本C4、固定成本C5和时间惩罚成本C6总和最小为目标函数，如式（17）所示，根据文献［23］中的TDVRP模型，构建如下车辆路径优化模型：
式（18）表示每位客户只由一辆冷藏车进行配送；
式（19）表示车辆到达某一客户点后必须从该客户点离开，以保证路径的连贯性；
式（20）表示每条车辆路径上总的客户需求不超过车辆最大容量；
式（21）表示每个客户只能被服务一次；
式（22）表示离开配送中心的冷藏车在完成配送后必须返回配送中心；
式（23）表示车辆到达下一个客户的时间是车辆到达上一个客户的时间、上一个客户的服务时间以及上一个客户到下一个客户的车辆行驶时间之和，车辆运行是一个连续的过程；
式（24）是为了消除子回路；
式（25）表示决策变量的取值范围。
ALNS 局部寻优能力更加精准，有较高的概率探索到更优解，但这也导致算法容易陷入局部最优，因此本文将自适应大邻域搜索算法融入ABC 算法中，提出了一种自适应大邻域搜索人工蜂群（Adaptive Large Neighborhood Search Artificial Bee Colony，ALNS_ABC）算法，以提高全局寻优的能力。另外算法采用自然数方式进行编码，并且对应的适应度值用目标总成本的倒数进行表示，即fit=1/C。
3.1 大邻域搜索算子设计
本文的目标成本主要和通行时间密切相关，而通行时间又和速度、路程相关，此外问题的特点还包括客户的时间窗要求，因此本文所提的大邻域算子主要围绕以上4 个特点进行设计。此外关联度算子、随机算子、贪婪算子、遗憾准则算子都是通用自适应大邻域搜索算法中高效的搜索算子，也都被本文考虑在内。另外在执行修复操作的同时需要保证修复后的解为可行解，即满足车辆的容量约束。本文使用了6种破坏（移除）算子和5 种修复（插入）算子。
3.1.1 破坏算子
1）关联度移除。该方法最初由Shaw［24］在1998 年提出。为适应本文研究的问题对该算子做出进一步改进，其基本原理是移除一组相关联的点，客户i和客户j之间的关联性由R(i，j)表示，其表达式如下：
其中：φ1、φ2、φ3、φ4分别代表距离、时间窗、需求以及路径的权重系数。R(i，j)越小表示两节点间的关联度越高。移除的所有节点之间要保证关联度尽可能低。如果i和j在同一条路径上，则φ4=1，否则为0。首先随机选择一个点放入被移除点的集合Lr，然后从未移除点集中选一个点j，根据公式j=argmin{R(i，j)}选择Nr个客户进行移除。通常情况下φ1=6，φ2=5，φ3=4。
2）时间最长移除。该算子的思想是移除对路径时间影响最大的点，以此减少整条路径上的通行时间。试探性地移除路径上的每一个点，并计算移除该点后路径行程的缩短时间。更新当前路径，并不断执行移除操作直到Nr个客户点被移除。
3）时间窗最远移除。由于本文考虑了时间惩罚成本，因此需要保证车辆抵达时间尽可能靠近客户时间窗要求。移除车辆抵达客户的时间离客户要求的时间窗最远的客户点。若车辆抵达时间满足客户i的时间窗，Δti=0，否则：
4）最 大速度差移除。该方法由Franceschetti 等［18］在2017 年提出，其基本思想是移除车辆抵达途径客户时前后出入速度之差最大的客户。本文研究考虑平均速度，前一条路径的速度为vij=dij/tij(x，vh)，后一条路径的速度为vjl=djl/tjl(x，vh)，前后路径 速度差为Δvj=vij-vjl。根 据j=argmax{Δvj}选择Nr个客户进行移除。
5）路径随机移除。该算子旨在为算法加入随机因素，以减少陷入局部最优的可能性。选择总成本最大的一条路径，再随机选择该路径上的一个客户进行移除，同时更新路径。不断执行移除操作直到Nr个客户被移除。
6）最差移除。该算子旨在移除对整条路径的成本费用影响最大的点，从而直观地减少总的运输成本。计算每一个点移除以后和未移除之前的目标函数差值，选择差值最大的客户点进行移除，同时更新路径。重复执行移除操作直到Nr个客户被移除。
3.1.2 修复算子
1）时间窗最近插入。从Lr中随机取出一个客户点m，试探性地将其插入到路径上的某一位置后，卡车到达m的时间为tkm，如果其插入以后的前一个点为i，则tkm=tki++tim。保证m插入到tkm和差值最小所对应的位置，即m=argmin{|tkm-|}，重复上述操作直到Lr为空集。
2）距离最短插入。从Lr中随机取出一个客户点m，将其插入客户i和客户j之间，那么总里程增量Δd(i，m，j)=dim+dmj-dij，选择增量最小的位置进行插入，即m=argmin{Δd(i，m，j)}，重复上述操作直到Lr为空集。
3）时间最短插入。从Lr中随机取出一个客户点m，将其插入客户i和客户j之间，那么总时间增量Δt(i，m，j)=t(0，…，i，m，j，…，0) -t(0，…，i，j，…，0)，选择增量最小的位置进行插入，即m=argmin{Δt(i，m，j)}，重复上述操作直到Lr为空集。
4）最优贪婪插入。选择对目标函数值影响最小的位置进行插入。随机选一个点，判断该点插入某一位置后该条路径的总成本增加值，选择增加值最低所对应的位置进行插入，重复上述操作直到Lr为空集。
5）遗憾准则插入。该算子在最优贪婪插入算子的基础上多考虑了一步，以保证算子的多元性。评估每一个移除点被插入的最优位置和次优位置，并计算最少的总成本增量和次少的总成本增量之间的差值。所有移除点对应该差值进行从大到小的排序，并按照该顺序选择下一个要插入的点，以最优贪婪方式进行插入。
3.1.3 自适应权重调整
每一次搜索过程中，移除和插入算子的选择都基于轮盘赌规则，以此增加算子选择的多样性。在计算开始时，每一个算子都有相同的权重和分值，并且初始分值为1。根据算子的不同表现情况阶梯式给分，得分越高表明算子表现越好。每一次计算过程中算子加分情况如下：
1）新解被接受作为下一次邻域搜索的出发解，得5 分。
2）新解被接受作为下一次邻域搜索的出发解，并作为当前最优解，再得5 分。
3）新解未被接受为下一次邻域搜索的出发解，且比当前解更差不得分。
根据每一轮的平均得分来计算当前算子参与轮盘赌选择的权重。此外还设定了一个权重更新系数ρ以避免收敛速度过快陷入局部最优。算子的权重按照式（28）更新：
其中：ηa为权重，sa为累计得分，ua为累计使用次数。
3.2 自适应大邻域搜索人工蜂群算法
人工蜂群算法是一种模拟蜜蜂采蜜行为的群智能算法，通过不同蜂种之间的分工合作，以实现优良的全局探索能力。在ABC 算法中，用蜜源的位置来表示解，用蜜源的花粉数量表示解的适应度值。所有的蜜蜂划分为雇佣蜂、跟随蜂、侦察蜂三组。雇佣蜂和跟随蜂各占蜂群总数的一半。雇佣蜂负责最初地寻找蜜源并采蜜分享信息，跟随蜂负责呆在蜂巢里根据雇佣蜂提供的信息去采蜜，侦察蜂在原有蜜源被抛弃后负责随机寻找新的蜜源来替换原有的蜜源。本文考虑用大邻域搜索方式替换ABC 算法中常用的随机邻域搜索方式。
3.2.1 初始解构造
首先在ALNS_ABC 算法中考虑构建出较为良好的初始解以提高求解质量。根据贪婪插入策略进行初始解的构造，需要注意的是本文根据距离最短进行插入，而非时间或者目标值最少时进行插入，以避免算法结果过早收敛而陷入局部最优。具体步骤如下：
步骤1 将所有客户点放入一个客户列表Lc中。
步骤2 从Lc中随机取出一个点放入一条空路径中并与配送中心相连。
步骤3 随机从Lc中取出一个点x，试探性地将其插入路径中的每一个位置，并计算相应的距离成本增量，计算公式如下：
其中：g(x)的计算包括两部分，一部分是实际距离的增量，另一部分是考虑插入的x离配送中心太远而产生的惩罚费用；
r表示惩罚系数，取一个固定的值0.3。客户点x在对应距离成本增量最低的位置进行插入。
步骤4 更新当前路径，重复执行步骤3，直到路径满足最大容量约束，该条路径构造结束。
步骤5 重复步骤2～4，直到客户列表Lc为空集。
3.2.2 ALNS_ABC算法设计
算法实现的具体步骤描述如下：
步骤1 参数初始化。确定蜜源的数量S，蜜源最大开发次数limit，最大迭代次数MaxIter，初始算子权重ηa集合、权重惯性因子ρ1，搜索范围也即移除和插入点个数Nr。
步骤2 蜂群初始化。根据初始解构造方法生成S组初始蜜源，每个蜜源即为一个初始可行解，每个可行解对应一组信息列表，包含了蜜源开发次数、各项算子的得分和各项算子的权重三类信息。
步骤3 雇佣蜂阶段。每只雇佣蜂采用轮盘赌方式选择对蜜源进行大邻域搜索的破坏-修复算子，每一次进行大邻域搜索后按贪心策略对蜜源进行选择，并且更新被使用算子所对应的分值和权重：如果通过大邻域搜索找到一个比当前蜜源质量更好的新蜜源，则替换原有蜜源，同时对记录的开发次数进行清零；
如果没有找到更好的蜜源，则增加一次开发次数。
步骤4 跟随蜂阶段。雇佣蜂向跟随蜂分享当前蜜源信息。跟随蜂根据蜜源的适应度值，也即目标总成本的倒数，采用轮盘赌策略选择蜜源进行跟踪开采，以保证质量更高的蜜源开采的概率更大。跟随蜂开采过程与雇佣蜂一样，通过大邻域搜索找寻新蜜源，并采用贪心策略对蜜源进行选择，同时更新开发次数以及算子的分数和权重。
步骤5 侦察蜂阶段。如果一个蜜源达到开发次数上限，则抛弃该蜜源，再根据构造初始解的方法搜索一个新的蜜源，并对开发次数进行清零；
同时需要还原算子所对应的分数和权重，因为新产生的解已经破坏了原有的邻域搜索结构，沿用之前的算子得分和权重对算子进行选择会造成搜索效果的偏差。
步骤6 重复步骤3～5，直到满足最大迭代次数。
4.1 实验算例与参数设置
本文分别选取文献［4］中的实例数据和Solomon 测试数据库中的VRPTW 算例数据进行仿真分析。货车在市区通行的自由流速度一般为40 km/h，另外本文考虑早高峰时段为6：00～10：00、晚高峰时段为16：00～20：00，早晚高峰的拥堵速度为25 km/h，中午12 时的拥堵速度为30 km/h。冷藏车每天上午8：00 出发进行配送服务。为方便研究，以直线距离作为客户位置间的最短距离，实验结果保留两位小数。车辆相关参数已在表1 中给出；
成本相关参数参照文献［4］，如表2 所示。
表2 成本相关参数Tab.2 Cost related parameters
本文认为R1、RC1 类数据集时间窗较窄，服务时间较短，更类似于冷链配送的情况，因此采用Solomon 测试数据库中的数据集R101-R103（随机分布）以及RC101-RC103（半堆分布）进行测试。此外，由于冷链配送呈现“批次多、批量少”的特点，客户规模相对较小，因此分别截取前25 和50 个客户点进行算法测试分析。
本文还另设计3 种混合ALNS 算法作为比较基准。1）自适应大邻域搜索精英蚁群算法（Adaptive Variable Neighborhood Search Elite Ant Colony，ALNS_EAC），该算法在蚂蚁完成周游后加入对精英蚂蚁进行自适应大邻域搜索的操作，直到连续10 次搜索都没有找到更优蚂蚁路径再更新信息素浓度。2）自适应大邻域搜索精英遗传（Adaptive Large Neighborhood Search Elite Genetic，ALNS_EG）算法，该算法用大邻域搜索算子代替传统遗传算法的变异算子，并保留较优个体。3）自适应大邻域搜索模拟退火（Adaptive Large Neighborhood Search Simulated Annealing，ALNS_SA）算法，该算法根据Metropolis 准则决定是否接受当前解。
使用Python3.7 在Anaconda 环境下编写算法求解。为保证实验的公平性，实验对比分析的各算法编码方式相同，大邻域搜索范围Nr=5，权重惯性因子ρ1=0.7。ALNS_ABC的参数设置为：蜜源数S为20，雇佣蜂和跟随蜂的数量各为10，最大开发次数limit为20。ALNS_EAC 的参数设置为：蚂蚁数M为20，信息素重要因子α1=1，启发式函数重要因子β1=3，信息素挥发因子γ1=0.7。ALNS_EG 的参数设置为：种群数为20，交叉率为0.9，变异率等价为邻域搜索范围Nr。3 类群智能算法迭代次数都为100，种群规模都为20。ALNS_SA 的参数设置为：初温T0为30℃，退火系数θ为0.96，终止温度为0.3，同一温度下的迭代次数为20。
4.2 仿真分析
采用ALNS_EAC、ALNS_EG、ALNS_SA、ALNS_ABC 四类混合算法和文献［25］中自适应可变邻域搜索精英蚁群（Adaptive Variable Neighborhood Search Elite Ant Colony，AVNS_EAC）算法（为保证可对比性还同时考虑了精英策略）分别对15 个客户点的实例数据进行10 次随机模拟仿真实验，各算法最优、平均结果以及最优路径如表3 所示。
由表3 可知，AVNS_EAC 的求解效果最不理想，相比之下，ALNS_EAC 求解性能更好，这说明自适应大邻域搜索算子比通用的随机邻域搜索算子拥有更高的搜索精度，能有效提高求解质量。其他四类混合算法都取得了相同的最优结果，且相较于AVNS_EAC 都有较大提升。从平均结果来看，ALNS_EAC、ALNS_EG、ALNS_SA，ANS_ABC 相较于AVNS_EAC 分别提升了7.1%、6.8%、6.6%、7.4%。可以看出ALNS_ABC 算法的提升效果相比之下较为明显。
表3 实例数据仿真结果Tab.3 Simulation results of data of a case
4.3 算法对比分析
为进一步对比四类混合算法在求解该类问题上的性能，根据Solomon 测试数据库中的R101-103、RC101-103 客户数据，分别截取前25、50 个客户点进行实验分析。数据集R101-103 的客户地理位置是随机生成的，数据集RC101-103的客户位置呈混合随机聚类分布。各参数和实例中保持一致，同时为保证结果的真实性，数据集中客户的需求和车辆容量扩展为原有的10 倍。
采用ALNS_EAC、ALNS_EG、ALNS_SA、ALNS_ABC 四类混合算法分别对以上所述的12 组数据分别进行10 次随机仿真实验，并计算所有结果的平均值，实验具体计算结果见表4。通过实例结果可知AVNS_EAC 的性能低于其他各类混合算法，因此用AVNS_EAC 对12 组数据各运行10 次，并将其平均结果作为对照依据，测试各算法在此基础之上的提升效果，以更加直观地评估四类混合算法的性能，具体结果如图2 所示。此外，为证明本文所构模型和算法同样适用于Solomon 测试数据库，分别对R101-50、RC101-50 数据组最好结果所对应的车辆运行图进行模拟，如图3 所示。
图2 不同混合算法的提升效果Fig.2 Improvement effect of different hybrid algorithms
图3 数据组R101-50、RC101-50的最优车辆运行图Fig.3 Optimal vehicle routing diagrams of data group R101-50 and RC101-50
表4 算例仿真结果Tab.4 Numerical example simulation results
从表4 可以看出12 组数据下的最好结果有10 次都是由ALNS_ABC 算法找到，这直接证明该算法在求解中小规模问题上寻优能力最强，能充分发挥大邻域搜索算子的作用，获得更优的局部搜索精度。而ALNS_EAC 只有4 次搜索到最好的结果，ALNS_SA 只有2 次，ALN_EG 只有1 次，说明其余三种算法的搜索精准度相对较低。结合图4 对比分析各算法的平均结果，可以看出，ALNS_ABC 在所有50 个客户规模数据下的平均结果表现都是最好的，反观ALNS_EG 在客户规模越大，客户位置分布越复杂的情况下，求解效果越不理想。ALNS_EAC 在25 个客户规模下的求解效果与ALNS_ABC 相近，而在50 个客户规模数据的求解上效果稍弱；
ALNS_SA 在25 个客户规模下的求解效果与ALNS_EG 相近，而在50 个客户规模数据的求解上与ALNS_EAC 相近。综合来看，采用ALNS_ABC 进行求解效果会更好。另外，由图4 可以看出，算法最优结果所对应的车辆行程较为理想，进一步说明了本文所构建模型和算法的有效性。
随后进一步对比算法的收敛性和稳定性。ALNS_EAC、ALNS_EG、ALNS_SA 和ALNS_ABC 四类混合算法随机运行10 次后的收敛时间如表5 所示。此外，用箱型图观察四类混合算法在求解50 个客户点的数据组时解的分布情况，如图4所示，其中加粗线条表示中位数，盒子的顶端表示上四分位数，底端表示下四分位数，竖线表示该组结果的平均偏差，竖线顶端的横线表示最大值，底端的横线表示最小值，空心圆表示异常值。
图4 数据组R101-103-50、RC101-103-50的箱型图Fig.4 Box-plots of data group R101-103-50 and RC101-103-50
表5 不同算法的时间对比Tab.5 Comparison of time among different algorithms
1）收敛性。由于各算法每次迭代会选择不同算子进行邻域搜索，而不同算子计算复杂度也不同，因此计算的CPU时间有较大差别。结合表5 进行分析可知，ALNS_SA 收敛速度快，但更容易陷入局部最优，相比其他群智能算法“爬山”能力较弱；
而ALNS_EG 求解时间长，收敛速度慢，求解效果也不理想。ALNS_ABC 比ALNS_EAC 在求解较小规模算例时的CPU 时间较长，但收敛速度快，而在求解较大规模算例时，尽管收敛速度稍慢，但CPU 时间更短。
2）稳定性。在图4 中，AEG1 代表ALNS_EG 求解序号为101 的50 个客户点数据集时所对应的箱型分布。综合来看，ALNS_EG 箱盒最长，求解效果不稳定。ALNS_SA 的箱盒箱较长，且有较多异常值出现。ALNS_EAC 在数据集R1 类数据集中箱盒较长，且存在异常值，求解效果不稳定，而在RC1类数据集中箱盒较短。ALNS_ABC 在6 类数据集中箱盒都较短，且只在1 组数据集的求解中出现异常点，尤其是在求解RC1 类数据集时，箱盒都非常短，因此可以认为ANLS_ABC在寻优过程中具有更强的稳定性。
综合以上分析可知，自适应大邻域搜索算法比随机邻域搜索有更强的局部寻优能力，考虑在其他元启发式算法中加入大邻域搜索算子能够提高算法的求解精度，获取更高的求解质量；
同时实验也证明，人工蜂群算法能充分发挥大邻域算子的优势，将人工蜂群算法和自适应大邻域搜索算法相结合效果最佳，能稳定且有效地求解本文所构建模型。
为助力实现碳中和、碳达峰的总目标方针，绿色、低碳和环保正逐渐成为当今企业发展的核心理念。物流企业如何在保证自身经济效益的前提下，构建绿色供应链体系，实现物流与生态的和谐发展，是当前所面临的一大挑战。本文着眼于冷链物流配送中高能耗、高排放、易货损的问题，结合城市路网中速度连续动态变化的情况，在考虑各项配送成本的基础上构建路径优化模型。本文设计了6 种破坏算子和5 种修复算子，并将大邻域搜索算子组合融入ABC 算法，提出了一种ALNS_ABC 算法，以提高全局搜索的能力。最后将所提出的ALNS_ABC 算法和ALNS_EG、ALNS_EAC、ALNS_SA 算法以及已有文献中的AVNS_EAC 算法进行对比分析。实验结果表明自适应大邻域搜索的寻优精度高，同时将自适应大邻域搜索算法和人工蜂群算法相结合能充分发挥大邻域搜索算子的优势，获得更加高效的寻优能力。
未来的研究中可以通过地图软件获取实时交通信息，综合考虑拥堵、天气、行人等因素，采用人工神经网络的方式拟合非线性连续型时间依赖函数，以更加精准地预测车速的实时变化。另外，也可以考虑多车型、多配送中心、多温共配等其他冷链运输情况，为保障企业经济效益，实现绿色环保发展提供更为科学合理的决策方案。
猜你喜欢 蜜源算子冷链 林下拓蜜源 蜂业上台阶林业与生态(2022年5期)2022-05-23中国冷链物流：应对冬奥的技术大考科技创新与品牌(2022年4期)2022-05-08国务院办公厅印发 《“十四五”冷链物流发展规划》农村百事通(2022年2期)2022-03-11Domestication or Foreignization：A Cultural Choice校园英语·上旬(2020年1期)2020-05-09重庆市冷链物流共同配送模式的研究智富时代(2019年4期)2019-06-01重庆市冷链物流共同配送模式的研究智富时代(2019年4期)2019-06-01指示蜜源的导蜜鸟高中生·天天向上(2018年1期)2018-04-14QK空间上的叠加算子卷宗(2017年16期)2017-08-30蜜蜂采花蜜学苑创造·B版(2015年12期)2016-06-23逼近论中的收敛性估计国外科技新书评介(2014年12期)2015-01-05