改进的蚁群算法在VRPTW中的应用

求解VRPSTW问题的参数优化蚁群算法
吴小峰;周军;王艳红;张娜
【期刊名称】《无锡职业技术学院学报》
【年(卷),期】2015(14)5
【摘要】蚁群算法中的关键参数α、β、γ、ρ对算法的求解效率和求解质量有重要的影响.本文利用遗传算法在参数寻优方面的优越性,在蚁群算法运行的同时利用遗传算法去优化关键参数α、β、γ、ρ,提出了求解VRPSTW问题的参数优化蚁群算法,实例证明效果好.
【总页数】4页(P52-55)
【作者】吴小峰;周军;王艳红;张娜
【作者单位】南通航运职业技术学院管理信息系,江苏南通 226010;南通航运职业技术学院管理信息系,江苏南通 226010;南通航运职业技术学院管理信息系,江苏南通 226010;南通航运职业技术学院管理信息系,江苏南通 226010
【正文语种】中文
【中图分类】TP301
【相关文献】
1.基于单物流配送中心的VRPSTW问题求解 [J], 魏国利;塔娜
2.一种求解VRPSTW问题的蚁群算法 [J], 吴小峰
3.基于蚁群算法求解TSP问题的参数优化与仿真 [J], 柳长源;毕晓君;韦琦
4.改进遗传算法求解VRPSTW问题 [J], 魏国利;陈劲;张玉春
5.求解TSP问题的萤火虫参数优化的改进蚁群算法 [J], 徐华丽;刘世林;马艳;苏守宝
因版权原因，仅展示原文概要，查看原文内容请购买。

基于蚁群算法求解VRPTW路径规划问题研究作者：魏子秋孙明哲来源：《物流科技》2022年第03期摘要：目前我国物流业迅速发展，但是同时伴有某些方面的不足，比如：成本控制不足。

文章将联系实际情况，同时以配送车辆的运输总成本、总行驶距离和碳排放量为目标函数，并充分考虑实际出现的约束条件，再利用MATLAB软件运行带有时间窗的蚁群算法，对车辆配送路径进行仿真实验，最后寻找到最优配送路径以满足目标函数。

通过实验表明，该数学模型和算法可以更好地解决物流配送路径选择的问题，以达到降低物流成本、提高物流效率等目的。

关键词：物流配送;蚁群算法;路径优化中图分类号：U116.2 文献标识码：AAbstract： At present， China's logistics industry is developing rapidly， but it is accompanied by some shortcomings， such as insufficient cost control. In this paper， according to the actual situation， taking the total transportation cost， total driving distance and carbon emissions of distribution vehicles as objective functions， and taking full account of the actual constraints， the MATLAB software is used to run ant colony algorithm with time window to simulate the vehicle distribution path， and finally find the optimal distribution path to meet the objective function. Experiments show that the mathematical model and algorithm can better solve the problem of logistics distribution route selection， so as to reduce logistics costs and improve logistics efficiency.Key words： logistics distribution; ant colony algorithm; path optimization0 引言在1959年，Dantzing和Ramser 在經过实验和思考后，首次提出配送车辆路径优化问题[1]。

改进的蚁群算法求解VRP问题Improved Ant Colony Algorithm for VRPSANG Guo-zhen1, WANG Feng2, YANG Rui-chen2(1.Weinan Teachers University, Weinan 714000, China;2.Chengde Petroleum College, Chengde 067000, China):A mutation is applied to the ant colony algorithm and the mutation probability is given for solving the VRP problem more efficiently. The formula of visibility and pheromone updating method are set reasonably. Combined with swap local search, a more stable ant colony algorithm for VRP is gained. Experiments show that the algorithm is stable and effective.Keywords:VRP; ant colony algorithm; mutation; local search 车辆路径问题[1] (vehicle routing problem,VRP) 是组合优化领域中著名的NP-hard 问题之一, 一般需使用启发式搜索算法求解。

蚁群算法是模拟蚂蚁觅食原理的一种仿生学启发算法, 其应用于VRP问题的求解具有更为明显的优势，很多人对此进行了研究。

1VRP问题采用赋权有向图G=(V,A,d) 来表示配送路径问题。

其中,V={vO,v1,v2,…,vn}为点的集合;v0表示配送中心;vi(i=1,2, …,n)表示各顾客;A={(vi,vj)|vi,vj € V,i 丰j}为弧的集合;dij是与弧(vi,vj) 相联系,表示vi到vj的距离。

基于改进蚁群算法对VRP线路优化
王晓东;张永强;薛红
【期刊名称】《吉林大学学报（信息科学版）》
【年(卷),期】2017(035)002
【摘要】针对基本蚁群算法存在易陷入局部最优解、收敛速度慢等缺点,先引入节约矩阵U作为先验信息引导蚂蚁搜索,然后通过不同搜索时段采用不同的信息素挥发因子,使算法更好地在“探索”和“利用”之间达到平衡,并对较优解应用2-opt 方法进行优化.最后将改进后的蚁群算法应用到物流配送车辆路径优化问题中.实验结果表明,相比基本蚁群算法,改进的算法可得到更好的物流配送路径,是解决物流配送路径优化问题的一种有效方法,可快速、高效地对送货车辆线路进行调整,满足消费者的需求.
【总页数】6页(P198-203)
【作者】王晓东;张永强;薛红
【作者单位】西安工程大学理学院,西安710048;西安工程大学理学院,西安710048;西安工程大学理学院,西安710048
【正文语种】中文
【中图分类】TP391.9
【相关文献】
1.基于改进蚁群算法的装配线VRPTD问题研究 [J], 刘凯;牛江川;申永军;韩彦军
2.基于改进蚁群算法的装配线VRPTD问题研究 [J], 刘凯;牛江川;申永军;韩彦军
3.一种基于CVRP的改进蚁群算法 [J], 王书勤;黄茜
4.基于改进蚁群算法的CVRP问题 [J], 张海军;徐廷学;逯程;韩玉
5.基于改进蚁群算法的CVRP问题研究 [J], 程亮;干宏程;刘勇
因版权原因，仅展示原文概要，查看原文内容请购买。

