多蚁群协同进化的滑行道调度优化

蚁群算法的基本原理蚁群算法 (Ant Colony Optimization, ACO) 是一种基于群体智能的优化算法，模拟了蚂蚁在寻找食物时候的行为，被广泛应用于求解组合优化问题、路径规划等领域。

蚁群算法的基本思路蚁群算法的基本思路是通过模拟蚂蚁在寻找食物的过程中释放信息素来获取全局最优解。

具体过程如下：1.初始化信息素: 首先，需要在所有可行解的路径上放置一些信息素。

在开始时，信息素值可以选择为等量的值或一些默认值。

2.蚁群搜索: 一开始，所有的蚂蚁都分别随机选择一个节点作为起点，并开始在网络中搜索。

蚂蚁行动的过程中，会根据路径上信息素浓度的大小来选择下一步的方向。

同时，每只蚂蚁都会记录其所经过的路径和信息素值。

3.信息素更新: 每只蚂蚁到达终点之后，计算其所经过路径的费用，然后根据一定的规则更新路径上的信息素。

较优的路径上将会添加更多的信息素，使下一次蚂蚁选择该路径的概率更大。

4.重复搜索: 重复上面的步骤，直到满足一个停止条件为止。

一种常见的停止条件是达到预定的迭代次数。

蚁群算法的优势蚁群算法在解决组合优化问题时，具有以下的优势：1.全局优化能力极强: 因为每只蚂蚁都只关注自己所经过的路径上的信息素值，所以可以同时搜索并更新多个路径，从而有可能找到全局最优解。

2.能够避免陷入局部最优: 蚁群算法可以通过信息素的挥发、说长存、信息素值的启发式更新等手段来避免陷入局部最优解。

3.易于扩展和并行化: 蚁群算法通常是一种并行的算法，可以很轻松地应用于分布式计算环境中。

蚁群算法的应用蚁群算法在解决组合优化问题、路径规划、调度等方面有着广泛的应用，如下所示：1.旅行商问题: 蚁群算法可以用于解决旅行商问题。

2.线性规划问题: 蚁群算法可以用于求解线性规划问题。

3.路径规划问题: 蚁群算法可以用于车辆路径规划问题。

4.调度问题: 蚁群算法可以用于作业车间调度问题。

蚁群算法是一种基于群体智能的优化算法，模拟了蚂蚁在寻找食物时候的行为。

目录第一章第一章绪论 (3)1.1研究背景 (3)1.2 本文研究目的和意义 (4)1.2.1本文研究目的 (4)1.2.2本文研究的意义 (5)1.3本论文的主要工作 (6)第二章路径优化研究现状与分析 (7)2.1研究现状 (7)2.2研究方法 (8)第三章各种智能优化算法介绍 (8)3.1 智能优化算法 (8)3.1.1禁忌搜索算法 (9)3.1.2 模拟退火算法 (9)3.1.3遗传算法 (10)3.1.4 粒子群优化算法 (10)3.1.5 神经网络算法 (11)第四章基于蚁群算法—系统开发基本思想 (11)4.1物流配送的问题描述 (11)4.2数学模型的建立 (12)4.3约束条件 (13)4.4优化目标 (13)4.5优化配送路线的蚁群算法 (14)4.5.1基本思想 (14)4.5.2 算法实现 (14)4.6TSP问题概述 (16)4.7基于蚁群算法求解旅行商问题（TSP）的基本流程 (16)4.8 VRP相关问题论述 (19)第五章蚁群算法的改进 (20)5.1问题描述 (20)5.2最大最小蚁群算法 (20)5.3蚁群算法的其他改进策略 (22)第六章软件实现 (25)6.1 功能要求 (25)6.2总体设计 (25)6.3 软件架构 (26)6.4 测试文档 (26)第七章总结语 (27)参考文献 (29)摘要：本文所要探讨的物流配送路径优化问题，是基于改进蚁群算法的物流最优路径选择系统，算法实际上是正反馈原理和启发式算法相结合的一种算法。

该软件采用C++语言编写，用Qt做界面，可在Win7下运行。

在选择路径时，蚂蚁利用了路径上的信息素，不断叠加，最终产生最优路径。

本系统提供给合乎用户需求的优化路径策略，如路径最短、时间最短等进行配送路线规划方案。

结合网上已有资源及多次实验计算，从而证明合理的使用蚁群算法进行路径线路，能够高效、快速的得到问题的最优解或接近最优解。

关键词：基本蚁群算法；最大最小蚁群算法；物流配送；蚁群系统；路径优化；第一章绪论1.1研究背景在美国，物流产业链被人们形象地比作“尚未开发的价值400亿美元的金矿"。

