基于蚁群选择超启发算法的低碳选址—路径问题

王 舜，赵燕伟,冷龙龙，张春苗，蒋海青

(浙江工业大学 特种装备制造与先进加工技术教育部重点实验室，浙江 杭州 310014)

0 引言

选址—路径问题(Location-Routing Problem, LRP)是一个经典的组合优化问题，可以看作是配送中心选址分配问题(Location Allocation Problem, LAP)与车辆路径问题(Vehicle Routing Problem, VRP)[1-2]的组合问题，是结合了两个复杂决策问题的NP-hard问题。配送中心选址与客户地理位置、车辆配送路线规划之间的相互依赖关系有利于帮助企业全面协调物流系统的各个环节，以最少成本、最短配送距离等满足客户的需求。

通过考虑现实物流的附加要求和各种路线建设限制，衍生出许多类型的LRP，其中包括带容量约束的LRP(Capacitated LRP, CLRP)[3-7]、带同时取送货的LRP(LRP with Simultaneous Pickup and Delivery, LRPSPD)[8-11]、带时间窗的LRP(LRP with Time Windows, LRPTW)[12-16]、多目标LRP(Multi-Objective LRP, MOLRP)[17-22]等。然而，基本LRP以及衍生出不同类型的LRP大多是以总运行成本为优化目标，少数以最小化配送时间、最大化客户满意度为目标。但是在全球低碳经济以及绿色经济的响应下，大量二氧化碳等温室气体的排放造成了日趋严重的环境污染，因此在物流配送过程中减少二氧化碳气体的排放已成为物流公司不得不解决的问题。基于此，本文提出了低碳选址—路径问题(Low Carbon LRP, LCLRP)，并设计了一种基于蚁群选择机制的进化式超启发算法(Hyper-Heuristic algorithm of Ant colony Selection mechanism, HHAS)进行问题模型求解，为物流公司提供参考。据笔者所知，目前尚未有学者将超启发算法用于求解LCLRP，本文采HHAS算法求解LCLRP，将大洪水、模拟退火、只接受好解作为高层自适应接受准则机制，以引导全局搜索并加快收敛。

考虑二氧化碳排放的LRP文献还比较欠缺，但是在VRP中考虑二氧化碳排放以及燃油消耗的文献比较丰富。车辆的碳排放量受到很多因素的影响，Demir等[23]指出影响碳排放量的因素主要有车辆参数、交通状况、坡度、环境以及驾驶人水平及习惯等。车辆参数包括车辆型号、尺寸大小、重量等等；交通状况包括道路拥挤情况、红绿灯等；环境主要指自然环境，如湿度、气温等。车辆运行过程中碳排放的计算十分复杂，部分文献将燃油消耗通过数学转换间接获得。例如，Scott等[24]从地形坡度和车辆装载率测量车辆的燃油消耗；Zhang等[25]考虑了行驶距离、车辆装载量两方面测量车辆的燃油消耗量；张春苗等[26]将车辆的重量和运输距离作为影响燃油消耗的主要因素；Palmer[27]建立了货车碳排放模型，研究了速度对燃油消耗的影响。常见模型如下：

(1)基于速度与装载量的燃油消耗模型

1)Barth等[28]考虑了车辆的速度与装载量对车辆油耗的关系，建立了货车燃油消耗模型：

Fn=λ(khNhVhd/v+Mhvαd+βhγdv2)。

式中：kh表示发动机摩擦系数；Nh表示发动机转速；Vh表示发动机排量；d表示行驶距离；v表示车辆瞬时速度；Mh表示车辆总重量；α、βh为车辆特定常数；λ、γ为常数。可以得出：khNhVhd/v为发动机相关模块，与运行时间呈线性数学关系；Mhvαd为重量模块，与车辆总重量呈线性关系；βhγdv2为速度模块，与速度呈二次方关系。

2)Zhang等[25]考虑了行驶距离、汽车行驶速度、车辆装载量等，假设增加车辆载重M会增加p百分比的燃油消耗，提出的燃油消耗模型为：

式中：FCij表示从节点i行驶到节点j所产生的燃油消耗，LPHij表示车辆从节点i到节点j单位时间所消耗的燃油消耗，dij表示节点i到节点j的行驶距离，vij表示节点i到节点j的平均速度。

