刘万强, 周亚勤, 杨建国, 尤 祥

(东华大学 机械工程学院, 上海 201620)

新型棋盘格密集仓库的出入库货位分配优化

刘万强, 周亚勤, 杨建国, 尤 祥

(东华大学 机械工程学院, 上海 201620)

从提升有轨自动化小车(RGV)出入库作业效率的角度出发, 在综合考虑RGV加减速和行走方向改变所带来的影响前提下, 对新型棋盘格密集仓库出入库复合作业模式下的货位分配问题进行研究, 设计了基于混合遗传算法的出入库货位分配算法, 以对货位分配问题进行求解.仿真试验结果证明,该算法能有效解决不同规模下新型棋盘格密集仓库的货位分配问题, 使RGV的整体作业效率提升40%左右, 并且具有货架规模越大则效率提升越明显的优势.

棋盘格密集仓库; 货位分配; 遗传算法(GA); 有轨自动化小车(RGV)

新型棋盘格密集仓库是一种由多层棋盘格货架(MCB)[1]和有轨自动化小车(rail guided vehicle, RGV)组成的新型自动化立体仓库.其作为一种全新的仓储模式, 既能满足货物的密集式储存, 又能满足货物的随机存取, 具有巨大的市场应用前景.在物流仓储行业中, 衡量自动化仓库好坏的重要指标是工作效率, 如何提升作业效率[2]成了新型棋盘格密集仓库亟待解决的问题, 而货位分配是实现自动化仓库高效运作的瓶颈.

国内外学者对自动化立体仓库的货位分配进行了大量的研究.肖建等[3]根据物料相关性及需求频率, 研究多巷道仓库货位分配的优化问题.杨朋[4]在提升堆垛机工作效率方面对多载具AS/RS(automated storage and retvieval system)的货位优化分配问题进行了研究. Chen等[5]根据停留持续时间的共享存储原则,对货位分配和交叉存取问题进行了研究.Pan等[6]提出一种基于启发式的遗传算法来求解货位分配问题, 通过平衡各采摘区的工作量来提高仓储作业效率.Onut等[7]在货位布局设计模型方面, 对降低仓库年运作成本进行了研究.

但目前对自动化立体仓库货位分配的研究仍存在一些不足.多数研究假设搬运设备为匀速运动, 未考虑加减速度或行走方向改变的影响, 难以体现实际的作业特点; 且目前多数研究仅单独考虑入库货物或出库货物的货位分配, 并没有考虑出入库复合作业模式下的货位分配. 因此, 本文从提升新型棋盘格密集仓库RGV作业效率的角度出发, 综合考虑RGV的加减速和行程方向改变的影响, 对新型棋盘格密集仓库出入库复合作业模式下的货位分配问题进行研究, 设计基于混合遗传算法[8-10]的出入库货位分配算法, 对出入库复合模式下的货位分配进行优化.

1 货位分配模型的建立

1.1货位分配优化问题的定义

新型棋盘格密集仓库主要由棋盘格立体货架、RGV和底层输送装置构成(如图1所示).其中, 棋盘格立体货架由货位和通道组成, RGV由母车和子车组成, 底层输送装置又由出库输送装置和入库输送装置组成, 出库输送装置连接所有通道, 入库输送装置仅连接入口通道.棋盘格立体货架是一个三维立体货架, 规模大小为M×N×K，其中M为总行数、N为总列数和K为总层数. 每个货位具有相同尺寸, 长和宽同为x, 高为h.通道用于RGV子车的纵向升降并抓取货物, 其中，入口通道既可用于货物的出库又可用于入库.

图1 多层棋盘格立体货架结构图Fig.1 Structure diagram of multilayers checkerboard based shelf

新型棋盘格密集仓库作业规则描述: (1) RGV母车在货架顶层行走; (2) RGV子车在货架通道中升降; (3) 棋盘格立体仓库在进行出库作业时, RGV母车到达出库货位的相邻通道, 子车通过通道运行到货物所在层取出货物, 并通过该通道将货物放置底层出库输送装置完成出库; (4) 进行入库作业时, RGV母车需先到达入口通道处, 通过子车抓取入库输送装置上的货物, 然后通过RGV母车运至目标货位的相邻通道, 子车通过该通道将货物放置目标货位完成入库; (5) RGV母车作业时存在4个过程, 分别是加速、匀速、减速和停止前的爬行, 且行程方向每改变一次就增加一次加减速和爬行过程.

