基于混合蚁群算法的冷链电动汽车车辆路径问题

刘志硕，刘若思，陈哲

（北京交通大学 交通运输学院，北京 100044）

0 引言

随着居民生活水平的提高，人们对瓜果蔬菜、禽蛋肉奶等生鲜产品的需求与日俱增。然而，冷链物流对环境和能源会产生更大的负面影响［1］。由于装载货物的特殊性，在运送途中必须提供低温环境以维持货品的质量，这无疑会消耗更多的能源和排放更多尾气。有数据显示，冷藏燃油车行驶过程中排放的尾气大约是普通燃油货车的1.3 倍。由此可见，随着冷链物流市场规模的不断扩大，其导致的环境污染和能源消耗问题也会愈演愈烈。

交通是温室气体排放的主要领域之一，随着我国私家车保有量的不断提升，大力发展“零碳排放”的电动汽车是降低交通碳排放的有力手段。电动汽车与燃油车相比，具有环境污染小的特点，将电动汽车应用于冷链物流领域承担运输和配送任务，对于缓解环境污染和降低化石能源消耗至关重要［2］。我国已经有一些冷链物流企业开始尝试采用电动冷藏车开展冷冻食品的末端配送。如何制定科学合理的配送方案来解决配送成本高、客户服务水平低等难题对基于电动汽车的冷链物流配送业务来说显得尤为重要。

本文将电动汽车的车辆路径问题（Vehicle Routing Problem，VRP）与冷链物流加以结合，建立了数学模型，设计了一种混合蚁群（Hybrid Ant Colony Optimization，HACO）算法求解。

本文的主要工作为：1）场景创新，顺应绿色物流的发展，着眼电动冷链车的路径规划问题，将电动汽车路径优化问题与冷链物流加以结合；2）模型创新，针对研究主体，建立了混合整数规划模型，在目标函数中创新考虑了冷链电动汽车的制冷成本。设计混合蚁群算法进行求解并设计了适合社会充电站的转移规则以及4 种局部优化算子，通过实验验证了所提算法的性能。

1 相关工作

1959 年Dantzig等［3］首次提出了车辆路径问题（VRP），该问题是物流研究领域中一个具有十分重要理论和现实意义的问题。目前，国内外已对车辆路径问题作了大量而深入的研究。求解性能较好的启发式算法主要有模拟退火算法、遗传算法、禁忌搜索（Tabu Search，TS）算法、粒子群优化（Particle Swarm Optimization，PSO）算法、大规模邻域搜索算法等。

1996 年Dorigo等［4］提出了蚁群（Ant Colony Optimization，ACO）算法，蚁群算法是一种用来搜索优化路线的几率型算法。它的开发受到自然界中蚂蚁智能行为的启示，有关学者汲取蚂蚁群体的多样性和内部存在的正反馈机制，开创了具有搜索能力强、收敛速度快等特点的启发式算法。蚁群算法在VRP 中得到了广泛的应用。Reed等［5］在研究垃圾回收的车辆路径问题中，提出使用蚁群算法来求解多隔舱的车辆路径问题。Li等［6］设计了改进的蚁群算法来解决多车场、多目标的车辆路径问题，提出了一种基于收益最大化，成本、时间和排放量最小化的多车场绿色车辆路径问题，设计改进的蚁群算法对问题进行了有效求解。Guo等［7］设计了改进的混合蚁群算法，以最小化总里程为目标求解多车厢车辆路径问题，并设计了基于加速搜索和先动策略的两种变邻域下降技术提高数据挖掘能力。Mutar等［8］提出一种改进的蚁群算法求解带车辆能力约束的车辆路径问题。

从冷链车辆路径问题（Refrigerated Electric Vehicle Routing Problem，REVRP）来看，Osvald等［9］考虑到新鲜蔬菜易变质的特点，提出有时间窗和行程时间约束下的冷链车辆路径问题，并设计了禁忌搜索算法求解。Amorim等［10］为解决葡萄牙食品分销公司面临的复杂的冷链车辆路径问题，构建了多时间窗的异构车队路径规划问题的模型，并使用自适应大邻域搜索算法求解。Abdi等［11］考虑去送回收作业的生鲜产品VRP，以同时提货和分货提高供应链效率，以多产品多周期的形式实现总成本最小化和客户服务最大化，提出了考虑环境因素和碳排放的车辆路径问题并求解。Zulvia等［12］提出优化运营成本、变质成本、碳排放和客户满意度的易腐产品车辆路径问题，采用多目标梯度进化算法求解模型。Li等［13］建立绿色生鲜食品物流异质车队车辆路径问题模型，提出自适应模拟退火变异遗传算法求解，同时降低了能源和燃料的消耗。

