基于带精英策略的非支配排序遗传算法的多层穿梭车仓储系统建模与优化

发布时间：2017-04-10 15:38

 

【摘要】 随着物流行业对于仓储配送的柔性和鲁棒性要求的提高,一种新型的自动化立体仓库——多层穿梭车仓储系统逐渐得到重视和应用。多层穿梭车仓储系统是由多层货架内的穿梭车与该巷道的提升机组成,出入库作业时用穿梭车与提升机的组合来替代传统自动化立体仓库中的堆垛机,提高了系统的柔性和鲁棒性。该新型仓储系统根据穿梭车能否跨层运动分为单层作业和跨层作业两种类型。本文以单层作业的多层穿梭车仓储系统为研究对象,分析其出库任务作业的运动过程和交接次序,建立出库作业任务完成的时间模型,综合运用开环排队网络、蚁群聚类算法和基于Pareto最优解的带精英策略的非支配排序遗传算法(NSGA-Ⅱ),从储位优化和任务调度两个方面对多层穿梭车仓储系统进行优化研究。本文的主要研究内容和成果如下：(1)分析多层穿梭车仓储系统的作业流程,在考虑各个设备运动特性的基础上,建立了基于并行取货、串行出库的作业时序数学模型,分析了作业时序数学模型的主要影响因素,并对其分别进行详细阐述说明。(2)建立开环排队网络模型分析多层穿梭车仓储系统,利用分解法分析设备配合作业的空闲时间和系统表现,利用品项间相关性和蚁群聚类算法形成初始储区。再设计相应存储原则,在二维平面内排列组合相应储区。最后将该算法应用到某配送中心的多层穿梭车仓储系统的货位分配问题中。(3)基于并行取货、串行出库的作业时序数学模型,分别对提升机和穿梭车进行分析,从而建立起以出库时间、提升机空闲时间和穿梭车等待时间最小为目标的任务调度模型,运用基于Pareto最优解的带精英策略的非支配排序遗传算法(NSGA-Ⅱ)进行模型求解。最后,为验证模型及算法的有效性,本章以某省电力公司电力仪表仓库实际出库单据为实验对象,确定最优的任务调度方案。最后,本文在单层作业的多层穿梭车仓储系统建模与优化基础上,对跨层作业的多层穿梭车仓储系统进行了分析和展望。 

第一章绪论

1.1引言
自动化立体仓库（Automated Storage and Retrieval System, AS/RS)是信息技术和工业生产飞速发展的产物，是物流作业全流程中具有重要意义的节点。现阶段，大多数自动化立体仓库是由负责存储货物单元（Stock Keeping Unit，SKU)的几层、十几层乃至几十层高层货架系统和能在二维空间按欧式轨线高速运行的堆操机组成。自动化立体仓库具有占地小、容量大、周转率强、准确率高、自动化程度高、环境适应能力强等特点，在机械、冶金、烟草、电子、医药等行业得到广泛应用，成为现代物流业仓储与配送不可缺少的重要组成部分[1]。
然而在传统自动化立体仓库中，这种由堆操机负责货物存取的方式存在两方面的不足。一方面是鲁棒性不强，，当堆躲机发生故障时，其所服务的巷道随即处于瘫痪状态，无法继续进行相应的出入库作业，且一般不存在备用设备，只能停机维修造成停工。另一方面是柔性不足，当传统堆躲机式的自动化立体仓库设计建造完成后，其出入库能力随之固定。随着电子商务的发展和定制化服务的深入，产品生命周期不断缩短，小批量、多批次、多品种、高时效特点的订单不断增多，使得现代企业的生产需求原则从“可靠性第一”逐渐转变成“柔性第一”。
此情况下，一种由负责水平运动的轨道导引车辆(Rail Guided Vehicle, RGV)和负责垂直运动的提升机（Lift)共同组成的新型仓储系统一一自动小车存取系统（Autonomous Vehicle Storage and Retrieval Systems, AVS/RS)于 2000 年左右在欧洲、美国等地开始陆续投入使用。该系统融合了自动导引车辆系统(Automated Guided Vehicle, AGV)的柔性和传统堆垛机式自动化立体仓库的高速出入能力，被认为是自动化立体仓库的发展方向[2]。在自动小车存取系统中，其每一层货架均有一辆或多辆轨道导引车辆，因此系统不会由于某辆车的故障而全线停机，使其柔性要远高于传统堆垛机式的自动化立体仓库[3]。
但是，自动存取小车系统也存在着其相应的弊端。一方面，该自动小车存取系统更适用于标准托盘化的货物仓储，即单次出入的货物单元内存货数量多，难以应对以周转箱为主要存储单元的小规格、多频次的存取需求；另一方面，每层货架上均有一辆或多辆小车，对车辆管理系统的调度、控制、防堵塞等方面要求高，存在着控制系统繁复、成本巨大等问题。因此，上述原因也限制自动小车存取系统的大量应用。
为了解决上述难题，在自动存取小车系统的基础上，另一种新兴的简化的自动化仓储系统应运而生，这就是多层穿梭车仓储系统（Multi-tier ShuttleWarehousing System, MSWS)。该系统既很好的解决自动存取小车系统难以适应以周转箱为主的小规格货物高频次存取问题，其简洁的系统设计又能使控制调度系统易于实现，降低信息管理系统与设备控制系统的开发难度以及设备调度过程中可能的出错率。随着顾客的订单日趋呈现多批次、小批量、多频次的趋势以及电子商务环境下对高效顾客订单履行的迫切需求，物流行业对于仓储配送的柔性化要求的日渐提高，该系统得到越来越多物流厂商的重视，并在医药、烟草等领域得到应用，例如Dematic公司的Multishuttle、Knapp公司的OSR Shuttle以及 Vanderlande 集团的 QUICKSTORE HDS shuttle system 等。
............................

