基于改进蚁群算法的多类型车辆逆向物流路径优化

郭元元 王 巍 蒋学微

（东北林业大学机电工程学院，黑龙江 哈尔滨 150040）

随着全球物流网络的不断发展和扩展，作为物流管理领域中的重要组成部分，逆向物流逐渐受到关注[1]，研究如何优化逆向物流车辆路径问题（Vehicle routing problem in reverse logistics，VRPRL）具有重要的理论和经济意义。逆向物流强调废弃物品的回收、再利用和环保处置，这一概念的兴起为减少资源浪费、降低环境负担提供了创新的解决途径。通过将废弃物重新纳入生产循环，逆向物流为企业创造了机会，不仅促进了可持续发展，也有助于构建更环保、经济且高效的供应链体系[2]。

本文研究了单个回收中心和多个回收点的路径规划，采用不同类型的车辆从回收中心出发去往若干回收点。为便于分析，做出以下9个假设。1）只有一个回收中心且能满足全部需求。2）回收中心有多种不同型号的回收车辆，所有回收车辆的实际载重不能超过其额定载重Qk。3）回收车辆对所分配的所有客户提供服务后，需要重新返回回收中心。4）每个回收点都有服务且只能被一辆车服务一次。5）每个回收点的位置、回收量和时间窗要求等信息都己知。6）所有车辆运行工作时间均相同且每辆车的工作时间不得超过其最大运输时间。7）车辆的行驶速度为时变速度。8）每辆车均使用相同型号的消毒设施与消毒液。9）回收车辆应在客户规定的时间窗内到达收集点。

1 模型的建立

1.1 车辆管理使用成本

车辆的使用管理成本包括车辆的发车成本和人力成本，其中人力成本为总行驶距离与单位费用的乘积。根据车辆型号的不同，发车成本和单位费用的值是不同的，则车辆的管理使用成本Z1如公式（1）所示。

式中：N为回收节点集合，N={i，j|i，j=0，1，2，...，N}；0代表回收中心；K为车型集合，K={k|k=1，2，...K}；Mk为k类型车辆的编号，集合为m，Mk={m|m=1，2，...，Mk}，m∈Mk；为k型车辆的发车成本，元；为k型车辆单位距离所产生的折旧费和人力成本，元/km；为0～1的变量，如果k类型车辆m从节点i驶向节点j，则为1，否则为0。

1.2 油耗成本

本文采用Barth等[3]提出的综合模式排放模型（comprehensive modal emission model，CMEM），通过该模型计算车辆的燃油消耗量，如公式（2）所示，并进一步列出油耗成本，如公式（3）所示。

式中：、和分别为k类型车辆的发动机模块系数、速度模块系数和载重模块系数；为k类型车辆m在时间段u内在道路（i，j）上的行驶距离；rk为k类型车辆的自重，kg；υiju为车辆在时间段u内在道路（i，j）上的行驶速度；为k类型车辆m在时间段u内行驶在道路（i，j）上的载质量，kg；为车辆m在时间段u内在道路（i，j）上的油耗量，L；Cf为单位油耗费用，元/L；为0～1的变量，如果k类型车辆m在时间段u内从节点i到j，则为1，否则为0。

1.3 碳排放成本

车辆的燃油消耗是造成碳排放的主要因素。研究表明，车辆的碳排放与燃油消耗呈正比。因此碳排放成本如公式（4）所示。

式中：FE为燃油排放参数，取值为2.621kg/L[4]；Ce为单位碳排放费用，元/kg。

1.4 时间惩罚成本

为保证按时完成回收任务满意，应严格要求回收时间，时间惩罚成本函数Z4如公式（5）所示。

式中：c1为早到惩罚因数，元/min；c2为晚到惩罚因数，元/min；Tim为车辆m到达回收点i的时间；[ETi，LTi]为回收点i的服务时间窗。

1.5 消毒成本

消毒成本指的是对回收人员、车辆以及回收物品进行消毒所产生的费用。消毒费用主要包括车辆本身、回收人员和回收物品。总的消毒成本Z5如公式（6）所示。

式中：Sk为k类型车辆的表面积；p0为每个回收人员的消毒成本；p1为单位面积内消毒液的价格；p2为单位物品的消毒成本。

由上述分析可知，本文构建的多车型GVRPRL的非线性规划模型如公式（7）所示。

2 算法设计

传统的蚁群算法通常在静止的情况下进行，但现实中道路条件会发生改变[5]。在静态条件下，算法不能适应真实的交通状况。同时，蚁群算法易受局部信息的影响，导致蚁群在搜索过程中只选取几条路线，而忽视其他可能更好的路线。蚁群进行路径选择时采用的局部信息素或启发式方法，会使蚁群只选取一条路径，不能对整个搜索空间进行高效搜索。为了改善上述问题，该文采用改进的蚁群算法。

2.1 算法中挥发因子ρ的改进