出入库货位分配优化问题, 即根据需要出入库的货物信息和货架当前储存状态, 基于新型棋盘格密集仓库作业规则, 综合考虑RGV母车加减速和行走方向改变对RGV母车行走效率的影响, 合理分配货物的出入库货位, 并制定最优任务执行顺序, 使RGV在最短时间内完成所有出入库任务.

1.2约束条件

根据RGV承载能力限制、单个货位的存储量限制以及货架当前存储状态等基本信息, 建立货位分配问题的约束条件:

(1) RGV在货架顶层只能沿x、y轴方向直线行走;

(2) 一台RGV每次只能搬运一个货物;

(3) 货架中一个货位只能存放一个货物;

(4) 同种出库货物的数量应不大于仓库中该种货物的数量;

(5) 入库货物的数量应不大于仓库中的空货位数量;

(6) 入库队列和出库队列货物的种类已知, 且两个队列之间无相同种类货物, 否则直接从出库队列将货物取走, 无须进入仓库;

(7) 由于行程方向的改变会增加RGV的加减速次数, 从而降低RGV的整体行走效率.因此, 将RGV在起始点和目标通道间行走时的方向改变次数限制为一次.

1.3目标函数

货位分配的最终目标是使RGV以最短的时间toc执行完所有出入库任务, 因此以RGV作业时间的总和作为目标函数.由于RGV作业时间分为RGV母车顶层的行走时间和子车的升降时间, 所以需分别对两部分时间建立相应的函数模型并求和.建立目标函数模型将用到的变量符号及其定义如表1所示.

表1 变量符号及定义Table 1 Symbols and definitions

(1)RGV母车行走时间的计算模型.RGV母车在货架顶层行走时分为4个阶段, 如图2所示.由于RGV母车停止前的爬行位移极短, 可忽略, 将模型简化成三个阶段, 如图3所示.RGV母车行走时又存在两种行走状态：行走距离较短时, 达不到最大运行速度的状态; 行走距离较大时, 达到最大运行速度的状态.

图2 RGV母车速度-时间图Fig. 2 Graph of RGV car motion-time

图3 RGV母车速度-时间简化图Fig. 3 Simplified graph of RGV car motion-time

RGV在执行出入库任务时, 由于起始点和目标通道常常不在一条直线上, 导致RGV母车行走方向发生改变, 需沿x(y)轴方向行走后, 需再沿y(x)轴方向行走.因此, 在计算RGV母车行走时间时, 需对x、y两个方向分别计算并求和.RGV母车在起始点和目标通道间行走时间的计算模型如式(1)所示.

(1)

由于新型棋盘格密集仓库出库作业和入库作业的规则不同, 因此RGV执行出库任务和入库任务时, RGV母车的行走时间的计算方式不同.当RGV执行的第i个任务为出库任务时, RGV母车行走时间Ti为RGV母车从上一任务通道到出库目标通道的行走时间; 当RGV执行的第i个任务为入库任务时, RGV母车行走时间Ti为RGV母车从上一任务通道到入口通道的行走时间与从入口通道处到入库目标通道的行走时间之和.

(2) RGV子车升降时间的计算模型.RGV在进行连续的出入库混合作业时, 存在如表2所示的多种不同作业工况, 并且每一种工况下RGV子车的行程时间计算公式都各不相同.如RGV在执行出库任务时, 其前一任务为入库任务, 且前一任务与当前执行任务不在同一通道, 则RGV子车的行程路径如图4所示(虚线为子车路径), 此时可根据式(2)计算子车的行程.

(2)

图4 RGV子车行程路径图Fig.4 Travel path of RGV sub car

而当上一个任务为出库任务时, 由于上一任务的结束位置点在底层输送装置处, 则RGV子车的提升行程变为(K+1)×h, 所以其子车总的行程计算公式就变为式(3).