从电动汽车车辆路径问题来看，Schneider等［14］针对时间窗约束下的电动汽车路径问题，考虑了充电站的因素，构建了以总出行距离最短为优化目标的数学模型，并提出一种将变邻域搜索（Variable Neighborhood Search，VNS）算法与禁忌搜索启发式算法相结合的混合启发式算法。Goeke等［15］研究了传统汽车和电动汽车的混合车队下带时间窗的路径优化问题。揭婉晨等［16］研究了带有时间窗的电动汽车路径问题，考虑多车型的问题设计，建立了混合整数规划模型并以分支定价算法求解。Gatay等［17］研究了部分充电策略下的电动汽车路径优化问题。Zhang等［18］考虑电动汽车行驶途中需访问充电站，以能耗最小为目标建立了数学模型，并提供了电动汽车能耗的综合计算，提出基于蚁群算法的元启发式算法进行求解。Macrina等［19］提出电动汽车和传统内燃机汽车组成的混合车队路线问题，考虑了电动汽车的充电时间窗口，设计一种迭代局部搜索启发式算法解决问题。Keskin等［20］提出带有软时间窗的充电站排队时间混合整数线性规划模型，设计了结合自适应大邻域搜索和混合整数线性规划的数学方法进行求解。Karakatič［21］提出了一个两层遗传算法，求解带时间窗的多车场车辆路径问题，进一步缩小了理论与实际的差距。

从上述分析可以看出，对于冷链车辆路径问题和电动汽车路径问题都开展了许多研究。然而，尽管在冷链物流行业已经有一些企业采用电动汽车配送冷冻食品等需要冷藏的商品，但尚没有研究考虑将电动汽车应用于冷链物流配送优化。究其原因，可能是电动汽车总体上来讲仍是一个新事物，无论技术上还是应用上，还存在诸多不足或不便之处，在冷链物流行业应用还非常少，因而还没有引起学者的足够重视。本文将电动汽车与冷链物流配送相结合，考虑电动汽车能耗特点和社会充电站的充电需求，提出了基于电动汽车的冷链车辆路径问题，建立了以配送总成本最小为优化目标的数学模型，并设计了一种混合蚁群算法进行求解。

2 问题描述和模型建立

2.1 问题描述

REVRP 可描述为：一个生鲜配送中心派出电动冷链车向V个超市配送同一温区的生鲜商品。车辆从配送中心出发时完全处于满电状态。车辆的容量为C，续驶里程有限，中途可能需要充电，充电采用社会公共充电站，充电方式为快充，且一次充满，已知配送区域里分布有F个充电站。在此问题中，假设车辆维持行驶状态的电能消耗速度与行驶里程成正比，为h/km，车厢维持低温环境所需的电能为l/h，要求制定最优的配送方案以使得配送总成本最低。

基本假设：1）配送中心只有一个，所有车辆出发之前在配送中心充满电，中途只能充电一次，且一次充满；2）每辆车只允许配送一趟；3）各配送点的需求量已知，且不超过车辆的容量；4）每个配送点只由一辆车配送一次；5）配送货物类型单一；6）配送车辆车型单一；7）配送中心和各配送点无时间窗要求；8）配送点和充电站的位置不变；9）配送车辆匀速行驶；10）充电速度恒定；11）为提供车辆动力所消耗的电能与运输里程成正比；12）制冷所消耗的电能与制冷的时间成正比。

2.2 模型建立

为便于模型的建立，设定相关的集合、参数和决策变量，如表1～2 所示。

表1 集合和参数设置Tab.1 Setting of sets and parameters

2.2.1 目标函数

REVRP 以配送总成本最小为目标函数，由固定成本Z1和可变成本构成，其中可变成本包含运输成本Z2和制冷成本Z3。

1）固定成本。

为完成配送任务，企业需要投入资金来维持整个配送流程的运行，包括车辆购置、支付员工工资、管理运营等。这些资金被分配到每辆配送车辆上，则固定成本如下：

2）运输成本。

由于采用电动冷链车进行配送，维持车辆动力所消耗的电能构成配送过程中的运输成本，其费用在车辆行驶时产生，用公式表示为：

3）制冷成本。

为保证商品的质量，需提供对应的低温环境，在这种条件下，电动冷链车通过制冷装备以消耗电能方式给车厢创造合适的温度，会产生制冷的费用，其费用在行驶途中（不包括车辆完成配送任务回到配送中心的这段路途）、卸货期间和充电期间产生，用公式表示为：

