自动化立体仓库固定货架拣选路径问题研究

杨 玮, 李 程, 傅卫平, 李雪莲

自动化立体仓库固定货架拣选路径问题研究

杨 玮1, 李 程1, 傅卫平2, 李雪莲1

(1.陕西科技大学机电工程学院,西安710021;2.西安理工大学机械与精密仪器工程学院,西安710048)

为提高自动化立体仓库拣选效率,以存取时间最短为目标,针对单巷道固定货架拣选作业过程,构建了解决拣选作业路径优化问题的数学模型,提出结合模拟退火算法的混合粒子群算法.该算法在求解过程中用粒子群算法初始化种群,提高了优化效率,缩短了搜索时间;在迭代过程中采用模拟退火算法,利用其概率突跳能力,以避免基本粒子群算法迭代过程中陷入局部最优和早熟收敛.通过实例验证,该算法比标准粒子群算法所用时间短、收敛速度快、迭代次数少.

混合粒子群算法;模拟退火算法;单巷道固定货架;拣选路径

固定货架拣选作业是自动化立体仓库调度的核心内容,也是影响自动化立体仓库效率的主要因素.合理安排拣选路径,能够减少堆垛机的工作量,缩短进出库的移动距离和作业时间,从而降低物流业务的成本,提高经济收益.国内外学者对自动化立体仓库系统的优化调度问题进行了大量的研究.王娴等[1]应用人工鱼群算法对自动化立体仓库的拣选作业优化问题进行了求解,并与遗传算法的优化结果进行了比较,证明此种算法得到了有效应用.黄杨波等[2]对自动化立体仓库拣选作业优化提出了一种免疫单亲遗传算法,仿真实验表明,这种改进遗传算法可行性好,且算法稳定性得到提高.方彦军等[3]采用最大最小蚁群算法克服了基本蚁群算法过早陷入局部最优的缺陷,对于求解自动化立体仓库拣选作业优化问题具有很好的效果.Sarker等[4]提出了一种基于控制和调度系统的混合智能方法,解决了自动化立体仓库固定货架拣选作业问题,证明了该方法求解此类问题的有效性.本文提出基于模拟退火的混合粒子群算法来解决自动化立体仓库拣选作业问题,并与PSO算法进行对比,通过实例验证了该混合粒子群算法的有效性和优越性.

1 单巷道固定货架拣选路径问题

1.1 问题描述

在固定货架系统中,若每条巷道内都配备有一台堆垛机负责同一巷道内相应两排货架的拣选作业,则这类问题称为单巷道固定货架拣选作业问题[5].

拣选作业过程描述:控制系统获得需求货单后,堆垛机携带空货箱从巷道口,或者说I/O台开始运行,对货单第一条目所对应的货位进行拣选操作;再向下一个被拣选货位运行,继续拣选;将货单中的所有条目拣选完毕后,堆垛机携带货箱返回I/O台,则一次拣选作业完成.

图1是单巷道固定货架结构示意图,出/入库台都设置在货架系统的同一端.图中x表示货架的列号,y表示货架层号,黑点表示需要堆垛机进行拣选作业的货位点,用坐标(X,Y)表示.将拣选出/入库台作为拣选作业的附加货位点,坐标表示为原点坐标.设每个货格长度为a,宽度为b,高度为h,且a,b,h均为常数.对于一个有n个货单条目的待拣选货单,问题的研究目标就是要寻找一条最优的货位拣选路径,使完成这个拣选订单n个条目所用总时间最少.

图1 单巷道固定货架结构示意图Fig.1 Schematic diagram of single aisle rack structure

1.2 数学模型

根据货物不同存取过程,为了简化研究,作出如下假设[6-7]:

a.堆垛机可在x轴(水平方向)和y轴(垂直方向)上同时运动且速度恒定,并设其运行速度分别为Vx和Vy,堆垛机的起止过程不作考虑;

b.堆垛机从货位中取货和放货时间设为常量Q和F,计算时可以忽略不计;

c.待拣选货单中的每个货位只进行一次拣选.

据上述假设,堆垛机开始拣选作业,拣选完货位i再对货位j进行拣选,操作过程所需时间为

式中,n为待拣选货单的货单条目数,即待拣选的货位总数;S表示待拣选的货位集合.式(2)要求堆垛机对货位进行拣选所用的时间最短;式(3)和式(4)是确保要求每个货位只被进行一次拣选;式(5)表示堆垛机进行拣选作业时,不能在拣选货位之间形成拣选回路,在拣选完所有的货位后返回拣选台.

2 混合粒子群算法解决拣选作业问题

2.1 基本粒子群算法

