DOI: 10.11817/j.issn.1672-7207.2016.06.015
多端口出入式自动化存取系统作业集成优化
宋宇博1，蒋兆远1，孙秉珍2
(1. 兰州交通大学 机电技术研究所，甘肃 兰州，730070；
2. 兰州交通大学 交通运输学院，甘肃 兰州，730070)
摘要：为了提高具有双板作业运作特点的多端口出入式自动化存取系统(AS/RS)整体作业效率，在统筹考虑货位分配和指令序列排序对作业时间影响的基础上，提出以最小化指令序列完工时间为优化目标的集成优化模型。引入交换和插入思想构建货位分配和指令排序的搜索邻域，并分析2种邻域构建方法对指令序列完工时间的影响。最后，设计二阶段禁忌搜索算法对问题进行求解，利用货位分配和指令排序2个阶段禁忌搜索过程的反馈获得模型最优解，其求解过程体现货位分配和指令排序2个优化方面在邻域搜索过程中互相影响、互相嵌套的复杂关系。研究结果表明：二阶段禁忌搜索算法在不同的货位规模和指令序列规模下均能获得满意解，具有较好的鲁棒性和计算效率；相比“先到先服务”和“最近邻”调度规则，本文优化方法能够有效缩短指令序列完工时间。
关键词：自动化存取系统；多端口出入式；集成优化；货位分配；指令序列排序；双板作业
中图分类号：TP391 文献标志码：A 文章编号：1672-7207(2016)06-1930-10
Integrated optimization of operations in multiple-I/O points automated storage and retrieval system
SONG Yubo1, JIANG Zhaoyuan1, SUN Bingzhen2
(1. Institute of Mechatronic Technology, Lanzhou Jiaotong University, Lanzhou 730070, China;
2. School of Traffic and Transportation, Lanzhou Jiaotong University, Lanzhou 730070, China)
Abstract: To improve the overall efficiency of multiple-I/O points automated storage and retrieval system (AS/RS) with double cargo transport characteristic, an integrated optimization model was established to minimize the completion time of command sequence on the basis of considering the influence of storage location assignment and command sequence sorting on the operation time comprehensively. The insert method and exchange method were introduced to construct search neighborhoods of storage location assignment and command sequence sorting, and the influence of the two neighborhood construction methods on the completion time of command sequence was analyzed. Finally, a two-phase tabu search algorithm was presented to solve this problem, and the optimal solution of the model was obtained by the feedback between the two stage tabu search processes of storage location assignment and command sequence sorting. The solving process embodies the mutual influences and mutual nesting relationships in the neighborhood searching process of the two optimal aspects, namely storage location assignment and command sequence sorting. The results show that the two-phase tabu search algorithm proposed in this paper can obtain satisfactory solutions under the condition of different command sequence scales and different storage location scales, and it has strong robustness and high efficiency. Compared with the First-Come-First-Served scheduling rule and Nearest-Neighbor scheduling rule, the presented optimization method can shorten the completion time of command sequence effectively.
Key words: automated storage and retrieval system; multiple-I/O points; integrated optimization; storage location assignment; command sequence sorting; double cargo transport
多端口出入式(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]。
等[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表示不满足双板作业条件。
图1 双板作业位置关系图
Fig. 1 Position relationship of double cargo transport
表1 搬运顺序组合对应关系
Table 1 Corresponding relationship of transport sequence combination
表2 双板作业条件
Table 2 Double cargo transport conditions
2 数学模型
2.1 符号定义
货位分配涉及到的集合有入库作业指令集合和空货位集合，分别表示为Cs和Le，指令序列排序涉及到的集合有出入库指令序列集合Ca，Cs与Ca中的元素有所区别，Cs中的指令i′和j′只有源地址，没有目的地址，Ca中的指令i和j既有源地址又有目的地址。Tc为ETV完成全部作业指令所需时间；若Ti为作业指令i执行时间，Bi为指令i开始作业时间，Ei为指令i结束作业时间，则有Ti=Ei-Bi；作业指令j的执行时间Tj=Ej-Bj，其中Bj为指令j开始作业时间，Ej为指令j结束作业时间。Tij为指令执行准备时间，即ETV从前1条指令i的目的地址移动到当前指令j的源地址所需时间，Tij=Bj-Ei，对指令序列当中的第1条指令而言，Tij为ETV从待命位移动到第1条指令源地址所用时间。(Sdi，Wdi，Hdi)为指令i的目的地址，其中Sdi，Wdi和Hdi分别为指令i的目的地址的侧方向坐标、列方向坐标和层方向坐标；(Soj，Woj，Hoj)为指令j的源地址，Soj，Woj和Hoj分别为指令j的源地址的侧方向坐标、列方向坐标和层方向坐标。qij为ETV执行指令i之后，后续指令j未执行之前载货台载货数量。P为货位宽度；Q为货位高度。Vw为ETV列方向速度；Vh为ETV层方向速度。作业指令开始时间Bi和结束时间Ei均采用相对时间，ETV完成单条指令所需作业时间表示为
(1)
模型中的决策变量
为货位选择决策变量，可取0或1，取1表示入库作业指令i′选择空货位k作为目的地址，
，
，否则取0。Yij为指令排序决策应变，可取0或1，取1表示ETV执行完指令i就执行指令j(
)，否则取0。另外，为了方便表达双板作业的约束条件，增加3个补充变量Dij，Mij和Nij，Dij可取0或1；取1表示相邻2条指令i和j作业路径沿巷道方向同向且有重合()；否则取0。Mij可取0或1；取1表示相邻2条指令i和j其源地址和目的地址的侧坐标满足
()；否则取0。Nij可取0或1；取1表示相邻2条指令i，j，指令j的源地址和目的地址在巷道的同侧()；否则取0。
2.2 数学模型
上述问题属于集成优化问题，涉及到货位分配和指令序列排序2个方面的优化内容，该问题可以抽象为下述整数规划模型。在货位分配阶段以ETV作业时间最短为优化目标，考虑双板作业的约束条件，确定入库货物货位分配方案；在指令序列排序阶段，待存货地址确定后，指令执行顺序的确定即转化为多起点多终点的车辆路径规划问题(vehicle routing problems，VRP)。VRP问题已经被证明是NP-hard问题，本文模型中空货位备选集合的规模较VRP更大且更复杂，ETV访问地址顺序规划需考虑地址访问的可行性、双板作业条件等因素，其约束条件比VRP模型更严格。
该数学模型的目标函数为
(2)
约束条件为
(3)
，
(4)
， (5)
，
(6)
，
(7)
，
(8)
，
(9)
其中：式(3)确保共用同1个端口出入库的入库指令优先于出库指令执行，式(4)确保在整个指令执行过程中，ETV载货台上的货物不超过2个，式(5)确保指令i和j能够执行双板作业，式(6)确保为申请入库的货物分配1个空货位存储，式(7)确保每个空货位最多只能存储1个货物，式(8)确保每条作业指令最多只能有1条紧后作业指令，式(9)确保每条作业指令最多只能有1条紧前作业指令。
3 问题特点与算法实现
3.1 问题特点
设π为任意排列的完整指令序列，Tc包括指令执行时间和指令执行准备时间，问题的目标是在指令序列集合Π中找到π*，使
(10)
由式(2)和式(10)可知：求解指令序列的最小完工时间就是找到1个货位分配方案和1个指令排序方案，使指令执行准备时间与指令执行时间之和最小。指令源地址和目的地址确定后，其执行时间为定值，其表达式为
(11)
性质1 由式(2)可知：当指令序列的指令执行时间为定值时，指令序列完工时间只与指令执行准备时间有关。因为每条指令的源地址和目的地址已知，所以相邻指令执行准备时间可以预先得到。所有相邻指令执行准备时间形成(n+1)×(n+1)时间距离矩阵T(包括ETV待命位)，即
(12)
其中：tij的计算公式为
(13)
不同指令排序方案的指令执行准备时间可直接访问矩阵T得到，因此，计算指令序列完工时间的时间复杂度为o(n)。
定理 1 对于任意1个排列的指令序列π，若将指令i插到指令j之后，则新排列的指令序列π*的最小完工时间为
(14)
(15)
(16)
证明 调整指令序列π中任意指令i在指令序列中的位置需删除和插入2个步骤。指令i在指令序列π中删除将减少2个指令相邻关系(i-1，i)和(i，i+1)，同时增加1个相邻关系(i-1，i+1)，则指令序列π的时间增量为
；指令i插入到指令序列π中将减少了1个指令相邻关系(j，j+1)，同时增加了2个相邻关系(j，i)和(i，j+1)，则指令序列π的时间增量为
；其他指令的排列关系不变，因此，
，式(14)得证。同理可证式(15)和式(16)。证毕。
定理2 对于任意1个指令序列π，任意选取2个作业指令i和j，将2条指令交换，形成新的指令序列π*，则新指令序列π*的最小完工时间为
(17)
(18)
(19)
证明 交换指令序列π中任意2条指令i和j的位置可分成2个插入操作，首先将指令i插入指令j的位置，再将指令j插入指令i的位置，指令i插入指令j的位置将减少2个指令相邻关系(i-1，i)和(i，i+1)，同时增加2个相邻关系(i-1，j)和(j，i+1)，产生的指令序列π的时间增量为
；同理，指令j插入指令i的位置将减少2个指令相邻关系(j-1，j)和(j，j+1)，同时增加2个相邻关系(j-1，i)和(i，j+1)，产生的指令序列π的时间增量为
，所以，交换指令i和j的位置后，新的指令序列π*相对指令序列π产生的时间增量为
，即
，式(17)得证。同理可证式(18)和式(19)。证毕。
3.2 算法实现
禁忌搜索算法常被用于求解集成优化问题，其核心思想是通过集中策略找到局部最优解，利用扩散策略实现全局搜索[13]。其中二阶段禁忌搜索算法是采用多级分解的方法将集成优化问题简化求解的多阶段启发式算法，ESCOBAR等[14-15]应用该算法成功解决了物流配送领域中的LRP问题和仓库堆垛机调度问题，本文采用该算法是为了利用不同优化层面的反馈作用关系，对分别优化方法获得的解的性能及其计算时间加以改善，以获取集成优化问题的全局最优解。
本文设计的二阶段禁忌搜索算法的基本思想是：将问题分为货位分配和指令排序2个阶段进行求解，在货位分配阶段，基于当前的出入库指令序列，在空货位集合(空货位集合包括已经为入库指令分配的空货位和剩余的空货位)当中搜索货位分配方案，并与入库指令匹配，形成完整的出入库指令序列，指令序列排序阶段以该序列为优化对象，在当前指令序列构建的邻域中通过另1个禁忌算法进行搜索，获取指令序列最佳的执行顺序，该指令序列又作为货位分配阶段禁忌搜索的依据，进一步影响货位分配阶段对货位分配方案的搜索，算法流程如图2所示。该算法通过循环方式将前一阶段的搜索结果传递到后一阶段，实现邻域搜索过程中货位分配和指令排序之间信息的反馈，获取货位分配-指令序列排序集成优化模型的全局最优解。下面将对算法中的几个关键环节加以介绍。
3.2.1 初始解的构建
初始解的货位分配方案按照时间距离最短原则，通过搜索半径递增的方法产生，其基本思想是以入库指令的源地址为圆心，搜索半径以单个货位尺寸的时间距离为单位递增，在空货位集合当中搜索空货位。由于货位宽度、货位高度以及ETV的水平和垂直方向运行速度不同，引入转换系数
(round(·)为对转换系数圆整)，统一度量水平方向和垂直方向的时间距离。其搜索过程如图3所示，算法描述如下：
i=1; Flag=false;
for (m=1; m≤|Cs|; m++)
While (Flag =false)
for (j=1; j≤Nlevel; j++)
for (k=1; k≤j*round(ξ); k++)
if (
)
更新入库指令目的地址；
Flag=true;
break;
end if;
end;
for (l=1; l≤j-1; l++)
if (
)
更新入库指令目的地址；
Flag=true;
break;
end if;
end;
if (Flag=true) break;
end;
end;
图2 二阶段禁忌搜索算法流程
Fig. 2 Process of two-stage tabu search algorithm
为了对指令序列进行排序，设置2个集合C1和C2，其中，C1=
，C2={所有作业指令}。首先根据式(11)得到时间距离矩阵T，在T中查找第0行的最小值，若t0i最小，则将指令ci添加到集合C1中，同时在集合C2中将指令ci删除。然后在T中查找第i行，若tij最小，则看指令cj是否属于集合C1，若属于，则重新在矩阵T中查找第i行的次小值，直到查找的指令cj不属于集合C1并且值最小，将指令cj从集合C2中转移到集合C1中。下次查找矩阵T的第j行，将找到的指令从集合C2中转移到集合C1中，直到转出C2中全部指令。这样，按照指令进入集合C1的先后顺序构成了1个初始解。算法描述如下。
1) 初始化时间距离矩阵T；
2) while (
)
{在矩阵T中查找第i行的最小指令执行准备时间，若为tij且cj不属于集合C1，则有
}
3) 将C1中指令按照进入顺序组成初始指令序列π0，算法结束。
3.2.2 领域搜索策略
采用0-1码来表示空货位分配方案，0表示未选择的空货位，1表示被选择的空货位，货位分配阶段当前解的邻域通过1-0和1-1这2种交换方法构建，构建方法如图4所示。货位分配方案确定后，指令执行时间和指令执行准备时间按式(11)和式(13)更新。
指令排序阶段的邻域采用插入法和交换法构建，构建方法如图5所示，插入点的选择和交换指令的选择均随机产生。根据定理1计算插入前后的指令序列完工时间增量，根据定理2计算交换前后的指令序列完工时间增量。
图3 入库指令目的地址搜索过程示意图(ξ=3)
Fig. 3 Search process diagram of storage command destination address (ξ=3)
图4 货位分配阶段邻域构
Fig. 4 Neighborhood construction in storage location assignment stage
图5 指令排序阶段邻域构建
Fig.5 Neighborhood construction in command sequence sorting stage
3.2.3 禁忌属性
在二阶段禁忌搜索过程中定义了不同的禁忌对象，货位分配阶段选择入库指令和入库货位的组合作为禁忌对象，通过指令索引和货位索引前后对应形成的二维数组行记录来表示；在指令序列排序阶段选择指令序列作为禁忌对象，通过指令索引构成的行记录来表示。二阶段的禁忌表均使用二维数组来记录，数组的列数由禁忌对象行记录的元素数确定，数组的行数由禁忌长度确定，每迭代1次，数组中的所有元素以行为单位下移1行，释放行坐标超出禁忌长度的禁忌对象，新得到的禁忌对象插入到二维数组的第1行。在邻域搜索过程中禁忌对象除了满足禁忌周期可以得到释放之外，指令序列完工时间小于当前最优解的禁忌对象可以特赦。
4 算例分析
以国内某国际机场集装区自动化存取系统为例，考虑1台ETV独立作业的情况，其垂直方向的速度为0.4 m/s，水平方向的速度为2 m/s，货位宽度为2.8 m，层高为2.4 m，选择100(2排×5层×10列)、150(2排×5层×15列)、200(2排×5层×20列)、300(2排×5层×30列)、450(2排×5层×45列)5种货位数规模，10列货架设置4个出入库端口，空侧陆侧各2个；15列货架设置6个出入库端口，空侧陆侧各3个；20列货架设置10个出入库端口，空侧陆侧各5个；30列货架设置15个出入库端口，空侧8个，陆侧7个；45列货架设置23个出入库端口，空侧13个，陆侧10个，选择5，10，15，20和30这5种指令序列规模。仿真结果采用多次计算取平均值的方式来记录，计算次数均取10次。初始货位是否被占用由随机函数确定，在确定的货位状态下随机生成出入库指令。采用的仿真工具为Matlab7.0，运算的计算机配置为：处理器Intel(R)Core(TM)i5@2.5 GHz，内存4.00 GB。为了比较本文算法在不同的指令序列规模和不同货位规模下对初始解的改善性能，分别取5种规模的指令序列和5种规模的货位进行仿真，每种指令序列规模下的货位规模相同，均为2排5层30列300货位的规模，每种货位规模的下的指令序列规模相同，均为10，仿真结果见表3和表4。
表3 不同指令序列规模的仿真结果
Table 3 Simulation results of different command scales
表4 不同货位规模的仿真结果
Table 4 Simulation results of different storage location scales
初始解的对比结果表明，初始解经二阶段禁忌算法优化之后得到的ETV作业时间均明显缩短，不同指令序列规模的平均作业时间缩短了15.17%，不同货位规模的平均作业时间缩短了16.06%。算法的计算时间随着指令序列规模和货位规模的增加略有增加，但最佳的货位分配方案和指令执行顺序均能在合理的计算时间内得到，满足航空货站AS/RS实际操作中的ETV调度需求。由图6可以看出：针对不同的指令序列规模，本文算法基本能在30代左右搜索到问题的最优解，且不会因为货位规模和指令序列规模的增加而影响算法的求解性能，具有较好的鲁棒性。
为了验证本文集成优化算法的性能，取2排5层30列300货位，针对不同指令序列规模，对货位分 配-指令排序分别优化方法和本文集成优化方法进行仿真对比，仿真结果如表5所示，其中分别优化中货位分配采用遗传算法，指令排序采用贪婪算法。由表5可知：对于不同指令序列规模，集成优化算法在解的性能比分别优化方法的好，计算时间比优化方法的低，最大改进率分别达到11.09%和23.98%。这是由于分别优化方法只有货位分配到指令排序的信息传递，缺少指令排序到货位分配的反馈。而本文提出的集成优化方法考虑了二者之间的关系，不但货位分配阶段存储位置的变化可以传递到指令排序阶段，且指令排序阶段指令顺序的变化也可以反馈到货位分配阶段。在各自独立的优化过程中，2个优化层面均能够统筹考虑货位分配和指令排序对指令序列完工时间的影响，通过不同优化层面的反馈作用以及算法的集中
策略和扩散策略的共同作用，快速收敛到全局最优解。
图6 算法收敛曲线
Fig. 6 Convergence curves of algorithm
表5 不同优化方法的性能对比
Table 5 Performance comparison of different optimization methods
表6 不同调度规则的结果对比
Table 6 Comparison results of different scheduling rules
为了验证本文集成优化方法的有效性，选择货位规模为300，针对不同指令序列规模，分别采用“最近邻”调度规则(nearest-neighbour scheduling，NN)和“先到先服务”调度规则(first-come-first-served scheduling，FCFS)进行仿真实验，并与本文优化方法进行对比，其结果如表6所示。
由表6可知：在不同指令序列规模下，本文的优化方法获得的ETV作业时间较FCFS和NN调度规则均有改进，平均改进率分别为25.78%和8.94%。3种调度规则下，FCFS的作业效率最低，这是由于该调度规则要求指令执行顺序要严格按照生成顺序执行，ETV的作业效率只能通过货位分配一方面的优化来提高。NN调度规则是依据时间距离最短原则获取存储货位的分配方案，并在此基础上基于NN调度规则进行指令排序，在其排序过程中同时考虑了ETV的双板作业。由于NN调度规则除了对货位分配进行了优化，同时也对指令序列进行了一定程度的优化，其优化方案的指令序列完工时间比FCFS调度规则下的时间短。但是，与本文优化方法相比，NN调度规则只具备货位分配阶段到指令序列排序阶段的单向信息传递优化，其优化过程缺少指令排序阶段到货位分配阶段的信息反馈，且NN调度规则对指令排序有一定的限制，因此，本文优化方法能够获得比NN调度规则更好的结果。
5 结论
1) 多端口出入式AS/RS具有双板作业、多指令并发、货位选择与指令排序相关性强等特性，从集成优化角度建立优化调度数学模型，并引入二阶段禁忌搜索算法进行模型求解，有效地解决了多端口出入式AS/RS货位选择和作业指令排序集成优化问题。
2) 总结了插入法和交换法对指令序列最小完工时间的影响规律，提出了基于插入法和交换法的邻域构建方法计算指令序列完工时间，降低了算法的时间复杂度。
3) 不同规模的指令序列和货位数量的仿真结果表明：所提出的货位分配和指令排序集成优化模型及其求解方法具有较好的鲁棒性；与分阶段优化算法的对比验证了二阶段禁忌搜索算法的有效性和计算效率；与不同调度规则的对比分析表明，本文建立的集成优化模型及其求解方法能够有效提高多端口出入式AS/RS整体作业效率。
参考文献：
[1] MUPPANI V R, ADIL G K. A branch and bound algorithm for class based storage location assignment[J]. European Journal of Operational Research, 2008, 189(2): 492-507.
[2] A. Optimizing the storage assignment in a warehouse served by milkrun logistics[J]. International Journal of Production Economics, 2011, 133(1): 312-318.
[3] 柳赛男, 柯映林, 李江雄, 等. 基于调度策略的自动化仓库系统优化问题研究[J]. 计算机集成制造系统, 2006, 12(9): 1438-1443.
LIU Sainan, KE Yinglin, LI Jiangxiong, et al. Optimazation for automated warehouse based on scheduling policy[J] . Computer Integrated Manufacturing Systems, 2006, 12(9): 1438-1443.
[4] MUPPANI V R, ADIL G K. A branch and bound algorithm for class based storage location assignment[J]. European Journal of Operational Research, 2008, 189(2): 492-507.
[5] ENE S, 
N. Storage location assignment and order picking optimization in the automotive industry[J]. International Journal of Advanced Manufacturing Technology, 2012, 60(5/6/7/8): 787-797.
[6] GAGLIARDI J P, RENAUD J, RUIZ A. On storage assignment policies for unit-load automated storage and retrieval systems[J]. International Journal of Production Research, 2012, 50(3): 879-892.
[7] 李英德，鲁建厦. 基于相关性的周期性货位优化的模型与算法[J]. 机械工程学报, 2011, 47(20): 75-80, 88.
LI Yingde, LU Jiansha. Model and algorithm for periodic storage allocation based on correlations[J]. Journal of Mechanical Engineering, 2011, 47(20): 75-80, 88.
[8] 许晓伟, 梁英宏, 吴耀华. 面向仓储物流的建模及控制系统设计方法[J]. 计算机集成制造系统, 2009, 15(12): 2335-2342, 2390.
XU Xiaowei, LIANG Yinghong, WU Yaohua. Modeling and control program design of automated storage and retrieval system[J]. Computer Integrated Manufacturing Systems, 2009, 15(12): 2335-2342, 2390.
[9] 杨朋, 缪立新, 秦磊. 多载具自动化存取系统作业调度优化[J]. 计算机集成制造系统, 2013, 19(7): 1626-1632.
YANG Peng, MIAO Lixin, QIN Lei. Job scheduling optimization in multi-shuttle automated storage and retrieval system[J]. Computer Integrated Manufacturing Systems, 2013, 19(7): 1626-1632.
[10] 
Application of genetic algorithms for sequencing of AS/RS with a triple-shuttle module in class-based storage[J]. Flexible Services and Manufacturing Journal, 2014, 26(3): 432-453.
[11] BESSENOUCI H N, SARI Z, GHOMRI L. Metaheuristic based control of a flow rack automated storage retrieval system[J]. Journal of Intelligent Manufacturing, 2012, 23(4): 1157-1166.
[12] HU Kuanyu, CHANG Tiansheng. An innovative automated storage and retrieval system for B2C e-commerce logistics[J]. International Journal of Advanced Manufacturing Technology, 2010, 48(1/2/3/4): 297-305.
[13] 邢文训, 谢金星. 现代优化计算方法[M]. 2版. 北京: 清华大学出版社, 2007: 51-52.
XING Wenxun, XIE Jinxing. Modern optimization computing method[M]. 2nd ed. Beijing: Tsinghua University Press, 2007: 51-52.
[14] ESCOBAR J W, LINFATI R, BALDOQUIN M G, et al. A granular variable Tabu neighborhood search for the capacitated location-routing problem[J]. Transportation Research Part B: Methodological, 2014, 67: 344-356.
[15] 陈旻, 陆志强. 基于订单总拖期的仓储作业调度建模与优化[J]. 上海交通大学学报, 2009, 43(12): 1917-1922.
CHEN Min, LU Zhiqiang. Modeling and optimization on operation scheduling with total tardiness objective for a storage system[J]. Journal of Shanghai Jiaotong University, 2009, 43(12): 1917-1922.
(编辑 刘锦伟)
收稿日期：2015-06-30；修回日期：2015-08-11
基金项目(Foundation item)：国家自然科学基金资助项目(61563029)；国家科技支撑计划资助项目(2012BAH20F05)；兰州交通大学青年基金资助项目(2011012)(Project(61563029) supported by the National Natural Science Foundation of China; Project(2012BAH20F05) supported by the National Science & Technology Pillar Program, China; Project(2011012) supported by the Youth Foundation of LanZhou Jiaotong University, China)
通信作者：宋宇博，博士，副教授，从事立体仓储系统建模与优化；E-mail：songyubo@mail.lzjtu.cn