VRPSTW的混合改进蚁群优化算法
崔雪丽;马良
【期刊名称】《计算机应用研究》
【年(卷),期】2010(027)003
【摘要】软时间窗车辆路径问题(VRPSTW)是VRP的一种重要扩展类型,定义了其惩罚函数并建立数学模型.设计用于求解该问题的混合改进型蚁群算法并求解标准数据库中的紧时间窗实例.经过大量数据测试,获得了较好的效果,并验证了蚁群算法用于求解软时间窗车辆路径问题的成功实现.
【总页数】5页(P845-848,852)
【作者】崔雪丽;马良
【作者单位】苏州科技学院,经济与管理学院,物流管理系,江苏,苏州,215011;上海理工大学,管理学院管理科学与工程系,上海,200093
【正文语种】中文
【中图分类】O223
【相关文献】
1.求解VRPSTW问题的参数优化蚁群算法 [J], 吴小峰;周军;王艳红;张娜
2.一种求解VRPSTW问题的蚁群算法 [J], 吴小峰
3.基于MIMIC算法和RPCA的混合蚁群优化算法 [J], 官娟;刘国华;刘天祺;秦健;张淼森
4.针对混合变量优化问题的协同进化蚁群优化算法 [J], 韦铭燕;陈彧;张亮
5.结合头脑风暴优化的混合蚁群优化算法 [J], 李蒙蒙;秦伟;刘艺;刁兴春
因版权原因，仅展示原文概要，查看原文内容请购买。

