多端口出入式自动化存取系统作业集成优化

宋宇博，蒋兆远，孙秉珍



多端口出入式自动化存取系统作业集成优化

宋宇博1，蒋兆远1，孙秉珍2

(1. 兰州交通大学机电技术研究所，甘肃兰州，730070；2. 兰州交通大学交通运输学院，甘肃兰州，730070)

为了提高具有双板作业运作特点的多端口出入式自动化存取系统(AS/RS)整体作业效率，在统筹考虑货位分配和指令序列排序对作业时间影响的基础上，提出以最小化指令序列完工时间为优化目标的集成优化模型。引入交换和插入思想构建货位分配和指令排序的搜索邻域，并分析2种邻域构建方法对指令序列完工时间的影响。最后，设计二阶段禁忌搜索算法对问题进行求解，利用货位分配和指令排序2个阶段禁忌搜索过程的反馈获得模型最优解，其求解过程体现货位分配和指令排序2个优化方面在邻域搜索过程中互相影响、互相嵌套的复杂关系。研究结果表明：二阶段禁忌搜索算法在不同的货位规模和指令序列规模下均能获得满意解，具有较好的鲁棒性和计算效率；相比“先到先服务”和“最近邻”调度规则，本文优化方法能够有效缩短指令序列完工时间。

自动化存取系统；多端口出入式；集成优化；货位分配；指令序列排序；双板作业

多端口出入式(multiple-I/O points)自动化存取系统(automatic storage and retrieval system, AS/RS)是一种高柔性、高吞吐量的新型仓储系统。由于该系统配置多个出入库端口，因此可以并发执行多个出入库作业。与同/两端出入式AS/RS相比，多端口出入式AS/RS可以缩短存取货行程，增加指令并发作业数量，有效缩短空载运行时间。多端口出入式AS/RS通过升降式转运车(elevation transfer vehicle, ETV)来处理存取货作业，ETV在巷道内依次访问作业指令的源地址和目的地址，通过左右2个独立控制的载货台进行存取货操作，最多可同时装载2件货物。ETV从巷道一端到另一端可以访问多个出入库端口以及货位，执行多个作业任务，货位分配和指令执行顺序具有较强的关联度，单独优化哪方面都很难缩短指令序列完工时间。基于上述特征，多端口出入式AS/RS作业优化任务是，从集成优化角度考虑货位分配和指令序列排序，实现指令序列完工时间最小化。在已有文献中，关于货位分配策略的研究多以同端出入式AS/RS为背景，关注如何寻找符合约束条件的货物最优存放位置，主要考虑货物流通率、货物类别以及货物属性相关性等影响因素[1]。KOVÁCS等[2]在假定需求概率已知的情况下，通过混合整数规划模型研究了货位分配问题，最大限度地缩短了作业时间。柳赛男等[3]同时考虑了货物周转率和货架稳定性，通过货品链与货位链的耦合关系进行库区分配和货位分配。MUPPANI等[4]应用非线性整数规划模型分析了基于货物类别的货位分配策略对存储空间和物料搬运成本的影响，并与固定货位分配策略进行了对比。ENE等[5]采用随机进化算法分两个阶段对基于货物类别的货位分配问题、配料问题和作业路径规划问题进行了研究。GAGLIARDI等[6]对随机存储策略、基于类型的存储策略和基于流通率的存储策略进行了对比，其研究结果表明，存储策略的确定与货物类型划分的方法、货物类型的规模以及工业环境等因素有关，基于周转率的存储策略不是适用各种类型AS/RS的最优存储策略。李英德等[7]针对物流配送中心提出了基于货物属性相关性的货位指派算法。总的来说，在已有文献中，多数学者研究的是单个出入口的AS/RS货位分配策略，其他配置类型(例如，多端口出入式AS/RS)的货位分配策略几乎没有涉及。部分关于AS/RS作业指令排序的文献中描述了各种使总/空行驶距离最小化的存取请求处理方法，包括Petri网[8]、遗传算法[9−10]、模拟退火算法[11]、蚁群算法[12]等，这些方法可应用于具有很高的不确定性和很少信息量的情况。此外，这些方法都能够学习和适应环境的变化，优化结果可以由存储货位分配、取货位置选择、排队选择和指令排序组合而成。然而大多数文献着重考虑的仍是单个出入口的AS/RS，关于多端口出入式AS/RS的货位分配和作业指令调度排序的优化研究少见涉及。本文作者从集成优化的角度对多端口出入式AS/RS货位分配和指令序列排序进行研究，以最小化指令序列完工时间为目标，建立具有双板作业约束条件的集成优化数学模型，设计二阶段禁忌搜索算法对模型进行求解，通过货位分配和指令排序2个阶段禁忌搜索过程的反馈获得模型最优解。