粒子群优化算法[8](particle swarm optimizer, PSO)是一种基于群智能方法的演化计算技术,最早由Kennedy博士和Eberhart博士于1995年提出.其原理可简单地表述为:每只鸟(粒子)在自己最优位置的基础上通过追踪有限个处于当前最优位置的邻居,逐渐向食物目标位置靠近.

数学模型表达如下:粒子的种群表示为X=(X1, X2,…,XN),粒子飞过的每个位置Xi=(xi1,xi2,…, xiD)T都对应于一个问题的解;飞行速度Vi=(vi1, vi2,…,viD)T,粒子飞行的过程就是搜索的过程;粒子在迭代过程中的最佳位置Pi=(Pi1,Pi2,…,PiD)T,种群迭代的最佳位置为第g个粒子的最优位置,表示为Pg.粒子的位置和速度更新公式为

式中,d是寻优空间维度,d=1,2,…,D;i为粒子群体数目,i=1,2,…,N;m为迭代次数;c1,c2为学习因子,也称加速系数,使粒子具有向群体中较优粒子学习的能力,从而向个体极值和全局极值方向靠拢;r1和r2为(0,1)上均匀分布的随机数,以保证粒子种群的多样性.对于位置和速度的更新变化,可以限定其变化范围,当更新值超过了其边界范围时,取其边界值.

2.2 模拟退火粒子群算法

模拟退火算法(simulated annealing,SA)是基于Monte Carlo迭代求解策略[9-10]的一种随机寻优算法,其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性.从某一较高初温出发,伴随温度参数的不断下降,结合概率突跳特性在解空间中随机寻找目标函数的全局最优解.基于模拟退火算法的混合粒子群算法的寻优策略是,求解过程中用粒子群算法初始化种群,利用模拟退火算法概率突跳的特性,求解全局最优解.混合粒子群算法的计算步骤如下:

a.根据编码思想对粒子种群进行初始化.利用公式

计算初始温度t0.式中,f表示目标函数值;fPg为初始种群中的全局极值.

b.确定适应度函数.

c.计算粒子的适应度值,由Pi相对于Pg的突跳概率公式

确定.式中,r为退温速率;m为迭代次数;tm为m代时的温度.根据式(6)和式(7)更新粒子的速度与位置,计算新粒子的适应度值,由步骤c确定最优粒子位置Pgl,完成退温循环.

e.循环过程完成后,得出最优结果.

结合模拟退火的粒子群算法流程如图2所示.

图2 混合粒子群算法的流程图Fig.2 Flow chart of SAPSO

3 基于混合粒子群算法拣选路径的实现

3.1 参数设定[11]

设一个自动化立体仓库固定货架的组成为10排72列,每排10层共720个货位;货架长度a= 1 m,宽度b=1 m,高度h=1 m;堆垛机水平运行速度Vx=3 m/s,垂直运行速度Vy=1 m/s;算法中最大迭代次数取mmax=800.需拣选的80个货位坐标如表1所示.

表1 80个货位点的实验数据Tab.1 Experimental data of the 80 cargo sites

3.2 实验结果及算法比较

采用整数编码[12-13]求解种群粒子及其速度,将待拣选的货位坐标设置为一个2维矩阵,矩阵的列由待拣选货位的货位数决定,以此矩阵作为编码思想中的源数据,进而粒子以向量的方式进入算法优化流程[14].针对不同的算法参数进行实验,平均运行30次,实验结果如表2所示.对于80个货位的拣选路径优化结果和算法收敛效果对比如图3和图4 (见下页)所示.

表2 两种算法性能比较表Tab.2 Performance comparison between the two algorithms

从图4可以看出:模拟退火粒子群算法的收敛速度快,迭代次数少,充分验证了利用该算法求解自动化立体仓库拣选路径优化问题的可行性.从表2可以得出,随着货位数的增加,混合粒子群算法的收敛性明显提高,优化效果更为显著,算法的应用效果更好.

图3 两算法货位拣选路径优化结果图Fig.3 Chosen path optimization results by the two algorithms

图4 两算法收敛效果对比图Fig.4 Convergence comparison between the two algorithms

4 结 论

针对单巷道路径拣选作业问题,将实际问题抽象为可以进行算法实现的数学模型[15-16];提出的混合粒子群算法兼有粒子群算法优化效率高、模拟退火算法概率突跳的优点,在求解大规模货物拣选作业优化问题时收敛速度显著提高,优势明显,可行性强.通过对80个货位拣选路径的分析,与标准粒子群算法对比,结果显示混合粒子群算法收敛速度快、迭代次数少,进一步验证了该算法的可行性和有效性.但是,算法的稳定性有待提高.因此在后续的研究中,将通过对算法中参数设置的调整,来提高算法的稳定性,并进一步将该算法应用到多巷道路径拣选作业中及其它组合优化问题中.