(3)

因此, 本文基于RGV子车多种作业工况, 建立子车行程时间的通用计算模型, 通过更改不同的参数来对应计算不同工况下子车的行程时间, 每种工况的参数(α,β,θ)值如表2所示.

表2 RGV子车行程时间参数Table 2 Travel time parameters of RGV sub car

(3) RGV执行完所有出入库任务所用时间的计算模型如式(4)所示.

(4)

由于RGV在执行第一个任务时, RGV子车起始点为货架顶层, 而其他任务的起始点不是在货架底层, 就是在上一个货物的入库货位处, 导致RGV子车执行第一个任务的起始点和其他任务起始点不同, 所以t1需要单独进行计算.

2 基于混合遗传算法的出入库货位分

配算法设计

新型棋盘格密集仓库的货位分配问题是一个组合优化问题, 主要依据RGV在某种货位组合下完成出入库任务时间的长短来评判该货位组合的优劣.在进行出入库任务时间计算之前, 还需对RGV的执行任务顺序进行优化排序, 采用传统的遗传算法无法同时对棋盘格密集仓库出入库货位分配优化问题和RGV任务执行顺序优化问题进行求解.因此, 本文设计基于混合遗传算法的出入库货位分配算法, 同时对以上两个问题进行求解, 采用遗传算法对出入库货位的分配方案进行寻优, 结合启发式排序算法对RGV任务执行顺序进行优化, 基于优化排序的结果, 根据式(4)计算RGV任务的执行时间, 并将时间的倒数作为遗传算法寻优过程中的适应度值, 整体的算法流程如图5所示.

2.1基于遗传算法的货位寻优

(1) 染色体编码设计.本文遗传算法的染色体采用货位编号进行编码, 编码根据货物种类分为多个片段.采用“入库货位+出库货位”的顺序排列, 其长度为入库货物数量和出库货物数量总和.为对出入库任务类型和货物的种类进行标识, 设计货物种类和任务类型的辅助字符串, 如图6所示, 任务类型的辅助字符串中, 0表示出库, 1表示入库.

图5 基于混合遗传算法的出入库货位分配算法流程图Fig.5 Flowchart of storage location assignment algorithm based on hybrid genetic algorithm

图6 染色体编码设计Fig.6 Design of chromosome coding

(2)初始种群生成.采用基于分片段货位数量限制的随机方法生成初始种群, 如图6所示，在保证每个片段中货位个数与对应的出库或入库货物数量相等的前提下, 从空位集合和存有该出库货物的货位集合中随机选取货位组成染色体.对于种群规模的选择, 取编码长度的2～4倍做为种群的规模.

(3) 染色体解码.染色体解码的目的是将货位编号转换成可用于适应度值计算的货位层坐标和相邻通道的行列坐标, 在每一条染色体随机生成前, 算法数据模型中已保存与每一种货物货位编号集合相对应的货位坐标集合.在随机生成染色体后, 根据染色体对应货位坐标, 在货架数据模型中搜索与货位相邻通道的行列坐标, 用通道的行列坐标取代货位的行列坐标, 从而实现染色体的解码.

(4) 适应度函数和种群选择.本文将RGV执行完所有出入库任务所需时间的倒数作为算法的适应度值.在计算RGV任务完成时间前, 需对RGV执行任务的顺序进行优化.本文采用启发式排序算法对RGV执行任务的顺序进行优化, 并根据经典轮盘赌的方法对种群的个体进行选择, 按照对应的概率分布选取染色体遗传到下一代.为了加速算法收敛, 采用精英保存策略, 将每代一定数量的最优个体强行遗传到下一代, 增加父体的选择压力, 提高最优个体被选中的概率.

(5) 交叉算子和变异算子.为了避免产生不可行解, 采用基于固定交配位的双亲双子方法进行交叉, 如图7所示, 随机选择1～T, 其中T为染色体编码按照设计结构划分的基因片段数(如上例中片段个数为4), 然后将待交配的两个父代的第t个基因片段进行交换, 其他基因片段不变, 产生两个子代.随机选择染色体片段中的某个货位, 用货架中与该片段相对应的可用货位替换该货位, 实现染色体的变异操作, 这种变异方法能够向染色体中添加新货位, 从而改变货位分配方案, 有利于丰富种群个体多样性.

