上海交通大学学报, 2022, 56(7): 858-867 doi: 10.16183/j.cnki.jsjtu.2021.283

电子信息与电气工程

考虑双端口布局的紧致化仓储系统堆垛机路径优化

闫青, 鲁建厦,, 江伟光, 邵益平, 汤洪涛, 李英德

浙江工业大学 机械工程学院,杭州 310023

Path Optimization of Stacker in Compact Storage System with Dual-Port Layout

YAN Qing, LU Jiansha,, JIANG Weiguang, SHAO Yiping, TANG Hongtao, LI Yingde

College of Mechanical Engineering, Zhejiang University of Technology, Hangzhou 310023, China

通讯作者: 鲁建厦,男,教授,博士生导师,电话(Tel.):0571-85290422;E-mail:ljs@zjut.edu.cn.

责任编辑: 王一凡

收稿日期: 2021-08-4  

基金资助: 国家重点研发计划(2018YFB1308100)
浙江省重点研发计划(2018C01003)
浙江省自然科学基金资助项目(LY18G020018)

Received: 2021-08-4  

作者简介 About authors

闫青(1989-),男,山东省济南市人,博士生,主要研究方向为智能仓储、布局规划和调度优化.

摘要

紧致化仓储系统是智慧物流技术领域内新兴的一种仓储技术,其最典型的特征是能够实现货物的多深位存储.研究该系统在双端口布局下堆垛机执行单一作业和复合作业并存的路径优化问题,并以堆垛机运行时间最短为优化目标建立该问题的数学模型.设计了遗传-集束搜索混合优化算法对模型进行求解,利用遗传算法得到的最优个体作为集束搜索的初始路径选择,避免算法陷入局部最优.通过算例仿真验证了模型与算法的有效性,验证结果表明,所建立的堆垛机作业路径优化模型与求解算法,能更好地适应双端口紧致化立体仓库出/入库任务调度要求,得到更为合理的堆垛机调度方案,提高存储效率.

关键词: 紧致化仓储系统; 堆垛机; 路径优化; 遗传算法; 集束搜索

Abstract

The compact storage system is a new storage technology in the field of intelligent logistics technology, and its most typical feature is that it can realize multi-depth storage of unit loads. In this paper, the path optimization problem of the co-existence of both single command (SC) and dual command (DC) operations of the stacker in the dual-port layout is studied, and the mathematical model of the problem is established with the shortest travel time of the stacker as the objective. A genetic algorithm (GA)-beam search (BS) hybrid optimization algorithm is designed to solve the model, and the optimal individual obtained by the GA is used as the initial path choice of the BS to avoid local optimum. The effectiveness of the model and algorithm is verified by numerical simulation, and the results show that the operation path optimization model of the stacker and the designed solution method can better adapt to the I/O tasks scheduling requirements in the compact three-dimensional warehouse with dual-port layout, get a more reasonable stacker scheduling scheme, and improve the storage efficiency.

Keywords: compact storage system; stacker; path optimization; genetic algorithm; beam search

PDF (2434KB) 元数据 多维度评价 相关文章 导出 EndNote| Ris| Bibtex  收藏本文

本文引用格式

闫青, 鲁建厦, 江伟光, 邵益平, 汤洪涛, 李英德. 考虑双端口布局的紧致化仓储系统堆垛机路径优化[J]. 上海交通大学学报, 2022, 56(7): 858-867 doi:10.16183/j.cnki.jsjtu.2021.283

YAN Qing, LU Jiansha, JIANG Weiguang, SHAO Yiping, TANG Hongtao, LI Yingde. Path Optimization of Stacker in Compact Storage System with Dual-Port Layout[J]. Journal of Shanghai Jiaotong University, 2022, 56(7): 858-867 doi:10.16183/j.cnki.jsjtu.2021.283

自动化仓储系统(Automated Storage/Retrieval Systems, AS/RS),又称自动化立体仓库,作为一种集存储、输送、拣选和管理等功能于一体的集成系统,在现代仓储中发挥着重要作用[1].然而随着电商快速发展和工厂向智能化转型,系统的工作效率及强度要求也在不断被推向新的高度,传统的仓储技术已经越来越难以应对日益增长的生产需求.加之城市化持续扩张导致土地供应不断下降,增加了土地和劳动力成本.所有这些因素都促使企业寻求更紧凑、更有效的仓储系统[2].紧致化仓储系统的出现有效解决了这些难题,该系统仍主要由一台传统的自动化堆垛机完成货物存/取任务,用以实现货物的水平和垂直运动,但在货架的深度方向,会有一台动力输送装置帮助实现货物的深度位移,有别于传统AS/RS只能实现单深位或双深位存储,也即紧致化仓储系统能够实现货物的多深位存储[3].本文研究一种考虑了双端口布局的紧致化立体仓库,相同空间条件下,该系统除了拥有更多的储位单元,更节省成本以外,还将拥有更高的柔性和吞吐量,因此得到了更为广泛的关注与应用.

