求解多目标车辆路径优化的改进蚁群算法研究

陈高华，郗传松

（1.太原科技大学电子信息工程学院，山西 太原 030024；2.太原科技大学电子信息工程学院，山西 太原 030024）

1 引言

随着全球污染日益严峻，低碳环保问题引起了各行业的重视，根据国际能源属2016年数据统计，车辆在物流配送中产生的碳排放量大约占全球总量的16.9%，因此降低车辆配送中所排出的二氧化碳（CO2）逐渐成为车辆路径优化问题的新的研究热点。文献［1］分别以配送成本最小、环境成本最小、配送成本与环境成本之和最小为目标构建3种VRP模型。文献［2］根据配送车辆载重不同建立碳排放成本模型，并设计带混沌扰动的蚁群算法来求解该模型。文献［3］以车辆载重、客户时间窗和冷链产品变质率为约束，考虑客户满意度的条件下建立了以碳排放量最小的冷链车辆路径优化模型。文献［4］在考虑低碳条件下，建立了车辆路径选择模型，并提出多种群遗传算法来求解模型，但该研究仅考虑碳排放量仅与车辆的行驶速度与行驶距离有关，其研究模型还存在改进空间。文献［5］通过分析最短路径建立了碳排放量最少的模型，并根据模型特点设计了改进算法来求解。文献［6］构建了低碳条件下新能源车辆路径问题模型建立最短路径和最小碳排放的多目标集货模型，通过改进两阶段启发式算法求解模型。文献［7］以带时间窗车辆路径为基础，通过对车辆行驶速度、载重和运行里程的改变建立了总成本最低、周转时间最小的车辆路径优化模型。文献［8］通过地图软件获取实际配送距离，以配送车辆载重为约束，构建了碳排放成本和时间窗惩罚成本等综合成本最低的物流配送模型。文献［9］在时变网络下将道路拥堵因素引入绿色车辆路径优化数学模型中，根据模型特点，设计了改进蚁群算法来求解。文献［10］针对AGV路径规划问题，根据规划模型提出了一种改进的蚁群算法来求解。文献［11］考虑车辆配送过程中载重的实时变化对油耗与碳排放量的影响，并给出配送网络内的最优路径决策。文献［12］在低碳环境下研究冷链物流配送路径优化问题，分别以为碳排放量最低和总行驶距离最少为目标构建了模型，不足是没有将两个目标进行综合考虑。

通过上述文献的研究，可以分析出碳排放量与车辆载重、行驶速度和行驶距离之间存在一定的关系，但既有研究大多都将研究重点放在了单目标优化方面，且没有将碳排放量与车辆载重、车辆速度和行驶距离等因素综合考虑，不符合实际的配送情况，降低了优化结果的适用性。在综合考虑车辆实时载重、行驶速度和行驶距离的基础上提出多目标车辆路径优化模型，并对模型设计了一种改进算法来求解，通过算例验证了模型和算法的有效性。

2 多目标车辆路径模型

2.1 问题描述

假设有一定数量的客户，各自有不同的货物和配送时间需求，在一定的约束下，达到配送总成本最低，碳排放量最小的要求，为了方便建模，假设如下：

（1）配送中心和需求点的地理位置、需求、时间窗全部已知。

（2）车辆由配送中心发出后，最后返回配送中心。每一个顾客只能有一辆车来进行配送，且服务时间恒定。

（3）所有的车为同一规格，每台车能服务一次，每辆车载重量要大于单个客户需求量，且每条路线上的客户需求总量不大于车辆最大载重。

（4）配送车辆的速度恒定，不考虑道路拥堵程度。

2.2 数学模型

综合考虑碳排放量最少和配送总成本最低两方面因素，其优化目标如下：

式中：minλ1—最小化碳排放量λ1；minλ2—最小化配送总成本λ2。

2.2.1 碳排放量因素分析

车辆在实际行驶过程中，由于以汽油，柴油等作为燃料，必然会产生碳排放的问题，其受到影响因素也比较多，这里主要考虑影响因素较大的车辆载重负荷、行驶速度和行驶距离。根据相关研究可知车辆碳排放量λ1与燃油消耗Cfuel呈倍数关系，所以采用一个燃油消耗因子F，即消耗单位燃油所释放的二氧化碳数量来计算碳排放量，表达式为：

