基于改进粒子群算法的AGV任务调度方法研究

关键词：AGV；任务调度；化肥物流；粒子群算法

中图分类号：F252；TP11 文献标识码：A

文章编号：1009-3044（2023）22-0034-06

0 引言

自动导引车（Automated Guided Vehicle，AGV）作为现代智慧物流中的重要工具，有力推动了传统企业向智能化、自动化方向转型和发展。目前，化肥农资产品以铁路运输为主，其运载环节采用传统的手工搬运和叉车搬运作业模式[1]。这种传统作业模式存在人力成本高、作业效率低下、自动化和智能化程度低等问题，难以满足当前化肥企业的需求。国内外学者对AGV 任务调度方法展开了大量研究。Zou等人[2]通过构建多目标混合整数线性规划模型并利用多目标进化算法求解多品种小批量生产制造车间取送货的任务调度问题；Hu等人[3]对自动集装箱码头的AGV调度和存储分配问题建立了混合整数规划模型并通过基于贪婪的多阶段分解方法进行求解；石楠路等人[4]构建了考虑AGV 换电过程的作业调度混合整数模型以减少等待时间，提高作业效率；霍凯歌等人[5]通过时间窗限制、负载均衡、现场实际情况等约束条件构建整数规划模型对生产运行总成本进行求解；颜骥等人[6]为解决多无人机多任务分配中的时序约束问题，扩展了分布式的一致性包算法；杨玮等人[7]以AGV执行任务的路径代价、时间代价以及任务均衡值代价为目标，建立多AGV仓储系统任务分配模型并提出了基于变邻域模拟退火的算法，提高了大规模任务下的求解精度和效率。尽管在各种应用场景中已有不少研究，但目前针对铁路化肥运载环节的相关研究尚在探索中。

因此，本文根据某化肥企业的实际需求，在化肥铁路物流运输的运载环节引入AGV来探索高效率的智能物流作业模式，分析化肥站台运载作业的特点，确定以运载任务工作量均衡为主要调度优化目标并构建出对应的数学模型，提出基于混合策略改进粒子群算法（Improved Particle Swarm Optimization，IPSO） 求解任务分配调度问题，以提高作业效率，推动企业智能化转型，增强企业竞争力。

1 问题建模

1.1 问题描述

1.2 模型构建

以某化肥企业站台堆区的运载环境为依据，通过栅格建模方法构建出化肥站台堆区的环境布局，规划示范点研究。该示范点的具体环境布局如图1所示，主要包括以下部分：1） 充电停靠区S：以S标记的栅格为AGV日常停靠和充电区域；2） 运载任务T：以T标记的栅格为待运载的化肥；3） 任务目的地G：以G标记的栅格为化肥运载目的地，即火车货厢；4） 站台堆区结构柱：以O标记的栅格为站台堆区的结构支撑柱，该结构柱位于运载任务T与运载目的地G之间且其不等间距分布；5） 行驶道路：站台堆区中的白色栅格为AGV的行驶道路。

根据上小节问题描述，结合化肥站台堆区的实际情况，不失一般性，做如下约束与假设：1） 火车进站时全部AGV可用并且停放在充电停靠区S 里；2） 任务的下达不受限制，即任一任务都可由任一AGV执行；3） 所有AGV同质，不考虑化肥被运载至货厢后的情况；4） 每一运载任务有且只能由一AGV执行，AGV可以执行多个运载任务，但每个AGV必须完成目前所执行的运载任务才能去执行下一运载任务；5） AGV每次从S 出发执行任务时电量充足且AGV在运行过程中无需充电；6） AGV执行任务过程不可中断，不允许出现任务中断或者任务变更的情况；7） 站台堆区上的化肥都已码垛整齐堆放在相对应的位置上并且每个位置上的化肥重量相同，不超过AGV的额定载重量；8） 站台堆区上的结构柱不会阻挡火车货厢厢门，影响运载任务，即所有货厢均能正常进行货物装载工作；9） 不考虑化肥被运载至货厢后的情况，即不考虑化肥在货厢内的卸载情况。

根据对站台堆区化肥运载问题的描述与分析，多AGV任务调度问题所定义的符号和变量如下所示：

1） 符号、集合和参数定义