2.2.2 数学模型

根据以上定义，将目标函数与所有相关约束组合即构成了所研究问题的数学模型，如下所示：

其中：式（4）为目标函数，表示总配送成本最小；式（5）表示车辆给配送点配送后必须离开该配送点；式（6）表示车辆走的是一个闭合回路；式（7）表示每个配送点只允许一辆车访问一次；式（8）表示每辆车所访问配送点的总需求量不超过车辆的最大容量；式（9）表示每辆车在配送过程中最多充一次电；式（10）表示如果车辆需要充电，在充电站的充电量；式（11）表示车辆从配送中心或充电站出发能访问任意一个配送点并返回配送中心；式（12）表示车辆到达任意节点的装载量为非负值，该节点的装载量取决于在上一节点的装载量和客户的需求量；式（13）表示车辆在开始配送任务之前的装载量不超过车辆的最大容量；式（14）表示车辆从配送点出发有足够电量到达其他配送点或充电站；式（15）表示车辆访问配送点后有足够电量回到配送中心；式（16）表示车辆从配送中心或充电站出发有足够电量到达配送点；式（17）表示车辆在充电站充完电后有足够电量回到配送中心。

3 混合蚁群算法

REVRP 的数学模型为线性规划模型，属于NP-hard 问题。当节点的规模比较小时，可以采用分支定界法、列生成法等精确方法求解；当节点的规模比较大时，解空间呈指数级增长，须采用近似方法、元启发式方法求解。求解算法主要分为邻域搜索、群体搜索两大类［22］。邻域搜索类有禁忌搜索算法、变邻域搜索算法、自适应大规模邻域搜索（Adaptive Large Neighborhood Search，ALNS）算法；群体搜索类有蚁群算法、粒子群优化算法。本文将蚁群算法和局部邻域搜索算法相结合，构造了一个混合蚁群算法求解REVRP。

蚁群算法［4］的基本流程如图1 所示。

3.1 转移规则

转移规则是蚁群（ACO）算法的关键法则之一，它决定着蚂蚁以何种方式选择下一节点，是蚂蚁在路径构造过程中不可或缺的计算准则。在本文研究的问题中，考虑将信息素浓度、节约值、两节点间的路径距离及车辆的容量利用率作为衡量转移概率的关键性指标，用公式表示如下：

其中：ξij表示节点j对节点i的吸引值；ηij表示节点i到节点j距离的倒数；τij表示节点i与节点j之间的信息素浓度；μij表示节点i与节点j之间的节约值；πij表示车辆容量的利用情况，即从节点i访问节点j后车辆的容量利用率；α、β、γ、δ为相关系数。

定义allowedk为备选节点j的集合，从节点i转移至集合allowedk中节点j的概率为：

在确定转移规则后，采用轮盘赌的方法从allowedk中选择备选节点j，以此确定路径的排列方案，最终得到可行的路径规划方案。

此外，为了提高搜索效率，缩小蚂蚁转移时的范围，减少无用的转移搜索，对allowedk里面的候选点数量进行限制，即Bell等［23］提出的小窗口策略。具体地，将allowedk里的候选点数量上限设置为客户总量的1，n一般可取值2、3、4。

3.2 路径构造过程

在REVRP里，节点分为三种类型，即配送中心、客户、充电站。因此，蚂蚁转移时存在多种情形，不同类型的节点i可以选择转移的节点j的类型不尽相同。分别阐述如下：

1）当蚂蚁位于配送中心。

将尚未配送并且同时满足容量约束、电能约束的客户，放入可行集合allowedk。

电能约束采用look ahead strategy［24］，用于确保蚂蚁去了节点j后，还有足够的电量返回配送中心N+1，或者到达离j点最近的充电站f*。电能约束条件如下：

然后使用转移规则，计算allowedk中各个节点的概率Pij，并按概率从中随机选择一个节点j。离开j点时的剩余电量为：

2）当蚂蚁位于客户。

根据容量约束、电能约束的不同情形，蚂蚁可以选择去下一个客户、充电站或者配送中心。电能约束为：

①如果allowedk≠∅，则按转移规则转移到下一个客户j或者返回配送中心N+1。若选择转移至客户j，则(tij+sj)×l-dij×h。若选择返回配送中心，则返回配送中心N+1，由于车辆在返回配送中心途中，车厢中的货物已全部配送完，不再需要制冷。如果还有客户未配送，则将蚂蚁k移至节点0，再模拟另一台车辆，重新出发配送。