对挥发系数进行动态调节来提高算法的适应性。在初始阶段，增大挥发系数可以使蚂蚁搜索可能解的空间更广阔，从而得到全局最优结果。在迭代中，逐步降低挥发系数可以延长信息素在路径上的累积时间，加快收敛速度，由此可得挥发系数如公式（8）所示。

式中：t为当前迭代次数；T为总迭代次数；x为最优解连续未进化的循环次数；xmax为一常数值；λ为控制挥发因子衰减速度的一个常数。

为了避免ρ衰减太多进而影响算法的性能，本文设置了一个ρmin值，当x=xmax时，就按照ρ（t）的方式降低ρ值，并将x置为0再次计数，按照此过程进行循环，直至ρ衰减到最小值ρmin为止。

2.2 基于精英蚂蚁策略的信息素更新方法

本文引入精英蚂蚁策略来提升算法的收敛速度，将每次迭代过程中总回收成本最小的精英蚂蚁a作为优化目标，对其进行信息素更新，如公式（9）～公式（11）所示。

式中：ρ为挥发率，0≤ρ＜1；为蚂蚁b在路段（i，j）上的信息素增加量；为精英蚂蚁a在路段（i，j）上的信息素增加量；H为与信息素轨迹相关的常数；Zb为蚂蚁b的总配送费用；ε为精英蚂蚁信息素的权重。

2.3 状态转移概率的设置

在蚁群算法中，最主要的问题是状态转移和信息素更新[6]。本文研究的是为回收中心提供一种总成本最小的回收策略，因此启发式因子ηij如公式（12）所示。

状态转移概率的计算过程如公式（13）所示。

式中：allowedm为蚂蚁m在下一步可以选择的位置集合；α为信息素的相对重要程度；β为期望启发因子的相对重要程度；Tij为节点i、j间的信息素浓度；τis为位置点i到初始点的信息素浓度。

3 算例分析

程序在MATLAB R2021a 中进行编程和实现，蚁群算法的种群数量为20，迭代次数为400，ρ=0.3，ρmin=0.1，xmax=10，λ=3，ε=4，H=10，α=1，β=3。对某回收中心的回收路径进行优化，采用3种类型车辆进行回收服务。回收中心的工作时间为6:00～22:00，共16h，即960min.根据城市交通规律，将上午7:00～9:00和下午18:00～20:00设定为交通拥堵时间段（即早、晚高峰时间段）。在此期间，车辆以拥堵速度υc行驶，在非拥堵时间段，车辆以正常速度υf行驶，υf和υc的取值分别为60km/h和20km/h。回收车辆参数[7]来自庆铃汽车官方网站。回收车辆信息见表1，其中包括每种车型的自重、最大载质量、发车成本、折旧和人力成本、各项模块系数以及车辆表面积等信息。涉及的回收点需求信息见表2，其中0表示回收中心；编号1～20表示20个回收点；X、Y分别表示回收中心和回收点的横、纵坐标。

表1 回收车辆信息表

表2 回收点需求信息表

分别采用传统蚁群算法（ACO）和改进后的蚁群算法（IACA）来实现该回收中心与各回收点间的运输，所求结果如图1、图2和表3所示。

图1 传统蚁群算法的回收路径

图2 改进蚁群算法的回收路径

表3 蚁群算法和改进后的蚁群算法对算例的运算结果

从上述算例的运算结果可知，传统的蚁群算法和改进后的蚁群算法均需要3种车型来运输。在传统蚁群算法的路径优化方法下，车辆载重率波幅较大，最大载重率为91.89%，最低为63.90%，最终总运输距离为555.79km，总行驶时间为2465.60min，总运输成本为3287.86元，油耗和碳排放成本之和为1125.15元。在本文改进蚁群算法的路径优化方法下，车辆载重率相对稳定，载重率最大为90.85%，最低为74.66%。最终总运输距离为464.20km，减少了91.59km；总行驶时间为2377.43min，减少了88.17min；总运输成本为2651.80元，减少了636.06元；油耗和碳排放成本之和为1022.25元，减少了102.90元。从上述各项结果的分析可知，改进后的蚁群算法无论在车辆使用数量和载重率方面，还是在总运输距离、总行驶时间、总成本、油耗和碳排放成本等方面均优于传统蚁群算法，说明改进后的蚁群算法性能更优，能得到更小的总目标值，而且油耗和碳排放量的降低也响应了国家绿色物流的号召，达到了节能减排的目的。

4 结语

优化和改善逆向物流回收过程中的车辆路径问题可以更有效地利用车辆和人力资源，降低资源浪费。同时，通过车辆优化路径，可以减少行驶距离和行驶时间，从而降低运输成本，也有效降低了车辆行驶过程中产生的油耗和碳排放。科学合理的车辆路径优化不仅有助于企业提高效益和竞争力，还有助于保护环境，推动可持续发展。比传统蚁群算法相比，本文的改进蚁群算法在寻优能力和寻优效率方面均有明显改善，对企业高效利用资源有重要现实意义，也符合可持续发展的理念。