[1] 王娴,杜亚江,栾睿.基于人工鱼群算法的拣选作业优化问题[J].兰州交通大学学报,2012,31(1):123-126.

[2] 黄杨波,刘万军,丁鹏,等.基于免疫单亲遗传算法的拣选作业优化[J].计算机工程,2011,37(11):206 -208.

[3] 方彦军,谢宜净.基于MMAS算法的计量检定中心仓储堆垛机拣选路径优化[J].武汉大学学报(工学版), 2013,46(5):645-648.

[4] Sarker R,Omar M.Hybrid evolutionary algorithm for job scheduling under machine maintenance[J].Applied Soft Computing Journal,2013,13(3):1440-1447.

[5] 田国会,张攀,尹建芹,等.基于混合遗传算法的固定货架拣选优化问题研究[J].机械工程学报,2004,40 (2):141-144.

[6] 谢树新.自动化立体仓库拣选作业路径优化方法研究[D].苏州:苏州大学,2010.

[7] 庞龙,陆金桂.基于蚁群遗传算法的自动化立体仓库拣选路径优化[J].计算机工程与科学,2012,34(3): 148-151.

[8] 江涛.改进的粒子群优化算法[D].长春:吉林大学,2013.

[9] Yang W Q,Deng L,Fei M R,et al.Multi-objective automated warehousing scheduling based on improved tabu search[J].Computer Integrated Manufacturing Systems,2013,19(8):2097-2104.

[10] 谢旻.一种混合粒子群优化算法在TSP中的应用[J].太原理工大学学报,2013,44(4):506-509.

[11] Khalid H,Beatrix B.Integration of products expiry dates in optimal scheduling of storage/retrieval operations for a flow-rack AS/RS[J].International Journal of Industrial and Systems Engineering,2013, 15(2):216-233.

[12] 傅家旗,叶春明.求解旅行商问题的混合量子算法[J].上海理工大学学报,2010,32(5):466-470.

[13] 陆园,洪跃.多目标下的自动化立体仓库拣选作业路径优化[J].机械制造,2012,50(3):84-87.

[14] 陈义雄,梁昔明,黄亚飞.一种改进的混沌量子粒子群优化算法[J].计算机工程,2013,39(8):253-256.

[15] 周蓉,叶春明.基于粒子群的多目标多执行模式项目调度[J].上海理工大学学报,2013,35(1):27-32.

[16] 贾建芳,杨瑞峰,王莉.混合遗传粒子群优化算法的研究[J].自动化仪表,2013,34(9):1-3.

(编辑:丁红艺)

Chosen Path Optiomization for Fixed Shelves in AS/RS

YANGWei1, LICheng1, FUWeiping2, LIXuelian1
(1.College of Mechanical&Electrical Engineering,Shaanxi University of Science&Technology,Xi’an 710021,China; 2.School of Mechanical and Precision Instrument Engineering,Xi’an University of Technology,Xi’an 710048,China)

To improve the order picking efficiency and shorten storage time in Automatic Storage &Retrieval System(AS/RS),a mathematical model was constructed to solve the problem of picking path optimization.According to the operation character of the order picking of fixed shelf storage area in a single roadway,an hybrid particle swarm algorithm combined with simulated annealing algorithm was presented.In the solution process,particle swarm optimization(PSO)was used to initialize the swarm,so as to improve the searching performance of the algorithm and optimize the results.The method can improve the optimization efficiency and shorten the searching time.In the iterative process,the simulated annealing algorithm was used to avoid premature convergence and to prevent from getting into local optimum as in the conventional PSO due to its probabilistic jumping ability.The examples show that compared with the standard PSO,the algorithm has the merits of shorter calculation time,faster convergence and fewer times of iterations.

hybrid particle swarm algorithm;simulated annealing algorithm;a single roadway fixed shelves;chosen path

TP 18

A

1007-6735(2015)01-0084-05

10.13255/j.cnki.jusst.2015.01.015

2014-04-10

国家自然科学基金资助项目(11072192);陕西科技大学科研启动基金资助项目(BJ12-21);国家级大学生创新创业训练计划资助项目(201210708037);陕西省农业科技创新与攻关项目(2014K01-29-01);陕西省科技厅基金资助项目(14JK1093)

杨 玮(1972-),女,副教授.研究方向:现代物流系统工程与技术、工业工程.E-mail:yangwei613@126.com