目前,鉴于系统新颖性与复杂性,国内外众多学者针对紧致化仓储系统所开展的研究还主要集中在模型分析[2,4 -5]和货架设计[6-8],调度优化相关的研究尚处于起步阶段.堆垛机作为系统出/入库作业最主要的搬运工具,对其进行路径优化以提高作业效率,同样具有较高的实用价值和研究意义.以下可以通过综述传统AS/RS堆垛机调度相关的文献资料来为紧致化仓储系统寻求研究视角.

现有文献中,针对传统AS/RS堆垛机的路径优化问题,国内外有大量学者进行了研究.Kim等[9]对系统出/入库作业任务进行分析,以堆垛机行程距离最短为目标,采用一种改进启发式算法进行求解.Hsu等[10]在货物存储规模和订单数量不同的情况下建立堆垛机行程距离最短优化模型,提出采用基于订单批次处理的遗传算法进行求解.田国会等[11]以堆垛机拣选所有货位所耗时间最小为目标,提出一种结合Hopfield网络模型的遗传算法,求解得到了堆垛机拣选作业的全局优化路径.杨玮等[12]针对单巷道固定货架堆垛机拣选路径优化问题,建立以存/取时间最短为目标的数学模型,提出采用结合模拟退火算法的混合粒子群算法进行求解,提高了优化效率.以上关于堆垛机路径优化问题的研究主要针对堆垛机的单一作业方式,堆垛机的行程距离和行程时间是最常考虑到的两个优化指标.Kung等[13]以多堆垛机共享分拣巷道为主要研究问题,建立了堆垛机行程距离最短的动态规划模型,并采用一种快速排序调度方法进行求解,提高了系统分拣效率.Gharehgozli等[14]研究AS/RS中的出/入库作业排序问题,采用多项式时间算法,实现堆垛机总行程时间最小.包珊珊等[15]建立了考虑半托盘出库情况的堆垛机复合作业拣选路径优化模型,以堆垛机拣选时间最小为目标,采用离散烟花算法求解,实现算法的全局搜索和局部搜索.杨小明等[16]通过构建能耗成本、作业时间以及出货惩罚值最小为目标的堆垛机复合拣选作业优化模型,提出采用改进NSGA-Ⅱ算法进行求解.以上研究主要针对堆垛机的复合作业方式,但由于系统对象并未涉及出/入库端口的布局和分配,所以并不需要考虑堆垛机在交替执行出/入库任务时的起始点变化问题.

本文与以上针对紧致化系统研究及堆垛机调度研究的区别在于:① 目前研究同类系统的文献聚焦于模型分析和货架设计,本文则首次提出了双端口紧致化系统的堆垛机路径优化问题.优化过程不仅考虑了出/入库任务的操作排序及端口选择问题,同时也兼顾考虑了输送装置作深度位移对出/入库任务产生的影响.② 针对批次任务订单中出库任务与入库任务数量往往不对等的情形,提出了堆垛机执行单一作业和复合作业并存的混合作业模式,使堆垛机的路径寻优过程更加符合系统实际,也更具有现实指导意义.

紧致化仓储系统作为传统AS/RS的一种扩展和创新,在动力输送装置的协助下实现了货物的多深位存储,因此与传统AS/RS相比,又可概括为多深系统与单深系统的区别.但考虑到动力输送装置作深度位移只可能影响堆垛机的作业时间,不会影响行程距离,所以在研究该类系统堆垛机路径调度问题时,将堆垛机的行程时间作为调度指标进行描述要更为准确.因此本文从出/入?舛丝诜峙洹⒊?入库作业排序和出/入库作业路径的集成角度,以双端口紧致化立体仓库为研究对象,再考虑堆垛机采用混合作业模式时的运行特性,建立了出/入库任务时间调度模型,然后提出一种遗传-集束搜索混合优化算法(Genetic Algorithm-Beam Search, GA-BS)进行求解.利用遗传算法(Genetic Algorithm, GA)得到的最优个体作为集束搜索(Beam Search, BS)的初始路径选择,再按照正常BS算法流程寻求堆垛机的最优出/入库作业路径.

1 系统描述与假设

1.1 系统模型

