基于改进蚁群算法的立体仓库三维空间路径优化

徐 兴，钱誉钦，赵 芸，张 云，陈小依，吕晓姝

(1.浙江科技学院 机械与能源工程学院，浙江 杭州 310023；2.心怡科技股份有限公司，浙江 杭州 310023；3.浙江科技学院 信息与电子工程学院，浙江 杭州 310023;4.阿尔托大学 建筑学院，芬兰 赫尔辛基 02150)

0 引言

智能仓储系统(Intelligent Storage System，ISS)是一种通过计算机控制，能够对仓库实时容量和货物位置全面掌握的一种管理系统，其主要通过货运小车和相关搬运设备来实现货物的自动出入库和仓储的管理。在制造企业的智能仓储系统中，货物的转移作业是智能仓储系统中最常见作业方式，同时也是体现其效率的最关键点。选择最优化的仓位间的三维运行路径是提高智能仓储系统整体运行效率的有效方法。

目前，国内外主流的运用于运动机器人的路径规划算法主要包括局部搜索算法[1-2]、模拟退火算法、禁忌搜索算法、狼群算法、蚁群算法等[3]。这些算法中部分算法具有较好的运行时间优势，但是又很容易陷入局部最优。在这些算法成果中，对于仓储系统三维路径优化问题的研究成果不在少数，如夏绪辉等[4]将时间和能耗引入仓库三维空间内的路径优化，提高了算法的全局优化性能，并有效地平衡了作业的能耗和作业的效率，提高了整体作业过程的绿色程度；杨玮等[5]在密集仓储系统的路径优化中对蚁群算法进行改进，引入遗传算法从而优化了其初始信息素的参数，使算法具有更好的全局性能，提高了整个系统的运行效率；刘利强等[6]研究了水下下潜器的三维空间路径优化，以蚁群系统(Ant Colony System, ACS)作为基础，详细研究了算法中信息素的表示方法和更新规则、路径点的选取原则以及启发函数的设计；李浩宇等[7]运用栅格离散的方法创建三维空间环境地图并引入了蚁群算法，得到了较快的收敛速度、较好的稳定性和更高的计算效率；陈家照等[8]将改进粒子群优化算法引入三维空间路径规划，对迭代过程中算法惯性系数分段设置和随机扰动粒子位置的方式进行改进，有效地提高了粒子群优化算法的计算效率和可靠性；方彦军等[9]主要针对轨道小车，采用人工狼群算法并引入禁忌表和拥堵因子采取自适应步长来避免算法陷入局部最优，同时也加快了后期收敛的速度；赵威等[10]将局部搜索算法结合三维空间路径优化，引入信息素因子和势场因子，使得迭代次数降低，路径点轨迹也更加平稳；Ma等[11]考虑作业载重和行驶距离等各方面因素,建立了一个多目标的路径优化模型，通过一种集成学习的优化算法降低了时间复杂度，解决了自动化的立体仓库的时间规划问题。

上述研究虽然对路径优化或者三维空间的适用性提出了各自的方法，但是在制造企业仓储系统中，特别是基于货架式的仓库中，自动导引小车(Automated Guided Vehicle，AGV)的三维空间路径优化研究尚存在一定缺陷，主要在三维空间中多目标点的路径选择方面，目前研究仅针对二维平面的AGV路径选择；算法的选择与优化方面，目前研究使用的算法时间复杂度较高、运行时间冗余。因此，本文主要针对制造企业仓储系统的AGV在货架间的三维空间路径优化开展研究，在提高程序运行效率的同时，实现AGV的运行路线距离最短。

1 三维空间路径优化问题建模

1.1 问题描述

在制造企业的智能仓储系统中，AGV是关键的作业承担者，AGV参与仓储系统中入库作业和出库作业两种模式。在作业过程中，多目标点之间遍历式操作是当前仓储作业的一种高效率的作业方式。对于单一AGV在多目标点之间遍历式作业,需要多目标点的定位，以及准确且快速的路径选择，且现有仓储系统多为货架式仓库需要进行三维定点以及三维空间的路径规划。对于三维平面的路径规划，不仅需要考虑水平面上AGV小车的运动，还要考虑其垂直平面上的运动以及跨货道间的运行路线。本文研究的工业场景为立体仓库，实验通过模拟现实货架和AGV来进行操作。所述模型如图1所示，现实实验场景如图2和图3所示。

本文所述仓库为某企业特定形式的立体仓库，可供AGV在同平面以及跨平面间进行作业运动，且本文所研究的AGV可以进行多目标点历遍式作业，免去了两点式作业(起始点到单一目标点)的多余路线与运行时间。基于本文特定实验场所，AGV能够在一个货道内进行上下与前后操作，但是跨货道操作必须退到货道外。