1.2多层穿梭车仓储系统简介
由于多层穿梭车仓储系统是由自动小车存取系统简化演变而来，所以有必要首先介绍自动小车存取系统。如图1-1所示，自动小车存取系统是由高层货架、轨道导引车辆、提升机以及铺满货架间隙的轨道组成。在传统自动化立体仓库中，出入库作业是由巷道中一个能够同时进行垂直运动和水平运动的堆操机完成，到达出库货位的时间为提升机垂直运动和水平运动分别所用时间的最大值。而在自动小车存取系统中，货物出入库所需的垂直运动和水平运动被分开成依次执行。从水平方向看，用轨道导引车辆来代替堆燥机完成巷道内的水平运动作业，利用车辆自身装置完成叉取/出货物作业；从垂直方向看，由一台或多台提升机完成货物或者轨道导引车辆的垂直方向移动。自动小车存取系统从一定意义上弱化了巷道的概念，每两排货架之间不再强制性要求设置一个巷道，当轨道导引车辆需要跨巷道作业，可以利用排与排之间的横向巷道来完成，以此来实现货物的密集存储。提升机的设计既可以用来运输货物单元，也可以将载货状态的轨道导引车辆运输到出入站台，又可以将空载状态的轨道导引车辆运送到某缺少轨道导引车辆的层内。因此，根据自动小车存取系统中轨道导引车辆是否能够借助提升机实现跨层作业，将其划分为单层作业和跨层作业两类。

如图1-2所示，多层穿梭车仓储系统是在自动小车存取系统基础上演变而来，其用穿梭车（shuttle)来代替能够在整个水平平面运动的轨道导引车辆，保留了传统堆採机式的自动化立体仓库中巷道概念。在多层穿梭车仓储系统内，每一层只有一辆穿梭车，每台提升机只负责一个巷道内垂直运动，穿梭车不能跨巷道运动，用组合式的“穿梭车+提升机”来代替了堆探机。

与自动小车存取系统的分类方式相同，多层穿梭车仓储系统根据其穿梭车能否在提升机的帮助下实现换层作业，可以分为以下两类：
单层作业的多层穿梭车仓储系统（Tier-captive Multi-tier ShuttleWarehousing System, TCMSWS ）
跨层作业的多层穿梭车仓储系统（Tier-to-tier Multi-tier ShuttleWarehousing System, TTMSWS ）
在单层作业的多层穿梭车仓储系统中，每一层均有一辆穿梭车。以执行出库作业为例，该层的穿梭车首先水平运行到相应出库货位，利用自身的货叉取出货物单元，然后再水平运行至该层首列向提升机申请调度服务，该服务请求被加入提升机的任务队列。如提升机当前没有执行其他相应任务，提升机将响应该调度服务请求，垂直运动至该层，进而与穿梭车完成货物单元交换，再由提升机将货物单元运送到I/O站台，而穿梭车则执行下一条该层出库任务，循环往复。
..............................