基于改进蚁群算法的智慧物流调度规划①叶杭璐, 何利力(浙江理工大学 信息学院, 杭州 310018)通讯作者: 叶杭璐摘　要: 随着物流业的大力发展, 通过发展智慧仓储物流, 可以极大降低物流成本, 加快产业的发展. 本文提出了一种在智慧仓储中的AGV 车辆系统避碰路径规划, 首先利用带时间窗的栅格方法模拟了AGV 的制造车间工作环境, 提出一种改进蚁群算法, 通过改进概率转换公式和信息素更新规则, 最后仿真结果验证了该算法可以解决多个AGV 的避障路径规划问题, 进而实现智慧仓储物流.关键词: 智慧仓储物流; AGV; 时间窗建模; 改进蚁群算法; 避障路径规划引用格式: 叶杭璐,何利力.基于改进蚁群算法的智慧物流调度规划.计算机系统应用,2021,30(1):207–213. /1003-3254/7802.htmlIntelligent Logistics Distribution Route Planning Based on Improved Ant Colony AlgorithmYE Hang-Lu, HE Li-Li(School of Information Science and Technology, Zhejiang Sci-Tech University, Hangzhou 310018, China)Abstract : With the vigorous development of the logistics industry, the development of smart warehousing logistics can greatly reduce logistics costs and accelerate the development of the industry. This study proposes an AGV vehicle system collision avoidance path planning in smart storage. First, the grid method with time windows is used to simulate the working environment of the AGV’s manufacturing workshop, and an improved ant colony algorithm is proposed. By improving the probability conversion formula and the pheromone update rule, the simulation results verify that the algorithm can solve the obstacle avoidance path planning problem of multiple AGVs, and then realize the intelligent warehouse logistics.Key words : intelligent warehouse logistics; AGV; time window modeling; improved ant colony algorithm; collision avoidance path planning目前, 我国物流业发展的特点之一是智慧物流进入创新爆发时期, “互联网+智慧仓储”等创新模式迅速发展. 人工智能技术已经融入到了物流行业的生产仓储环境中, 智慧仓储物流设备的使用大大节省了人力资源, 充分发挥机器换人、货物找人、可视管理的运行理念, 遵循依托物联网与智能算法, 进行物流仓储的全流程自动控制的核心思想, 通过生产物流的信息化、快速、高效、可追溯性, 实现真正智能化. 智慧仓储物流通过依托物联网与智能算法, 进行全流程自动控制, 实时、有效地管理物流, 提供更具社会价值的物流效应[1]. 中国作为生产大国, 智慧物流为大势所趋.智慧物流调度设计的关键是要满足系统订单货物运送的要求, 满足客户、AGV 和云技术之间动态协作的需求以及满足物流仓储的实际操作需求. 高效率和一致性是智慧物流调度系统的关键. 在智慧仓储中, 货物被放在可以移动的货架上, 用来进行货物运送工作计算机系统应用 ISSN 1003-3254, CODEN CSAOBNE-mail: Computer Systems & Applications,2021,30(1):207−213 [doi: 10.15888/ki.csa.007802] ©中国科学院软件研究所版权所有.Tel: +86-10-62661041① 基金项目: 国家重点研发计划(2018YFB1700702)Foundation item: National Key Research and Development Program of China (2018YFB1700702)收稿时间: 2020-06-06; 修改时间: 2020-07-31, 2020-08-10; 采用时间: 2020-08-13; csa 在线出版时间: 2020-12-31207的自动引导车(Automated Guided Vehicle, AGV)是一种先进的自动化物流设备, 具有自动化程度高, 生产线灵活的特点. 当接收到需要处理的命令时, 控制系统对AGV发送指令, AGV执行具体的指令, 完成物料货架的搬运工作, 等货架上的物品被取下后, 然后再将货架再送回至指定位置[2].本文通过对概率转换公式的改进和更新信息素,提出一种改进的蚁群算法, 规划AGV的运行路线. 在规划最佳路径的同时, 需要考虑AGV互相之间的碰撞或与货架碰撞的情况. 通过时间窗模型, 为优化路径规划的模型和算法提供了有效的方法. 最后在基于理论的基础上, 结合仓储物流的实际运行环境, 建立栅格地图, 通过模拟仿真实验, 表明该算法可以快速、准确地获得最优解.1 建立AGV的工作环境模型在智慧仓储的制造车间内, 从AGV的起始移动位置到指定货物对应的货架位置, 需要获取一条优化的路径来引导AGV的运动[3]. 首先根据AGV的工作环境建立模型, 通过模型的建立把车间内AGV的工作环境转化为机器能够识别的信息. 在制造车间内, 由于货物数量庞大, 货架布局时会尽量工整、对称, 为AGV 的行驶设计出便于通行的过道. 因此在制造车间内, 只考虑静态障碍物的情况下, 所有障碍物的数量及规模都是有限的且已知的[4].1.1 栅格法栅格法建立模型时将需要建模的空间环境视为一个平面, 然后将平面分割成一个个栅格, 存储了环境信息. 栅格类型可分为两种类型: 阴影部分表示障碍栅格(由1表示), AGV禁止通行的区域; 白色部分表示自由栅格(由0表示), AGV可以通行的区域[5]. AGV只能在自由栅格中移动, 单位栅格的大小必须完全包含AGV[6].为了避免碰撞, 在规定障碍物栅格时应该适当的预留出一定的安全空间. 本文使用栅格法[7]将制造车间划分为由m×n个大小相同的栅格方块组成的二维空间.路径规划的目标是寻找包含开始网格、结束网格和有序网格子集的网格集, 并在遇到障碍物网格时避开它们[8]. AGV实时上报位置信息, 在这些栅格化的环境中,将通过相应的算法检索路线, 遍历整个栅格地图并记录整个路线[9]. 本文栅格环境的编号是从左到右、由下往上的, 如图1所示, 为模拟车间的10×10的栅格图模型.图1 环境栅格模型图按行驶方向, 图1中AGV1在节点32, 则它下一步到达的节点为33, AGV2在节点55, 则它下一步到达的节点为45.1.2 时间窗模型AGV从进入节点到离开节点所形成的时间周期称为时间窗, 每个时间窗口的时间段只能通过当前AGV, 其他AGV不允许通过当前AGV停留时间窗内的节点[10]. 在对多个AGV进行路径规划时, 为了避免出现冲突和死锁现象, 每个节点在任务开始到任务结束期内, 通过节点的AGV小车将时间划分为不同的预留时间段, 每个节点预留时间段中间的空闲时间间隔可以用来规划其他A G V的行驶路径, 此时其他AGV可以通过该节点.r k nf k nr133r134r135r136r137r145r235r125r115AGV通过每个网格的时间可以通过各种传感器收集, 并且可以分为保留时间和空闲时间. 如图2引入变量: 保留时间是在第n个节点占用的第k个时间窗;空闲时间是在第n个节点占用的第k个空闲时间窗[11].通过空闲时间窗口来计划避障, 根据图1的两个AGV 的行驶方向, 规划路径: AGV1的路径信息位节点32、33、34、35、36, 最终到达目标节点37, 相应节点的保留时间窗为、、、、; AGV2从起始节点55出发, 经过节点45、35、25, 到达目标节点15, 相应节点的保留时间窗为、、、. 两个AGV的时间窗口模型的示意图如图2所示.当出现选择路径冲突时, AGV行进的优先级先后顺序根据3个方面来制定: (1)装有行李架的AGV 的优先级高于未装有行李架的; (2)任务完成设定的时计算机系统应用2021 年 第 30 卷 第 1 期208间早的AGV优于任务完成时间迟的; (3)当出现两个AGV朝同一目标节点移动的情况, 后一个AGV根据等待策略重新规划[12].图2 时间窗模型图2 基于蚁群算法的路径规划在智慧仓储物流中的路径调度规划需要解决3方面问题: (1) AGV与障碍物碰撞问题; (2)实现任务完成的时间最小化和货物运送效率最大化的目标; (3)传统的蚁群算法不能直接用于解决有障碍的最短路径问题.因此, 应改进蚁群算法的实用性来解决障碍问题, 这也解决了理论上的困境问题.2.1 基本蚁群算法蚁群算法是以类比蚁群现实生活中寻找食物的行为为灵感. 蚂蚁在觅食的过程中随机行走, 并在沿途铺设名为信息素的化学痕迹. 信息网将信息发送给其他成员, 其他蚂蚁则很可能沿着铺有信息素的路径行走, 而不是随意走动. 这一观察结果启发了意大利学者Dorigo等人, 提出了一种智能多主体系统的启发式算法, 鲁棒性更强, 速度更快, 分布式计算和良好的可扩展性[13], 并且具有实现全局最优解的概率更高.在蚁群算法中, 蚂蚁运动的过程可用图3表示. 蚁巢(起点)和食物(终点)之间往往有多条路径, 可用{e1}、{e2、e3}集合表示. 在蚂蚁觅食寻路的过程中,信息素残留量会开始蒸发, 因此减少对蚂蚁的吸引力.路径越长, 信息素蒸发量越多.因此最短路径上的信息素强度增加到与蒸发速率相平衡的水平, 导致较短路径上的信息素数量比较长路径上的信息素增量更快.在自动催化过程中通过信息素的积累, 当蚂蚁面对交叉点时, 信息素量越大的路径更易优先被选择.完整的蚂蚁的寻路过程包括两部分: 路径选择和信息素释放.图3 蚂蚁寻路模型图p ki j(t)表示在t时刻, 蚂蚁k位于栅格i时, 选择下一栅格j的概率, 表达式如式(1)所示:allow kαβτi j(i,j)d i jηi jηi j d i j其中, 表示蚂蚁k当前可以选择到达的节点的集合; 表示信息启发因子, 用来表示蚂蚁在行路过程中积累的信息量产生的作用大小[14], 表示期望启发因子, 值越大, 表示启发信息在蚂蚁运动方向的选择中越受重视[15], 表示t周期时路段上的联系信息素,表示城市i与j之间的距离, 表示启发函数, 和的关系如式(2)所示:蚂蚁在每次觅食中信息素的量主要由两个因素组成: 蒸发的信息素和新添加的信息素. 经过一段时间n后, 蚂蚁完成一个周期, 会更新并更改通过路径上的信息素数量, t+n时刻在路径(i,j)上信息素更新规则为:ρρ∈(0,1) 1−ρ∆τi j(t,t+n)(t,t+n) (i,j)∆τi j(0)=c∆τki j(t,t+n)(t,t+n)其中, 是信息素蒸发的速率, 且取值范围为,为信息素残差因子, 是在时间段内路径增加的信息素的量, 在循环开始时,. 是由蚂蚁k在增加的信息素的量.2.2 改进蚁群算法智慧物流制造车间的空间环境属于静态空间, 改进的蚁群算法通过环境地图和目标节点的位置信息,通过优化概率转移公式来改变运动方向和信息素更新两个方面[16], 选择从起始节点到目标节点的最佳路径.在改进的算法中, 提高算法全局寻优能力和收敛性[17].2.2.1 优化概率转移规则蚁群算法在禁忌表的限制下, 前期迭代的过程中会产生大量交叉路径, 导致蚂蚁行进的过程中容易进2021 年 第 30 卷 第 1 期计算机系统应用209入一个凹形的障碍物区域, 出现无路可走的“死锁”状态时, 就成为路径死锁[18]. 蚂蚁进入死角时, 死锁状态的位置如图4所示.图4 死角示意图图4中, 蚂蚁运动到13节点时, 进入死角, 成为死锁状态. 在路径搜索过程中进入死角, 则死角的位置会被列在禁忌表中, 蚂蚁会返回到前一个位置, 然后搜索下一个位置. 本文通过建立死角表并引入惩罚函数[19]来解决这个问题. 当蚂蚁遇到死角时, 使用惩罚函数而不是更新规则, 惩罚函数为:惩罚函数使死角的周围边缘信息素减少, 指引蚂蚁在下一个迭代搜索的过程中忽略那些边缘, 解决了死锁问题, 加快找到运动方向路径.2.2.2 信息素更新优化v s l n S 为起点, E 为终点, n 是从S 到E (包括S 和E )所经过的路径上的网格数[20], m 为转弯处网格数, AGV 的速度保持恒定且转向模式是绕自己的中心旋转, 则用表示角速度. 网格的单位长度用. 基本蚁群算法的路径成本函数为:改进的路径成本函数为:∆τi j (t ,t +n )因此, 可以表示为:L k Q 表示信息素总量, 能在蚂蚁运动的过程中影响算法速度. 表示在此次任务中, 蚂蚁k 所经过的路径长度.2.2.3 算法步骤本算法选用蚁群算法对智慧仓储物流的车间的地图模型进行优化, 设AGV 的出发点为S , 目标货架为E 处, 算法的目的目的是绕开所有障碍物, 寻找一条从S 到E 的最短路径, 引导AGV 小车运作. 基于改进蚁群算法的路径规划的算法实现步骤如算法1.算法1. 基于改进蚁群算法的路径规划算法αβρ∆τi j (0)=c tabu k ∆τi j (0)=01) 初始化参数. 首先读取栅格地图的信息, 设置AGV 个数m , 最大迭代次数K , 信息素强度Q 以及、、, 初始化常数. 将蚂蚁放在起始位置S 处, 同时将此网格位置设置为禁忌表的第一个元素, 此时各边上的信息素相等, 则;2) 当蚂蚁k 选择了下一个网格时, 如果不是目标网格, 则蚂蚁根据式(1)选择概率最高的下一个空闲网络; 如果是目标网格, 则该蚂蚁将在循环中完成了此次无碰撞路径的任务.3) 根据式(4)和式(8)更新路由, 由式(7)计算在路线上消耗的最佳时间.4) 重复执行2)、3), 直到蚂蚁到达终点或者无处可去, 迭代结束.5) 根据式(3)更新信息素矩阵, 并且不考虑到达目的地的蚂蚁, 直到迭代结束.通过改进的蚁群算法, 结合时间窗网格法, 多AGV 的避障规划算法步骤如算法2.算法2. 多AGV 的避障规划算法1) 根据优先级对所有AGV 进行排序, 对优先级最高的AGV 进行最优路径搜索, 得了该AGV 所经过的所有网格都占据的时间窗, 然后初始化时间窗.2) 安排下一个优先级高的任务, 并搜索下一个AGV 的最佳路径, 同时获得该AGV 通过的网格的时间窗口, 并更新所有网格的时间窗口. 将网格进行比较, 以确定是否发生时间窗口冲突.tabu k 3) 如果2) 中存在冲突, 则根据优先级规则采用等待策略, 将在表(k = 1, 2, …, m )中放置冲突节点, 然后再次搜索路线. 如果2)中没有冲突, 则规划结束.基于改进蚁群算法的多AGV 的避障路径规划算法步骤流程图如图5所示.3 实验分析3.1 路径优化仿真实验已知某工厂生产车间的货物暂存区的平面设计图如图6所示.αβρ本文通过Matlab 仿真实验验证算法, 首先利用栅格法建立25×25仿真环境模型, 从左到右、从下到上对该环境进行编号, 蚂蚁数量m 、信息启发因子、期望启发式值、信息素的蒸发系数、信息素强度Q 、最大迭代次数K 的参数设置如表1所示.AGV 车从起始节点25, 到达目标节点510. 仿真结果如图7、图8所示.计算机系统应用2021 年 第 30 卷 第 1 期210图5 多AGV路径规划算法流程图机器人运行区单品种辅料暂存区空货架暂存区单品种辅料暂存区单品种辅料暂存区单品种辅料暂存区单品种辅料暂存区单品种辅料暂存区图6 某生产车间平面布置图表1 仿真实验系数设置表参数mαβρQ K 数值400150.37010ES 20 101020图7 基本蚁群算法路径规划图图8 基本蚁群算法收敛曲线采用改进的蚁群算法对路径优化进行仿真, 仿真结果如图9.ES20101020图9 基于改进蚁群算法路径规划图根据实验结果结果表明, 由图8基本蚁群算法收敛曲线可得经过73次迭代后, 达到最短路径40, 而根据图10可得改进蚁群算法可以经过60次迭代后, 达到最优路径长度为38. 因此改进的蚁群算法具有更好的性能, 能加快收敛速度, 更快地找到最优路径.3.2 多个AGV避障规划仿真实验避障路径规划的仿真实验设计了3个AGV, 设置优先顺序为AGV1 >AGV2>AGV3, 各AGV的起始节点和目标节点位置参数如表2所示.根据算法2中步骤1)规划AGV1和AGV2的行驶路径, 分别从S1和S2出发, 冲突未解决时, 仿真结果如图11所示.根据栅格地图和时间窗, 在节点94时存在冲突,则AGV2将采用等待策略, 它将在节点上等待1 s, 以便AGV1能够提前通过冲突, 路径规划后的仿真结果如图12所示.2021 年 第 30 卷 第 1 期计算机系统应用211图10 基于改进蚁群算法收敛曲线表2 多AGV 节点位置小车序号起始节点目标节点AGV122238AGV224415AGV351311E110201020AGV2AGV1E2S2S1图11 存在冲突的AGV 行驶路线E110201020AGV2AGV1E2S2S1图12 冲突解决后的AGV 行驶路线通过时间窗再次检测冲突, 由于没有冲突, 所以执行第二步, 根据AGV1和AGV2的路径规划, 更新所有节点的时间窗, 并搜索AGV3的最短路径. 当冲突未解决时, 仿真结果如图13所示.E110201020AGV3AGV2AGV1E2E3S2S3S1图13 存在冲突的多AGV 行驶路线tabu k 根据时间窗模型, 当AGV3到达节点238之后,与AGV1之间存在冲突, 因此再次搜索AGV3的最短路径, 并将节点238放置在AGV3的表中, 最后进行路径规划. 仿真结果如图14所示.E110201020AGV3AGV2AGV1E2E3S2S3S1图14 冲突解决后的多AGV 行驶路线通过对仿真结果的分析, 将改进的蚁群算法与时间窗模型相结合, 得到了较为理想的结果.将本方法应用于某大型制造企业的生产物流系统设计中, 在Flexsim 平台对该系统的入库环节进行物流仿真实验, AGV 的数量为12, 各AGV 的利用率如图15所示.本方法应用于实际系统中, 在多AGV 的路径规划计算机系统应用2021 年 第 30 卷 第 1 期212中, 能够合理规划各AGV的行驶路线, 进而提高系统整体运输任务的效率, 保证系统顺利运行.LoadingUnloadingIdle Travel empty Travel loaded Offset travel emptyAGV192.60%90.83%89.58%88.37%84.70%81.67%78.45%72.53%64.14%54.99%40.76%23.42%AGV2AGV3AGV4AGV5AGV6AGV7AGV8AGV9AGV10AGV11AGV12图15 入库环节各AGV的利用率4 结论与展望在智慧物流制造车间的环境下, 通过改进的蚁群算法结合带有时间窗的网格法根据环境的变化不断调整AGV的行驶轨迹. 本文以制造车间实际环境为模型, 建立仿真实验, 对单个AGV和多个AGV避障规划情况进行分析, 验证了该算法能有效避免在设备的碰撞问题. 本设计已经应用于某大型制造企业的生产物流的设计过程中, 不久将全面投入使用.随着人工智能的迅猛发展, 发展智能制造, 智慧仓储物流已是整个制造业必然的发展趋势. 以智慧物流为核心的科学管理的、信息丰富的、决策智能的物流运营模式会成为人类社会不断追求的生产生活方式.参考文献李远远. 智慧物流信息平台规划研究. 学术论坛, 2013,36(5): 140–143. [doi: 10.3969/j.issn.1004-4434.2013.05.032]1王永鼎, 杨家朋. RFID和AGV集成系统及其在配送中心的应用. 计算机系统应用, 2011, 20(11): 131–134. [doi: 10.3969/j.issn.1003-3254.2011.11.032]2Li YB, Soleimani H, Zohal M. An improved ant colonyoptimization algorithm for the multi-depot green vehiclerouting problem with multiple objectives. Journal of CleanerProduction, 2019, 227: 1161–1172. [doi: 10.1016/j.jclepro.2019.03.185]3李奕颖, 秦刚. 基于Spark的改进蚁群算法对带时间窗车辆路径问题的求解. 计算机系统应用, 2019, 28(7): 9–16.4葛伟宽, 王保平. 基于栅格图法的移动物流机器人全局路径规划方法. 科技通报, 2019, 35(11): 72–75, 80.5Chia SH, Su KL, Guo JH, et al. Ant colony system basedmobile robot path planning. Proceedings of the 2010 4thInternational Conference on Genetic and EvolutionaryComputing. Shenzhen, China. 2010. 210–213. [doi: 10.1109/ICGEC.2010.59]6赵江, 王晓博, 郝崇清, 等. 栅格图特征提取下的路径规划建模与应用. 计算机工程与应用, 2020, 56(10): 254–260.[doi: 10.3778/j.issn.1002-8331.1901-0232]7刘晓磊, 蒋林, 金祖飞, 等. 非结构化环境中基于栅格法环境建模的移动机器人路径规划. 机床与液压, 2016, 44(17):1–7. [doi: 10.3969/j.issn.1001-3881.2016.17.001]8柳长安, 鄢小虎, 刘春阳, 等. 基于改进蚁群算法的移动机器人动态路径规划方法. 电子学报, 2011, 39(5): 1220–1224.9侯玉梅, 贾震环, 田歆, 等. 带软时间窗整车物流配送路径优化研究. 系统工程学报, 2015, 30(2): 240–250.10何小锋, 马良. 带时间窗车辆路径问题的量子蚁群算法. 系统工程理论与实践, 2013, 33(5): 1255–1261. [doi: 10.3969/j.issn.1000-6788.2013.05.021]11Saidi-Mehrabad M, Dehnavi-Arani S, Evazabadian F, et al.An Ant Colony Algorithm (ACA) for solving the newintegrated model of job shop scheduling and conflict-freerouting of AGVs. Computers & Industrial Engineering, 2015,86: 2–13.12史恩秀, 陈敏敏, 李俊, 等. 基于蚁群算法的移动机器人全局路径规划方法研究. 农业机械学报, 2014, 45(6): 53–57.[doi: 10.6041/j.issn.1000-1298.2014.06.009]13张强, 陈兵奎, 刘小雍, 等. 基于改进势场蚁群算法的移动机器人最优路径规划. 农业机械学报, 2019, 50(5): 23–32,42. [doi: 10.6041/j.issn.1000-1298.2019.05.003]14熊瑜. 基于贪心策略的自适应蚁群算法在TSP中的应用.计算机与数字工程, 2012, 40(1): 37–39. [doi: 10.3969/j.issn.1672-9722.2012.01.014]15周显春, 杨婷婷, 刘小飞, 等. 基于改进蚁群算法的智能物流配送路径优化方法. 内蒙古师范大学学报(自然科学汉文版), 2017, 46(6): 888–892.16何雪海, 胡小兵, 赵吉东, 等. 基于自适应转移概率的蚁群优化算法. 计算机工程, 2010, 36(23): 165–167. [doi: 10.3969/j.issn.1000-3428.2010.23.054]17梁凯, 毛剑琳. 基于改进蚁群算法的移动机器人动态路径规划. 电子测量技术, 2020, 43(7): 56–60.18赵伟, 蔡兴盛, 曲慧雁. 一种基于惩罚函数和新信息素更新方式的蚁群算法. 计算机工程与科学, 2013, 35(3): 103–107. [doi: 10.3969/j.issn.1007-130X.2013.03.017]19裴振兵, 陈雪波. 改进蚁群算法及其在机器人避障中的应用. 智能系统学报, 2015, 10(1): 90–96.202021 年 第 30 卷 第 1 期计算机系统应用213。