,],]年!!+月郑州大学学报!工学版"J >D ^!,],]第2*卷!第2期J @>K (#D @G _&’(I O &@>;(C P ’K E C =$!Z (I C (’’K C (I <B C ’(B ’"4@D ‘2*!U @‘2收稿日期!,],]a]*a ]1%修订日期!,],]a ]7a **基金项目!国家自然科学基金资助项目!3*1+3*38#3*8,,]+,"作者简介!朱晓东!*8+]&"#男#河南郑州人#郑州大学副教授#主要从事智能控制及智能信息处理方面的研究#ZH N #C D’O &>y[?cO O >^’?>^B ((!!文章编号!*3+*a 31..",],]#]2a ]]7,a ]+求解双目标.$B 0T 的改进混合蚁群算法朱晓东!王!鼎!郑州大学电气工程学院#河南郑州27]]]*"摘!要!为了解决基本混合蚁群算法在求解大规模带时间窗车辆路径问题$450)6%时存在的问题!提出一种改进的双目标混合蚁群算法"首先在节点选择上使用周边选择策略提升选择效率!并提出一种首节点选择策略来加速算法收敛&其次在信息素叠加公式上增加了与车辆数有关的惩罚函数!使算法能够同时优化距离与车辆数两个目标&最后提出一种新的局部优化算法!通过将节点数较少的线路中的节点插入到其他线路来提升车辆利用率"通过该算法在<@D @N @(标准数据集上的实验和对比!说明了改进的算法具有搜索能力强#收敛速度快#鲁棒性强等优点"关键词!蚁群算法&车辆路径问题&时间窗&双目标中图分类号!)0.]*‘3文献标志码!9P EI !*]‘*.+]7d Y ^C E E (^*3+*a 31..‘,],]^]2‘]]273引言车辆路径问题**+!P ’&C B D ’K @>=C (IFK @WD ’N #450"是指使用一组车辆从配送中心出发给已知客户进行配送服务#在满足一定约束条件下#求解最短路径的线路(带时间窗的车辆路径问题!P ’H &C B D ’K @>=C (I FK @WD ’NS C =&=C N ’S C (?@S #450)6"是450的拓展#它在450的基础上增加了服务时间的限制#即每个客户都有接受服务的时间范围#称为时间窗#车辆必须在时间窗内对客户进行服务(良好的路径规划不仅可以节省运输成本#提高配送效率#还可以提升服务质量#带来巨大的经济效益(由于450)6是一个非确定性多项式难题!U 0H R #K ?"#精确算法无法在有效时间内完成求解#使用启发式算法求解大规模客户450)6问题受到专家学者的广泛关注#比如遗传算法*,a .+)差分进化算法*2+)粒子群优化算法*7+)布谷鸟搜索算法*3+等(蚁群算法*++在解决450)6问题上取得了众多成果#如b>等*1+提出了蚁群算法和禁忌搜索混合的算法#该算法先使用蚁群算法得到一个局部最优解#然后使用一次禁忌搜索算法来跳出局部最优%QC (I 等*8+对蚁群系统作了进一步改进#在计算转移概率时考虑了节点之间的节约值#同时采用,H C (=’K B &#(I ’作为局部优化方法#提升了算法的收敛速度%朱杰等**]+将模拟退火算法和蚁群算法结合#改进了蚁群算法中状态转移公式和信息素更新策略#提高算法搜索能力%刘云等***+将单亲遗传算法和蚁群算法相结合#提升了传统蚁群算法的计算效率和收敛速度#并通过实际算例说明算法的实用性%柴获等**,+采用一种混合蚁群算法来解决双目标带时间窗车辆路径问题#提出了一种新的搜索空间构建方法#并改进了蚁群算法的状态转移公式%孙小军等**.+提出一种动态混合蚁群优化算法#该算法将蚁群算法和遗传算法进行融合#自适应控制蚁群算法参数%葛斌等**2+提出了一种动态混合改进蚁群算法#该算法在对客户分区的基础上#引入了交通拥堵因子来改进传统算法中的状态转移公式#并将挥发因子设置为随机变量#使算法更稳定地收敛到全局最优解(上述文献通过对传统蚁群算法的改进#促进了蚁群算法在450)6问题上的应用及发展#但仍存在不足(如b>等*1a *]+提出的算法均是以最短路径为目标#但是在实际问题中还要考虑车辆数等多个目标#单目标优化无法满足实际需求(刘云等***a *,+提出了解决实际问题的多目标改进!第2期朱晓东#等’求解双目标450)6的改进混合蚁群算法7.!蚁群算法#但所解决问题中节点数较少#在解决大规模节点问题上存在搜索能力不足)收敛速度慢等缺点(针对这些问题#笔者提出一种用于解决大规模双目标450)6的改进混合蚁群算法(53.$B 0T 数学模型记!!T#*"为赋权图#T 为顶点集#T !T ]*T B #其中T ]!1]2表示配送中心#T B !1*#,#$#12表示配送节点%*为边集#*!1!6#P "I 6#P %T #6.P 2表示节点6和P 之间的有向线段(设>6P 表示节点6)P 之间的距离#H 6P 表示车辆从6到P 的时间(节点6的需求量为>6#接受服务的时间窗为**X 6#5X 6+#服务时长为ZX 6(]!1*#,#$#22表示车辆编号#每辆车载重恒定为%#车辆/到达节点6的时间X 6/#若车辆/在时间窗开始之前到达#则需等待一段时间S 6/#S 6/!N #[!]#*X 6&X 6/"(定义变量’B 6P /!*#车辆/从6行驶到P %]#其他({U /6!*#节点6由车辆/服务%]#其他({!!本文中450)6的双目标数学模型可表述为’)*!N C (#6%T #P %T #/%]>6P B 6P /#!*"),!N C (#P %T #/%]B ]P /#!,"E ^=’#6%T>6U/6(%#’/%]#!."#6%T BU /6!*#’/%]#!2"#6%TB6P /!U /P #’P %T #’/%]#!7"#P %T B6P /!U /6#’6%T #’/%]#!3"#P %T BB]P /!#P %T BB ]P /!*#’/%]#!+"X 6/C5X 6#’6%T #!1"X 6/(S 6/(ZX 6(H 6P C5X P #’6#P %T #’/%](!8"其中#式!*")!,"为目标函数#表示以路径的最短距离和最小车辆数为目标%约束条件!."表示每条线路上的客户需求量不能超过车辆容量限制%约束条件!2"表示每个客户只能被访问一次%约束条件!7"表示车辆在服务节点P 之前只服务了一个节点6%约束条件!3"表示车辆在服务节点6后只服务了一个节点P#避免线路内部产生回路%约束条件!+"表示每辆车的起点和终点都必须是配送中心%式!1"F !8"为时间窗约束(63基本混合蚁群算法求解.$B 0T6D 53可行解的构建使用基本蚁群算法求解450)6时#首先令每只蚂蚁从配货中心出发#根据状态转移概率随机地从候选节点集合中选择下一节点来构建可行线路#若线路上无可行节点添加时#该蚂蚁返回配货中心#完成一条可行线路的构建(接着重复上述过程#继续从剩余节点中构建可行线路#直到所有节点都被访问#完成一个可行解的构建(假设当前节点为6#下一个节点的候选集合为^]#蚂蚁从节点6转移至节点P 的转移概率为’Q 6P!+’6P ,-.6P #P %^]+’6P ,-.6P #!P %^]%]#!其他#!*]"式中’Q 6P 表示蚂蚁从节点6转移到节点P 的概率%+6P 为6)P 两点的信息素浓度%-6P!*>6P 为能见度%’).为启发因子(当所有蚂蚁完成可行解的构建后#按照下式进行全局信息素更新(+(’S 6P !!*&"",+@D ?6P ()+6P#!**"!)+6P!#2G !*8>6=!G "#!!6#P "%5!G "%]#!其他#{!*,"式中’"!]C "C *"为常数#表示信息素的挥发速率%)+6P 为信息素累计量%2为蚂蚁数量%5!G "为第G 只蚂蚁的路径#>6=!G "表示第G 只蚂蚁的总距离%8为常数#表示每只蚂蚁释放信息素的总量(6D 63局部优化算法车辆路径问题中常用的局部优化算法有,H C (=’K B &#(I ’和@K H C (=’K B &#(I ’(,H C (=’K B &#(I ’用于两条路径间的邻域搜索#该算法从两条路径分别选取M 和K 个节点进行交换来产生邻域解!M #K %1]#*#,2且M 和K 不同时为]"(图*表示了M !*)K !*时的一个样例’将路径4中的*个节点B 与路径/中的*个节点U 进行交换产生邻域解(@K H C (=’K B &#(I ’用于单条线路的邻域搜索#将线路内部两个节点交换位置来产生邻域解(图,表示将路径4中B )\两个节点交换产生邻域解(72!郑州大学学报!工学版",],]年图53#g 5&$g 5时6d I K M N X A OK LM 变换(I LG N M 536d I K M N X A OK LM S N OK Q \EN UOS I EKb A M K #g 5’$g5图63EN d I K S M N X A OK LM 变换过程(I LG N M 63EN d I K S M N X A OK LM S N OK Q \EN U R N EX M Q Q:3改进的混合蚁群算法在面对大规模450)6时#由于较多的节点数量和复杂的约束#上述基本混合蚁群算法收敛速度慢#搜索效率低#并且无法满足多目标的需求(笔者从候选节点的选择)转移概率和信息素叠加机制等方面对基本蚁群算法进行改进#并提出了一种新的局部优化方法来提升算法的搜索能力(:D 53候选节点集合的改进!*"周边搜索策略(在解决大规模节点问题时#基本蚁群算法产生的候选节点集合中节点数量较多#算法难以搜索到最优解(笔者结合450)6的问题特点#采用周边搜索策略来缩小候选节点搜索范围(该策略是从下一个可行节点的集合中#选择距离当前节点最近的若干节点作为候选节点集合^#如图.所示(图:3周边选择策略(I LG N M :3B M N I R A M N OF Q M F M X S I EKQ S N OS M LV!,"首节点的选择(在可行线路的构建过程中#线路上首节点的选择将会影响接下来整条路径的节点选择#对全局规划来说非常重要(面对大规模客户的450)6问题#线路上的首个节点相对于其他节点来说约束较少#可行节点的数量远多于路径中的节点#为了能够从众多可行节点中选择最合适的节点#笔者提出一种首节点选择策略来提升算法的收敛性(该策略可表述为’迭代初期#每条可行线路上的首个节点按概率从候选节点中随机选取#当迭代进度达到一定条件时#首节点为候选节点中转移概率最大的节点(线路的首节点用6*表示#其选取规则如下’6*!#K I N #[Q ]6*#6H6H N Y $%K #(?@N 6*%^#其他#{!*."式中’Q ]6*表示配货中心到6*的转移概率%6H 表示当前迭代次数%6H N 表示最大迭代次数%$表示迭代的进行程度的参数%^为候选节点集合(:D 63转移概率公式改进在解决大规模复杂约束的车辆路径问题时#基本蚁群算法的转移概率公式中包含节点的特征信息较少#导致算法搜索能力不足#收敛速度慢(为了提升算法的收敛性#将节约算法**7+加入转移概率公式(节约算法首先将两个节点6)P 分别分配到一条空余的线路上#再计算将两个节点合并到一条线路上后可节省的节约值Z 6P (式!*2"为节约值计算公式(Z 6P !>]6(>]P &>6P#!*2"式中’>]6)>]P 和>6P 分别表示配货中心到6)P 节点的距离和6)P 两节点的距离(改进后的状态转移公式如下’Q 6P!Z 6P ,+’6P ,-.6P #P %^Z 6P ,+’6P ,-.6P #!P %^%]#!其他(!*7":D :3信息素叠加公式的改进基本蚁群算法在叠加信息素时仅考虑路径的总距离#未对车辆数进行优化(为了在优化距离的同时降低车辆数#本文算法对基本蚁群算法的信息素叠加公式进行了改进#如式!*3"所示#使其能够完成双目标的优化()+6P!#2G !*8>6=!G ",3!/"#!!6#P "%5!G "%]#!其他({!*3"!!和式!*,"相比#式!*3"中增加了和车辆数相关的函数3!/"(3!/"如式!*+"所示(3!/"!*(N #[!]#T I D @W#D W’E =&T !/""*(N #[!]#T !/"&N #[!T D @B #D W’E =#T I D @W#D W’E =""#!*+"!第2期朱晓东#等’求解双目标450)6的改进混合蚁群算法77!式中’T!/"为第/只蚂蚁求得可行解的车辆数%T I D @W#D W’E =为当前迭代种群中的最小车辆数%T D @B #D W’E =为全局最小车辆数(3!/"可以根据当前解的车辆数对它的信息素浓度进行奖励或惩罚’若当前迭代种群中的最小车辆数大于全局最小车辆数#则对T !/"YT D @B #D W’E =的解进行惩罚%若当前迭代种群中最小车辆数小于全局最小车辆数#那么对T !/"YT I D @W#D W’E =的解进行惩罚#对T !/"CT I D @W#D W’E =的解进行奖励(由于蚁群算法中信息素叠加是一个正反馈过程#为了避免搜索停滞#笔者采用最大最小蚁群算法将信息素浓度限定于*+N #[#+N C (+#如式!*1"所示+6P!+N #[#+6P Y +N #[%+C (C =C #D #+6P C +N C (#{!*1"式中’+C (C =C #D 表示信息素的初始值(:D 43改进的局部优化算法笔者通过实验研究发现#在处理大规模节点和复杂约束的450)6问题时#基本蚁群算法构建的可行解中会产生客户数量比较少的线路#这将极大降低车辆的利用率#传统的局部优化算法对此类问题考虑不够(因此笔者提出了一种新的局部优化方法#将插入算法和,H C (=’K B &#(I ’结合#在优化距离同时降低车辆数#提高车辆的利用效率(算法步骤如下(/S M R5!将当前解分为节点数量不小于.的线路集合N A 和节点数量小于.的线路集合N E #如图2所示(图43路线分类示意图(I LG N M 43/X A M UOS I X P I OLN OU E\N EG S M X F OQ Q I \I X OS I EK/S M R6!使用,H C (=’K B &#(I ’和@K H C (=’K B &#(I ’对N A 进行局部优化\次(迭代初期\取较大值可以加速解的收敛#随着迭代进行#算法产生更优邻域解的难度逐渐加大#通过\取值逐渐减小来提升算法效率(在本文算法中#\初始值为3#每经过*]次迭代减小*(/S M R:!设4!6"为N E 中第4条线路上的第6个节点#初始化4!*#6!*(/S M R4!将4!6"插入到N A 中的所有节点之间(若4!6"插入N A 中第/条线路的第P 个节点后产生了可行解#根据式!*8"计算插入后的))W =H 46/P (式!*8"中#+W =H 为线路的总距离%4)/为插入前的线路%4(’S )/(’S 为插入后的线路(直到遍历N A 中所有线路上的所有节点#计算所有可行解的))W =H 46/P #跳转<=’F 3(若4!6"插入N A 的所有节点之间均无法产生可行解#则转到<=’F 7())W =H 46/P !+W =H !4"(+W =H !/"&+W =H !4(’S "&+W =H !/(’S "(!*8"!!/S M Rc !将4!6"与N A 中随机一个节点进行交换#要求交换后不改变解的可行性(然后重复<=’F 2(值得注意的是#每个节点优化时本步骤仅执行一次#若仍无可行解产生#则跳转至<=’F +(/S M R?!将4!6"插入到/)W =H 46/P 最大的位置(更新插入后的线路(/S M R8!令6!6(*#返回至<=’F 2#继续对下一个节点进行优化#直到线路4上所有节点完成优化(/S M R=!令4!4(*#转至<=’F ,#继续对下一条线路进行优化#直到N E 中所有线路完成优化(/S M R;!将N E 中剩余节点使用,H C (=’K B &#(I ’方法优化(:D c3改进算法整体过程改进算法整体流程图如图7所示(43实验与分析笔者将改进的蚁群算法在<@D @N @(**3+标准数据集上进行实验(<@D @N @(标准数据集有5*)5,)%*)%,)5%*)5%,共3类问题(这3类问题按节点分布方式可分为随机分布!5")聚集分布!%"和混合分布!5%"(其中5*)%*)5%*问题中节点的时间窗较窄#车辆载重较小%5,)%,)5%,问题中节点的时间窗较宽#车辆载重较大(<@D @N @(数据集场景多样具有代表性#因此其常被文献用于算法评估(4D 53参数设置笔者提出的改进混合蚁群算法中主要参数有式!*7"中启发因子’).和式!*3"中每只蚂蚁信息素总量8(为了分析这些参数对算法的影响#笔者在%*]*测试问题上进行实验(每组实验均进行7次#取结果的平均值(实验最大迭代次数6H N g 3]#信息素挥发速率"g ]‘]1(’).与结果的关系如图3所示(每只蚂蚁释放信息素总量8与结果的关系如图+所示(73!郑州大学学报!工学版",],]年图c3改进算法整体流程图(I LG N M c30A M EJM N OF F \F Eb X A ON S E\S A M I UR N EJM POF LEN I S AU图3!&"取值与总距离的关系(I LG N M ?30A M N M F OS I EK Q A I R>M S b M M KS A M JOF G M Q E\!’"OK PS A M S ES OF P I Q S OK X M 从图3可以看出#当*‘7z ’z ,‘7).g ,时#算法取得较好结果(从图+可以看出#3]z 8z *]]时#算法可以取得较好结果(4D 63首节点选择策略的有效性为了验证首节点选择策略的有效性#在标准数据集中%*]*测试问题上进行了相关实验(首先对式!*."中参数$的取值进行相关实验(若$过小#算法会过早收敛#陷入局部最优%若$较大#算法收敛速度慢#不能收敛于最优解(本实验中对每个$取值都进行7次实验#结果取平均值(实验结果如图1所示(图83%取值与总距离的关系(I LG N M 830A M N M F OS I EK Q A I R>M S b M M K %OK PS ES OF P I Q S OK XM图=3#取值与总距离关系(I LG N M =30A M N M F OS I EK Q A I R>M S b M M K #OK PS ES OF P I Q S OK X M从图1中可以看出#当]‘,z $z ]‘.时算法取得较好结果(在相同条件下将无首节点选择策略的算法和加入首节点选择策略的算法进行对照试验(两者都运行7次#结果取平均值#实验结果如图8所示(从图8中可以看出#虽然两者算法都收敛于最优解#但是加入首节点选择策略后算法的收敛速度明显变快#这也证明笔者提出的首节点选择策略可以提高算法的收敛速度(4D :3标准数据集测试为了说明本文算法具有适应性和有效性#笔者从标准数据集的每类问题中选取一个进行实验#将实验结果与基本蚁群算法和)’$N @>K C #(等*3+提出的混合蚁群算法)V &@E ’C K C 等**++提出的混合遗传算法进行比较(实验用A 9)L 9/,]*3#进行编程#在-(=’D %@K ’C 7H 7,]]%0;#2V /内存#!第2期朱晓东#等’求解双目标450)6的改进混合蚁群算法7+!图;3添加首节点选择策略和无首节点选择策略的比较(I LG N M;32EUR ON I Q EK Q E\OP P I K L\I N Q S K EP M Q M F M X S I EKR EF I X V OK PK Ed\I N Q S K EP M Q M F M X S I EKR EF I X V S C(?@S E1‘*操作系统的计算机上运行(实验参数蚂蚁数量2g*7#最大迭代次数6HNg3]#"g]‘]1#根据参数设置的实验结果取’g,).g,)8g1](本文算法在所选问题上运行.次取最优结果#实验结果如表*所示(其中总距离为X%#车辆数为T E(为了便于比较算法平均值之间的差异#设R L=表示本文结果的平均值#R L=9表示其他算法结果的平均值#/表示结果之间的差距百分比#按式!,]"计算(/!R L=&R L=9R L=_*]]‘(!,]" !!从表*中可以看出#在得出的*,个结果中#笔者提出的改进算法在总距离和车辆数上都明显优于基本混合蚁群算法%和文献中算法相比#本文算法+7k的结果取得了最优解#文献*3+算法表53/EF EUEK数据集测试结果0O>F M53/EF EUEKP OS O Q M S S M Q S N M Q G F S Q测试问题基本混合蚁群算法文献*3+算法文献**++算法本文改进算法X%T E X%T E X%T E X%T E%*],8.]‘8**1,1‘8*]1,1‘857=65D;57 5*],*+13‘**854;5D7*1*7**‘1*1*7]*‘*58 5%*]7*172‘+*8*3*+‘8*7*3**‘7*75?7?D:54 %,]*12*‘77c;5D c:c;5D c:c;5D c: 5,]**+7,‘.35654D6+*.7*‘24*,18‘24 5%,].*2]3‘81*]23‘.3*]3]‘]4574cD?7平均值*2,1‘+**‘.55:5D?8‘1**78‘,8‘]**2,‘31‘1 /a,7‘]k a,1‘.k*‘]k a**‘.k a*‘2k a*‘8k&&2*‘3k的结果取得最优解#文献**++算法2*‘3k 的结果取得最优解(从所有结果的平均值来看#与基本混合蚁群算法相比#本文算法在总距离上领先了,7‘]k#在车辆数上领先了,1‘.k%与文献*3+算法相比#本文算法在总距离上落后了*‘]k#但是在车辆数上领先了**‘.k%与文献**++算法相比#本文算法在总距离上领先了*‘2k#在车辆数上领先了*‘8k(此外本文算法在不同类型测试问题上均采用相同参数进行实验#这也说明了本文算法具有较强的适应能力(c3结论笔者通过分析传统混合蚁群算法在求解大规模带时间窗路径规划问题!450)6"中存在的不足#提出了一种改进的双目标混合蚁群算法(该算法有针对性地采用了首节点选择策略和改进状态转移公式来加速收敛过程%考虑到路径距离与车辆数量两个优化目标#在信息素叠加过程增加了车辆数惩罚#同时改进了全局信息素更新策略(本文改进算法有效地提高了车辆利用率#扩大了搜索空间#能够在双目标下给出较优解(通过在<@D@N@(标准数据集上的实验#验证了笔者所提算法的有效性(参考文献!**+!Q9U)_-VV/#59A<Z5J R^)&’=K>B X?C E F#=B&C(I FK@WD’N*J+^A#(#I’N’(=E B C’(B’#*878#3!*"’1]a8*^*,+!A M R9A A Z Q A9#V9U-A"9#R9A Z Q5-#’=#D^<@D P C(I P’&C B D’K@>=C(I FK@WD’N W$>E C(IC N FK@P’?I’(’=C B#D I@K C=&N G@K@F=C N#DE@D>=C@(*J+^J@>K(#D@G B@N F>=#=C@(#D E B C’(B’#,]*+#,*’,77a,3,^ *.+!Q ZM L-4Z-59Q9%M<)905#A9;%Z5-<#%95H 5M L L0#’=#D^9I’(’=C B#D I@K C=&N G@K#I K’’(P’&C B D’K@>=C(I FK@WD’N*J+^Z D’B=K@(C B(@=’E C(?C E B K’=’N#=&’HN#=C B E#,]*1#32’37a+2^*2+!汪慎文#杨锋#徐亮#等^离散差分进化算法求解共享单车调度问题*J+^郑州大学学报!工学版"#,]*8#2]!2"’21a7.^*7+!崔岩#张子祥#时新#等^考虑顾客时间紧迫度的生71!郑州大学学报!工学版",],]年鲜电商配送路径优化问题*J+^郑州大学学报!工学版"#,]*+#.1!3"’78a3.^*3+!)Z b A M;5-9UZ#"9b49U T954#"M A9"-VA#’= #D^Z(&#(B’?C(=’D D C I’(=S#=’K?K@FE#(?B>B X@@E’#K B&#D I@K C=&N EG@KE@D P C(I=&’B#F#B C=#=’?P’&C B D’K@>=C(IFK@WD’N*J+^-(G@K N#=C@(E B C’(B’E#,]*3#..2’.72a.+1^*++!Q M5-V MA#A9U-Z__M4#%M L M5U-9^9(=E$E=’N’@F=C N C O#=C@(W$#B@D@($@GB@@F’K#=C(I#I’(=E*J+^-Z Z Z=K#(E#B=C@(E@(E$E=’N E#N#(#(?B$W’K(’=C B E#F#K=/!B$W’K(’=C B E"#*883#,3!*"’,8a2*^*1+!b;/#b9U V__#b9M/_^9&$WK C?#D I@K C=&NG@K P’H &C B D’K@>=C(IFK@WD’N S C=&=C N’S C(?@S E*J+^Z[F’K=E$E=’N E S C=&#FFD C B#=C@(E#,]**#.1!*"’2.7a22*^*8+!Q-U V:L#R;e0#<;U LJ#’=#D^9(C N FK@P’?#(= B@D@($@F=C N C O#=C@(#(?C=E#FFD C B#=C@(=@P’&C B D’K@>=C(I FK@WD’N S C=&=C N’S C(?@S E*J+^U’>K@B@N F>=C(I#,]*,#81’*]*a*]+^**]+朱杰#张培斯#张询影#等^基于改进蚁群算法的多时间窗车辆路径问题*J+^计算机技术与发展#,]*8#,8!*"’*],a*]7^***+刘云#张惠珍^多目标带时间窗的车辆路径问题的单亲遗传混合蚁群算法*J+^公路交通科技#,]*3#..!3"’87a*]]#*]3^**,+柴获#何瑞春#苏江省#等^求解双目标带时间窗车辆路径问题的蚁群算法*J+^交通运输系统工程与信息#,]*1#*1!2"’*73a*3,^**.+孙小军#介科伟^求解带时间窗动态车辆路径问题的改进蚁群算法*J+^大连理工大学学报#,]*1#71!7"’7.8a723^**2+葛斌#韩江洪#魏臻#等^求解带时间窗车辆路径问题的动态混合蚁群优化算法*J+^模式识别与人工智能#,]*7#,1!+"’32*a37]^**7+%L95"ZV#65-V R)J6^<B&’?>D C(I@G P’&C B D’E G K@N #B’(=K#D?’F@==@#(>N W’K@G?’D C P’K$F@C(=E*J+^M F’K#=C@(E K’E’#K B&#*832#*,!2"’731a71*^**3+<M L M A M UA A^9D I@K C=&N E G@K=&’P’&C B D’K@>=C(I#(?E B&’?>D C(I FK@WD’N E S C=&=C N’S C(?@SB@(E=K#C(=E*J+^M F’K#=C@(E K’E’#K B&#*81+#.7!,"’,72a,37^**++V R M<Z-5-"#V R9U U9Q0M;5<T^A>D=C H@WY’B=C P’P’&C B D’K@>=C(IFK@WD’N S C=&=C N’S C(?@S E>E C(II@#DFK@I K#N N C(I#(?I’(’=C B#D I@K C=&N*J+^9FFD C’?E@G=B@N F>=C(I#,]*]#*]!2"’*]83a**]+^&K-U R N EJM P*V>N I P&K S2EF EK V&F LEN I S A U\EN W I d E>[M X S I JM.$B0T_R;e C#@?@(I#69U VQ C(I!<B&@@D@G Z D’B=K C B#D Z(I C(’’K C(I#_&’(I O&@>;(C P’K E C=$#_&’(I O&@>27]]]*#%&C(#"&>Q S N OX S’-(@K?’K=@E@D P’=&’FK@WD’N E@G W#E C B&$WK C?#(=B@D@($#D I@K C=&N C(E@D P C(I D#K I’H E B#D’450)6# #(C N FK@P’?WC H@WY’B=C P’&$WK C?#(=B@D@($#D I@K C=&N S#E FK@F@E’?^T C K E=D$#=&’F’K C F&’K#D E’D’B=C@(E=K#=’I$ S#E>E’?=@C N FK@P’=&’E’D’B=C@(’G G C B C’(B$##(?#G C K E=(@?’E’D’B=C@(E=K#=’I$S#E FK@F@E’?=@#B B’D’K#=’=&’B@(P’K I’(B’@G=&’#D I@K C=&N^<’B@(?D$##F’(#D=$G>(B=C@(K’D#=’?=@=&’(>N W’K@G P’&C B D’E S#E#??’?=@=&’F&’K@N@(’E>F’K F@E C=C@(G@K N>D#=@@F=C N C O’=&’(>N W’K@G P’&C B D’E S&C D’@F=C N C O C(I=&’?C E=#(B’^T C(#D D$## (’SD@B#D@F=C N C O#=C@(#D I@K C=&NS#E FK@F@E’?=@C N FK@P’P’&C B D’>=C D C O#=C@(#(?’[F#(?=&’(’C I&W@K&@@?E@D>H =C@(W$C(E’K=C(I(@?’E C(K@>=’E S C=&G’S’K(@?’E C(=@@=&’K K@>=’E^Z[F’K C N’(=E#(?B@N F#K C E@(E@(<@D@N@( W’(B&N#K X FK@WD’N E E&@S’?=&#==&’C N FK@P’?#D I@K C=&N&#?=&’#?P#(=#I’E@G E=K@(I E’#K B&#WC D C=$#G#E=B@(H P’K I’(B’E F’’?#(?E=K@(I K@W>E=(’E E^]M V b EN P Q’#(=B@D@($#D I@K C=&N%P’&C B D’K@>=C(I FK@WD’N%=C N’S C(?@S%WC H@WY’B=C P’。

