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

中国新技术新产品2024 NO.3（下）-130-技 术 经 济 与 管 理随着全球物流网络的不断发展和扩展，作为物流管理领域中的重要组成部分，逆向物流逐渐受到关注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）所示。Zff dxkkijijkmmMkKjNiNk1121100?（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；f1k为 k 型车辆的发车成本，元；f2k为 k 型车辆单位距离所产生的折旧费和人力成本，元/km；xijkm为 01 的变量，如果 k 类型车辆 m 从节点 i 驶向节点 j，则为 1，否则为 0。1.2 油耗成本本文采用Barth等3提出的综合模式排放模型（comprehensive modal emission model，CMEM），通过该模型计算车辆的燃油消耗量，如公式（2）所示，并进一步列出油耗成本，如公式（3）所示。FCk m iju=1kdk m iju/iju+2kdk m iju2iju+3k（rk+k m iju）dk m iju（2）ZFC C hijukmfijukmmMkKjNiNk21100?（3）式中：1k、2k和 3k分别为 k 类型车辆的发动机模块系数、速度模块系数和载重模块系数；dk m iju为 k 类型车辆 m 在时间段u 内在道路（i，j）上的行驶距离；rk为 k 类型车辆的自重，kg；iju为车辆在时间段 u 内在道路（i，j）上的行驶速度；k m iju为 k 类型车辆 m 在时间段 u 内行驶在道路（i，j）上的载质量，kg；FCk m iju为车辆 m 在时间段 u 内在道路（i，j）上的油耗量，L；Cf为单位油耗费用，元/L；hk m iju为 01 的变量，如果 k 类型车辆 m 在时间段 u 内从节点 i 到 j，则为 1，否则为 0。1.3 碳排放成本车辆的燃油消耗是造成碳排放的主要因素。研究表明，车辆的碳排放与燃油消耗呈正比。因此碳排放成本如公式（4）所示。ZFEFC C hijukmeijukmmMkKjNiNk31100?（4）式中：FE 为燃油排放参数，取值为 2.621kg/L4；Ce为单位碳排放费用，元/kg。1.4 时间惩罚成本为保证按时完成回收任务满意，应严格要求回收时间，时间惩罚成本函数 Z4如公式（5）所示。ZcETTTETETTLTcTLTLTTiimimiiimiimiiim41200?,?（5）式中：c1为早到惩罚因数，元/min；c2为晚到惩罚因数，元/min；Tim为车辆 m 到达回收点 i 的时间；ETi，LTi 为回收点 i 的服务基于改进蚁群算法的多类型车辆逆向物流路径优化郭元元王巍蒋学微（东北林业大学机电工程学院，黑龙江 哈尔滨 150040）摘 要：低碳经济是经济发展的新趋势，也是逆向物流可持续发展的新兴路径。本文根据车辆的时变速度和负载情况，建立一个度量函数来描述车辆的油耗和碳排放的变化。在此基础上，将车辆管理使用成本、油耗成本、碳排放成本、时间惩罚成本和消毒成本之和最小化作为优化目标，从低碳经济的角度构建多类型车辆回收过程中的逆向物流绿色车辆路径问题（GVRPRL）模型，并设计了一种改进的蚁群算法来求解该模型。为了验证模型和算法的有效性，对真实算例进行求解，并与传统的蚁群算法的结果进行比较。结果表明，本文构建的模型和改进算法能够更有效、更合理地规划车辆行驶路径，降低总成本、车辆油耗和碳排放，促进物流企业绿色出行和节能减排。关键词：逆向物流；绿色车辆路径问题；时变速度；碳排放；蚁群算法中图分类号：U116文献标志码：A中国新技术新产品2024 NO.3（下）-131-技 术 经 济 与 管 理时间窗。1.5 消毒成本消毒成本指的是对回收人员、车辆以及回收物品进行消毒所产生的费用。消毒费用主要包括车辆本身、回收人员和回收物品。总的消毒成本 Z5如公式（6）所示。Zpp Sp qkimMkKjNiNk50121100?（6）式中：Sk为 k 类型车辆的表面积；p0为每个回收人员的消毒成本；p1为单位面积内消毒液的价格；p2为单位物品的消毒成本。由上述分析可知，本文构建的多车型 GVRPRL 的非线性规划模型如公式（7）所示。minZ=Z1+Z2+Z3+Z4+Z5（7）2 算法设计传统的蚁群算法通常在静止的情况下进行，但现实中道路条件会发生改变5。在静态条件下，算法不能适应真实的交通状况。同时，蚁群算法易受局部信息的影响，导致蚁群在搜索过程中只选取几条路线，而忽视其他可能更好的路线。蚁群进行路径选择时采用的局部信息素或启发式方法，会使蚁群只选取一条路径，不能对整个搜索空间进行高效搜索。为了改善上述问题，该文采用改进的蚁群算法。2.1 算法中挥发因子 的改进对挥发系数进行动态调节来提高算法的适应性。在初始阶段，增大挥发系数可以使蚂蚁搜索可能解的空间更广阔，从而得到全局最优结果。在迭代中，逐步降低挥发系数可以延长信息素在路径上的累积时间，加快收敛速度，由此可得挥发系数如公式（8）所示。?tt exxttT?1max,minmaxotherwise（8）式中：t 为当前迭代次数；T 为总迭代次数；x 为最优解连续未进化的循环次数；xmax为一常数值；为控制挥发因子衰减速度的一个常数。为了避免 衰减太多进而影响算法的性能，本文设置了一个 min值，当 x=xmax时，就按照（t）e-tT的方式降低 值，并将 x 置为 0 再次计数，按照此过程进行循环，直至 衰减到最小值 min为止。2.2 基于精英蚂蚁策略的信息素更新方法本文引入精英蚂蚁策略来提升算法的收敛速度，将每次迭代过程中总回收成本最小的精英蚂蚁 a 作为优化目标，对其进行信息素更新，如公式（9）公式（11）所示。?ijnewijoldijbijabB?11?（9）?ijbbHZ?/,0,otherwise当蚂蚁 b 在本次迭代中经过边 ij 时 （10）?ijabHZ?/,0,otherwise当精英蚂蚁 a 在本次迭代中经过边 ij 时（11）式中：为挥发率，01；bij为蚂蚁 b 在路段（i，j）上的信息素增加量；aij为精英蚂蚁 a 在路段（i，j）上的信息素增加量；H 为与信息素轨迹相关的常数；Zb为蚂蚁 b 的总配送费用；为精英蚂蚁信息素的权重。2.3 状态转移概率的设置在蚁群算法中，最主要的问题是状态转移和信息素更新6。本文研究的是为回收中心提供一种总成本最小的回收策略，因此启发式因子 ij如公式（12）所示。?ijZ?1（12）状态转移概率的计算过程如公式（13）所示。PZZjallowedijmijiss allowedmm?11,0,otherwise?（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:0022:00，共 16h，即 960min.根据城市交通规律，将上午 7:009:00 和下午 18:0020:00 设定为交通拥堵时间段（即早、晚高峰时间段）。在此期间，车辆以拥堵速度 c行驶，在非拥堵时间段，车辆以正常速度 f行驶，f和 c的取值分别为 60km/h 和 20km/h。回收车辆参数7来自庆铃汽车官方网站。回收车辆信息见表 1，其中包括每种车型的自重、最大载质量、发车成本、折旧和人力成本、各项模块系数以及车辆表面积等信息。涉及的回收点需求信息见表 2，其中 0 表示回收中心；编号 120 表示 20 个回收点；X、Y 分别表示回收中心和回收点的横、纵坐标。分别采用传统蚁群算法（ACO）和改进后的蚁群算法（IACA）来实现该回收中心与各回收点间的运输，所求结果如图 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 元。从上述各项结果的分析可知，改进后的蚁群算法无论在车辆使用数量和载重率方面，还是在总运输距离、总行驶时间、总成本、油耗和碳排放成本等方面均优于传统蚁群算法，说明改进后的蚁群算法性能更优，能得到更小的总目标中国新技术新产品2024 NO.3（下）-132-技 术 经 济 与 管 理值，而且油耗和碳排放量的降低也响应了国家绿色物流的号召，达到了节能减排的目的。表 2 回收点需求信息表编号X坐标/km Y坐标/km 回收量/kg左时间窗/min右时间窗/min0454501925612507078482271313671432823482616496788014103213283420952443115941551467462155230141073186196957771684175308417032596341126269082710151013253224311824166627237312155813127338701338251395581666149801525214331153871356206325168245208970484717781211255886671880301426104255198573147319031320658220592594264 结语优化和改善逆向物流回收过程中的车辆路径问题可以更有效地利用车辆和人力资源，降低资源浪费。同时，通过车辆优化路径，可以减少行驶距离和行驶时间，从而降低运输成本，也有效降低了车辆行驶过程中产生的油耗和碳排放。科学合理的车辆路径优化不仅有助于企业提高效益和竞争力，还有助于保护环境，推动可持续发展。比传统蚁群算法相比，本文的改进蚁群算法在寻优能力和寻优效率方面均有明显改善，对企业高效利用资源有重要现实意义，也符合可持续发展的理念。参考文献1 赵娆，陈志华.基于局部搜索的逆向物流车辆最短路径优化 J.计算机仿真，2022，39（11）：215-219.2 满子会.我国再生资源回收利用产业发展成效、挑战与进路 J.价格理论与实践，2023（6）：1-4.3WANG J，RAKHA H A.Fuel consumption model for heavy duty diesel trucks：Model development and testingJ.Transportation research part D-Transport and environment，2017，55：127-141.4HOEN K M R，TAN T，FRANSOO J C，et al.Effect of carbon emission regulations on transport mode selection under stochastic demand J.Flexible services and manufacturing journal，2014，26（1-2）：170-195.5 陈志新，闫昊炜，张昕宇，等.基于改进蚁群算法的 B2B城配模式下车辆路径优化 J.公路交通科技，2023，40（7）：231-238.6 李婷婷，邓社军，陆曹烨，等.一种基于改进蚁群算法的垃圾车辆低碳收运路径优化方法 J.公路交通科技，2023，40（5）：221-227.7LI S，DAN B，GE X.Low-carbon heterogeneous vehicle routing problem under multi-graph networkJ.Computer integrated manufacturing systems，2019，25（11）：2973-2982.表 1 回收车辆信息表车型k车辆自重rk/kg最大载质量Qk/kg发车成本f1k/元折旧和人力成本f2k/（元km-1）发动机模块系数1k速度模块系数2k载重模块系数3k车辆表面积Sk/m3127003500501.51.11810-33.71310-71.68110-8402695088558021.39010-34.40110-71.49410-890310200146051202.51.44310-35.19810-71.34510-8130表 3 蚁群算法和改进后的蚁群算法对算例的运算结果算法车辆型号行驶路径载质量/kg 载重率/%总运输距离/km总行驶时间/min总成本Z/元油耗和碳排放成本（Z2+Z3）/元ACO10-9-3-13-0310688.74555.792465.603287.861125.1510-5-12-14-0279679.8920-6-19-20-7-8-0813791.8930-4-11-10-2-15-17-18-16-1-0933263.90IACA10-9-18-17-0261374.66464.202377.432651.801022.2520-5-4-11-10-2-15-13-3-0804590.8530-6-16-1-19-20-8-7-14-12-01271387.05图 1 传统蚁群算法的回收路径 图 2 改进蚁群算法的回收路径100806040200100806040200001001008080606040402020Y坐标Y坐标X坐标X坐标7819191181715313111024509121478206166117151011121320942313051816