基于蚁群优化的云任务调度策略的研究任金霞;刘敏【摘要】为了解决云任务调度过程中虚拟机资源使用不合理导致任务完成时间长的问题,提出一种基于蚁群优化的任务调度算法.采用集团资产管理模式管理虚拟机资源,同时确定云任务优先级,根据任务优先级与虚拟机的实时情况确立启发因子,增强算法的搜索能力;改进信息素更新规则,提高任务求解率;建立云任务调度过程模型.通过CloudSim模拟仿真器实验仿真,结果表明改进算法在任务平均完成时间上比ACO算法减少了,负载均衡值上降低了.%In order to settle the problem that as for the virtual resource unreasonable be used so that task time is long in the cloudlet scheduling,ant colony optimization task scheduling is proposed.Adopting the group assets government pattern to govern virtual resource,and ensuring the cloudlet priority,according to the cloudlet priority and virtual machine establish heuristic function to improve the algorithm's search capability;and improving the pheromone updating way to cloud task's solved rate;then building the cloudlet scheduling pattern.Finally,simulating by CloudSim shows that the task average time of the improved algorithm is reduced to ACO algorithm,and the load balancing value is decreased.【期刊名称】《贵州师范大学学报（自然科学版）》【年(卷),期】2017(035)003【总页数】5页(P77-81)【关键词】任务优先级;集团管理模式;任务平均完成时间;负载均衡值【作者】任金霞;刘敏【作者单位】江西理工大学电气工程与自动化学院,江西赣州341000;江西理工大学电气工程与自动化学院,江西赣州341000【正文语种】中文【中图分类】TP316云计算技术是20世纪伴随着互联网技术的发展而蓬勃发展起来的新兴技术，当前世界范围内许多公司企业在进行投资研究，并且在人们的日常生活中得到广泛使用。

