基于混合算法的自动导引车调度问题研究

屈新怀, 严 飞, 丁必荣, 孟冠军

(合肥工业大学 机械工程学院,安徽 合肥 230009)

0 引 言

随着电子商务与工业自动化等行业的飞速发展,自动化仓库在各领域扮演的角色愈加重要。自动导引车(automated guided vehicle,AGV)作为现代仓库的重要一环,对提高仓储效率有着重要意义[1]。目前,针对解决AGV作业效率问题,主要从优化AGV任务调度[2]、AGV作业路径以及避免交通拥堵[3]3个方面入手。

AGV任务调度问题属于NP-hard问题,精确算法只能用于求解该类问题小型实例,因此求解策略集中于使用启发式算法。文献[4]用改进的三交换交叉算子遗传算法求解AGV调度问题,同时对所有AGV总行驶距离和单AGV最长行驶距离进行优化;文献[5]针对制造车间AGV运输问题设计了一种粒子交叉、变异新机制的改进粒子群算法,并用实验验证该算法求解AGV最短运输时间问题的有效性;文献[6]用改进的遗传算法求解多AGV作业车间调度问题,并分析了运输时间、AGV数量与电量之间的相互影响关系;文献[7]在仓储AGV任务调度问题中提出了基于LRU缓存的高效K-opt优化算法,改进了原始计算方式,加快了算法收敛速度。以上研究虽然对AGV行驶距离有较好的优化结果,但研究目标较为单一,没有考虑AGV总能耗等目标,忽略了AGV载重约束,对实际问题刻画过于理想。

近年来,求解AGV任务调度问题的启发式算法有遗传算法、粒子群优化算法、差分进化算法、蚁群算法、模拟退火算法等[8]。其中蚁群算法因操作简便性和易于改进性得到广泛研究。蚁群算法的优化速度可以通过设计算法参数自适应规则、设置多蚁群协同优化、改进信息素更新规则3个方面加以改进[9]。文献[10]针对带碳排放约束的车辆路径问题,提出一种在信息素更新规则中引入混动扰动机制的改进蚁群算法,有效提高了求解车辆行驶里程最短和碳排放量最小的多目标非线性规划模型的概率;文献[11]提出一种伪动态搜索蚁群优化算法,改进了信息素更新规则,避免了局部优化,提高了算法的收敛速度。

根据上述研究,本文基于AGV任务调度问题的基本模型,构建以AGV行驶总距离和总能耗最小为目标的非线性规划模型;利用结合离散差分进化算法与蚁群算法的混合算法对该模型进行求解,并通过算例来验证本文所提出算法的有效性。

1 问题描述和数学模型

1.1 问题描述

多自动导引车多任务点调度问题描述为:在自动化仓库分拣中心(编号为0),一共有M辆单一型号AGV可执行任务,每辆AGV的空车质量为w,每辆AGV的额定载重为Q,一段时间内随机生成的分拣任务数量为N,每个任务i(i=1,2,…,n)对应的需求质量为qi(qi

单个AGV多任务的行驶流程为:AGV从分拣中心点出发,根据接收的任务点信息,规划合理行驶方案,前往各个任务点取对应货物,再返回分拣中心点。

在AGV多任务调度过程中引入能耗约束,需对小车行驶过程中能源消耗进行刻画。小车行驶中的能耗受到小车类型、载重负荷、行驶速度、行驶距离等多个变量的影响。参考文献[12],考虑仓库中AGV行驶速度较慢,忽略空气阻力对能耗的影响,在本文中,采用下式计算AGV能耗eij:

eij=μ(w+lijk)gdij/θ+(dij/V)P

(1)

其中:μ为滚动阻力系数;w为空车质量;lijk为车辆的负载;g为重力加速度,取9.81 m/s2;dij为车辆行驶距离;θ为驱动功率因数;V为车辆行驶速度;P为车载系统功率。

1.2 数学模型

根据以上关于多自动导引车多任务点调度问题的描述,本文构建的考虑能源消耗的AGV调度问题的数学模型如下。

目标函数为:

(2)

(dij/V)P]xijk

(3)

约束条件为:

(4)

(5)

(6)

(7)

(8)

xijk=0, ∀i=j,k∈M,i,j∈N

(9)

xijk,yik∈{0,1},i,j∈N,k∈M

(10)