其中，式（1）定义了目标函数，即求解最小总成本代价和最小化各AGV运载任务的工作量差距；式（2） 表示每次火车进站所有AGV的总运载任务代价成本；式（3）表示各AGV运载总重量均衡；式（4）表示AGV_k 运载任务自身成本代价和任务间的关联成本代价；式（5） 表示AGV将任务i 运载至相对应货厢h 的欧式距离；式（6）表示AGV执行完任务i 要去执行任务j 间的欧式距离；式（7）表示每次火车进站各AGV运载任务的总重量；式（8）表示每次火车进站AGV运载任务的平均重量；式（9）、（10）表示一个运载任务只能由一辆AGV 执行；式（11）表示全部运载任务都分配给到相对应的AGV执行。

2 基于混合策略的改进粒子群算法

站台堆区多AGV运载任务的分配问题是典型的NP-hard问题，难以利用传统的数学方法在短时间内得到问题的精确解。本文设计了一种改进粒子群算法，用来解决站台堆区多AGV任务分配问题，以便为各AGV合理分配运载任务，得到全局近似最优分配方案。

2.1 任务粒子的编解码设计

为建立粒子群算法与站台堆区多AGV任务分配问题的映射关系，本文设计了一种实数编码方案，粒子的每一位置代表着一种候选的任务分配方案，粒子位置的每维分量表示一个运载任务需求，通过求解最优粒子位置，可得到最佳任务分配方案。每一候选任务分配方案中包含两方面的信息，一个是任务对应的AGV序号，另一个则是任务执行的顺序。粒子编码如式（12）所示。

2.2 基于Circle 混沌反向学习的种群初始化策略

初始种群的优劣在一定程度上影响着任务分配方案的质量，传统的种群初始化方法容易导致后期种群多样性丧失，陷入局部最优。为保证初始种群的多样性，增强算法寻优能力，尽可能得到全局最优解，本文提出了基于混沌反向学习的种群初始化方法，先利用混沌模型生成初始粒子种群，改善初始种群粒子的分布情况，提高种群粒子个体的多样性，然后，通过反向学习方法进一步丰富种群的多样性，提高种群的质量，增强粒子群算法的全局探索能力。混沌序列初始化的主要思想是利用混沌其自身强随机性、非周期和多样性的特性，将初始解通过映射变换至混沌变量域，利用混沌模型方程产生混沌序列，然后再将混沌序列线性地映射回到原优化变量空间。本文采用Circle混沌模型[8]对粒子种群进行初始化，其映射定义表达式如式（13）所示：

种群初始化具体步骤为：先通过Circle混沌映射模型生成粒子种群P，接着对混沌种群P 中的每一粒子个体利用反向学习方法构建粒子反向种群RP，然后计算粒子种群P 和粒子反向种群RP 中每一个粒子个体的适应度值并对适应度值进行排序，最后，从粒子种群P 和粒子反向种群RP 的综合排序中选择适应度较优的个体组成粒子初始种群Pop。

2.3 权重自适应非线性更新策略

在粒子群算法中，惯性权重系数ω 在平衡全局搜索和局部开发方面发挥着重要的作用。因此，为了更好地提高算法性能，本文采用自适应非线性更新策略来调整惯性权重ω的值，具体如式（14）所示：

其中，ω_min 和ω_max 为惯性权重基准的初始值和终止值；t 为当前迭代次数；T _max为算法设定的最大迭代次数；a，b 和c 为正数，作用于惯性系数非线性更新；通过惯性权重系数变化曲线图可以看出，权重系数自适应非线性更新策略在迭代前期一定时间内保持较大的值，增强全局搜索能力，以便能在解空间寻找更多可能的最优解区域；在迭代后期保持较小值的同时减小幅度变化，提高局部搜索性能，更快收敛到最优解。通过自适应非线性更新权重系数很好地平衡了粒子群算法的全局和局部搜索能力，兼具收敛速度的同时有效地提高了粒子群算法的收敛精度，避免局部解的产生。

2.4 基于差分学习的粒子变异策略

粒子群算法在经过多次迭代后，大量种群粒子会出现趋同性，发生聚集现象，容易导致算法陷入局部最优。为解决该问题，提出基于差分学习的粒子变异策略来对粒子进行变异扰动，增加种群的多样性，扩大粒子的搜索广度，跳出局部位置，以增强算法全局寻优能力，其主要根据种群聚集程度对全局极值粒子采用差分进化算法中变异和交叉双重操作生成新的全局极值位置，用以替代历史全局最优位置，具体操作如下：