图7 交叉操作Fig.7 Crossover operation

2.2启发式排序算法设计

对出入库任务进行排序的目的是为了减少RGV母车在顶层的行程和子车在通道内的行程, 从而增加RGV整体作业效率.为减少RGV母车在各目标通道间的行走路程, 可结合基于最近邻策略(NN)[11]的排序方法对RGV母车到达通道的先后进行排序, 且位于同一通道的任务由RGV母车连续执行. 而RGV子车在同一通道内执行多个任务时, 子车按照货位的层数从上往下执行任务, 所走路程最短.

基于以上棋盘格密集仓库RGV作业的特点, 进行出入库混合模式下的任务排序优化算法设计, 算法流程如下:

(1) 获取外层染色体的货位编号、解码得到的货位位置及相邻通道位置等信息;

(2) 循环比较出入库队列中第i～n, 将行列坐标信息相同的货位排在一起;

(3) 将(2)中相邻同一通道的货位按其所在层数, 从高到低依次排序, 高的货位排在低的货位前面;

(4) 将相邻同一通道的货位作为一个整体, 根据各个通道与RGV母车起始点之间的距离, 采用基于最近邻策略(NN)的排序方法, 对RGV母车到达各通道的先后顺序进行排列.

RGV按照以上出入库货位的排列顺序, 依次到达各个货位完成出入库任务, 调用式(4)计算RGV完成任务的时间.

3 测试案例与分析

选用货架规模为6×8×4棋盘格密集仓库进行案例测试, 其中，6为货架的行数, 8为货架的列数, 4为货架的层数.密集仓库共140个货位, 13个通道, 其中货位的长和宽均为0.4 m, 货位的高度为0.6 m, RGV母车在顶层行走的速度为2 m/s, 加速度为1.5 m/s2, RGV子车速度为1.5 m/s2.货位的状态分布如图8所示, 将三维货架分层展开, 其中, 图8(a)～(d)依次为为货架的第1～4层; 入口通道1个(32号货位右边), RGV停靠站1个(100号货位对应的货架顶层处); 其方格内字母表示所储存的货物类型, 带有编号且没有字母的方格表示为空货位, 白色的方格为通道.根据棋盘格密集仓库当前储存状态, 进行出入库作业.出库任务为货物A、B、C、G, 出库数量分别为3、3、2、1; 入库任务为货物D、E、F, 入库数量分别为2、2、1.

(a) 第1层

(b) 第2层

(c) 第3层

(d) 第4层

利用本文提出的混合遗传算法进行求解, 遗传算法种群规模取30, 交叉率取0.8, 变异率取0.1, 最大迭代次数取400.遗传算法寻优过程如图9所示.

图9 种群迭代变化曲线图Fig.9 Population iteration change curve

在算法迭代开始时的平均作业时间较大, 然后迅速下降, 染色体的择优速度很快, 在100次左右获得了稳定解, 且后续各代种群均被有效地控制在较优水平, 算法的运行时间为0.388 s, 算法运行效率很高.算法求解得到的RGV任务执行顺序为: E-G-D-C-C-D-B-B-B-F-A-A-A-E, 对应的出入库分配货位为: 98-125-126-132-27-26-130-25-19-48-76-83-88-66, RGV完成所有出入库任务的时间为67.35 s.

在不同货架规模下, 为测试算法对货位分配的优化效果, 设计如下试验数值: 仓库货架规模为12×16×4、18×20×6、24×26×8, 每种货架规模下随机生成20种货物的初始分布, 分别对每种试验方案进行50次仿真试验, 并与随机货位分配下RGV执行完出入库任务的时间进行对比, 对比结果如表3所示.从表3中数据可以看出，采用基于混合遗传算法的货位分配算法求解新型棋盘格密集仓库货位分配问题, 可以大大提升RGV作业效率, 且货架规模越大则效率提升越明显.从表3中最后一行可以看出, 在最大货架规模情况下, 算法平均运行时间为4.806 s, 算法运行效率很高.