基于改进蚁群算法的低碳车辆路径优化目录一、内容概览 (2)1.1 研究背景 (3)1.2 研究意义 (4)1.3 国内外研究现状 (5)1.4 研究内容与方法 (6)二、相关理论知识介绍 (7)2.1 蚁群算法概述 (8)2.2 改进蚁群算法 (10)2.3 低碳车辆路径优化问题描述 (11)2.4 数据预处理与特征提取方法 (12)三、系统设计与实现 (13)3.1 系统架构设计 (14)3.2 改进蚁群算法参数设置及调整 (15)3.3 系统实现流程 (17)3.4 系统测试与验证 (18)四、实验结果分析与讨论 (19)4.1 实验数据集介绍 (20)4.2 实验结果分析与比较 (20)4.3 结果讨论与结论 (21)五、总结与展望 (22)5.1 研究成果总结 (23)5.2 存在不足与改进方向 (24)5.3 进一步研究方向展望 (25)一、内容概览本论文《基于改进蚁群算法的低碳车辆路径优化》旨在针对当前低碳交通发展中的车辆路径优化问题，提出一种基于改进蚁群算法的解决方案。

随着全球气候变化和环境恶化，节能减排已成为交通运输领域的紧迫任务。

低碳车辆路径优化不仅有助于减少交通排放，还能提高能源利用效率，对促进绿色出行和可持续发展具有重要意义。