首先，计算每代粒子种群的适应度方差σ²，种群适应度方差σ2 可以反映当前种群的多样性和聚集程度，当σ² 越大时，种群粒子就越分散，种群多样化越大，不易陷入局部解，反之，当σ² 越小时，陷入局部解的概率越高[9]；其种群适应度方差计算如式（15）、（16） 所示：

2.5 IPSO 求解多AGV 任务分配问题的步骤

采用IPSO算法求解多AGV任务分配问题的具体步骤为：

步骤1：确定火车进站货厢数量、停靠的位置和AGV的数量。

步骤2：根据运载任务生成和选择环节确定总任务量和每个任务与货厢间的匹配关系。

步骤3：设置算法参数，包括种群规模Ps、最大迭代次数G max，权重系数ω、学习因子c1，c2、扰动阈值ε、最大停滞迭代数it等。

步骤4：采用实数编码的编码方式对任务进行编码，并通过基于Circle混沌反向学习的种群初始化策略生成初始解集。

步骤5：计算种群里各个粒子的适应度值，并确定和更新各粒子历史最优位置和群体全局最优位置。

步骤6：利用权重自适应非线性更新策略更新惯性权重系数ω，更新种群每个粒子速度和位置。

步骤7：重新计算种群里各个粒子的适应度值，并确定和更新各粒子历史最优位置和群体全局最优位置。

步骤8：判断是否需要进行全局最优位置变异，若需要，则采用基于差分学习的粒子变异策略，更新全局极值位置；否则转步骤9。

步骤9：迭代次数更新G = G + 1，判断是否达到终止条件G ≤ G max，若未达到，则转步骤6，反之，则算法终止，输出最优解。

步骤10：对求解的最优解进行解码操作，得到站台堆区AGV任务分配最佳方案。

3 算例验证与结果分析

以图1所示的化肥站台堆区示范点为仿真实例对IPSO求解站台堆区多AGV任务分配问题的有效性和优越性进行验证。仿真实验中的算法均采用Mat⁃lab2020b 软件编程，测试环境为AMD [email protected] 处理器，16G RAM、64位的Windows10操作系统。

为验证IPSO算法求解站台堆区多AGV任务分配问题的可行性，本文假设3辆AGV在示范点中执行20 个运载任务，其中运载任务的位置和货厢的位置在站台堆区示范点随机生成，具体任务如表1所示。

IPSO算法求解站台堆区多AGV任务分配问题的适应度变化曲线如图2所示，任务分配结果如表2所示。从适应度变化曲线图中可以看出IPSO算法收敛速度较快，在迭代到第20代附近时即可找到问题的可行解，并且在迭代后期粒子通过变异策略能够跳出局部最优，让算法具有较强的寻优能力；从任务分配结果可知，IPSO算法能够很好地均衡每个AGV的任务，在兼顾任务数量均衡合理分配的同时也保证各AGV 执行任务代价相对均衡，避免过大代价差异。由此，通过该实验验证了IPSO 算法求解站台堆区环境下AGV运载任务均衡分配问题的可行性。

为验证IPSO算法求解站台堆区多AGV任务分配问题的优越性能，本文首先在三种不同条件的仿真场景下将本文改进粒子算法（IPSO）和基础粒子群算法（PSO）、遗传算法（GA）、基于概率分层的简化粒子群优化算法 （PHSPSO）、社会学习粒子群优化算法 （SLPSO） 以及基于自适应策略的改进粒子群优化算法 （MPSO） 进行对比仿真实验，其中，场景参数如表3所示；然后进行不同AGV数量下的算法性能对比，最后进行不同任务规模下的算法性能对比，进一步验证所提算法的优越性。上述仿真实例的任务在站台堆区示范点中随机生成。

为尽可能避免算法随机性的影响，每种算法在10、30和50任务规模的仿真实验条件下独立运行30 次，且以1 000次最大运行迭代次数为算法终止条件。表3统计了在A1、A2和A3仿真场景中，六种算法任务分配方案的数据结果，表中列举了不同算法求解分配方案的适应度值的最优值F min、最差值F max、平均值Favg 和标准差Fstd，以及分配的成功率P，其中分配的成功率是指满足约束条件的任务分配方案次数与实验总分配次数的比值。图3是六种算法在A1、A2、A3仿真实验中平均适应度的收敛曲线。