假设配送车辆的载重量限制为f，配送车辆从客户i点到客户j点，其距离为dij，实时载重负荷为fij，行驶速度为vij。

（1）车辆的载重负荷与燃油消耗量存在一定的关系因车辆载重负荷的所产生的燃油消耗的表达式［13］为：

式中：w—配送车辆自身重量；ε0—空载时燃油消耗率；ε*—满载时燃油消耗率。

（2）车辆的行驶速度与燃油消耗量存在一定的关系［14］，因行驶速度产生的燃油消耗表达式为：

式中：β1= 0.5Cd Ap，Cd—载重汽车的牵引力系数；A—载重汽车正面表面积；p—空气密度。

2.2.2 配送总成本因素分析

物流车辆配送时配送总成本λ2主要包括三个方面，分别为车辆固定使用成本λ12、车辆行驶距离成本λ22和违反客户服务时间的时间窗惩罚成本λ32，具体表达式如下：

式中：m—配送中心使用的配送车辆总数；g—每辆车的固定使用成本；N={1 ，2，…，n}—客户需求点个数；1—配送中心；c—配送车辆行驶单位距离的成本；e(i)—客户接受服务的最早时间；l(i)—客户接受服务最晚时间；time(i)—客户点接受服务的时间；p1—物流车辆提前到达客户点而产生的单位时间惩罚成本；p2—车辆晚于最迟时间到达而产生的单位时间惩罚成本。

决策变量：

通过对碳排放量因素、配送总成本因素的分析建立，构建碳排放量最少、配送总成本最低的多目标数学模型如下：

约束条件：

式（8）表示车辆配送过程中产生碳排放量最少的目标函数；式（9）表示物流车辆配送时配送总成本最低的目标函数，主要包括三个方面，分别为车辆行驶距离成本、车辆固定使用成本和时间窗惩罚成本；式（10）表示客户点的载重负荷限制；式（11）表示每个客户点仅被访问一次；式（12）、式（13）表示每个需求点仅被一辆车服务；式（14）表示配送车辆的起点和终点必须为配送中心；式（15）表示配送车辆从配送中心出发的时刻为0。

3 基于改进蚁群算法的模型求解

蚁群算法是一种新型的启发式算法，被广泛应用于各个领域，在解决车辆路径问题时，虽然能规划出从起始点到目标点的路径，并且具有很强的鲁棒性，但存在容易陷入局部最优、过早停止收敛、搜索时间长、效率低等缺点，这里分别从初始信息素，转移规则和信息素更新方式方面进行了改进，加快了算法在初始阶段的寻优速度，提高了算法的搜索效率。

3.1 初始信息素

在初始时刻，将信息素总量与各个需求点和配送中心的距离作为信息素分布矩阵，因此，各个需求点之间影响不同，增加了较优路径被选择的概率，加快了算法在初始阶段的寻优速度。初始信息素的改进数学表达式为：

式中：Q—每一次搜索蚂蚁释放的信息素总量；d1i—需求点i和配送中心的实际距离。

3.2 转移规则

基本蚁群算法在转移规则中只考虑了客户i与客户j的距离，易陷入局部最优。综合考虑客户i与客户j的时间窗宽度及碳排放量，改进表达式如下：

式（17）中概率模型pkij，如式（18）所示。

式中：q—假定的固定阈值，用来控制状态转移规则参数；q0—一个在区间［0，1］上的随机数，当q＜q0，采用确定性搜索模型，当q≥q0时采用改进的概率模型；α—信息素浓度重要因子；β、ω和γ—启发函数重要程度因子；ηij= 1/dij—启发函数；Widthij=l(i) -e(i)—客户的时间窗宽度，时间窗越紧，表示客户的需求越紧迫，优先服务此类顾客；Zij—路径上需求点i到需求点j配送车辆产生的碳排放量，其值越小，说明点i到点j的所积累的信息素浓度越高，则蚂蚁选择该条路径的可能性越高。

3.3 全局信息素更新策略

蚁群算法收敛到最优解的过程是信息素浓度不断增强的体现，信息素的更新策略对于蚁群算法的成功搜索具有重要的意义。传统蚁群算法仅利用蚂蚁经过路径的整体信息（经过路径的总长）计算释放的信息素浓度，没有区分当前最优路径和较差路径，使其信息素分布无法进行较快改变，从而使算法的收敛速度和求解质量较差。改进的信息素更新数学表达式为：