图1为某双端口布局的紧致化仓储系统实例,该系统由货物出/入库子系统、堆垛机子系统和紧致货架子系统组成:① 货物出/入库子系统,由货物拣选台、出/入库输送装置及出/入库端口构成,实现出库或入库外围对接的功能;② 堆垛机子系统,由堆垛机和直行导轨构成,实现货物在货架上的存/取功能;③ 紧致货架子系统,由紧致化货架和货格内的动力输送装置(见图2)构成,主要实现货物存储以及货物在货架深度方向上的运动功能.

图1

图1   双端口紧致化立体仓库平面布局图

Fig.1   Plane layout diagram of compact storage system with dual-port


图2

图2   动力输送装置示意图

Fig.2   Schematic diagram of power conveyor


系统中,每相邻的两排货架产生1条巷道,巷道两端各设有1个出/入库端口.货架采用紧致化货格单元设计,每个货格单元内都包含一个动力输送装置,能够实现货物的多深位存储以及深度位移.相比传统AS/RS,双端口紧致化立体仓库具有以下优势:

(1) 作业效率高,双端口布局有效减少了堆垛机在巷道中的行走时间,提高了系统作业效率.

(2) 仓储密度大,紧致化货架以及动力输送装置的设计实现了多深位仓储,扩展了系统仓储密度.

(3) 投入成本低,紧致化货架在有效提升系统仓储密度的同时,也减少了堆垛机的投入数量以及可利用土地资源的使用成本.

1.2 堆垛机作业方式分析

堆垛机执行出/入库作业任务时通常有单一指令(Single Command, SC)和复合指令(Dual Command, DC)两种作业方式[17].一个作业周期内,堆垛机完成一次入库或一次出库的单一操作为SC作业;完成一次入库和一次出库的复合操作为DC作业,两种作业方式如图3所示.图中:x为货架的水平方向;y为货架的垂直方向;O为入库端口;R为出库端口;P为货位点;P1为入库货位点;P2为出库货位点.在批次出/入库任务订单中,出库任务和入库任务的数量往往不对等,尽管DC作业的效率更高,但堆垛机难免还是要执行部分SC作业.因此,为进一步提升作业效率,就要考虑如何规划出更加合理的DC/SC任务队列,使堆垛机完成出/入库任务的时间最小.本文即针对考虑双端口布局的紧致化立体仓库,提出了更加符合实际生产的DC/SC混合作业方式,并以此建立堆垛机的出/入库作业调度模型,进而对系统出/入库端口分配、出/入库作业序列和出/入库作业路径展开优化研究.

图3

图3   堆垛机作业方式示意图

Fig.3   Schematic diagram of operation mode of stacker


1.3 基本假设

为方便构建模型,通过分析相关设备的实际运行方式,对系统各项运行参数作如下设定:

(1) 紧致化货架共有X×Y个货格单元,其中X表示货架列数,Y表示货架层数;每个货格单元可以存放k件货物(图4k=5);货格单元的列宽为l,层高为h,深度为z.设第x列、y层货格单元内所有货位的坐标为(x,y),则左端口的坐标为(0,1),右端口的坐标为(X+1,1).

图4

图4   待出库货物货位示意图

Fig.4   Schematic diagram of the location of loads to be sorted


(2) 设堆垛机为单载运行,水平运行速度为vx,垂直运行速度为vy,两个方向均为恒速运行,忽略堆垛机的启动时间和制动时间.

(3) 设动力输送装置在深度方向上的运行速度为vz,亦为恒速.堆垛机执行任务先到达指定货格单元,输送装置再启动将货物运送至货格单元的前端,此时堆垛机会产生等待时间,但由于目标货物始终处于货格单元最前端或仅仅落后一个货位的位置,如图4所示,也即堆垛机的等待时间不会太长,所以将该时间统一假设为一定值.

由以上假设,可以得到堆垛机由某一货格单元位置P1(x1, y1)运行至位置P2(x2, y2)所需要的时间为

TP1P2=max x1-x2lvx,y1-y2hvy

堆垛机到达指定货格单元后的等待时间(定值)为

TW= zkvz

2 堆垛机作业调度模型

考虑双端口紧致化仓储系统的实际作业流程,所建立的堆垛机调度模型需要优化两个目标:① 对出/入库任务的操作序列进行合理排序;② 对堆垛机作业的出/入库端口进行合理选择.调度模型建立过程中,虽然堆垛机需访问的货物或货位在仓库两端各有一个端口可供选择,但从实际情况来看,不管是SC作业还是DC作业,其所对应的出/入库端口是由堆垛机执行该任务时所耗较少行程时间来决定的.

将堆垛机看作服务节点,系统完成批次订单任务的总作业时间可定义为堆垛机完成所有SC任务与所有DC任务时间之和.假设订单内有m个入库任务,n个出库任务,且m≠n.取

Z1=max{m, n}
Z2=min{m, n}