湖州师范学院————————————————商学院毕业附属过程管理材料（20XX届）专业物流管理学号11012645学生姓名屠娟湖州师范学院教务处印制目录1.湖州师范学院本科生毕业诚信承诺书2.湖州师范学院本科毕业开题报告3.文献综述4.湖州师范学院本科毕业指导教师审阅表5.湖州师范学院本科毕业评阅人评阅表6.湖州师范学院本科毕业答辩记录表7.湖州师范学院本科毕业评分表湖州师范学院本科生毕业诚信承诺书湖州师范学院毕业开题报告文献综述11012645 屠娟摘要：物流配送已经成为企业经营发展的关键环节，而合理的配送路径优化能够有效利用现有资源进行车辆调度，从而缩减成本，实现利润最大化。

本综述评述了物流配送路径优化的基本概况，从货物、客户的相关属性等方面指出了目前配送路径优化的实施难点，并对物流配送路线优化问题的分类以及配送路径优化问题的解决算法即精确算法、传统启发式算法和现代启发式算法的现有文献进行总结分析，以期对未来路径优化问题的解决提供帮助。

关键词：VRP问题;路径优化问题;物流配送前言随着企业的发展，作为第三利润源的物流的重要性便越发突出。

而在企业经营中，物流配送能力的高低已成为体现企业竞争力的一大方面，配送中心的配送决定了物流配送效率,而配送效率的高低是衡量企业盈利能力的重要指标。