根据立体仓库模型以及多目标定位点定位后，本文中AGV对于货物的出入库作业描述为如下3个环节：①AGV到达其自身位置最近的某一目标点，作为起始点开始作业；②AGV通过计算后得到的目标点运行顺序从起始点出发一次到达下一个目标点，并进行作业；③AGV在历遍所有目标点完成相关作业以后回到起始位置等待下一步指令。当AGV接收到系统任务时，其目标点之间的运行顺序直接影响了单台AGV的作业效率以及运行时间。因此各个目标点最短路径的优化将是系统整体运行效率的体现。

1.2 数学模型

根据本文所针对适用的三维立体仓库模型，假设AGV能够在三维空间内运动，且运动路径只能是水平与竖直的两个方向。水平方向的运动是通过AGV自主运行，而竖直方向的运动是通过升降机来辅助运行，升降机的运动和AGV的运动在启动与分离时的速度影响与时间影响的考虑均设定为均值，对之后的路径选择与优化不会产生影响。

与其他仓储系统路径优化问题研究不同的是，本文将制造企业仓储系统中的路径优化问题扩大到三维平面，并根据仓库的实际情况，在路径中加入添加点，从而实现AGV小车的运行路径平行于X，Y，Z轴。

本文研究将AGV运行轨迹分为如下三类运动，分别是：①两点在同一平面内，并且有相同的X坐标或Y坐标或Z坐标；②两点在同一平面内，并且X，Y坐标或X,Z坐标或Y，Z坐标均不相同；③两点在不同平面内，且X，Y，Z坐标均不相同。

假设两点的空间坐标分别为i=(x1,y1,z1)，j=(x2,y2,z2)。当AGV做一类运动时，其基本的物理位移公式为：

S=|y1-y2|或|z1-z2|。

其次，当要进行X方向上的运行操作时，由于要跨巷道运行，需要将小车退到巷道口来实现X方向上的移动，其基本的物理位移公式为：

S=2|y|+|x1-x2|。

当AGV做二类运动时，由于在同一平面内但是又并非同一直线，需要添加一个辅点来帮助AGV小车来实现两点间的运动。当要进行X方向上的运行操作时，由于要跨巷道运行，需要将小车退到巷道口来实现X方向上的移动，从而实现小车运行的路径平行于坐标轴。其基本的物理位移公式为：

S=|x1-x2|+|y1|+|y2|或

S=|x1-x2|+|z1-z2|+2|y|或

S=|y1|+|y2|+|z1-z2|

当AGV做第三类运动时，由于不在同一平面，并且X，Y，Z坐标均不相同，其实现的是跨平面间的运动，因此需要添加两个辅助点来实现两点间的运动。当要进行X方向上的运行操作时，由于要跨巷道运行，需要将小车退到巷道口来实现X方向上的移动，从而实现小车的运行路径平行于坐标轴。其基本的物理位移公式为：

S=|x1-x2|+|y1|+|y2|+|z1-z2|。

2 基于三维空间路径的改进蚁群算法设计

2.1 蚁群算法

蚁群算法[12](Ant Colony Algorithm, ACA)由Macro Dorigo在1992年提出，是一种群优化算法，模拟自然界中蚂蚁群的觅食行为。蚂蚁在寻找食物源的时候，会在其经过的路径上释放一种信息素，其他蚂蚁能够感知这种信息素。将此行为抽象到算法当中时，信息素浓度的大小表征了目标点路径的远近，信息素的浓度越高，表示对应的路径越短。通常情况下，蚂蚁会优先选择信息素浓度较高的路径，并且其自身会释放一定量的信息素，从而增强了该条路径上信息素的浓度，因此形成了一个正反馈机制，同时信息素的浓度也会随着时间的推移而减弱。最终，可以通过不断的迭代获得一段从出发点到目的地的最短的路径。

路径优化问题映射到算法当中就是求解最优解的问题，其目的是通过蚁群算法来求解最短路径。在蚁群算法中，路径较短的蚂蚁释放的信息素的量较多，随着时间的推移，在较短路径上累积的的信息素浓度逐渐增高，因此选择该路径的蚂蚁数量也逐渐增多。最终，整个蚂蚁群会在正反馈的作用下集中到最短路径上，此时对应的解即为最优解。

通过蚁群算法原理，可以得出每一只蚂蚁选择的下一个目标点的概率公式为[13]：

当蚂蚁走过所有路径点以后，返回原来起始点，从而完成一次路径的循环，之后再一次更新信息素。因此，每条路径上的信息素总共分为两个部分：①前一次蚂蚁通过路径时所遗留且还未挥发的信息素；②当前蚂蚁所经过时留下的信息素。因此其信息素的迭代公式为[14]：