②如果若存在客户j满足容量约束，但不满足电能约束，且≥×h+×l，则将蚂蚁直接转移到离i点最近的充电站f*，充电直至充满。充电时长为：

③若上述两种情形均不能满足，则蚂蚁只能返回配送中心。

3）当蚂蚁位于充电站。

蚂蚁可以选择去下一个客户或者配送中心。电能约束为：

如果没有可行的客户，则必须返回配送中心。否则按转移规则转移到下一个客户j或者返回配送中心N+1，若选择转移至客户j，则与第1）步一样更新剩余电量。

算法1 HACS 算法的路径构造过程。

3.3 信息素更新策略

蚁群算法的信息素更新策略分为局部更新策略和全局更新策略，本文仅采用全局更新策略［25-26］，即在所有节点间设定初始信息素浓度，当蚂蚁构造好一个完整的路径后，需要对路径中的信息素进行更新。具体地，采用全局更新策略［25］，仅对每次迭代的若干个最好解以及迄今为止的最好解施放信息素。

此外，为了避免蚁群算法的停滞现象，提高算法的全局搜索能力，对路径上的信息素浓度设置固定的范围，即MIN-MAX 策略［26-27］。

3.4 局部优化策略

局部优化策略被广泛证明能够很好地改善蚁群算法的搜索性能。大部分用于局部优化的邻域算子源于λ-opt［28］，特别是最常用的2-opt［29-30］。本文借鉴前人所设计的邻域算子，针对REVRP 的特点，先将各个回路里的充电站去掉。在不考虑电量的条件下，执行Balseiro等［31］提出的邻域算子，分为单回路交换和多回路交换两类算子。其中单回路交换算子包括Relocate（记为LS1）、Exchange（记为LS2）两种算子；多回路交换算子包括Relocate（记为LS3）、Exchange（记为LS4）两种算子。需要强调的是，在各个算子中，每次执行操作后还需要判断是否需要插入充电站，在满足电量约束和时间窗约束的前提下以目标值大小确定充电站插入的最佳位置。充电站的插入采用Best Station Insertion 算法［32］。

4 数学实验与结果分析

用于测试算法性能的算例来源于文献［14］，该算例集由文献［33］中的基准算例集改编而来。本文针对REVRP 的特点，对文献［14］中的算例集进行改造，制作出满足要求的算例集。实验环境为Windows 10 操作系统，CPU 为Intel Core i7-8550U，频率为3.4 GHz，内存为16 GB，使用Dev-C++版本编程软件。

4.1 实验设计

所设计的算例集按节点数目分为大规模和小规模两个子集。其中，节点规模小的算例有18个，包含5 个客户、10个客户、15 个客户的算例有6 个。每种数量规模的算例按照节点的分布类型再分为C 类、R 类、RC 类三类，其中C 类表示节点的分布形态为集群式分布，R 类表示节点的分布形态为随机分布，而RC 类则结合C 类分布和R 类分布的特征，每种类型的算例各4 个。节点规模大的算例有6个，每个算例包含100 个客户节点、20 个充电站节点，节点的分布同样有C类、R 类、RC 三类。每种类型的算例按照分布类型下算例节点坐标区分各2 个。每个算例的信息包括配送中心、客户、充电站等节点坐标、客户需求、车辆的额定载重量、额定电量、充电速率。电动汽车的性能参数以及ACO 算法的参数，如表2～3 所示。

表2 决策变量设置Tab.2 Setting of decision variables

表2 电动汽车的性能参数Tab.2 Electric vehicle performance parameters

表3 ACO算法的参数Tab.3 ACO algorithm parameters

4.2 小规模算例实验结果

对小规模算例，分别采用CPLEX（WebSphere ILOG CPLEX）12.6.1 和ACO 算法求解。CPLEX 是一款用于线性规划、混合整数规划和二次规划的高性能数学规划求解器，它使用精确求解算法，在时间足够的条件下，CPLEX 可以求解出数学模型的最优解；但它的缺点是在大规模运算时，求解时间过长甚至无法计算。因此，本文将ACO 算法与CPLEX 计算出的最优解进行对比，以验证ACO 算法的可行性。实验结果如表4 所示，其中：Z表示路径方案的配送总成本；t表示各方法的程序运行时间。

表4 小规模算例实验结果Tab.4 Experimental results of small-scale examples

小规模算例实验结果表明，ACO 算法取得了和CPLEX相当的精确解，能够有效解决客户节点数少的REVRP。在5客户、10 客户和15 客户的算例中，由于客户节点数少，使用ACO 算法可以找到精确解。从实验结果中可以看到：CPLEX能够在预先设置的7 200 s 内得到各个算例的最优解，平均用时94.7 s；而ACO 算法能够快速搜索到它们的最优解，平均运算时间只需要0.36 s，可节省99.6%的运算时间，可见ACO 算法大幅度缩短了运算时间。