第二章多层穿梭车仓储系统建模

多层穿梭车仓储系统的运行设备与传统的自动化、):体仓库有着很大的区别，尤其是出入库任务调度方面。因此，本章以单层作业的多层穿梭车仓储系统完成出库任务为例进行分析，建立出库作业时间模型，分析影响作业效率的重要因素。

2.1系统描述与作业流程
单层作业的多层穿梭车仓储系统的作业模式不同于传统堆採机式的自动化立体仓库，其每层均由穿梭车来完成货物的水平移动和货位存取，再统一经由提升机来实现货物单元的垂直方向移动，如图2-1。在该系统中，出入库作业由并行运动的穿梭车和顺序执行的提升机共同完成，在一定程度上提高了作业效率。

如同传统的自动化、y.体仓库一样，多层穿梭车仓储系统也存在简单作业模式和复合作业模式。在简单作业模式下，该型仓储系统只执行出库任务或只执行入库任务；在复合作业模式下，该型仓储系统可以在某一层实现入库作业，而同时在另一层实现出库作业。在实际仓储作业中，入库作业和出库作业往往存在不同的时间窗，因此，本文的所有分析均基于简单作业模式，即在该型仓储系统的分析过程巾，只存在出库作业或者入库作业。此外，项0运营中存在不同的设备调度规则，例如：“先到先服务”、“优先权服务”、“随机服务”和“后到先服务”等。本文以穿梭车和提升机双方均遵循“先到先服务”（First Come FirstService, FCFS)的调度原则。
在此基础上，以出库作业为例，多层穿梭车仓储系统出库作业流程如图2-2:

在单条出库任务执行时，首先进入对应层的穿梭车任务队列等待空闲状态的穿梭车。当穿梭车按照FCFS规则执行该任务后，首先水平运动到相应出库货位，利用自身货叉从货位上取出对应货物，再水平运行到该层首列向提升机申请调度服务并等待提升机响应。若提升机此时空闲则会立即响应服务并前往该层与穿梭车完成货物交接。交接完成后的穿梭车再次进入空闲状态等待任务分配，而提升机则继续垂直运动将货物运送到I/O站台，两者间的货物交接见图2-3。
...........................

2.2作业效率影响因素
通过上文分析，我们可以将影响多层穿梭车仓储系统作业效率的主要因素为两个部分：（1）硬件设计方面，包括穿梭车最大速度Vp提升机最大速度TV和货架层列比等；（2）运营管理方面，包括储位分配和任务调度。下文对影响仓储管理水平和作业效率的因素进行理论性概要分析。
(1).穿梭车最大速度vA
多层穿梭车仓储系统出库作业可以类比成流水线作业调度，增加穿梭车最大速度，能够缩短第一个出库任务申请提升机调度服务的时间。同时，穿梭车提速后使得申请提升机调度任务的时刻提前，在其他因素不变的前提下有助减少提升机的空闲时间。
(2).提升机最大速度Vy
所有的出库任务均需要提升机完成最后一步，因此提升机的运行速度与整体作业效率有着重要意义。提升机提速后能够减少完成单次任务完成时间，从而有效的提高单位时间内所服务的穿梭车申请任务数。
(3).货架层列
比在总库存量一定的情况下，货架系统的不同的层列比也对作业效率有着影响。在传统自动化立体仓库中，立库货架长高比为SIT (Square in Time)时堆燥机出入库效率最高，此时堆操机的到达最远端货位的水平方向用时与垂直方向的用时相同[5]。但是，对于多层穿梭车仓储系统而言，一方面，随着层数（穿梭车数量）的增多，一定时间段内提升机调度服务的申请数量增多，能够减少提升机的空闲时间；另一方面，随着列数的增多，不同层穿梭车完成水平运动的时间差值会增大，防止较短时间内出现多辆穿梭车申请提升机调度服务的情况，减少穿梭车等待时间。
(4).储位分配
在传统堆躲机式旳自动化立体仓库中，常见储位分配策略有共享存储、分类存储、随机存储和定位存储等，大多基于货物全周转率或者订单体积指数的分配原则。在多层穿梭车仓储系统中，这些原则并不完全适合。一方面，高频率货物均靠近I/O点会造成穿梭车申请提升机任务时刻集中，造成穿梭车等待时间变长，车辆利用率降低；另一方面，仅仅考虑货物自身属性而忽略了品种间关联性，也会影响货物分配的效果。因此，在多层穿梭车仓储系统中，储位分配是依据最小化提升机空闲时间和最大化穿梭车利用率的原则进行。
(5).任务调度
传统堆垛机式的自动化立体仓库的任务调度研究大多将此类问题归结为旅行商问题，即如何在复合作业模式下有效的将两个或多个货位出库任务进行组合，从而减少堆躲机行驶路程。在多层穿梭车仓储系统中，减少提升机的空闲时间要求两个或多个穿梭车申请提升机调度的时刻差正好满足提升机完成上一任务，而不是简单的两个出库任务路径之和最短。
..............................