引入改进的蚁群系统（ACA）算法，通过引入信息素更新策略、局部搜索策略和动态权重系数，提高了算法的全局搜索能力和收敛速度。

结合低碳交通背景下的特殊需求，如车辆排放成本、新能源车辆优先等，设计了一种考虑多种约束条件的目标函数，使优化结果更符合实际应用场景。

通过仿真实验验证了改进算法的有效性和优越性，并与现有方法进行了对比分析，证明了所提方法在低碳车辆路径优化问题上的有效性和可行性。

本文的研究为低碳交通领域的车辆路径优化提供了新的思路和方法，有助于推动绿色出行的发展和低碳城市的建设。

1.1 研究背景随着全球经济的快速发展，交通运输行业在城市化进程中发挥着越来越重要的作用。

改进多目标蚁群算法在动态路径优化中的应用吴耕锐;郭三学;吴虎胜;薄鸟【摘要】为对城市动态车辆路径进行优化,设计一种具有贪婪转移准则的改进多目标蚁群算法.对蚂蚁执行多目标迭代局部搜索,在多个邻域上优化解或产生新的帕累托解.使用SUMO和NS2仿真软件,并用TraNS软件进行交互,对西安市区500组不同出发点和终点数据进行测试.结果表明,与两种传统优化算法相比,计算复杂度略有增加,但求解旅行时间明显缩短(平均少10％左右);与三种最新优化算法对比,在不同迭代次数和不同车辆数量条件下,虽然收敛速度不全都最快,但求解旅行时间均为最短(平均少5％左右).该算法能更好满足行车时间硬要求,规避交通拥堵,能较好应用于动态车辆路径优化问题.【期刊名称】《计算机应用与软件》【年(卷),期】2019(036)005【总页数】7页(P249-254,288)【关键词】蚁群算法;动态;路径优化;多目标;改进【作者】吴耕锐;郭三学;吴虎胜;薄鸟【作者单位】武警工程大学装备管理与保障学院陕西西安710086;武警警官学院信息通信系四川成都610213;武警工程大学装备管理与保障学院陕西西安710086;武警工程大学装备管理与保障学院陕西西安710086;武警警官学院基础部四川成都610213【正文语种】中文【中图分类】TP180 引言随着科技发展，城市交通向集成化、智能化、网络化不断发展，车辆、设备、网络形成了一个共同体，为研究车辆运输路径提供海量动态信息已然成为可能，动态路径优化问题成为了研究热点。