4.3 大规模算例实验结果

针对大规模算例，分别采用带有4 种邻域算子的混合蚁群算法进行求解。HACO-I 表示ACO+LS1 策略，HACO-II 表示ACO+LS2 策略，HACO-III 表示ACO+LS3 策略，HACO-IV表示ACO+LS4 策略，HACO-V 表示ACO+所有邻域算子。每个算例各运行10次，分别记录每次运行所找到的最佳路径方案、目标值（best）以及发现最好解的时间t；并针对每个算例，计算出各个算法与ACO 之间的偏差（ΔZ），如表5 所示。

从表5 可以看出，5 种策略得到的目标值均优于ACO 算法；除R201 算例外，其他算例的最好解总是由HACO-V 得到。运行时间方面，ACO 算法的平均用时21.7 s。ACO 与单独邻域算子组合的算法中，HACO-I 的用时最少，平均用时为71.5 s，是ACO 算法的3.3 倍；HACO-III 的平均用时为130.0 s，是ACO 算法的6 倍；HACO-V 综合运用了4 种邻域算子，因此用时最高，平均用时高达252.0 s，是ACO 算法的11.7 倍。这是因为4 种邻域算子均是对ACO 算法产生的可行解进行改进，因此混合蚁群算法的平均运行时间要高于ACO 算法的程序平均运行时间。

为了解不同类算例的整体情况，在表5 结果的基础上进行进一步计算，计算结果如图2 所示。由图2（a）可以看出，节点的分布形式影响了路径方案的构成，C 类算例（集群式分布）的路径方案中车辆单次配送能够访问更多的客户，导致了C 类算例的平均目标值小于R 类和RC 类算例。由图2（b）可以看出，C 类算例的程序运算速度也更快。可见，节点的集群式分布可以降低成本和程序的运算时间。

表5 大规模算例实验结果Tab.5 Experimental results of large-scale examples

图3 中可以看出每组算例中两个不同算例之间的目标值存在较大的差异，如C101 和C201、R101 和R201、RC101 和RC201，这是由于C201、R201、RC201 算例对应车型的电池容量分别比C101、R101、RC101 的高，车辆在一次配送任务中访问的客户节点较多，车辆装载率较高，使用车辆数较少，其配送成本也随之减小。可见电池容量对配送成本影响较大，相同条件下电池容量越大，配送成本越小。

由表5 可知，5 种策略对ACO 算法都起到了一定的改进作用，求取每种策略下所有算例的目标值改进率的平均值，如图4 所示。相较于蚁群算法得到的路径方案，4 种邻域算子都能在此基础上对解进行改进，其中ACO 与单独邻域算子组合的策略中，HACO-III 对于所有算例的目标值平均改进率最大，为2.81%；HACO-IV 的目标值平均改进率最小，为0.99%；综合运用了4 种邻域算子的HACO-V 的性能最好，最好解的改进率达到4.45%。

综合分析表5 和图4 可知，在所有6 个算例中，有5 个算例的最好解来自HACO-V，仅R201 的最好解来自HACO-III，但HACO-III 的平均目标值为1 093.1元，不如HACO-V 的1 087.1 元；从平均值来看，HACO-V 求解所有算例的平均值均是最小的。

如图5 所示，对于不同的节点分布形式，不同策略的改进效果不尽相同。HACO-I 和HACO-III 对R 类节点分布形式改进效果更明显，其余均对RC 类改进效果更为明显。可见节点分布形式也会影响算法的改进效果，算法对于随机分布和随机、集群混合式节点分布形式改进效果更好，对集群式节点分布改进效果稍差。

5 结语

本文研究了基于电动汽车的冷链物流策略路径问题。在此基础上，构建了面向社会充电站的REVRP 的数学模型，设计了一种混合蚁群算法解决该问题，并制定了基准算例集。实验结果表明，所设计的混合蚁群算法能够有效求解小规模和大规模节点的REVRP。当节点数量比较少时，针对所有算例，蚁群算法均能找到与CPLEX 一样的最好解；当节点规模较大时，蚁群算法与不同局部优化算子组合后各自找到的最好解存在明显差异，意味着在求解大规模节点的REVRP中，不同算子所带来的算法性能有优劣之分。其中，算子LS3 效果最佳，而算子LS4 效果最差，而将所有4 种算子同时使用时的性能最佳。