τij(t+n)=(1-ρ)·τij+Δτij(t,t+n),

蚁群算法具有如下特点：

(1)采用正反馈机制，使得搜索过程不断的收敛，最终逼近最优解。

(2)每个个体可以通过释放信息素来改变周围环境，且每个个体能够感知周围环境的实时变化，个体间通过环境间接地通讯。

(3)搜索过程采用分布式的计算方式，多个个体同时进行并行计算，大大的提高了算法的计算能力和运行效率。

(4)启发式的搜索方式，不容易陷入局部最优解，易于找到全局最优解。

2.2 改进蚁群算法三维空间路径的实现方法

在蚁群算法中，蚂蚁被随机分配到各个点位，并且需要游历所有的目标点，其目标点顺序的选择与转移概率有关，而各个点之间的转移概率由路径间的信息素浓度和启发式因子决定。每条路径上信息素的浓度通过上述的迭代公式来计算，而启发式因子根据现实情况来确定。

针对仓库内三维立体货架，需要考虑水平面与垂直平面上AGV小车的运行路径的选择。本文依托于现有仓库，以及其中货架的摆放情况，优化了蚁群算法，将原有两点间直线路径更改为平行于各个坐标轴的折线路径。

引入cenpt变量，来确定添加点的个数，部分MATLAB代码如下：

cenpt=0;

if C(R(i),1)～=C(R(i+1),1)

cenpt = cenpt+1;

end

if C(R(i),2)～=C(R(i+1),2)

cenpt = cenpt+1;

end

if C(R(i),3)～=C(R(i+1),3)

cenpt = cenpt+1;

end

当cenpt=3时，表示两点X，Y，Z坐标均不相同，则需要加入3个添加点，其坐标分别是a=(x1,0,z1),b=(x2,0,z1),c=(x2,y2,z1),以及实现的两点间具体路径为：i→a→b→c→j;当cenpt=2时，表示两点的某一个坐标值相同，只需要加入一个添加点，(当X坐标相同)添加点坐标为a=(x,y2,z1),两点间的具体路径为：i→a→j，(当Y或Z坐标相同)则需要3个添加点，其坐标为a=(x1,0,z),b=(x2,0,z),c=(x2,y2,z)，以及实现的两点间具体路径为：i→a→b→c→j;当cenpt=1时，表示两点间的某两个坐标值相同，则不需要加入添加点，两点间的具体路径为：i→j。

本文提出的基于三维空间路径的改进蚁群算法具体步骤如下：

步骤1将算法内的变量初始化，设置算法的最大迭代次数Nc_max，以及蚂蚁的总数为m，并且将蚂蚁随即放在各个点位上。信息素因子设置为Alpha,启发因子Beta，信息素的蒸发系数Rho，以及信息素的加强系数Q。

步骤2每只蚂蚁随机分配起始点，确定每个蚂蚁初始的信息素，逐个蚂蚁进行路径选择，将到达的目标点位加入到禁忌表中，避免重复访问，并且初始化解空间。通过概率函数来进行下一个目标点的选择，m只蚂蚁按照概率函数选择下一个点，完成各自周游。概率函数通过当前点与其余点的距离的倒数来确定，并在每一步访问后实时更新禁忌表，且运用cumsum函数将每段路径元素累加求和。其概率计算公式如下[15]：

ηij=λexp(ιn,e-ιn+1,e)。

当完成一次所有点的访问循环，比较每一只蚂蚁的路径距离，记录本次迭代的最短路径以及所有蚂蚁循环后的平均距离。具体代码如下：

for i=1:(ceil(m/n))

Randpos=[Randpos,randperm(n)];

end

Tabu(:,1)=(Randpos(1,1:m))';

for j=2:n

for i=1:m

visited=Tabu(i,1:(j-1));

J=zeros(1,(n-j+1));

P=J;

Jc=1;

for k=1:n

If length(find(visited==k))==0

J(Jc)=k;

Jc=Jc+1;

end

End

%下面计算待选点的概率分布

for k=1:length(J)

P(k)=(Tau(visited(end),J(k))^Alpha)*(Eta(visited(end),J(k))^Beta);

end

P=P/(sum(P));

%按概率原则选取下一个点

Pcum=cumsum(P);

Select=find(Pcum>=rand);

to_visit=J(Select(1));

Tabu(i,j)=to_visit;

end

end

if NC>=2

Tabu(1,:)=R_best(NC-1,:);

End

步骤2判断k的值，若k≥m，表明该蚂蚁已经历遍了所有目标点则继续步骤4，否则返回步骤2。

步骤3更新全局信息素，迭代后将下一次路径循环上的信息素蒸发系数Rho，以及信息素加强系数Q进行更新。再进行全局信息素更新时，该模型能够很好地将全局路径上的信息素统一归纳更新。其更新信息素公式如下[11]：