其中:(2)式表示所有AGV行驶路径的长度之和;(3)式表示所有AGV行驶过程中能耗之和;(4)式表示AGV载重负荷约束;(5)式表示每个任务有且只能被一辆AGV完成;(6)式表示所有AGV从分拣中心点出发并返回分拣中心点;(7)式表示AGV接受某个任务,必定从某个地方行驶到该任务点,且任务完成后必定从该任务点离开;(8)式表示每辆AGV行驶路线中没有子回路,S为若干任务的集合;(9)式、(10)式定义决策变量是0-1变量。

2 模型求解

本文研究的考虑能耗的多自动导引车调度问题是以行驶总距离和总能耗最小为目标的路径问题,属于典型的NP难题,拟用结合离散差分进化算法与蚁群算法的混合算法对该模型进行求解。蚁群算法是一种模仿蚁群觅食行为的群体智能算法[13],具有系统性、自组织性、正反馈性与较强的鲁棒性,可以在短时间内找到问题较为满意的解,但当求解问题规模较大时,蚁群算法容易出现早熟、停滞现象[14]。离散差分进化算法区别于经典差分进化算法,可以应用于离散空间,帮助解决离散域中的组合优化问题。当蚁群算法陷入停滞时,引入离散差分进化算法的变异、交叉、选择操作,扩大算法搜索解的空间,帮助蚁群算法跳出停滞。因此,利用2种算法结合的混合算法对本文的多自动导引车调度问题进行求解,算法流程如图1所示。

图1 混合算法求解流程图

2.1 状态转移概率的设置

状态转移概率是指蚂蚁在搜索路径时从一个点到另一个点的转移概率。经典蚁群算法中考虑从当前任务点i到所选任务点j的路径长度和路径 (i,j)上的信息素浓度2个方面的因素,其状态转移公式如下:

(11)

本文研究的是考虑能耗的多自动导引车调度问题,在设置状态转移概率时既要考虑AGV行驶距离,又要考虑能耗量。为此,将能耗量作为启发信息引入到状态转移概率计算模型中,即

(12)

2.2 信息素更新策略

蚁群算法在一次寻优结束后,需要对各任务点间的信息素浓度进行更新,信息素更新的快慢将直接影响算法优化结果。更新过快,算法将陷入局部最优解甚至停滞;更新过慢,算法收敛速度缓慢。本文提出一种引入排名因子的信息素更新策略,提高较优解的信息素浓度,加快算法收敛速度。具体更新策略如下:

τij(t+1)=(1-ρ)τij(t)+Δτij(t)

(13)

(14)

(15)

同时,在迭代中早期,允许更多蚂蚁表达信息素,即参与排名;在迭代晚期,只允许排名前列的蚂蚁表达信息素,加快收敛速度又防止陷入局部最优解。

2.3 离散差分进化算法

利用上述改进的蚁群算法求解多自动导引车调度问题时,连续5次迭代搜索到的最优解不发生变化,可以认为算法陷入停滞,引入离散差分进化算法的变异、交叉、选择操作,帮助算法扩大搜索空间,跳出局部最优解。

2.3.1 变异

将每只蚂蚁寻找的完整路径中的分拣中心点(编号)去除,并按顺序存放于解矩阵X;随机选取矩阵中不等于Xi的3行向量,并按以下操作生成该行对应的变异向量Vi,即

Vi=Xp1+F⊗(Xp2-Xp3),

p1≠p2≠p3≠i

(16)

j=1,2,…,n

(17)

(18)

(19)

其中:(16)式表示离散差分进化算法的变异操作;(17)～(19)式表示离散域中变异向量各位置的取值规则。差分进化算法中,F为变异尺度参数,本算法中F定义为常量,取0.5;r1∈[0,1],为随机变量。

2.3.2 交叉

按以上操作取得每只蚂蚁对应解X的变异矩阵V后,可以求得对应向量Xi的交叉向量Di。求解公式如下:

(20)

其中:r2∈[0,1],为随机变量;pcr为常量,取0.5。

每只蚂蚁解的交叉向量Di可以根据随机变量的值,从解向量Xi和变异向量Vi对应位置处求得。同时,交叉操作前应先去除变异向量中可能重复的任务点,以保证任务不会重复完成。

2.3.3 选择

每只蚂蚁对应解向量Xi和交叉向量Di均已生成,根据车辆(蚂蚁)额定载重限制,生成对应完整路径(包含分拣中心点),比较车辆总行驶距离,选择更优解进入迭代。同时为保证扩大搜索空间,设置一定交叉向量Di的被选择概率。

离散差分进化算法的变异、交叉操作如图2所示。

图2 离散差分进化算法变异、交叉操作实例

2.4 2-opt局部优化改进

为对离散差分进化算法与蚁群算法相结合的混合算法搜索到的路线进行进一步优化,本文采用2-opt法对路线内子路径(即调度方案内某车辆的行驶路径)进行改进。