(2)瞬时油耗模型

Akcelik等[29]考虑了车辆自身特性，如车辆重量、行驶速度、加速度等，建立了车辆瞬时燃油消耗模型：

在时间t内的燃油消耗量为

其中：RT是车辆的牵引力(单位：kN)；M是车辆装载量(单位：kg)；v是连续速度(单位：km/h)；a是加速度(单位：m/s2)；β1是车辆燃油消耗参数(单位：g/kJ)；β2是车辆加速时相关数值g/(kJ·m/s2)。

1 问题描述

1.1 碳排放模型

上述两个燃油消耗与二氧化碳排放计算模型考虑了车辆的自身参数，建立了与车辆速度以及加速度有关的油耗模型，但是在VRP以及LRP中车辆的速度与加速度很难进行具体描述。根据日本政府网[30]在2010年的报告，同一类车辆的油耗与载重量成正比例关系。鉴于此，Xiao等[31]将车辆考虑为匀速行驶，只考虑载重量与行驶距离对车辆燃油排放的影响，将车辆重量分成空载重量Q0和载重量Q1两部分，则燃油消耗率(Fuel Consumption Rate, FCR)

φ(Q1)=α(Q1+Q0)+b。

(1)

将车辆可以承受的最大载重量定义为Q，则空载时的FCR以及满载时的FCR就可以分别表示为φ0=αQ0+b和φ*=α(Q0+Q)+b，其中α=(φ*-φ0)/Q。因此，φ(Q1)=φ0+(α(φ*-φ0)/Q)*Q1，说明FCR与车辆的载重呈现出线性关系，其中截距为φ0，斜率为φ*-φ0/Q。

车辆在路径中的燃油消耗可以表示为[32]：

(2)

式中：xij为决策变量，当车辆由客户点i驶向客户点j时，xij=1，否则xij=0；因为φij与载重量有关，所以总燃油消耗Cfuel可以依靠调整装货卸货顺序来优化。令yij为从点i运送到点j的货物重量，因此根据式(3)可以得到：

(3)

1.2 LCLRP数学模型

LCLRP可定义为一个完整的定向网络G=(N,A)，N由ND与NC构成，表示物流系统内所有点的集合。其中ND为候选配送中心集合，NC为客户点集合，每个候选仓库的容量与位置已知，每个客户的需求量与地理位置已知。车辆从配送中心出发，按照安排的路径依次服务客户，满足客户的送货要求，模型的目标是选择配送中心位置并分配车辆，设计车辆路径以使车辆的总碳排放量最小化。各符号定义如表1所示。

表1 参数符号含义

选址—路径问题的数学模型可表示如下：

(4)

s.t.

(5)

(6)

(7)

xik≤zik,∀i∈NC,k∈ND；

(8)

xki≤zik,∀i∈NC,k∈ND；

(9)

∀i,j∈NC,i≠j,∀k∈ND；

(10)

(11)

(12)

xij∈{0,1},∀i,j∈N；

(13)

Yk={0,1},∀k∈ND；

(14)

zik={0,1},∀i∈NC,k∈ND。

(15)

其中：式(4)为目标函数，表示车辆碳排放量最小；式(5)～式(6)保证了每个客户点都要被访问且只能被访问一次；式(7)表示每个客户点只能分配给一个配送中心；式(8)～式(10)表示所服务车辆必须返回原配送中心；式(11)保证每个配送中心访问的顾客总需求小于配送中心的容量；式(12)保证车的载重量不超过载重能力,S为某车辆所服务的客户集合；式(13)～式(15)为决策变量。

2 考虑燃油消耗的选址路径问题优化

2.1 超启发算法概述

常见的用于求解选址路径问题的算法主要有遗传算法(Genetic Algorithm, GA)[32]、禁忌搜索(Tabu Search, TS)[33]、粒子群算法(Particle Swarm Optimization, PSO)[34]等，这些算法都是对解空间进行直接操作的。超启发式算法(Hyper-Heuristic Algorithms, HHA)是近年来发展起来的一种新型启发式算法，可以简单阐述为“寻找启发式算法的启发式算法”，具有更高级智能系统的特征，是未来启发式优化领域研究的主流方向之一，其严格定义如下[35- 36]：超启发式算法提供了一种高层次启发式方法，通过管理或操纵一系列底层次启发式算法(Low-Level Heuristic, LLH)，以产生新的启发式算法。这些新启发式算法被用于求解各类组合优化问题。