表3 不同货架规模下RGV作业效率提升程度Table 3 RGV efficiency improvement on shelves with different sizes

4 结 语

本文对新型棋盘格立体仓库出入库复合模式下的货位分配问题进行了研究, 从提升RGV出入库作业效率的角度出发, 针对出入库货位选择和RGV任务执行顺序两个优化问题, 设计了基于混合遗传算法的出入库货位分配算法, 并且设计了多组试验数值来检验算法的求解效果.结果证明, 本文提出的算法能够有效地解决新型棋盘格立体仓库的出入库货位分配问题, 使RGV的作业效率得到大幅度提升, 算法运行效率很高, 并且具有货架规模越大则效率提升越明显的优势.

[1] 杨建国, 符鹏程, 吴平平, 等.多层棋盘格式立体货架及其货位排布算法研究[J].工程设计学报, 2015, 22(3): 211-218.

[2] 孙嘉炜.立体仓库出入库货位优化模型与算法研究[D].沈阳: 东北大学信息科学与工程学院, 2013.

[3] 肖建, 郑力.考虑需求相关性的多巷道仓库货位分配问题[J].计算机集成制造系统, 2008,14(12): 2447-2451.

[4] 杨朋. 多载具自动化存取系统货位分配与作业调度研究[D].北京: 清华大学工业工程系, 2011.

[5] CHEN L, LANGEVIN A, RIOPEI D. The storage location assignment and interleaving problem in an automated storage /retrieval system with shared storage [J]. International Journal of Production Research, 2010, 48(4): 991-1011.

[6] PAN C H, SHIH P H, WU M H, et al. A storage assignment heuristic method based on genetic algorithm for a pick-and-pass warehousing system [J]. Computers & Industrial Engineering, 2015, 81: 1-13.

[7] ONUT S, TUZKAYA U R, DOGAC B. A particle swarm optimization algorithm for the multiple-level warehouse layout design problem [J]. Computers and Industrial Engineering, 2008, 54(4): 783-799.

[8] 郑红星, 于凯.基于混合遗传算法的混堆箱区内场桥调度研究[J].交通运输系统工程与信息, 2013,13(5): 150-158.

[9] 马永杰, 蒋兆远, 杨志民.基于遗传算法的自动化仓库的动态货位分配[J].西南交通大学学报, 2008,43(3): 415-421.

[10] 马永杰, 云文霞.遗传算法研究进展[J].计算机应用研究, 2012,29(4): 1201-1206.

[11] 饶卫振, 金淳, 黄英艺.求解TSP问题的最近邻域与插入混合算法[J].系统工程理论与实践, 2011, 31(8): 1419-1428.

(责任编辑:杜佳)

OptimizationofAllocationAssignmentofNewCheckerboardIntensiveWarehouse

LIUWanqiang,ZHOUYaqing,YANGJianguo,YOUXiang

(College of Mechanical Engineering, Donghua University, Shanghai 201620, China)

In order to improve the efficiency of rail guided vehicle (RGV) in warehousing operation, allocation assignment has been carried out for the new checkerboard Intensive warehouse with the consideration of the influence of RGV acceleration and deceleration. Allocation assignment algorithm based on nested genetic algorithm is designed to solve the allocation problem. Simulation experiments show that the algorithm can effectively solve the allocation problem of checkerboard warehouse under various scales, so that the overall operating efficiency of RGV increased by about 40%, and the larger the shelf size, the more obviously the efficiency increases.

checkerboard intensive warehouse; allocation assignment; genetic algorithm (GA); rail guided vehicle (RGV)

K 826.16

A

1671-0444 (2017)04-0496-07

2017-04-05

上海市自然科学基金资助项目(15ZR1400600)；上海仓储物流设备工程技术研究中心资助项目(17DZ2283800)

刘万强(1992—)，男，四川资阳人，硕士研究生，研究方向为智能仓储.E-mail:987557046@qq.com

周亚勤(联系人)，女，副教授，E-mail: zhouyaqin@dhu.edu.cn