决策者应当将动态路径问题看成一个系统问题，包括数据信息采集、数据传输和路径优化计算等。

目前动态路径优化的研究较多。

如刘波等[1]结合冷链物流特点，建立了以配送总成本最小为优化目标的带时间窗冷链配送动态车辆路径优化模型，提出了一种自适应改进人工鱼群算法，利于节约企业资源和提高客户满意度。

李治等[2]提出了小波神经网络的速度预测模型，针对动态最优路径选择问题，确定了基于短时交通预测的动态路径求解算法。

改进蚁群算法在多AGV作业调度中的应用夏田;王娜【摘要】为实现AGV完成作业任务行驶距离最短,建立了路径调节解决冲突的模型.分析蚁群算法的突出缺陷后,应用改进蚁群算法完成对多AGV系统的优化调度.最后以某车间内物料搬运多AGV调度优化为实例,利用matlab软件针对蚁群算法和改进蚁群算法进行实验对比,验证了改进蚁群算法在多AGV调度优化中的有效性.【期刊名称】《物流技术》【年(卷),期】2015(034)012【总页数】4页(P87-89,115)【关键词】自动导引小车;蚁群算法;作业调度;调度优化【作者】夏田;王娜【作者单位】陕西科技大学机电工程学院,陕西西安710021;陕西科技大学机电工程学院,陕西西安710021【正文语种】中文【中图分类】TP18;TP278制造业生产过程中的物料搬运环节是整个生产中必不可少的一部分,因为它对各工位、各车间、各仓库间完成每项任务的物资流动有重要的影响。