如图1所示为超启发算法框架，可分为上层控制领域与底层问题领域两个部分。在控制领域，由智能计算机专家进行高层启发式策略的设计，可以分为选择策略与接受准则两个部分，选择策略用于搜索底层启发式算子构成的空间，并根据底层启发式算子的历史性能选择底层启发式算子；接受准则根据子代解的质量判断是否代替父代解。图1中：Scurrent表示子代解，Sprev表示父代解。在问题领域，由领域专家提供底层启发式算子以及问题描述、目标函数等信息。底层启发式算子与待解问题相关，用于直接搜索问题空间。问题领域与控制领域存在领域屏蔽，用于隔离上层控制领域与底层问题领域。由于控制领域与问题领域之间存在领域屏蔽，只要修改问题领域的底层启发式算子空间、问题描述以及目标函数，就可以将算法应用到其他问题中。由此可见，超启发算法具有很强的通用性。因此，超启发算法已经应用到诸多领域中，如考试时间表问题[37]、图形着色问题[38]、排班问题[39]等。

表2给出了不同选择策略与接受准则，选择策略与接受准则可以两两进行组合，根据选择策略提供的启发式机制来选择一个或一系列的底层启发式算子，并由底层启发式算子对父代解进行操作获得子代解，最后由接受准则所提供机制判断是否接受子代解。如SR+AM就表示选择策略为简单随机，接受准则为接受所有解的高层启发式策略。

表2 选择策略和接受准则

2.2 选择策略描述

本文设计了蚁群选择机制作为超启发算法的高层进化式选择策略，提出一种基于蚁群选择机制的超启发算法[40],即将蚁群选择机制作为高层启发式策略，评估底层启发式算子的性能，并管理和操纵一系列底层启发式算子，蚁群选择机制并非直接对问题空间进行搜索操作，而是运用蚁群选择机制对底层算子所组成的空间进行搜索操作。每个顶点代表底层启发式算子，如图2所示，假设有m只蚂蚁，均匀分布在底层启发式算子之中，每只蚂蚁根据每个路径中的信息素来确定下一个顶点，一旦蚂蚁到达一个新的顶点，便应用顶点所对应的底层启发式算子。例如，1-1-2-3就表示其中一只蚂蚁的路径，路径表示底层启发式算子的选择顺序；如图3所示，弧(i,j)表示蚂蚁从底层启发式算子i移动到底层启发式算子j。但是不同于TSP，在超启发算法中，算法对底层启发式算子进行操作，因此每只蚂蚁允许多次访问同一个点，意味着每个底层启发式算子在一次迭代中可以进行多次操作。

参考文献[40]，采用可见度函数ηj来评判底层启发式算子的优化性能:

(19)

式中：Ikj(t)是在蚂蚁k的路径中，底层启发式算子j在迭代次数为t时的改进值(可以为负)；Tkj(t)是在蚂蚁k的路径中，底层启发式算子j在迭代次数为t时所占用的CPU运行时间；γ是一个位于0到1之间的权重值。

每条弧上的信息素

(20)

式中：ρ(0<ρ<1)表示信息素的蒸发系数，1-ρ表示信息素的持久系数；Pk(t)表示蚂蚁k周游过程所产生的选择底层启发式算子的顺序；#ij(Pk(t))表示在蚂蚁k的路径中弧(i，j)所出现的次数；I(Pk(t))表示蚂蚁k在路径中改进的量；T(Pk(t))表示蚂蚁k完成路径周游所占用的CPU时间。

蚁群选择的决策过程需要算法结合信息素和可见度两个量来进行，因此，引入一个变量V来结合信息素和能见度：

Vij(t)=αηj(t)+βτij(t)。

(21)

这里，为了使表现不好的底层启发式算子也有一定的概率被选中，引入变量PV：

PVij(t)=max{Vij(t),QσVij(t)}。

(22)

式中

(23)

式中：H为底层启发式算子的集合;n=|H|表示底层启发式算子的个数；ε和σ保证表现性能不佳的底层启发式算子仍有一个很小但不为0的概率被选中。若弧(i,j)未出现在路径中，则PVij(t)=0；若所有底层启发式算子的性能表现都不好，则Q=0，并将所有PV的值都设为1，保证所有底层启发式算子都以相等的概率被选取。最后，弧(i,j)被选择的概率