第三章多层穿梭车仓储系统储位优化........................................ 19
3.1问题描述........................................ 19
3.2开环排队网络........................................ 20
3.3基于蚁群聚类的储位分配........................................ 25
3.3.1存储策略........................................ 25
3.3.2传统自动化立体仓库储位优化模型........................................ 26
3.3.3基于聚类分析的储区划分........................................ 27
3.3.4蚁群聚类算法........................................ 28
3.3.5储位分配........................................ 32
3.4实例分析........................................ 33
3.5本章小结........................................ 37

第四章多层穿梭车仓储系统任务调度

4.1问题描述
在多层穿梭车仓储系统中，提升机和穿梭车的服务规则为“先到先服务”(First-Come-First-Serve, FCFS)。当执行出库作业时，由不同层上的穿梭车并行完成取货任务，再由提升机串行顺序将货物出库到I/O站台。当多个穿梭车与一个提升机进行任务交接时，会出现两种不同类型的交接时间：穿梭车的等待时间和提升机的空闲时间。当穿梭车完成水平取货作业后，将会申请提升机调度服务，若此时提升机正在执行其他任务，则此穿梭车申请的调度5艮务将会放入提升机任务队列中，穿梭车处于等待服务状态直到提升机响应该申请，此段时间为穿梭车的等待时间；若此时提升机处于空闲状态，会立即响应穿梭车申请的调度服务，但是提升机从上一次响应服务到本次响应服务的这段时间内处于空闲状态，此段时间为提升机的空闲时间。
由于所有出库任务最终均由提升机顺序串行完成，依前文分析，多层穿梭车仓储系统执行出库任务作业时可看作流水线作业模式，其总出库任务完成时长等于出库开始时刻到第一个穿梭车申请提升机调度服务的时长与提升机执行完所有出库任务的时长之和，即与提升机总工作时间长度和第一个完成出库任务的穿梭车用时之和。
以上三种作业时间长度分别反映了多层穿梭车仓储系统在完成出库任务任务时的各类设备表现，既有相互促进的效果，也有相互矛盾的地方。一方面，较长时间的提升机空闲时间降低了提升机的利用率，延长了出库任务作业总时长；另一方面，较长时间的穿梭车等待时间造成该层出库任务排队等待，影响了穿梭车利用率。
对于以存储为重点的面向仓储行业的多层穿梭车仓储系统而言，其出库作业任务往往是根据出库单据中的各品种货物出库数量，按照货物“先进先出”(First-In-First-Out, FIFO)原则选择出库货位，形成出库任务队列。这与前文所述的面向准时生产制（JIT)的生产性或订单分拣性的多层穿梭车仓储系统有着较大的区别。其出库任务次序不再是由生产系统或订单分拣系统“拉动”形成，而是对一个固定时间窗（Time Window)内所有出库货物的数量形成任务队列，该任务队列的次序是可以根据实际情况进行调整的。
面向仓储行业的多层穿梭车仓储系统，可以通过对一个时间窗口内的任务队列进行次序调度，从而能有效的减少穿梭车等待时间和提升机空闲时间，增加穿梭车和提升机的利用率，提高货物出入效率。基于此，本章将从任务调度方面进行研究，以出库完成时间、提升机空闲时间和穿梭车等待时间最短三个目标进行综合优化，建立出库任务调度优化模型，并釆用带精英策略的非支配排序遗传算法（NSGA-II)进行求解，某电力仪表仓库验证了该模型和算法。
..............................