则该订单有Z2DC任务和Z1-Z2SC任务组成.堆垛机完成订单所有出/入库任务的总作业时间为

T= i=1Z1-Z2TSC,i+ j=1Z2TDC,j

式中:TSC,i表示堆垛机执行第i个SC任务所用的时间;TDC,j表示执行第j个DC任务所用的时间.

堆垛机执行第i个SC任务所用的时间可表示为

TSC,i= TIOa,Pi+ TPi,IOb+TWa,b∈{1, 2}

式中:TIOa,Pi表示执行第i个SC任务时,堆垛机由IOa端口运行至Pi货格单元的时间;TPi,IOb表示执行第i个SC任务时,堆垛机由Pi货格单元运行至距离较近的IOb端口的时间;IOaIOb代表左端口或右端口.

由此,堆垛机执行所有SC任务的总作业时间为

TSC= i=1Z1-Z2(TIOa,Pi+ TPi,IOb)+(Z1-Z2)TW

同理,堆垛机执行第j个DC任务所用的时间可表示为

TDC,j= TIOa,Pj+ TPj,Pj+1+ TPj+1,IOb+2TW

式中:TIOa,Pj表示执行第j个DC任务时,堆垛机由其中一个端口载货运行至Pj货格单元的时间;TPj,Pj+1表示堆垛机从入库货格单元Pj运行至出库货格单元Pj+1的时间;TPj+1,IOb表示堆垛机从出库货格单元Pj+1运行至距离较近的端口的时间.

由此,堆垛机执行所有DC任务的总作业时间为

TDC=j=1Z2(TIOa,Pj+TPj,Pj+1+TPj+1,IOb)+2Z2TW

综上可得,堆垛机完成订单内所有出/入库任务的总作业时间为

T=TSC+TDC=i=1Z1-Z2(TIOa,Pi+TPi,IOb)+ j=1Z2(TIOa,Pj+TPj,Pj+1+TPj+1,IOb)+(Z1+Z2)TW

则系统完成该批次所有订单任务时,堆垛机出/入库作业最优路径模型为

g(T)=min T

3 堆垛机作业调度算法设计

在研究双端口紧致化仓储系统堆垛机的路径优化问题时,计算的复杂性随着需访问的出/入库任务货位数的增多而增加,且堆垛机同时存在SC和DC两种作业方式,常规方法很难在这样的搜索空间寻找到最优解,而针对传统堆垛机系统所提出的一些智能算法又难以保证求解精度及优化效果.因此,在建立的出/入库作业调度模型的基础上,采用一种遗传-集束搜索混合优化算法进行求解,并结合系统过程仿真寻找堆垛机的最优路径方案.

3.1 集束搜索算法的思想

集束搜索作为一种启发式图搜索算法,其基本思想与分支定界法类似,区别则是集束搜索并不是对所有节点进行分支[18].为减少搜索所占用的空间与时间,算法在进行每一层深度扩展的时候,会尝试剪掉一些质量较差的节点.图5所示,首先设定集束宽度bBW=2,即从根节点开始,往下层扩展出去的3个节点会按某种规则进行评估,从中选出质量较优的2个节点作为束节点(染色节点),然后将这2个束节点作为搜索起始点,继续进行分支,选出最优的束节点后再进行分支,以此类推,直到获得满足条件的叶子节点.搜索结束后将得到bBW个可行路径,对比后选择最优的路径进行输出.

图5

图5   集束搜索示意图

Fig.5   Schematic diagram of beam search


集束搜索算法为寻找堆垛机最优作业路径提供了一种思路,即在一定程度上,能够剪掉一部分输出质量较差的路径,寻优效率较高.但这并不是说算法的寻优过程是与系统完全适配的.

3.2 遗传算法优化集束搜索

集束搜索在对堆垛机的作业路径进行选择时缺乏一定的约束性,即对每层节点进行评估时,只能发现前γ个满足条件的节点,即使该层还存在其他合适的节点也将不再被保留,搜索稳定性差,容易产生局部最优解.而遗传算法的收敛性较好,同时又具备良好的全局寻优能力,将其引入集束搜索以求解堆垛机的最优出/入库作业路径,能有效减小搜索范围,提高求解精度.

遗传算法部分的主要实现步骤如下.