1 问题描述

多端口出入式AS/RS货位分配和指令排序集成优化问题可描述为：出库指令源地址、目的地址以及入库指令的源地址均已确定；空货位集合是为申请入库的货物提供的存储位置集合，同时约定每个空货位最多存储1个货物；出入库指令组成作业指令序列，由ETV逐条执行；ETV具有双板作业能力，即同时执行指令数小于等于2；作业指令一旦开始执行便不能中断，即必须将货物从源地址搬运到目的地址；货位空闲/占用状态已知；货架单元格横纵长度为定值；假设无论在装载或空载情况下，ETV在水平和垂直方向均做匀速运动且速度已知，忽略ETV取货和存货耗时。需解决的问题是：如何确定申请入库货物存储位置分配方案并安排出入库指令执行顺序，在满足约束条件的前提下，使指令序列的完成时间最小。

合理的双板作业组合能够有效缩短指令序列完工时间，ETV执行双板作业需满足如下条件：1) 搬运路径：2条指令为相邻指令，且2个待搬运的货物沿巷道方向具有同向且重合的搬运路径；2) 搬运顺序与装载方式：当2个货物同时装载到ETV载货台，货物的搬运顺序可分为4种，即“先上先下”、“先上后下”、“后上先下”和“后上后下”，货物的装载方式可分为2种，即“同侧装载”和“异侧装载”。在2个货物同时搬运的过程中，搬运顺序组合对应关系如表1所示。表1中，若“先下”货物离开ETV载货台时不与另一个货物干涉，则可以执行双板作业，按照搬运顺序和装载方式的不同组合归纳的双板作业条件如表2所示。表2所列4种情况对应图示如图1所示。满足条件1)和条件2)的2条作业指令可由ETV执行双板作业。2条指令是否满足双板作业条件由来描述，=1表示满足双板作业条件，=0表示不满足双板作业条件。

(a) 同侧装载，先上先下；(b) 异侧装载，先上先下；(c) 同侧装载，后上先下；(d) 异侧装载，后上先下

表1 搬运顺序组合对应关系

Table 1 Corresponding relationship of transport sequence combination

表2 双板作业条件

Table 2 Double cargo transport conditions

2 数学模型

2.1 符号定义

货位分配涉及到的集合有入库作业指令集合和空货位集合，分别表示为s和e，指令序列排序涉及到的集合有出入库指令序列集合a，s与a中的元素有所区别，s中的指令′和′只有源地址，没有目的地址，a中的指令和既有源地址又有目的地址。c为ETV完成全部作业指令所需时间；若T为作业指令执行时间，B为指令开始作业时间，E为指令结束作业时间，则有T=E−B；作业指令的执行时间T=E−B，其中B为指令开始作业时间，E为指令结束作业时间。T为指令执行准备时间，即ETV从前1条指令的目的地址移动到当前指令的源地址所需时间，T=B−E，对指令序列当中的第1条指令而言，T为ETV从待命位移动到第1条指令源地址所用时间。(di，di，di)为指令的目的地址，其中di，di和di分别为指令的目的地址的侧方向坐标、列方向坐标和层方向坐标；(oj，oj，oj)为指令的源地址，oj，oj和oj分别为指令的源地址的侧方向坐标、列方向坐标和层方向坐标。q为ETV执行指令之后，后续指令未执行之前载货台载货数量。为货位宽度；为货位高度。w为ETV列方向速度；h为ETV层方向速度。作业指令开始时间B和结束时间E均采用相对时间，ETV完成单条指令所需作业时间表示为

2.2 数学模型

上述问题属于集成优化问题，涉及到货位分配和指令序列排序2个方面的优化内容，该问题可以抽象为下述整数规划模型。在货位分配阶段以ETV作业时间最短为优化目标，考虑双板作业的约束条件，确定入库货物货位分配方案；在指令序列排序阶段，待存货地址确定后，指令执行顺序的确定即转化为多起点多终点的车辆路径规划问题(vehicle routing problems，VRP)。VRP问题已经被证明是NP−hard问题，本文模型中空货位备选集合的规模较VRP更大且更复杂，ETV访问地址顺序规划需考虑地址访问的可行性、双板作业条件等因素，其约束条件比VRP模型更严格。

该数学模型的目标函数为

约束条件为

(3)