(24)

2.3 接受准则描述

接受准则是超启发算法的上层框架，用于判断子代解是否能替换父代解，其表现性能的好坏直接影响超启发算法的收敛速度与优化精度。

(1)接受所有解 无论改进与否，接受所有解。

(2)概率接受 接受所有的改进解，对于非改进解，有50%的概率接受。

(3)模拟退火 与模拟退火算法类似。设置初始温度T、降温系数λ，每次迭代后根据温度更新退火温度：T=T×λ。每次迭代使用底层启发式算子，若得到了改进解，则接受；若得到了非改进解，则以一定的概率接受，概率p=eΔ/T。

(4)大洪水 设置下界LB，LB为当前迭代的最优解。每次迭代使用底层启发式算子，若得到了改进解，且子代解ftemp小于一阈值，则接受该子代解，该阈值为LB+(f0-LB)×(1-iter/Tmax)。其中：ftemp表示子代解，f0表示初始解，iter表示当前迭代次数，Tmax表示最大迭代次数。

2.4 算法流程

HHAS算法用于求解LCLRP模型时，首先进行配送中心选址分配，再采用路径优化的方法进行求解，具体流程如下：

步骤1初始化。设蚂蚁运行路径长度为LP。首先进行种群初始化，求出初始种群的解S，并将S赋值于最佳解Sb。对于底层启发式算子j∈H，初始化可见度ηj=0。对于路径中每条弧(i,j),设置一个初始值τij(t)=0。将m只蚂蚁均匀分布在n个顶点上，并赋予每只蚂蚁初始种群与初始解S，并将蚂蚁k的解赋值于矩阵Sk中。

步骤3蚁群选择机制参数更新。根据式(19)更新底层启发式算子的可见度ηj，根据式(20)更新各个底层启发式算子之间的信息素τij，最后根据式(24)更新选择底层启发式算子概率probabilityijk(t)。

步骤4满足停止条件(即达到迭代次数)，则输出结果，否则返回步骤2。

假设采用蚁群选择机制作为选择策略，模拟退火作为接受准则，超启发算法组合的伪代码如算法1所示。

算法1超启发算法伪代码。

1:Input:Low-level heuristics(LLH1-LLH13)

2: Initial Solution:S

3: Number of iterations:C

4: Pheromones:τ

5: Evaporation coefficient:ρ

6: Initial temperature:T

7: Minimum temperature:Tmin

8: Cooling coefficient:r

9:Output:Best Solution:S′

10:Solution S←initialiseSolution()

11:for i←1:C

12: Solution S′←S

13: LLHi←SelectHeuristics(AntSelect(LLHs))

14: S′←ApplyHeuristic(LLHi)

15: Δ←Function(S)-Function(S′)

16: while T>Tmindo

17: if Δ>0 then

18: S=S′

19: else

20: if exp(Δ/T)>r then

21: S←S′

22: end if

23: T=T*r

24: end if

25: end while

26: τ←(1-ρ)×τ+α

27: Update probability

28:end for

2.5 底层启发式算子描述

在本文研究的LCLRP模型中，底层启发式算子根据文献[41]的分类标准，构建以下算子：变异算子(mutation heuristics)、破坏重组算子(ruin-recreate heuristics)、局部搜索算子(local search heuristics)、交叉算子(crossover heuristics)。底层启发式算子用于直接对解空间进行操作，具体如下：

(1)变异算子 变异算子是一种对解微小扰动的突变算子。所有这些算子都将返回任何满足约束的路径，无论目标函数值是改进或恶化。

1)路径变异算子。

LLH1：2-opt。如图4所示，任意选择一条路径，交换相邻两客户点的位置；

LLH2：Or-opt。如图5所示，任意选择一条路径，把相邻两客户点插入到其他位置；

LLH3：Interchange。如图6所示，任意选择两条路径，交换任意两个客户点位置；

LLH4：Shift。如图7所示，任意选择两条路径，在一条路径上找一个任意的客户插入到另一条路径中合适的位置。

2)配送中心变异算子。

LLH5：Interchange。如图8所示，任意选择两条路径，交换配送中心；