为了实现高效率的配送，就需要根据企业配送模式进行配送路线优化,实现配送资源的充分利用。

通过对配送路径的优化，能够使货物在客户规定的时间内高效送达，实现对企业资源利用的最大化，提高客户的满意度，提升企业服务质量，从而达到降低配送成本，提升企业的潜在效益的目的。

目前对于物流配送路径优化有许多研究，本文拟对物流配送路径优化基本概况及问题的解决算法进行了解与综述，为物流配送路径优化问题的解决提供相应建议。

主题一、物流配送路径优化基本概况随着中国经济的愈加繁荣，物流配送业也得到了快速发展。

但在物流配送环节中，仍存在许多优化问题有待解决。

国外将物流配送车辆优化调度问题归结为VRP问题和VSP问题（Vehicle Scheduling Problem）。

VRP问题首次于1959年被Dantzig和Ramser提出，并很快引起运筹学、组合数学、应用数学、网络分析与图论、计算机应用、物流科学等学科的专家以及配送计划的制定者和管理者的极大的重视，从而成为运筹学与组合优化领域的前沿与研究热点。

近年来，许多学者都利用蚁群算法对各种VRP 问题进行了大量的研究，并设计了各种类型的蚁群算法，由此形成了一些可行的解决方案。

物流配送车辆优化调度，是物流配送优化中关键的一环。