因此,改善物料搬运的管理、提高物料存放过程中的自动化程度,不但可以提高作业效率和加快物料之间的流动，而且能够减小生产成本、缩短生产周期、提高经济效益。

集多方面优点的自动智能无人搬运小车AGV,逐渐发展为自动化生产系统中必不可少的运输工具。

采用蚁群算法对某发动机外装配车间内AGV完成作业进行优化调度。

蚁群算法的核心思想是，蚂蚁在选择路径时以前边蚂蚁留在路径上的信息素浓度大小做判断，路径选择概率与信息素浓度成正比。

某一路径走过的蚂蚁越多，则最优路径确定。

2.1 问题描述图1描述了某发动机外装配车间总体布局图，图中1、5是零件暂存区，2是实验区，3是装配线1,4是半成品库，5是装配线2。

其主要工作流程是，将零件从零件暂存区运送到装配线1上进行装配，装配完后运行到实验区进行测试，将测试合格的成品运送到装配生产线2上继续进行装配（不合格的成品由工作人员进行相关操作），然后把成品运送至半成品库中储存。

鉴于在装配车间多AGV调度较复杂，故作如下假设：（1）各AGV在运行期间速度一致。

协同进化算法
协同进化算法是一种新型的优化算法，它结合了遗传算法、粒子群算法和蚁群算法，将多种优化算法相结合，使用统一的框架对复杂的优化问题进行求解。