(1) 编码设计.采用整数编码结构.具体设计过程:① 每批订单出/入库任务的优化由一条染色体代替;② 染色体上的基因数与出/入库任务的总数量相对应,每个基因允许由多个数字组成;③ 染色体上的每一个基因代表着每一个出/入库任务,该基因所在染色体的位置则对应出/入库任务在该处的编码.采用3个整数x,y,x'分别表示货架的列、层和出/入库端口,其中x'∈{1, 2}.现将某批订单的入库任务进行编号,组成一段编码;将出库任务在入库任务编号的基础上进行编号,组成另一段编码;同时将每个出/入库任务所对应的端口写入两段编码,分别用1、2表示对左右两个端口的选择.假设目前有2个入库任务和2个出库任务需要执行,(1, 1, 1)表示将编号为1的入库任务从左端口搬运到坐标为(1, 1)的货格单元中;(6, 2, 2)表示将编号为3的出库任务由(6, 2)货格单元处搬运到右端口,如表1所示.(1, 1, 1)(6, 2, 2)(3, 2, 2)(4, 2, 1)表示一条染色体上的基因,把该基因组合放在一起表示一条完整染色体,即批次出/入库任务的最优解,最优解序列如表2所示.

表1   出/入库订单任务对应编码

Tab.1  Encodings corresponding to I/O order tasks

入库任务编号对应数字编码出库任务编号对应数字编码
1(1, 1, 1)3(6, 2, 2)
2(2, 3, 2)4(2, 4, 1)

新窗口打开| 下载CSV


表2   出/入库订单任务最优序列

Tab.2  Optimal sequence of I/O order tasks

