最新新闻
我要投稿
联系电话:027-87592219/20/21转188
投稿邮箱:tb@e-works.net.cn
您所在的位置:首页 > 智库 > 智能供应链

自动化立体仓库的货位分配优化

发布时间:2017-03-16 作者:杨玮 张文燕 常晏彬 邱小红 王雯  来源:万方数据库
为有效解决自动化立体仓库(AsiRS ),即自动存取系统的货位分配问题,以货架稳定性和出人库效率为目标,结合多色集合、粒子群算法和模拟退火算法三者优势,建立区域划分、货位分配两阶段的多目标货位分配决策模型。区域划分阶段考虑货物出人库效率和货架受力情况,采用多色集合的围道布尔矩阵进行划分。货位分配阶段根据人库货物的类型和数目,采用结合模拟退火算法的混合粒子群算法求解货位分配优化问题。在MATLAB软件中运行实例,结果证明,与遗传算法和粒子群算法比较,混合粒子群算法在求解货位分配优化问题时的收敛速度快、稳定性高,且能在保证货架稳定性的前提下提高出人库效率。
    0引言
    
    自动化立体仓库(Automated Storage and Retrieval System , AS/ RS )的效率高低主要受货位分配的影响,采用合适的货位分配原则实现货物分配最优位置存储,可以充分利用储存空间,缩短出入库移动的距离和作业时间,并能使得货架受力情况良好,保证货架的稳定性,加快货物周转,提高工作效率以及货架可靠性。
    
    国内外学者在货位分配问题上做了深入研究。Lu Chen和Andre' Langevin等人〔4〕根据停留持续时间的共享存储原则,解决了自动化立体仓库的货位分配与交叉存取问题;Guo Shin}VIing, Liu Tsai}ei等人分析了多通道立体仓库存储环境下,双梭系统在基于不同产品类型存储问题下的优势,以及不同存储分配问题对双梭系统性能的影响;赵雪峰〔6]、鄂晓征〔7〕等人以出入库效率和空间利用率为目标,分别提出两级遗传算法和混合遗传算法解决仓储货位优化问题;张晓兰、蒋丽娜等人〔s〕采用遗传算法对货位动态分配优化问题进行了研究,通过权重系数变换法较好地解决了存取路径距离以及货架承重能力和稳定性多目标之间的相互冲突问题。
 
    目前,对立体仓库货位分配、存储问题常用的优化算法包括:枚举法、随机法和迭代算法等。采用遗传算法进行优化求解时,进行选择、交叉以及变异等遗传算子的操作会影响解的质量,本文提出将模拟退火算法、粒子群算法相结合的混合粒子群算法解决货位分配问题,在反复寻找最优货位分配的迭代过程中,采用模拟退火算法来优化粒子群算法的速度更新公式,从而避免结果陷入局部最优,最后采用MAT-LAB软件实现所有算法的求解。
 
    1货位分配原则
    
    为提高自动化立体仓库效率,加强货位管理,自动化立体仓库货位分配应遵循以下原则。
    
    1)上轻下重,使货架的受力稳定。
   
    2)先进先出,加快周转。
    
    3)根据货物的特性和出入库频率,将存储区域划区分段存储。
    
    4)进行出入库操作时,先确定该货物所在货位的分区,再选择该分区内距离出入库台最近的货位作为出入库的货位。
    
    本文在考虑上述原则的基础上,从自动化立体仓库实际情况出发,根据货物出入库频率和货物重量进行分类存储,建立多色集合和混合粒子群算法相结合的决策模型,以解决自动化立体仓库货位分配时货架稳定性和出入库效率问题。
 
    2基于多色集合理论实现货位分区
 
    2.1多色集合的概念
    
    多色集合是一种新兴的系统理论和信息处理工具,其核心思想是对不同对象(产品、设计过程、工艺利于进行计算机编程。
 
    2.2利用多色集合理论进行货位分区
    
    考虑货物出入库效率和货架受力情况,采用多色集合理论进行货架分区。将货位编号作为多色集合的统一颜色(代表所有货位的共同特征),将货位特征、货物出入库频率和货物重量作为多色集合的设计元素(代表货物的个体特征),把两者相互联系建立立体仓库货位分区的数学模型,组成围道布尔矩阵[BxF(B)],其中B为统一颜色集合,F(B)为设计元素。
    
    统一颜色集合B由不同货位编号组成,其数学表达式为:B=(b1,b2,b=,...,bt,...,bR),bt表示第r个货位的物理编号。
 
    设计元素F(B)是指影响立体仓库出入库因素的集合,包括货位特征、货物出入库频率和货物重量,其数学表达式为:F(B)=(F1,F2...,Ft,...,Fs)F表示第s个设计元素。
    
    [BxF(B)]从整体上表示约束立体仓库出入库的货位特征、货物出入库频率和货物重量与货位之间的关系。
 
    2.3基于多色集合理论的货位分区实例
    
    本文以12层60列的立体仓库为例,该仓库存储的货物按照所需货位个数、出入库频率和货物重量等分为5类,货物特征表如表1所示。
 
    表1 货物特征表

货物特征表
 
    组成围道布尔矩阵[BXF(B)]如图1所示,(i,j)为第i列第j层的货位坐标,分别代表货架的列数和层数,其中i=1,2,...,60;x=1,2,...,12。货位的物理编号为b厂,其中r=60x(j-1) +i。
    
    F1~F5为货物出入库频率特征,分别表示频率在40%一50%之间、30%一40%之间、20%一30%之间、10%一20%之间和10%以下,对应出入库频率的五个等级:高、较高、中等、较低以及低。
    
    F6一F10为货物重量特征,分别表示重量在800-1 000 N之间、600一800 N之间、400一600 N之间、200-400 N之间和200 N以下,对应货物重量的五个等级:重、较重、中等、较轻以及轻。
 
    F11一F15为货物存放层数,分别表示货物存放在1一5层、6一7层、8一9层、1层和11一12层,对应货物存放层数的五个等级:低、较低、中等、较高以及高。
    
    F16一F20为货物存放列数:分别表示货物存放在1一13列、14一33列、34 } 49列、50一59列和60列,对应货物存放列数的五个等级:近、较近、中等、较远以及远。
    
    F( br)为集合B中元素br的个人着色(个体特征)。例如,对于F(b14) -(F2,F6,F 11,F17),用布尔矢量表示为F( b,4 )=(0,1,0,0,0,1,0,0,0,0,1,0,0,0,0,0,l,0,0,0>,在图i中,将布尔矢量表达式中的i和0分别用“.”和空格表示。
    
    根据图i所示的货位编号—货位、货物特征的围道布尔矩阵,利用MATLAB软件将货架分为5个区域,分别用A,H,C,K,E表示各分区号,货位分区图如图2所示。
    
    分区A存放第1类货物,分区H存放第2类货物,分区C存放第3类货物,分区K存放第4类货物,分区E存放第5类货物。
 
货位编号—货位、货物特征的围道布尔矩阵图[BxF(B)]
 
    图1 货位编号—货位、货物特征的围道布尔矩阵图[BxF(B)]
 
货位分区图
 
    图2 货位分区图
 
    3基于混合粒子群算法实现货位分配
 
    3.1货位分配的数学模型
    
    假设某自动化立体仓库固定货架共有I列J层,处于第i列第j层的货位坐标记为(I,j)(其中i=1,2,...,1;j=1,2,...,J>,距离出入库台最近的列记为第1列,最底层记为第1层。假设各个货位的长度、高度相同,货箱重量相同,每个货位重心位置位于该货位中心,并且忽略堆垛机的启动、制动时间以及存取货物操作时间,则固定货架的货位分配优化问题可以描述为:
 
自动化立体仓库的货位分配优化
 
    式中:i,j为第i列第J层的货位坐标;jG、jG为货架重心位置坐标;t为堆垛机存取货物的时间;Gij为第i列j层货位上物货重量;G0为整个货架最大承重能力l,h为每个货位的长度和高度v;为堆垛机的水平运行速度和垂直运行速度;sf。为第a列J层货位上货物存取频率t。为忽略堆垛机启动和制动的条件下,将第a列J层货位上的货物运送到巷道口所用的时间S为进行出入库操作的货物总数量。
    
    在固定货架的货位分配优化模型中,式(1)表示在水平方向货架重心尽可能靠近出入库台;式(2)遵循上轻下重的原则,保障货架稳定性,使货架重心位置最低;式(3)根据最短路线原则,满足对存取效率的要求,使堆垛机存取货物的时间最短,即离巷道口的出入库台的距离最短;式(7)表示货架存储货物的总重量不能超过货架的最大承重能力。由此可见,该优化问题是一个关于货架稳定性和出入库效率的组合多目标优化问题。
    
    3.2混合粒子群算法的货位分配思路
 
    3.2.1粒子群算法简介
  
    粒子群算法(Particle Swarm Optimization , PSO)作为一种新兴的进化算法,近年来发展迅速,在多目标优化、模式识别以及信号处理等领域得到了广泛应用。相对于遗传算法(Genetic Algorithm , GA)而言,二者都是基于群体的迭代搜索,PSO算法没有GA算法的“交叉”和“变异”操作,是通过个体之间的协作来搜寻最优解,以其具有的运算容易、精度高以及收敛快等优点引起了学术界重视,在解决实际问题中展示了其优越性。PSO算法的数学模型描述如下。
    
    设粒子(即入库货物通过初始化分配的货位)所在的搜索空间为D维(货位分配问题的搜索空间为粒子的求解空间),总粒子数为popsaze。xn=(xn1,xn2...,xnd,....xnD)为第n个粒子的位置(即第n个粒子的空间解);Pn=(pn1,pn2,...,pnd,...,pnD)为第n个粒子的当前最优位置,即第n个粒子的局部最优解,尸、为所有粒子到目前找到的最优位置,即全局最优解;Vn=(vn1,vn2,...,vnd,...,vnD)为第n个粒子的速度,代表位置变化量,如:Vndk表示从k-1次迭代到k次迭代时,粒子n位置在d维空间的变化值。粒子在寻优过程中通过式(8)、式(9)更新粒子的速度Vndk+1+和位置xndk+1为:
  
自动化立体仓库的货位分配优化
 
    式中:d为搜索空间维数,d=1.2....D;粒子n =1,2,…,popsaze;w为粒子的惯性权重,用以实现对粒子飞行速度的有效控制与调整;r1 r2为均匀分布在(0,1)之间的随机数,用来保持群体的多样性;k为到目前为止粒子反复寻优的迭代次数;C1C2=为学习因子,可调节粒子向自己的历史最优点以及群体内最优点靠近。
    
    第d(1小于等于d小于等于D)维的位置变化范围为[Xmin,Xmax],速度变化范围为[Vmin,Vmax},迭代中若位置和速度超过边界范围则取边界值。
 

3
本文来源于互联网,e-works本着传播知识、有益学习和研究的目的进行的转载,为网友免费提供,并以尽力标明作者与出处,如有著作权人或出版方提出异议,本站将立即删除。如果您对文章转载有任何疑问请告之我们,以便我们及时纠正。联系方式:editor@e-works.net.cn tel:027-87592219/20/21。