第五章总论与展望

5.1工作总结与创新点
本文以多层穿梭车仓储系统为研究对象，详细阐述了传统堆操机式的自动化立体仓库在“柔性第一”的企业需求下的弊端和多层穿梭车仓储系统的发展和应用，分析了多层穿梭车仓储系统的设计原理和思路，建立了出库作业时序模型，确定了影响仓储作业效率的影响因素。在此基础上，综合运用开环排队网络、蚁群聚类算法、NSGA-II算法等工具，从储位分配和任务调度两个方面优化多层穿梭车仓储系统，对于提高多层穿梭车仓储系统作业效率有重要意义，能够为物流仓储系统设计人员提供理论指导。本文主要的研宄内容和创新点如下：
1、描述了多层穿梭车仓储系统的作业流程，建立了基于并行取货、串行出库的作业时序数学模型。通过对模型的分析，得到了影响出库作业总时间的多个因素，并对其进行详细阐述说明。
2、建立了多层穿梭车仓储系统的开环排队网络模型，利用分解法分析穿梭车与提升机配合作业的各设备空闲时间长度和系统表现。建立了各品项的相关性矩阵并用其表示品项间距离。利用蚁群聚类方法对货物进行聚类分析确定储区划分。再依照储位优化原则在二维平面内将储区排列组合，解决多层穿梭车仓储系统储位分配优化问题。
3、建立了以出库作业时间、提升机空闲时间和穿梭车等待时间最短为目标的多层穿梭车仓储系统的任务调度模型，将任务调度问题转化为流水线并行多机成组调度问题，利用NSGA-II算法进行多目标优化求解。 
...............................
参考文献:

[1] 罗键,苏海墩,何善君,吴长庆.  基于改进遗传算法的自动小车存取系统升降机调度建模与优化控制[J]. 厦门大学学报(自然科学版). 2010(03)
[2] 吴长庆,罗键,陈火国,庄进发,彭彦卿.  基于Petri网的RGVs系统中环路死锁研究[J]. 计算机科学. 2009(04)
[3] 罗键,钟寿桂,吴长庆.  基于离散粒子群算法的AVS/RS货位优化[J]. 厦门大学学报(自然科学版). 2009(02)
[4] 罗键,程勇,吴长庆.  基于着色赋时Petri网的堆垛机建模与调度研究[J]. 计算机工程与应用. 2009(01)
[5] 吴长庆,何善君,罗键.  自动小车存取系统中轨道导引小车环路死锁控制的研究[J]. 计算机集成制造系统. 2008(09)
[6] 倪庆剑,邢汉承,张志政,王蓁蓁.  蚁群算法及其应用研究进展[J]. 计算机应用与软件. 2008(08)
[7] Ya-hong HU1, Zheng-dong ZHU2, Wen-jing HSU3 (1College of Information Engineering, Zhejiang University of Technology, Hangzhou 310032, China) (2Department of Computer Science, Xi’an Jiaotong University, Xi’an 710049, China) (3School of Computer Engineering, Nanyang Technological University, Singapore 639798, Singapore).  AS/RS based yard and yard planning[J]. Journal of Zhejiang University(Science A:An International Applied Physics & Engineering Journal). 2008(08)
[8] 宋存利,时维国,黄明.  遗传算法在并行多机调度问题中的应用[J]. 大连铁道学院学报. 2004(02)
[9] 衣杨,汪定伟.  并行多机成组工作总流水时间调度问题[J]. 计算机集成制造系统-CIMS. 2001(07)
[10] 田国会,刘长有,林家恒,常发亮,贾磊,路飞,李晓磊,商允伟,李国锋.  自动化立体仓库若干优化调度问题及其研究进展[J]. 山东工业大学学报. 2001(01)

 

 


本文编号：11735