LLH6：Shift。如图9所示，任意选择一条路径，开启一个新的配送中心，并替换这条路径的配送中心。

(2)局部搜索算子 与变异算子一样，通常是以交换或插入的形式产生新路径。然而，与变异算子不同的是局部搜索算子只会返回一个等于或优于初始的解。

1)LLH7：2-opt*。任意选择两条路径，根据衡量准则选择一个位置，交换此位置后的所有客户点，并且只接受好解。

2)LLH8：Shift。和LLH4一样。不同的是LLH8根据衡量准则来选择客户，备选客户插入到另一路径的任意位置，并且只接受好解。

3)LLH9：Interchange。和LLH3一样，不同的是此算子只接受好解。

4)LLH10：GENI。计算不同路径上的任意两个客户的距离，采用最短距离作为基准距离，选择移除距离最接近基准距离的客户，并且只接受好解。

(3)破坏重组算子 选择一些客户根据其与“基准客户”的接近程度从路径中删除。

LLH11:Location-based Radial Ruin。随机选择一个客户作为“基准客户”，根据客户位置接近“基准客户”的原则，以[1%，10%]的概率将客户从路径中删除。

(4)交叉算子 选择两个父代路径作为输入，生成一条子代路径，通常可以通过一点、两点和均匀交叉来完成。

1)LLH12：Combine。随机选择两个父代，以[25%,75%]的概率将一个父代复制得到一条子路径，添加来自另一个父代中非冲突的路径，并随机插入剩余客户。

2)LLH13：Longest Combine。随机选择两个父代，所有路径以服务客户点数量的降序来考虑，任何不重复客户的路径都会被添加生成一条子路径，并随机插入剩余客户。

3 实验结果及分析

3.1 算法参数设定正交实验

关于燃油消耗的参数，车辆空载时单位距离燃油消耗系数φ0=1，车辆满载时单位距离燃油消耗系数φ*=2[7]，燃油转换系数C0=2.68。不考虑配送中心和车辆的固定成本。

HHAS算法参数设定如下：蚂蚁路径长度LP=11；蚂蚁数量m=(10，15，20)；权重参数α=(0.6，0.7，0.8),β=(0.6，0.7，0.8),γ=(0.6，0.7，0.8)；增强系数ε=0.001,σ=1.001[41]。

由于本节尚未确定接受准则的性能，每次迭代随机选择一种接受准则(GD、SA、OI)。

对于HHAS算法，单个蚂蚁在一次循环中所经过的路径，即为底层启发式算子集中的一个解，m只蚂蚁在一次循环中所经过的路径，则表现为底层启发式算子的一个子集，蚂蚁数量的变化决定了算法的稳定性；而α、β以及γ反映了蚁群在路径搜索中随机因素作用的强度。因此，为了使所提算法获得更好的算法性能，针对关键参数蚂蚁数量m、权重参数α、β、γ，设置3个参数水平(如表4)，选择规模L(34)的正交实验，在各种参数组合下选择中等规模的基准实例Christ50x5ba进行10次独立实验，每次实验迭代1 000次，测试结果如表5所示。HHAS算法使用MATLAB 2015编程，计算机环境为Intel(R)Core(TM)i5-3230M CPU @2.60 GHz, 4 GB RAM, Windows 10系统。

表4 参数水平分布

表5 不同参数正交实验结果

由表5，可得如表6所示各参数响应值。由表5与表6可知，m、α、β、γ均会对算法性能造成影响：蚂蚁数量m增多，可以提高算法的全局搜索能力以及算法的稳定性，但m增大后，会使大量的曾被搜索过的路径上的信息素变化趋于平均，信息素正反馈作用不明显，蚂蚁数量减小，搜索的随机性减弱，使算法的全局性能降低，容易出现过早停滞；α、β、γ的大小反映了蚁群在路径搜索中随机性因素作用的强度，较大的值将造成随机性减弱，而当值过小时，则易使蚁群的搜索陷入局部最优。如图10所示折线图，在当m、α、β、γ处于参数水平2时所得到的解最优，即m=15,α=0.7,β=0.7,γ=0.7。

表6 各参数响应值

3.2 不同接受准则实验结果对比

