第38卷第5期2021年5月吉林化工学院学报JOURNAL OF JILIN INSTITUTE OF CHEMICAL TECHNOLOGYVol.38 No.5May. 2021文章编号:1007-2853 (2021 )05-0090-05基于改进蚁群算法的物流配送车辆路径优化方法濮明月1，张彦如2(1.安徽新华学院商学院，安徽合肥230088；2.合肥工业大学机械工程学院，安徽合肥230009)摘要：目前路径优化方法忽略了客户时间窗约束产生的惩罚成本，导致惩罚成本过高，无法得到最优配 送路径，因此，提出基于改进蚁群算法的物流配送车辆路径优化方法•结合遗传算法完成对蚁群算法的 改进,对物流配送车辆路径问题进行建模，得到路径规划问题的目标函数,并根据配送过程的实际情况 和具体要求设定目标函数的约定条件，计算固定成本和变动成本为路径优化提供判断依据，设计出路径 优化问题的算法流程•在算例分析中，选择某生鲜企业的物流配送作为算例,实验结果表明，设计的方法得到的最优路径总体成本远远低于传统方法,说明所提方法实用性较强.关 键 词：改进蚁群算法;物流配送;路径优化中图分类号：F252 文献标志码：A D0l ：10.16039/22-1249.2021.05.019物流配送是物流系统中的重要环节,在企业 配送过程选择一个合理的路径规划能够降低物流 成本,提高自身的核心竞争力，尤其是生鲜等容易腐败产品的运送,冷链运输成本较高,如果路径规 划不当，会造成很大的货损和较高的运输成本，因此对物流配送车辆路径进行优化十分必要[1-2].在传统的路径优化方法中，仅仅考虑到运输过程中的成本和损耗,忽略了客户时间窗约束产生的惩罚成本，导致物流路径的优化效果并不理 想，因此设计一种基于改进蚁群算法的物流配送车辆路径优化方法.引入时间窗的惩罚机制，科学、合理地解决物流配送路径优化问题，对物流配送车辆路径进行合理规划,尽量减少配送过程中的惩罚成本和货损成本,压缩运输损失.1物流配送车辆路径优化方法1.1蚁群算法的改进蚁群算法实际上是模仿蚂蚁的觅食行为来寻找最优路径，基于蚁群的个体数量庞大，它们之间通过信息素进行沟通,为同伴传递信息,大量的蚂蚁形成一个反馈系统，因而具有较高的效率和时间复杂度,有效解决了寻找食物的问题[3-4].研究的是物流车辆的路径优化,主要目标是缩短配送距离,降低成本,为企业创造更高的利润.蚁群算法是一种基于种群的进化算法，将其应用在路径优化中,刚开始所有的蚁群会选择不同的路径寻找食物，在搜索过程中，蚁群会靠信息素进行沟通,选择较优的路径进行二次食物寻找,如此反复 迭代,会寻找到一条最优路径,其路径搜索过程如图1所示.图1蚁群觅食路径择优过程收稿日期：2021-01-11基金项目：安徽新华学院重点科学研究项目“基于改进遗传算法的物流车辆路径优化研究”(2019rw005)；省级重大 教学改革研究项目“应用型高校新商科人才培养改革与实践研究”(2018jyxm1084) •作者简介:濮明月(1987-)，女，浙江绍兴人，安徽新华学院讲师，硕士，主要从事设施规划与物流工程方面的研究第5期濮明月，等:基于改进蚁群算法的物流配送车辆路径优化方法91蚁群算法具有很好的搜索能力，但是它的初始信息速匮乏,收敛速度比较慢,因此将蚁群算法和遗传算法相结合,提出改进的混合蚁群算法进行迭代求解.结合蚁群算法,得到路径优化问题的算法流程，如图2所示.图2改进蚁群算法流程以上算法的改进主要体现在信息素的更新步骤上.主要待解决问题的目标为路径的最优解•为更新信息素，假定蚁群中的蚁群数量为",物流配送终点客户z和x的距离为d Z x，且设定I为客户之间的亲密程度，即为可见度.1=1,在某时刻t的d zx某蚁群到z客户之间的不可逆移动概率计算公式为：'1(t)"P zx={X1(t),z e B.(1)t=1、0,z年B公式(1)中,B为蚁群没有达到的客户集合,根据这个过程的不断调整，得到路径的信息素更新结果为：A5(t+n)=X皿•(2)公式(2)中的0为信息残留程度.在路径信息素的更新基础上,建立在基因编码上进行遗传算法的选择、交叉和编译3个遗传操作.采用模仿染色体编码的方法对配送路径进行编码,得到一组自然数组成的配送方案编码,选择的核心思想是复制，复制继承父代中的最优解继续改进，避免优质解丢失,交叉可以产生新个体,增加多样性,防止早熟停滞,对最优个体进行变异操作,保存最优解.1.2基于改进蚁群算法的物流配送车辆路径优化建模路径优化问题中,主要包括物流配送中心、需求地点、货物、车辆、约束条件和目标函数等要素构成.在实际的物流配送过程中，会存在一个车辆实际载重问题,假设在一次配送过程中，有K辆车共同配送到N个需求地点，第i个地点对于运送货物的需求量为耳,每辆车的最大载重设为Q,需求点i到需求点j的距离表示为%,车辆的平均行驶速度为s,需求点i要求货物到达的最早时间表示为a’，要求货物到达的最晚时间表示为b，第i辆车的配送路线上需求点的数量表示为"k，那么研究问题最优蚁群目标函数可以表示为：N N Nz=min X X X血％(3)i=0j=0k=1若第k辆车从需求点i行驶到了到需求点j,那么x ljk的值为1,否则为0[5-6].针对上述的目标函数做出假设,设定的配送中心仅有一个且位置确定不变,配备足够的产品和物流配送车辆,所有的配送车辆都需要送配送中心出发,最后再返回配送中心，方便对物流车辆进行下一次的调度管理,所有的需求点位置已知且固定不变，根据上述条件,能够得到目标函数的约束条件为：KX九=1G=2,…，N)k=1NX m^ik W Q(k=1,2,…，K)i=1K<X y0k=K.(4)k=1K NX X x i0k=Kk=1i=1KX x k W Lk=192吉林化工学院学报2021年公式(4)中L为客户总数.在配送过程中，若第k辆车完成需求点i的配送服务，那么y ik的取值为1,否则为0[7-8].在约束条件中，对配送过程进行相关的配送约束，约束条件中的第1个约束公式表示每个需求点有且仅有1次配送服务，也就是说只能由一辆车进行配送;第2个约束公式表示每辆车的配送路线上所有需求点的货物需求量总和不能超过车辆的最大载重;第3个公式表示配送车辆的出发地点都必须在配送中心；第4个公式表示配送车辆完成配送后都必须回到配送中心.1.3物流配送成本在物流配送的过程中，为保证配送物品的新鲜与完整，配送的成本一般包括固定成本和变动成本•固定成本主要是指与车辆有关的购置费、折旧费以及开车司机和装卸工人的工资等，固定成本是在进行配送服务之前就已经产生了，与后续的配送路程没有关系,且固定成本是由配送车辆的数目决定的[9-11].变动成本包含的项目比较多，主要包括运输成本、货损成本、惩罚成本以及生鲜类商品需要冷链运输的制冷成本[12-13].对物流配送车辆路径进行优化的主要目的就是要降低变动成本,其中的运输成本主要是指商品在运输过程中所产生的费用，包括燃油费以及制冷费等与车辆行驶的距离和时间成正比，可以表示为：C2=C k d ir%k.(5)i e B r e B k e〃式(5)中,B代表所有需求点的集合;〃代表所有车辆的集合;C k表示运输车辆单位里程的运输成本.当车辆k从需求点i行驶到需求点r时,％为1,否则为0,货损成本可以表示为：C3=C0(P1t irk+卩2d r)y rk.(6)e U r e B式(6)中,p1表示配送产生的货损比例;d表示卸货货损比例;C0表示单位商品的价值;t irk表示车辆k从需求点i到r的行驶时间.当车辆k完成 对需求点r的配送时,九为1,否则为0.制冷成本可以表示为[14-15]:C4=〉(1+a0)x E x S out S in xe U(臨-F in)Xp(7)式(7)中,a0表示车体劣化程度;E为热传导率；S out、S in分别表示车体的外、内表面积;F out、T in 分别表示车体的外、内温度为制冷剂价格.运送的惩罚成本可以表示为：C5=5C0M i.(8)式(8)中,5为惩罚因子;M i表示需求点i的缺货数量•根据上述的成本计算公式,能够清晰地计算出物流配送过程中的固定成本和变化成本.对于路径的优化有很好的参考作用.至此完成基于改进蚁群算法的物流配送车辆路径优化.2算例分析2.1数据来源算例分析以某连锁生鲜经营企业的物流配送为例,选取生鲜作为算例中的配送产品，由配送中心对编号1-18门店进行冷却生鲜配送.目标是优化配送中心生鲜的车辆配送路径,将物流的配送成本降到最低.配送中心以及各个门店的地理位置如图3所示：937153226^1U T13图3配送中心和各个门店的地理分布图图3中,标号为0的地标代表配送中心,标号1〜18代表18家门店，配送中心在对各个门店进行生鲜产品配送时,要保证在规定时间内送达，且需要保证供应数量,否则会给该门店造成一定损失，配送要受到惩罚.因此在进行路径规划时，需要对生鲜商品需求量以及约定的服务时间窗进行设置,如表1所示.各个门店、配送中心之间的最短行驶距离可以通过地图后台的数据获取，在配送的过程中,采第5期濮明月，等:基于改进蚁群算法的物流配送车辆路径优化方法93用4辆车进行生鲜配送，每辆车的最大装载量为9t,固定成本为120元/次,单位里程的运输费用(包括制冷剂)为3元/km,车辆平均的行驶速度为40km/h,从5:00开始从配送中心出发进行配送.蚁群算法中，蚁群数量设置为15,最大迭代次数为200.分别使用路径优化方法和传统方法对算例进行求解，算例平台使用的是matlab7.1软件,进行多次求解后,得到最佳路径，并对最后的结果进行分析对比.表1各门店生鲜商品需求量以及时间窗门店编号需求量/t可接受的时间窗1 1.3[5：00,6：25]2 2.1[5：10,6：40]3 1.7[5：20,6：30]4 1.9[5：40,6：40]5 2.1[5：30,6：50]6 2.4[5：00,6：30]7 1.8[5：00,6：20]8 1.6[5：20,6：40]9 1.7[5：50,6：50]10 1.6[5：20,6：40]11 2.1[5：30,6：30]12 1.7[5：40,6：20]13 2.3[5：50,6：30]14 1.6[5：00,6：40]15 1.9[5：30,6：20]16 2.7[5：20,6：10]17 2.6[5：50,6：30]18 2.7[5：50,6：50]2.2实验结果分析在分别对算例进行100次求解后，最终得到了传统文献［3］方法和所提方法的最优配送路径,如图4所示：(b)所提方法图4不同配送路径对比图4(a)为传统方法最终得到的最优路径;图4(b)为所提方法最终得到的最优路径.对这两种配送路径进行成本分析,如表2所示：表2路径成本分析成本分类传统方法路径所提方法路径固定成本480480运输成本293.4257.6货损成本981.2737.2能耗成本2037.51971惩罚成本4732.0总成本3839.13477.8在路径分析中，考虑了5种成本进行路径优化，在实际应用中的约束效果更好,得到的最优路径能够明显的节省运输成本,提高收益；惩罚成本是从各个门店的视角出发，能够体现配送满意度•在验证所提方法的成本约束基础上，为更直观测试不同方法的物流配送车辆路径的有效性,以耗时为实验指标进行实验结果输出.假定本次实验中所有物流运输车辆的车速一致，其耗时越低,则说明其路径越短,优化效果越好,具体实验由图5的实验结果可以看出，随着待配送门94吉林化工学院学报2021年店数量的增多，两种方法的路径耗时不断增加•但是很明显，所提方法的耗时始终低于文献［3］方法，且门店数量达到300个以上时,耗时的增量较小•通过以上实验结果可以得出结论:使用设计的方法对物流配送车辆路径进行优化,在满足车辆容量约束、时间窗约束和惩罚约束的情况下,能够得到总成本最低的物流配送路径方案.3结论物流车辆的入境规划是物流配送的关键，基于传统路径规划方法的缺陷，将蚁群算法与遗传算法进行结合设计了一种新的物流车辆配送路径优化方法•实验结果表明，所设计方法对路径进行优化后，能够有效地降低变动成本•但是研究还有一些不足之处，建立的模型约束条件相对于实际情况考虑的不够全面，例如交通方面出现突发状况时，缺乏实际的调度能动性，在今后的研究中需要进一步解决.参考文献：［1］王蕾，蔡翠，裴爱晖，等.基于改进蚁群算法的物流配送中多取货车辆的最优路径研究［J］.公路交通科技:应用技术版,2018,14(5)：317-320.［2］陈志,江治杰，刘瑶.基于改进蚁群算法的不同路段低碳物流路径优化研究［J］.生态经济，2019,35(12)：53-59.［3］范厚明，杨翔，李荡，等.基于生鲜品多中心联合配送的半开放式车辆路径问题［J］.计算机集成制造系统,2019,25(1)：260-270.［4］江明，王飞，葛愿，等.基于改进蚁群算法的移动机器人路径规划研究［J］.仪器仪表学报，2019,40(2):113-121.［5］李卓,李引珍，李文霞.应急物资运输路径多目标优化模型及求解算法［J］.计算机应用,2019,39(9)：2765-2771.［6］聂清彬，潘峰，吴嘉诚，等.基于改进蚁群算法的自适应云资源调度模型研究［J］.激光与光电子学进展,2020,57(1)：90-96.［7］唐立，郝鹏，张学军.基于改进蚁群算法的山区无人机路径规划方法［J］.交通运输系统工程与信息,2019,19(1):158-164.［8］谢景海，苏东禹，卢诗华，等.基于改进蚁群算法的输电线路路径规划关键技术［J］.电测与仪表,2020,57(4)：122-128.［9］王雷，石鑫.基于改进蚁群算法的移动机器人动态路径规划［J］.南京理工大学学报(自然科学版),2019,43(6)：700-707.［10］许凯波，鲁海燕，黄洋，等.基于双层蚁群算法和动态环境的机器人路径规划方法［J］.电子学报,2019,47(10)：2166-2176.［11］陈侠,艾宇迪，梁红利.基于改进蚁群算法的无人机三维航迹规划研究［J］.战术导弹技术,2019(2):59-66,105.［12］涂亮杰，李林升,林国湘.基于改进蚁群算法的果园移动机器人路径规划研究［J］.机床与液压,2019,47(23)：69-73.［13］姚源果，贺盛瑜.基于交通大数据的农产品冷链物流配送路径优化研究［J］.管理评论，2019,31(4)：240-253.［14］王芳,饶德坤，游静，等.基于改进蚁群算法的带硬时间窗的接送机场服务路径优化研究［J］.系统科学与数学,2019,39(1)：76-89.［15］刘艳秋，徐世达，蔡超.部分联合运输策略下的物流车辆路径优化问题研究［J］.运筹与管理，2018,27(8)：10-19.Vehicle Routing Optimization Method for Logistics Distributionbased on Improved Ant Colony AlgorithmPU Mingyue1,ZHANG Yanru2(1.School of Business,Anhui Xinhua University,Hefei230088,China;2.School of Mechanical Engineering,Hefei University of Technology,Hefei230009,China)Abstract：At present,the path optimization method ignores the penalty cost generated by the time window constraint of the customer,resulting in the high penalty cost and the inability to obtain the optimal distribution path.Based on this,an optimization method for the logistics distribution vehicle path based on the improved ant colony algorithm is plete genetic algorithm combining with improvements on ant colony algorithm,the model of logistics distribution vehicle routing problem is the objective function of the path planning problem,and according to the actual situation of distribution process and the conditions of specific requirements to set the terms of the objective function,to calculate the cost of fixed and variable costs to provide judgment for path optimization,design the arithmetic flow path optimization problem.In the example analysis,the logistics distribution of a fresh enterprise is selected as the example.T he experimental results show that the total cost of the optimal path obtained by the design method is much lower than that of the traditional method,indicating that the proposed method is more practical.Key words：improved ant colony algorithm;logistics distribution;path optimization。