其中，Δτij、Δτijkk和Δτij*的表达式，如式（20）所示。

式中：Δτij(t)—在第t次迭代时，需求点i和需求点j之间路径上的信息素浓度；p—每一次迭代后，路径上信息素的挥发因子；Δτij—每一次迭代的i点与j点信息素改变总量；在该次迭代中，第kk个蚂蚁对于点i与j点信息素改变的贡献值；额外对目前获得的最优路径的奖励，让该路径上的信息素进一步加强；lkk—第kk个蚂蚁选择的路径的总长；lbest—目前获得的最优路径的总长；sizepop—蚂蚁总数。

3.4 混沌扰乱机制

蚁群算法在应用于车辆路径问题时，如果蚁群（车辆）搜索得到的可行解都相同，算法此时可能陷入局部最优，这时引入混沌扰动机制，首先对信息素进行混沌初始化，给出新的启发式信息来对路径进行搜索，具体改进方法为：首先根据混沌迭代方程生成一组混沌变量，混沌变量是通过Logistic 映射（一种经典的混沌映射）产生的，具体方式如下：

但混沌初始化在加快收敛速度的同时也可使算法陷入局部最优解，因此为在蚂蚁完成一轮搜寻后，在信息素更新中加入混沌扰动，可以增加搜寻的遍历性及随机性。引入混沌扰动后的信息素更新表达式为：

式中：ξ—可调节系数，是一个常数；Fij(t)—混沌变量；μ—控制变量，μ的取值范围一般为［3.5-4.0］。

模型求解的具体流程如下：

（1）初始化参数，设定最大迭代次数Maxiter，按照式（16）对每个客户点之间产生初始信息素，初始化Nc（迭代次数）=0，确定每个参数的函数值。

（2）创建禁忌表，让所有的蚂蚁（配送车辆）从配送中心出发，在满足约束的前提下，按照式（17）来选择下一个需求点，并将此需求点添加至禁忌表。

（3）若配送车辆不满足下一个客户点的需求，则配送车辆返回配送中心，更新禁忌表，重复该过程，直到所有的客户点全部加入到禁忌表中，禁忌表更新满足时间窗和载重限制。

（4）采用2-opt对每次路径内的配送路径进行局部优化。

（5）所有蚂蚁完成循环后，按照式（19）来更新信息素，计算当前迭代得到的可行解，并与前代所得到的可行解进行对比，记录最优解，若算法5次得出的可行解不变，则引入混沌扰动机制，按照式（21）、式（22）来更新信息素。

（6）当Nc=Nc+1且Nc＜Maxiter则执行步骤（2）～步骤（5），否则算法迭代结束，输出最优解。

4 算例求解及结果分析

4.1 算例求解

为了验证所提方法的有效性，这里所有测试都在数据集都采用solomom中的R101算例，但R101的各个数据没有设定具体的量纲，所以人为设定载重量以kg为单位，距离以km为单位，时间以s为单位，假设车辆载重f= 200kg，车辆自重W= 100kg，β1= 1.75，信息素浓度Q= 100，蚂蚁数量sizepop= 60，信息素重要程度因子α= 1.5，启发函数重要程度因子β= 3、γ= 1、ω= 1.5，转移阈值q= 0.3，最大迭代次数maxiter= 200，信息素挥发因子p= 0.4车辆固定使用成本g= 200，每公里运输固定成本c= 20元/km时间窗惩罚系数p1= 0.2元/s、p2= 0.4元/s，车辆行驶速度v= 13m/s，车辆空载时燃油消耗率ε0= 0.254，车辆满载时燃油消耗率ε*=0.276，燃油消耗因子F= 2.61kg/L。

由于这里是解决多目标优化问题，对于一个多目标优化问题而言，由于存在目标之间的冲突和无法比较的现象，在目标函数没有进行加权处理的情况下，一个解在某个目标上可能是最好的，在其他目标上可能是最差的，这些在改进任何一个目标函数的同时，必然削弱至少一个其他目标函数的解称为非劣解（非支配解）或Pareto（帕累托）解，其Pareto解不是唯一的，而是多个解构成Pareto最优解集。