对于超启发算法，不同的高层启发式策略的性能效果是不同的，为了使HHAS算法达到更好的性能，通过实验对比来选择出一个最佳的接受准则：选择策略均为蚁群选择机制，接受准则分别为GD、SA以及OI。每个基准实例独立运行10次，迭代次数为1 000次。实验结果如表7所示，其中HHAS算法中的参数m=15,α=0.7,β=0.7,γ=0.7。

由表7可以看出，在18个基准实例测试中，AS+OI取得最优解的个数为13次，AS+SA取得最优解5次，而AS+GD只获得了0次最优解，其中，在小规模实例中，AS+OI获得最小解6次，AS+SA获得最小解2次；在中等规模实例中，AS+OI获得最小解6次，AS+SA获得最小解2次；在大规模实例中，AS+OI获得最小解1次，AS+SA获得最小解1次，AS+GD获得最小解0次。而且，在算法稳定性上，OI接受准则所得结果标准差比GD、SA接受准则所得到的结果标准差小，算法稳定性更高。

表7 不同接受准则计算碳排放量实验结果

例如在图11，Gaskell22x5的求解结果中：GD接受准则得到的最佳解为2 685.0 kg，平均值2 688.1 kg，标准差为0.9；SA接受准则得到的最佳解为2 407.7 kg，平均值为2 426.0kg，标准差为8.7；OI接受准则得到的最佳解为2 288.5 kg,平均值为2 288.9 kg，标准差为0.2；Gaskell36x5的计算结果中：GD接受准则得到的最佳解为3 385.0 kg，平均值为3 393.3 kg，标准差为1.9；SA接受准则得到的最佳解为3 214.0 kg，平均值为3 243.1 kg，标准差为8.8；OI接受准则得到的最佳解为2 576.5 kg，平均值为2 580.5 kg，标准差为2.4；Perl85x7的计算结果中，GD接受准则获得的最佳解为6 831.6 kg，平均值为6 927.5 kg，标准差为25.6；SA接受准则获得的最佳解为6 692.8 kg，平均值为6 750.4 kg，标准差为12.9；OI接受准则获得的最佳解为6 287.6 kg，平均值为6 310.2 kg，标准差为4.8。综上所述，AS+OI在求解不同规模的实例时表现均优于AS+GD与AS+SA，接受准则为OI时超启发算法性能最优，在接下来的实验分析中将使用OI接受准则进行实验。

3.3 算法求解基本LRP有效性分析

为说明HHAS算法对求解LRP的有效性，用HHAS算法求解基本LRP模型，并与LRGTS算法[5]、GRASP算法[42]的计算结果进行对比。HHAS算法运行环境与3.1节中的一致，GRASP算法与LRGTS算法均使用Visual C++编码，运行环境为DELL PC Optiplex GX260,2.4 GHz Pentium 4处理器，512 MB运行内存，Windows XP操作系统。HHAS算法求解Barreto算例的流程与2.4节中的算法流程一致，蚁群选择机制参数为m=15,α=0.7，β=0.7，γ=0.7，接受准则为OI，不同之处在于优化的目标函数为总成本而不是车辆碳排放。总成本[42]：

式中：Oi表示配送中心开放成本;ci表示配送过程中的路径成本;F表示车辆成本;xijk为决策变量，当车辆k由节点i行驶向节点j时xijk=1，否则xijk=0。其他约束条件与1.2节中的一致。得到的仿真结果计算比较结果见表8。其中：Q表示车辆的最大载重量，BKS表示已知最优解，cost表示成本，gap表示成本相对LB的偏差率，cpu表示程序运行时间，HHAS算法参数设置为m=15，α=0.7，β=0.7，γ=0.7。每个实例独立运行10次，迭代次数为5×(M+N+K)2,其中：M表示客户数量，N表示配送中心数量，K表示车辆数量。

表8 算法求解LRP问题实验结果

续表8

如表8所示，HHAS算法相对LRGTS算法与GRASP算法时间效率较差，但在3个算法对比过程中，HHAS算法在13个算例中总共获得12次最优，优化效果明显优于LRGTS算法与GRASP算法，在有效时间内，可以获得更好的解，说明HHAS算法对于求解LRP是有效的。

3.4 算法求解LCLRP有效性分析