τij(t+1)=ρ·τij(t)+Δτij(t),

L=zeros(m,1);

for i=1:m

R=Tabu(i,:);

for j=1:(n-1)

L(i)=L(i)+D(R(j),R(j+1));%原距离加上第j个点到第j+1个点的距离

end

L(i)=L(i)+D(R(1),R(n));

end

L_best(NC)=min(L);

pos=find(L==L_best(NC));

R_best(NC,:)=Tabu(pos(1),:);

L_ave(NC)=mean(L);%此轮迭代后的平均距离

NC=NC+1;

Delta_Tau=zeros(n,n); %更新信息素

for i=1:m

for j=1:(n-1) Delta_Tau(Tabu(i,j),Tabu(i,j+1))=Delta_Tau(Tabu(i,j),Tabu(i,j+1))+Q/L(i);

End

步骤5禁忌表的清零与实验结果的输出。当达到最大迭代次数以后，将禁忌表清零。最后优化信息素增量函数，进行多次迭代，待算法能够收敛，比较所有次迭代的最短路径与其最短距离，得到巡回所有点的最优调度顺序。该算法的基本思维运行结构如图4所示。

3 仿真实验对比与结果分析

本文借助MATLAB R2014a实验平台来对该算法进行仿真实验，以验证该算法的有效性。以某大型制造企业内部仓储系统为研究对象，该仓储系统中有12列货架，每列货架有4层，每层包含30个仓位，共计1 440个仓位。针对本文所应用的AGV，均可在货架间的巷道与货架上按照货架固有的结构作业，并且AGV可以进行多目标点历遍式作业。为验证本文算法的优越性，采用遗传算法、普通蚁群算法作为比较对象，对相同数量的目标点进行路径优化对比，并进行多次实验对比，以确保其准确性有效地降低了小概率偶然因素的影响。本次实验优化蚁群算法的各个参数设置为：最大迭代次数NC_max=100;蚂蚁数量m=30;信息素因子Alpha=1.5;启发因子Beta=2;信息素蒸发系数Rho=0.1;信息素加强系数Q=106。实验结果曲线如图5和图6所示。

图5和图6所表示的是不同算法在不同数量目标标点作业之后的收敛效果对比。由图5和图6可知，虽然每种算法都能很好地得到收敛效果，但是在不同次作业下，本文所用的优化蚁群算法具有更快的反应时间和更少的迭代次数。

通过具体实验，由于本文实验仓库有12列货架，而实验AGV在货架间运行需要从每一列货架退出再进入操作，为了能在每列货架上都有操作机会，检测最大化的时间，所以本实验随机生成了12个目标点来进行仿真实验，获得的结果如图7和图8所示。

由图7可得此次仿真实验通过迭代得到的最短距离以及平均距离，图中下方折线即为最短距离，本次仿真实验的12个目标点之间的最短距离为100个单位，而上方折线即为当次迭代的平均距离。由此可知，迭代次数的增加对路径的优化有很好的作用，各次平均距离有大幅度的下降。而通过图8能更加直观地看到在本次仿真实验中获得的12个随机点的最短路线轨迹，图中实心点为本次最短路径的起始点，黑圈点为所要经过的各个目标点而白圈点即为生成路径所需要的添加点。如表1所示，本文随机生成了12个目标点X坐标范围是(1，12)，Y坐标范围是(1，30)，Z坐标范围是(1，4)。通过表2可以更加直观地看到本次仿真实验在12个目标点之间的路径运行顺序。通过图7与图8，可以得到本文所用的优化蚁群算法对于实验仓库有很好的适用性，通过极少次的迭代就能够获得多个随机目标点之间的最短路径，并且能直观地看到本文所创新的添加点在轨迹路线中的作用。

表1 仿真实验的随机生成的目标点

表2 仿真实验目标点运行顺序

4 结束语

本文研究了在制造企业内仓储系统立体货架中AGV小车对于三维空间下的路径优化算法，在原有二维平面的蚁群算法路径选择的基础上，针对其AGV的运行空间，将二维平面扩张到三维空间中，使其能够在多个三维空间点中找到最优路径。利用两目标点之间增加添加点的思想以及现实环境中立体仓库货架的运作方法，拓展了原有蚁群算法中路径距离的计算方法，虽然增加了具体路线的长度，但是优化计算得到的路径更加适用于当前制造企业中的仓储环境。通过改进算法中的概率模型与禁忌表的思想，有效解决地避免了陷入局部最优的情况。最后，通过制造企业的案例分析，证实了该算法的实用性以及可行性，其能够很好地解决现实仓库中AGV的路径规划问题。下一步将针对AGV集群在本实验环境中的三维空间路径优化展开研究。