采用所提出的算法通过Intel（R）Core（TM）i5-8300H CPU@2.30GHz，运行内存为8GB，操作系统为Win10家庭中文版的matlab2016a上迭代200次，这里提出的多目标模型算例求解结果的非劣解分布图，如图1所示。多目标模型下目标λ1（碳排放量）取极值时对应的车辆路径规划图，如图2所示。多目标模型下目标λ2（配送总成本）取极值时对应的车辆路径规划图，如图3所示。

图1 非劣解分布图Fig.1 Distribution of Non-Inferior Solutions

图2 碳排放量最少时车辆最优路径分布Fig.2 Optimal Path Distribution for Vehicles with the Lowest Carbon Emission

图3 配送总成本最低时车辆最优路径分布Fig.3 Optimal Path Distribution of Vehicles at the Lowest Total Distribution

将所提算法对不同目标函数进行求解，求解的结果，如表1所示。其中A是只虑碳排放量最少，不考虑配送总成本时的单目标优化结果，B只考虑配送总成本最低，不考虑碳排放量时的单目标优化结果，C1是多目标模型下目标λ1（碳排放量）取极值时对应的数据。C2是多目标模型下目标λ2（配送总成本）取极值时对应的数据。

表1 不同目标函数下的结果统计Tab.1 Results Statistics Under Different Objective Functions

对A和C1的数据进行分析可得，相比于多目标优化，在只考虑碳排放量这一单目标优化时，虽然碳排放量降低了1.9%，但是配送总成本却增加了7.04%；对B和C2的数据进行分析得，相比于多目标优化，在只考虑配送总成本这一单目标优化时，其成本降低了1.7%，碳排放量却增加了3.2%，所以提出的多目标优化模型在同时解决配送总成本和碳排量这两个目标时，相比于单目标，具有更好的实用性。

4.2 算法性能分析

为了验证这里算法的性能，在参数设置完全相同的情况下，将改进蚁群算法和经典蚁群算法各运行10次后，两种算法的非劣解分布，如图4所示。两种算法的碳排放量收敛曲线对比，如图5所示。两种算法的配送总成本的收敛曲线的对比，如图6所示。两种算法的优化改进比例统计结果，如表2所示。

图4 非劣解分布对比Fig.4 Distribution Comparison of Non-Inferior Solutions

图5 碳排放量收敛曲线Fig.5 Convergence Curve of Carbon Emission

图6 配送总成本收敛曲线Fig.6 Convergence Curve of Distribution Cost

由图4可知，相比于经典的蚁群算法，改进蚁群算法的Pareto解集中非劣解不仅在数量上更多，而且Pareto前沿也具有更好的分布性。由图5、图6可以看出改进算法在求解质量和收敛速度上具有明显优势。由表2可知，在配送总成本方面，最低成本的改进比例为4.5%，最高成本的改进比例为8.4%，平均成本改进比例为6.5%；在碳排放量方面，最少碳排放量的改进比例为4.2%，最高碳排放量改进比例为1.4%，平均碳排放的改进比例为3.5%。与经典蚁群算法相比，所提出改进算法在降低配送总成本和减少碳排放量方面均有明显改进。

5 结语

在带软时间窗和容量限制的车辆路径优化问题上，综合考虑了汽车载重负荷、行驶速度和行驶距离等影响碳排放量的因素，提出了同时考虑碳排放量和配送总成本的多目标车辆路径优化模型，针对经典蚁群算法的不足，重新设计了初始信息素和路径转移规则等环节，提高了算法的全局搜索能力，再用2-opt算法对局部进行搜索，进一步优化了解的质量，其次引入了新的信息素更新公式和混沌扰动机制来更新路径上的信息素，加强了解的多样性，通过对模型的求解，算例分析结果如下：（1）分别以只考虑碳排放量，不考虑配送总成本、只考虑配送总成本，不考虑碳排放量和同时考虑碳排放量和配送总成本为目标函数，在相同的数据集中测试表明所提出的多目标模型能够在降低物流企业配送成本的同时实现节能减排，更符合企业的发展。（2）通过对solomo数据集的测试，所提出的改进的蚁群算法在配送总成本的和碳排放量的优化上均优于经典的蚁群算法，证明该算法在一定程度上能求解出有效的满意解。所提出的模型和改进的算法能够有效的解决物流配送问题，但笔者未考虑当客户需求点发生动态变化以及道路拥堵等动态因素，这是下一步研究的重点。