改进方法如下:设路线内子路径任务点为:(i,i+1),…,(j-1,j)。反转i+1与j-1之间的路线,若反转后整个路线行驶距离减少,则更新该车辆行驶路线。依次对所有车辆路径进行2-opt优化,减少整个调度方案车辆行驶距离。

3 数值仿真及算例分析

为验证所设计的混合算法的有效性及对实际问题的求解能力,本文设计了2个实验:

(1) 实验1。利用本文算法对CVRPLIB SET P标准数据集求解,并与改进蚁群算法、遗传算法等求解结果进行对比,以验证本文算法的有效性。

(2) 实验2。为验证算法能有效提高自动化分拣仓库作业效率及降低AGV能耗,分别运用本文混合算法与改进蚁群算法对案例模型进行求解。

使用MATLAB R2016a编写算法代码,在Intel Core i7-7500U 2.7 GHz (8.00 GiB RAM)、Windows 10操作系统的环境下运行算法。

本文算法相关参数设置为:蚂蚁数量AntNum=50;最大迭代次数Max-Iter=200;信息素重要程度因子α=1;启发式因子β=2,γ=1;信息素挥发系数ρ=0.5;变异尺度参数F=0.5;常量pcr=0.5。

3.1 混合算法有效性验证

为验证本文混合算法的有效性,实验1利用本文算法对CVRPLIB SET P标准数据集求解,并与文献[15]改进的蚁群算法、遗传算法、模拟退火算法、粒子群算法求解的最优解对比。实验对比结果见表1所列。

表1 本文算法与其他算法求解算例结果对比

表1中加粗数据表示该算例最优解。由表1可知,本文算法在小型、中型算例中均能取得较好的解,仅在P-n23-k8、P-n51-k10、P-n55-k10、P-n65-k10、P-n76-k4、P-n76-k5这6个算例中相较于其他算法未取得最优解,且结果与最优解差距不大,说明本文提出的混合算法在求解路径问题上表现较好,可以对AGV任务调度模型求解。

3.2 自动化分拣仓库AGV调度

实验1验证了本文算法的有效性,但未对具体案例场景进行实验分析。本文借鉴文献[16]中的仓库模型,提出一典型的自动化分拣仓库模型,其栅格地图如图3所示。

图3 自动化分拣仓库模型

多辆AGV根据图中3个订单任务点信息,在载重约束下,从分拣中心出发前往各订单任务点,并返回分拣中心点。栅格长宽均为5 m;AGV空车质量w=60,额定载重Q=200,行驶速度V=1,滚动阻力系数μ=0.03,驱动功率因数θ=0.6,车载系统功率P=25。

采用改进蚁群算法和本文提出的混合算法对自动化分拣仓库AGV调度问题进行求解,算法分别运行10次,平均解中AGV行驶总距离及总能耗见表2所列,算法运行迭代图如图4所示。

表2 本文算法与改进蚁群算法求解结果对比

图4 算法运行迭代图

由表2可知,应用本文算法对提出的自动化分拣仓库AGV调度问题求解,AGV行驶总距离及总能耗均小于改进蚁群算法求解结果。同时由图4算法运行迭代图可知,本文算法收敛结果、收敛速度均优于改进蚁群算法。这表明本文提出的混合算法可以有效提高自动化分拣仓库作业效率及降低AGV能耗。

4 结 论

本文对自动化仓库中AGV多任务调度问题进行了研究,在考虑车辆载重等前提下,构建了以车辆行驶总距离和总能耗最小为目标的非线性规划模型,并提出了一种离散差分进化算法与蚁群算法相结合的混合算法求解模型。主要贡献可归结如下:

(1) 根据所提出能源消耗模型,改进了蚂蚁状态转移公式。

(2) 提出一种引入排名因子的信息素更新策略,提高较优解的信息素浓度,加快算法收敛速度。

(3) 在蚁群算法中引入离散差分进化算法的变异、交叉、选择操作,扩大了算法搜索范围,降低了算法陷入局部最优概率。

最后设计了2种实验,验证了本文算法的有效性。结果表明,本文提出的混合算法可以根据实际算例规划合理路线,有效提高自动化仓库仓储效率。

考虑电子商务和工业自动化等行业的飞速发展,未来自动化仓库环境必将更加复杂,对仓储效率的要求也愈加提高。未来的研究可以更贴合AGV运输的实际情况和任务的动态需求。在求解方法上,可以设计多启发式算法结合的混合算法以及人工智能算法对大型问题进行更高效求解。