为了进一步说明HHAS算法对求解低碳LRP的有效性，将求解结果与量子进化算法(Quantum Evolutionary Algorithm, QEA)[44]对比。对比实验所使用的实例采用LRP基准实例的Prodhon[5]算例，目标函数为碳排放量，结果用CE表示，cost表示成本。QEA的实验数据从文献[26]中获得，算法使用MATLAB编程，计算机环境为intel(R)Xeon(R)CPU E3-1230 v5 @3.40 GHz,4 GB RAM, Windows 10系统。对比实验结果如表9和图12所示。

表9 求解CECLRP对比实验结果

如表9所示，HHAS算法求解得到的碳排放量均优于QEA算法，14个算例求解中最大的改进率可以达到14.3%，平均改进率为5.7%。基于此，该实验验证了HHAS算法对于求解LCLRP数学模型的有效性。

3.5 LCLRP与CLRP对比实验分析

为证明所提LCLRP模型的有效性，与以车辆总行驶距离为目标的CLRP模型所得到的数据进行对比。本文选择了算法参数为m=15,α=0.7,β=0.7,γ=0.7，接受准则为OI的HHAS算法对于求解LCLRP和CLRP实例的计算结果。CLRP模型以车辆的总成本为目标。每个基准实例都运行10次，每次迭代次数为5×(M+N+K)2，计算得出车辆行驶的总成本(Cost)与总碳排放量(CE)。LCLRP与CLRP运行10次所取得的最小值(min)与平均值(mean)，结果如表10所示。其中，RelatedCost是在LCLRP以碳排放量为目标所得到的相关成本，RelatedCE是在CLRP以总成本为目标所得到的相关碳排放量。表格最后两列描述的是差值百分比，计算公式如下：

表10 CECLRP与CLRP实验对比结果

CEdev.=((CE-RelatedCE)/

RelatedCE)×100，

(25)

Costdev.=((RelatedCost-Cost)/Cost)×100。

(26)

由表10可以看出，求解LCLRP模型得到的平均碳排放量比求解CLRP模型得到的平均碳排放量低5.7%，而总成本增加了4.0%；在比较运行10代所获得的最佳解时，求解LCLRP模型得到的碳排放量比求解CLRP模型得到的碳排放量低5.7%，距离却只增加了3.7%。由图13可以看出，减少的碳排放量明显低于增加的总成本，其中基准实例Gaskell22x5、Gaskell32x5a、Gaskell32x5b以及Christ100x10的优化效果最为明显。以Christ100x10为例，比较以碳排放量最少为优化目标与以总成本最小为优化目标的路径，结果如图14所示。

如图14，当以总成本最小为优化目标时，求解得到的碳排放量为2 819.3 kg，对应的总成本为836.4元，而当以碳排放量最少为优化目标时，求解得到的碳排放量值为2 516.9 kg，对应的总成本为863.4元，碳排放节约了约10.7%，而总成本只增加了约3.1%，优化效果明显。由图中可以看出，当以碳排放量最少为优化目标得出的车辆行驶距离大于以总成本最小为优化目标的车辆行驶距离时，碳排放量反而减少了。因此，简单的行驶路径减少并不一定意味着碳排放量减少，合理安排车辆路径，优化卸货顺序即减少车辆的载重量可以有效减少物流过程中的碳排放量。

4 结束语

本文考虑了环境污染这一现状，将碳排放因素考虑到车辆路径中，建立了以碳排放最少为优化目标的LCLRP模型，并提出一种基于蚁群选择机制的超启发算法，构造了基于LCLRP模型的底层启发式算子。通过对基准实例的计算测试出算法最佳的参数组合以及高层策略组合；通过对比以碳排放量最少为优化目标函数的LCLRP与以总成本最小为优化目标函数的CLRP发现，以碳排放量最少为优化目标的LCLRP模型可以有效减少车辆行驶过程中的碳排放量，且总成本增加量少，模型的有效性得到了验证，可为物流公司提供一定的参考。

LRP以及VRP对于速度以及加速度的改变难以进行预测，因此本文构建的碳排放量模型仅考虑了车辆的装载以及行驶距离。在未来的研究过程中，可将其他因素如路况、车辆速度等因素参数加入到碳排放模型中；另外，本文所设计的基于蚁群选择机制的超启发式算法效率相对已有算法的效率表现较差，如何提高算法效率也是下阶段研究的问题之一。