协同进化算法是一种基于种群的优化算法，它可以有效地解决复杂的优化问题，其目标是通过进化算法有效地改善搜索空间中的最优解。

它可以有效地改善搜索空间中的最优解，可以有效地降低优化问题的复杂度，并且可以有效地改善算法的收敛性能。

协同进化算法在许多应用中发挥了重要作用，如模式识别、机器学习、优化设计、经济学等。

它可以有效地解决多种复杂的优化问题，并且具有较强的鲁棒性和收敛性。

协同进化算法是一种新型的优化算法，它结合了多种优化算法，可以有效地解决复杂的优化问题，并且具有较强的鲁棒性和收敛性，可以有效地改善搜索空间中的最优解。

基于双层蚁群算法和轨迹优化的移动机器人导航算法
郝延春
【期刊名称】《计算机应用与软件》
【年(卷),期】2022(39)6
【摘要】针对蚁群算法在路径规划中存在收敛速度慢、易陷入局部最优的问题,提出一种双层蚁群优化算法(DL-ACO)。

提出一种并行蚁群优化方法,在复杂地图中生成初始无碰撞路径;采用拐点优化算法(TPOA),对初始路径的长度、转折点数进行优化。

为了便于拐角处移动机器人的跟踪控制,设计分段B样条路径平滑器,使拐角处更为平滑。

仿真实验表明,所提出的DL-ACO算法在路径长度、平滑度和算法稳定性上均优于其他几种算法;场景实验表明,DL-ACO算法能够有效应用于移动机器人的路径规划。

【总页数】7页(P239-245)
【作者】郝延春
【作者单位】吉林大学电子科学与工程学院;吉林铁道职业技术学院质量监控处【正文语种】中文
【中图分类】TP391.41
【相关文献】
1.基于智能蚁群算法的移动机器人轨迹规划
2.基于模糊蚁群算法的移动机器人轨迹规划研究
3.基于改进蚁群算法的移动机器人全局轨迹规划研究
4.基于改进免疫遗
传优化蚁群算法的移动机器人路径寻优研究5.改进蚁群算法在移动机器人轨迹规划中的应用研究
因版权原因，仅展示原文概要，查看原文内容请购买。

基于滑动窗口和蚁群优化算法的二次路径规划算法赖智铭;郭躬德【摘要】针对蚁群优化(ACO)算法在复杂环境下规划能力较弱的问题,提出了一种基于滑动窗口和蚁群优化算法的二次路径规划(QACO)算法.对回退蚁群优化(ACOFS)算法的回退策略进行改进,通过降低回退路径上的信息素量,减少回退次数.第一次规划中,使用改进后的ACO算法对栅格环境进行全局路径规划;第二次规划中,滑动窗口沿着全局路径滑动,通过ACO算法规划出滑动窗口中的局部路径,并使用局部路径对全局路径进行优化,直至滑动窗口中包含目标位置.仿真实验表明:相比ACO、ACOFS算法,QACO算法的平均规划时间分别下降了26.21％、52.03％,平均路径长度下降了47.82％、42.28％,因此在复杂环境下QACO算法具有将强的路径规划能力.【期刊名称】《计算机应用》【年(卷),期】2015(035)001【总页数】7页(P172-178)【关键词】滑动窗口;蚁群优化算法;二次路径规划;栅格法【作者】赖智铭;郭躬德【作者单位】福建师范大学数学与计算机科学学院,福州350007;福建师范大学网络安全与密码技术福建省重点实验室,福州350007;福建师范大学数学与计算机科学学院,福州350007;福建师范大学网络安全与密码技术福建省重点实验室,福州350007【正文语种】中文【中图分类】TP242.6;TP18蚁群优化(Ant Colony Optimization, ACO)算法是一种新颖的启发式进化算法，其算法基本思想受到了蚁群觅食过程的启发[1]。

生物学家经过大量的观察研究发现，蚂蚁个体在运动过程中会释放出一种具有挥发性和可叠加性的分泌物——信息素(pheromone)。

蚂蚁个体之间通过信息素来传递信息，信息素的浓度表征了路径对蚂蚁的吸引力，蚂蚁个体倾向于选择信息素浓度较高的路径。

一段时间内，经过同一路径的蚂蚁个体越多，这条路径上的信息素浓度就越大；反之，经过该路径的蚂蚁个体越少，信息素浓度就越低。