1324任务最优序列
(1, 1, 1)(6, 2, 2)(2, 3, 2)(2, 4, 1)(x,y,x')

新窗口打开| 下载CSV


(2)确定适应度函数.由于本文的目标函数为求堆垛机作业时间T最小,优化效果越好的个体,其目标函数值越小,所以需要在目标函数和适应度函数之间加以改进,使得优化效果越好的个体其适应度函数也越大.适应度函数设定为

f(T)=Cmax-g(T)

式中:Cmax为函数值相对较大的数,以保证f(T)为一正值.

(3) 选择算子.采用轮盘赌选择法选挑选个体,假设种群的规模为mpop,个体的适应度值为f(k),则每个个体被选择的概率p

p= f(k)k=1mpopf(k)

(4) 交叉算子.在本文的研究中,染色体上的每个基因代表着每个出/入库任务及其所对应的端口选择,因此在新生成的染色体中,原有的基因不能消失,也不允许重复,故采用如下交叉策略.

第1步,随机选择一对染色体(父代)中几个基因的起止位置(被选位置相同),具体操作如图6所示.

图6

图6   交叉操作I

Fig.6   Crossover operation I


第2步,交换以上两组基因的位置,如图7所示.

图7

图7   交叉操作II

Fig.7   Crossover operation II


第3步,根据映射关系将存在冲突的基因进行转换,映射关系如图8所示.

图8

图8   交叉操作 III

Fig.8   Crossover operation III


经过映射,生成如图9所示的新的子代染色体.

图9

图9   新子代染色体

Fig.9   New offspring chromosome


此外,还对交叉算子进行了自适应改进,使适应度值较小的个体能够拥有更大的交叉率得以实现个体改善,同时适当减小适应度值较大的个体的交叉率.具体表达式为

pc= pc,min+(pc,max-pc,min)×  fmax-fcfmax-favg,f>favgpc,max,ffavg

式中:pc,maxpc,min分别表示交叉率的最大值和最小值;fmaxfcfavg分别代表当代种群中的个体适应度最大值、被选中两个个体中的较大适应度值和种群适应度平均值.

(5) 变异算子.采用换位变异的方法,以某一较小变异率pm完成操作.

对于被选中进行变异操作的染色体,其上第u位基因存在pu∈[0,1],将适应度值最大的两个同任务类型基因进行互换,例如存在如图10所示的染色体X.

图10

图10   染色体X

Fig.10   Chromosome X


定义基因1~5位的变异率分别为:p1=0.01,p2=0.05,p3=0.02,p4=0.04,p5=0.03,则将第2、4位基因进行互换,变异后产生新染色体Y,如图11所示.

图11

图11   新染色体Y

Fig.11   New chromosome Y


此外,为增强局部搜索能力,在对指定的数位基因进行变异操作时,引入密集因子α (0.5<α<1)评估当代个体之间的离散程度.当代的平均适应度值和最大适应度值越接近,表明种群个体越集中,且当两者满足如下关系时,将原有的变异率增大ε倍,有表达式:

pm= pm,αfmax<favgεpm,

式中:pm是变异率设定值.

综上,经过选择、交叉和变异等操作,遗传算法可以输出较为理想的个体,从而为集束搜索提供初始路径选择,然后再按照集束搜索流程正常训练即可实现系统出/入库作业运行效率的优化,并求得堆垛机的最优作业路径.采用遗传算法优化集束搜索的整体流程,如图12所示.

图12

图12   遗传算法优化集束搜索流程图

Fig.12   Flow chart of genetic algorithm optimizing beam search


4 仿真验证

选取某企业实际使用的立体仓库为例进行仿真验证.该立体仓库采用上述双端口紧致化布局设计,订单拣选模式为固定货架批次拣选.每排货架有12层60列,共有12×60×2=1 440 个货格单元,货格单元的动力输送装置上设有5个货位,每条巷道共可完成 1 440×5=7 200 个货物的存储.左右两个出/入库端口的坐标分别标记为(0, 1)和(61, 1).系统各项运行参数如表3所示.

表3   系统运行参数

Tab.3  Operating parameters of the system

参数数值
货架货格纵深/m5.5
货架货格列宽/m1
货架货格层高/m1
堆垛机水平方向运行速度/(m·s-1)3
堆垛机垂直方向运行速度/(m·s-1)1
动力输送装置运行速度/(m·s-1)1

新窗口打开| 下载CSV


为验证已建立模型的有效性,选取系统10批次任务订单进行仿真实验,每批订单包含50个出/入库作业任务,其中一个批次的出/入库任务序列信息和对应货格坐标在表4中列出.货格属性值:0为入库作业命令,1为出库作业命令.表5为仿真实验与模型计算的对比结果.

表4   出/入库作业订单的任务序列和对应货格坐标

Tab.4  Task sequences and corresponding location coordinates of I/ O operation orders

编号坐标命令编号坐标命令
1(16, 7)026(43, 10)0
2(3, 8)027(32, 7)0
3(50, 2)028(41, 6)0
4(43, 7)029(21, 4)0
5(9, 2)030(49, 3)0
6(1, 12)031(44, 7)0
7(57, 5)032(29, 5)0
8(21, 8)033(7, 3)1
9(51, 7)034(58, 6)1
10(55, 2)035(8, 6)1
11(58, 12)036(55, 11)1
12(18, 8)037(37, 12)1
13(40, 6)038(40, 7)1
14(3, 4)039(15, 3)1
15(17, 6)040(36, 6)1
16(39, 5)041(29, 8)1
17(12, 9)042(35, 8)1
18(46, 10)043(39, 9)1
19(10, 8)044(18, 4)1
20(30, 2)045(48, 5)1
21(25, 12)046(33, 3)1
22(19, 5)047(9, 10)1
23(26, 1)048(11, 2)1
24(38, 4)049(29, 11)1
25(22, 9)050(18, 2)1

新窗口打开| 下载CSV


表5   仿真实验与模型计算结果对比

Tab.5  Comparison of the results of simulation experiment and model calculation

订单批次出/入库作业总时间/s误差率/%
仿真实验本文模型
1968.75912.766.13
2995.27939.385.95
3929.72988.145.91
4910.36979.567.06
5938.88999.496.06
6982.67921.336.66
7915.22983.126.91
8997.48929.267.34
9978.85918.106.62
10976.11923.735.67
平均959.33949.496.43

新窗口打开| 下载CSV


由表中实验数据可知,对系统50个出/入库任务进行仿真实验的平均作业时间为959.33 s,模型的计算结果为949.49 s,平均误差为6.43%.可以认为建立的堆垛机出/入库作业过程模型是有效的.

针对表4所列出/入库任务订单,采用GA-BS混合算法对其进行优化求解,同时以GA和BS算法为基准,验证该混合优化算法的优越性.设定混合算法中GA种群规模为 1 000,交叉概率pc=0.95,变异概率pm=0.05,设定BS束宽γ=10,评估函数为g(T),最大迭代次数为500.运用所建立的堆垛机作业调度模型进行优化仿真,堆垛机出/入库任务执行时间的优化曲线如图13所示.图中:η为算法迭代次数.

图13

图13   堆垛机执行时间优化曲线

Fig.13   Optimization curve of stacker execution time


由图可知,与GA和BS算法相比,GA-BS混合算法在求解双端口紧致化立体仓库出/入库任务调度问题的质量方面表现更优,能够使堆垛机更加快速高效地完成任务,且收敛速度较之BS算法也有很大提升.GA-BS混合算法在迭代至244代时达到最优,此时堆垛机执行所有出/入库任务的总时间为938.88 s,而如果不对订单序列进行优化,堆垛机执行所有出/入库任务的总时间为 1 569 s,优化后的执行效率提高了40.16%.

图14为优化后堆垛机执行所有出/入库任务所用时间最短的调度路径,该路径所对应的出/入库任务序列以及出/入库端口选择即为最优调度方案,如表6所示.

图14

图14   堆垛机执行任务最优调度路径

Fig.14   Optimal scheduling path for stacker to execute tasks


表6   出/入库任务序列及其对应的出/入库端口序列

Tab.6  I/O task sequence and its corresponding I/O port sequence

出/入库
序列
入库
端口
出库
端口
出/入库
序列
入库
端口
出库
端口
211*331*
372*321*
112*342*
362*42*
262*382*
411*242*
291*391*
441*191*
151*471*
402*221*
182*452*
491*72*
81*102*
422*282*
272*302*
351*92*
51*312*
481*132*
251*202*
432*21*
162*171*
462*231*
32*11*
501*121*
141*61*

注:1*、2*分别表示左出/入库端口和右出/入库端口.

新窗口打开| 下载CSV


由上述最优出/入库作业调度路径,可以得出堆垛机执行批次订单任务的运行序列:1*→21→37→2*→11→36→2*→26→41→1*→29→44→1*→15→40→2*→18→49→1*→8→42→2*→27→35→1*→5→48 →1*→25→43→2*→16→46→2*→3→50→1*→14→33→1*→32→34→2*→4→38→2*→24→39→1*→19→47→1*→22→45→2* →7→2*→10→2*→28→2*→30→2*→9→2*→31→2*→13→2*→20→1*→2→1*→17→1*→23→1*→1→1*→12 →1*→6→1*.

综上所述,本文所建立的出/入库作业调度模型适用于双端口布局的紧致化立体仓库,通过GA优化BS算法求解得到了堆垛机出/入库作业路径的最优解,并验证了该混合优化算法的有效性和优越性.

5 结语

本文针对双端口布局的紧致化仓储系统堆垛机调度优化问题,聚焦于新系统的出/入库任务排序和出/入库端口选择展开研究.主要成果有:

(1) 建立了以堆垛机完成出/入库任务总作业时间最小为评价标准的数学模型,提出更加符合实际生产的DC/SC混合作业模式,并通过对系统工作流程与运行特性的充分分析,将货物对端口的选择以及货物的深度位移综合考虑在堆垛机的调度模型当中,使路径寻优过程更加合理.

(2) 采用GA-BS混合算法对模型进行求解,利用GA较好的全局寻优能力和搜索特性对BS进行优化,将GA得到的最优个体作为BS的初始路径选择,提高了求解精度.算例仿真表明,与GABS相比,GA-BS算法能够更加准确地求解该类型仓储系统的出/入库作业调度问题,得到更优的堆垛机作业路径方案.

本文所述研究实现了双端口布局下紧致化仓储系统堆垛机的路径优化,但考虑到系统更适用于生产任务较大与货架货位数量较多的仓储环境,因此当批次出/入库任务序列更多时如何设计更有效的求解方法将会是后续研究的重点.

参考文献

欧阳永强, 张新艳.

考虑堆垛机加减速的节能自动立库设计

[J]. 浙江大学学报(工学版), 2019, 53(9): 1681-1688.

[本文引用: 1]

OUYANG Yongqiang, ZHANG Xinyan.

Design of energy-saving automated storage and retrieval system considering acceleration and deceleration of storage and retrieval machine

[J]. Journal of Zhejiang University (Engineering Science), 2019, 53(9): 1681-1688.

[本文引用: 1]

KOU X, XU G, YI C.

Belt-conveyor based efficient parallel storage system design and travel time model analysis

[J]. International Journal of Production Research, 2018, 56(23/24): 7142-7159.

DOI:10.1080/00207543.2018.1436784      URL     [本文引用: 2]

LE-DUC T, MBMD K, YU Y.

Optimal storage rack design for a 3-dimensional compact AS/RS

[J]. International Journal of Production Research, 2008, 46(6): 1495-1514.

DOI:10.1080/00207540600957795      URL     [本文引用: 1]

LIU D, MOU S, LU M, et al.

Travel time model of a new compact storage system

[J]. International Journal of Control and Automation, 2014, 7(7): 447-460.

DOI:10.14257/ijca.2014.7.7.37      URL     [本文引用: 1]

XU X, ZHAO X, ZOU B, et al.

Travel time models for a three-dimensional compact AS/RS considering different I/O point policies

[J]. International Journal of Production Research, 2019, 58(18): 5432-5455.

DOI:10.1080/00207543.2019.1659519      URL     [本文引用: 1]

YANG P, MIAO L, QIN L, et al.

The impact on designing storage rack for a multi-deep compact AS/RS on the speed profile of the storage and retrieval machine

[C]∥International Conference on Information Management, Innovation Management and Industrial Engineering. Xi’an, China: IEEE, 2013: 209-212.

[本文引用: 1]

HAO J, YU Y, ZHANG L, et al.

Optimal design of a 3D compact storage system with the I/O port at the lower mid-point of the storage rack

[J]. International Journal of Production Research, 2015, 53(17): 5153-5173.

DOI:10.1080/00207543.2015.1005767      URL     [本文引用: 1]

邓旭东, 张马萍, 吴应强, .

三维紧致化存储系统中货架尺寸的优化研究

[J]. 包装工程, 2019, 40(21): 173-178.

[本文引用: 1]

DENG Xudong, ZHANG Maping, WU Yingqiang, et al.

Optimization of rack dimensions of the 3D compact system

[J]. Packaging Engineering, 2019, 40(21): 173-178.

[本文引用: 1]

KIM B I, HERAGU S S, GRAVES R J, et al.

Clustering-based order-picking sequence algorithm for an automated warehouse

[J]. International Journal of Production Research, 2003, 41(15): 3445-3460.

DOI:10.1080/0020754031000120005      URL     [本文引用: 1]

HSU C M, CHEN K Y, CHEN M C.

Batching orders in warehouses by minimizing travel distance with genetic algorithms

[J]. Computers in Industry, 2005, 56(2): 169-178.

DOI:10.1016/j.compind.2004.06.001      URL     [本文引用: 1]

田国会, 张攀, 尹建芹, .

基于混合遗传算法的固定货架拣选优化问题研究

[J]. 机械工程学报, 2004, 40(2): 141-144.

[本文引用: 1]

采用一种结合Hopfield网络模型的遗传算法,解决了自动化立体仓库中固定货架拣选作业路径优化问题。在利用Hopfield/Tank神经网络的快速局部搜索能力的同时,又利用了遗传算法的全局寻优特性,有效地获得全局优化的拣选路径。仿真结果表明,算法能够满足待拣选货位点数目在较大范围内变动的要求。

TIAN Guohui, ZHANG Pan, YIN Jianqin, et al.

Research on optimization of fixed shelf selection based on hybrid genetic algorithm

[J]. Journal of Mechanical Engineering, 2004, 40(2): 141-144.

[本文引用: 1]

An approach of a genetic algorithm combined with Hopfield neural networks(HP NNs) is adopted to resolve the order-picking optimization problem in the automated warehouse. While HP NNs model is utilized with the property of high speed of local search, the global solution can also be well achieved. Experimental results verify that the requirement of wide range of the picking materials number can be satisfied.

杨玮, 李程, 傅卫平, .

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

[J]. 上海理工大学学报, 2015, 37(1): 84-88.

[本文引用: 1]

YANG Wei, LI Cheng, FU Weiping, et al.

Chosen path optimization for fixed shelves in AS/RS

[J]. Journal of University of Shanghai for Science and Technology, 2015, 37(1): 84-88.

[本文引用: 1]

KUNG Y, KOBAYASHI Y, HIGASHI T, et al.

Order scheduling of multiple stacker cranes on common rails in an automated storage/retrieval system

[J]. International Journal of Production Research, 2014, 52(3-4): 1171-1187.

DOI:10.1080/00207543.2013.848040      URL     [本文引用: 1]

GHAREHGOZLI A H, YU Y G, ZHANG X D, et al.

Polynomial time algorithms to minimize total travel time in a two-depot automated storage/retrieval system

[J]. Transportation Science, 2017, 51(1): 19-33.

DOI:10.1287/trsc.2014.0562      URL     [本文引用: 1]

包珊珊, 张敏, 尹健康, .

考虑半托盘出库的堆垛机复合作业拣选路径优化研究

[J]. 工业工程, 2019, 22(1): 90-99.

[本文引用: 1]

BAO Shanshan, ZHANG Min, YIN Jiankang, et al.

A research on the order picking optimization for stacker’s composite operation of semi-tray out of the automated warehouse

[J]. Industrial Engineering Journal, 2019, 22(1): 90-99.

[本文引用: 1]

杨小明, 徐子奇, 金雯, .

复合拣选策略下堆垛机作业序列优化问题

[J]. 计算机集成制造系统, 2021, 27(3): 933-942.

[本文引用: 1]

YANG Xiaoming, XU Ziqi, JIN Wen, et al.

Optimization of automatic stacker picking sequence under the mixed picking strategy

[J]. Computer Integrated Manufacturing Systems, 2021, 27(3): 933-942.

[本文引用: 1]

BASILE F, CHIACCHIO P, COPPOLA J.

A hybrid model of complex automated warehouse systems—Part I: Modeling and simulation

[J]. IEEE Transactions on Automation Science and Engineering, 2012, 9(4): 640-653.

DOI:10.1109/TASE.2012.2215322      URL     [本文引用: 1]

ARAYA I, MOYANO M, SANCHEZ C.

A beam search algorithm for the biobjective container loading problem

[J]. European Journal of Operational Research, 2020, 286(2): 417-431.

DOI:10.1016/j.ejor.2020.03.040      URL     [本文引用: 1]

/