随着物流配送向集约化、一体化的方向发展，常对配送的各环节进行综合考虑，主要是配送车辆的集货、配货及送货过程[5]。

VRP问题根据不同的标准可分为不同的类别。

根据物流配送中心的数目，可分为单物流配送中心问题(配送系统中仅有一个物流中心）和多物流配送中心问题（配送系统中存在多个物流中心）；根据运输车辆的种类多少，分为单车型问题（配送车辆的载重量完全相同）和多车型问题（所有配送车辆的载重量不完全相同）；根据车辆对车场的所属关系分，有车辆开放问题（车辆在完成配送任务后可以不返回其发出的车场）和车辆封闭问题（即车辆在完成配送任务后必须返回其发出的车场）；根据车辆是否有容量约束分，有容量约束的VRP问题和无容量约束的VRP问题（即TSP问题）；根据货运任务的性质分，有纯送货问题（仅考虑从物流配送中心向用户送货，也称为纯卸问题）或纯取货问题（仅考虑把各用户供应的货物取到物流中心，也称为纯装问题）以及取送混合问题（既考虑将用户需求的货物从物流配送中心送达到各个用户，同时也考虑将各用户供应的货物从用户取到物流配送中心，也称为装卸混合问题或集货、送货一体化问题）；根据优化的目标数分，有单目标问题（仅考虑一个目标约束）和多目标问题（同时考虑多个目标约束）；根据货运任务的完成是否有时间约束，又可分为有时间窗约束的VRP问题（VRPTW）和无时间窗约束的VRP问题；根据货运任务时间窗约束的强度，又可将VRPTW问题划分为硬时间窗约束的VRP问题（VRPHTW，Vehicle Routing Problem with Hard Time Windows，用户要求货物必须在规定的时间窗内送达或取走，但是不能提前也不能拖后）和软时间窗约束的VRP问题（VRPSTW，Vehicle Routing Problem with Soft Time Windows，用户要求将货物尽量在规定的时间窗内送达或取走，可以提前或拖后，但在提前或拖后时，要对配送企业实施一定的惩罚）。

改进蚁群算法的送餐机器人路径规划
蔡军;钟志远
【期刊名称】《智能系统学报》
【年(卷),期】2024(19)2
【摘要】蚁群算法拥有良好的全局性、自组织性、鲁棒性,但传统蚁群算法存在许多不足之处。

为此,针对算法在路径规划问题中的缺陷,在传统蚁群算法的状态转移公式中,引入目标点距离因素和引导素,加快算法收敛性和改善局部最优缺陷。

在带时间窗的车辆路径问题(vehicle routing problem with time windows,VRPTW)上,融合蚁群算法和遗传算法,并将顾客时间窗宽度以及机器人等待时间加入蚁群算法状态转移公式中,以及将蚁群算法的解作为遗传算法的初始种群,提高遗传算法的初始解质量,然后进行编码,设置违反时间窗约束和载重量的惩罚函数和适应度函数,在传统遗传算法的交叉、变异操作后加入了破坏-修复基因的操作来优化每一代新解的质量,在Solomon Benchmark算例上进行仿真,对比算法改进前后的最优解,验证算法可行性。

最后在餐厅送餐问题中把带有障碍物的仿真环境路径规划问题和VRPTW问题结合,使用改进后的算法解决餐厅环境下送餐机器人对顾客服务配送问题。

【总页数】11页(P370-380)
【作者】蔡军;钟志远
【作者单位】重庆邮电大学自动化学院
【正文语种】中文
【中图分类】TP273
【相关文献】
1.列车用送餐机器人路径规划研究及软件设计
2.基于局域降维Dijkstra算法的校园送餐机器人多目标路径规划
3.基于改进蚁群算法的移动机器人路径规划
4.基于多策略改进蚁群算法的机器人路径规划
因版权原因，仅展示原文概要，查看原文内容请购买。