发布时间：2014-07-22 22:41

摘要：为了提高多载具自动化存取系统整体进出库效率，分析了多载具自动化存取系统的运作特点，建立了同时考虑货位分配和拣选路径的集成优化模型。模型以最小化单位指令周期的行程时间为优化目标，最后设计了两阶段禁忌搜索算法求解该问题。不同货位规模和不同载具数量的数值实验结果表明两阶段禁忌算法获得的行程时间较初始解有至少40%的改善，而且与分别优化的方法相比行程时间也能降低7%~23%。
关键词：集成优化；多载具；自动化存取系统；货位分配；拣选路径
中图分类号：TP391     文献标识码：A
Integrated optimization of storage location assignment and routing planning in a multi-shuttle automated storage and retrieval system
YANG Peng, MIAO Lixin, QI Mingyao
(Research Center for Modern Logistics, Graduate School at Shenzhen, Tsinghua University, Shenzhen518055, China)
Abstract: The patterns of operating the multi-shuttle automated storage and retrieval system (AS/RS) are analyzed to improve the overall efficiency of multi-shuttle AS/RS. The integrated optimization model of storage location assignment and routing planning is established to minimize the travel time of performing corresponding storage and retrieval operations in command cycle. To solve this complicated problem, a two-phase tabu algorithm is developed. According to numerical experiments combined with different location sizes and various shuttle numbers, at least 40% reduction for travel time can be obtained relative to the initial solutions using this algorithm. Additionally comparison to the result using the separate optimization method shows that the travel time is reduced by 7%~23%.
Key words: integrated optimization; multi-shuttle; automated storage and retrieval system; storage location assignment; routing planning
 
配送领域中自动化存取系统（Automated Storage and Retrieval System,简称AS/RS）货位分配优化关注指令周期内为待存货物分配合适空货位以及为待取货物选择合适取货货位（待取的货物可能存放在多个货位上），以提高出入库效率。单载具AS/RS一次行程最多访问两个货位，货位分配和拣选路径（行程内货位访问的顺序）的关联度较弱，单独优化货位分配即能取得较好成效，但是多载具（multi-shuttle）AS/RS拥有多个载具（大于等于2个），一次行程可以同时存放和取出多个货物单元，行程内访问的货位数将大大增加。如果仍然单独优化货位分配，将难以从整体上提高进出库效率。
货位分配的已有研究着重于单载具AS/RS货位分配优化^[1,2]和man-on-board(person-on-board)系统（即拣选人员在存取设备上完成存取货作业，存取设备可以穿越不同的通道行走）货位分配优化研究^[3-5]，但仅关注为入库货物寻找最优货位存放，主要考虑货物周转率、保持货架稳定上轻下重、货物相关性等因素，少量文献^{[6, 7]}同时考虑了存货货位和取货货位的优化，但大部分忽略了取货货位的分配优化。多载具AS/RS控制优化文献较少，集中在存取指令作业调度排序^{[8, 9]}和吞吐能力仿真^[10]上，从集成角度对多载具AS/RS货位分配和拣选路径规划的优化还未见研究。
本文针对多载具AS/RS的特点，以配送领域为应用背景，从集成优化的角度对多载具AS/RS的货位分配和拣选路径问题进行研究。

1 问题描述

实际配送环境下存取系统不停进行出入库作业，连续到达的存取货指令分别形成入库队列和存货队列，多载具自动化存取系统按照指令周期（command cycle）模式进行运作，根据单位时间内存货队列和取货队列的长度，可组合划分为多个指令周期，假设堆垛机有n个载具(n≥2) ，一个指令周期内最多可以完成n个货物单元的存货操作和n个货物单元的取货操作。根据系统存货队列和取货队列的情况，堆垛机可以进行复合式和单一任务式两种指令周期作业方式，其中复合式指令周期指堆垛机一次行程同时完成m₁(0<m₁≤n）个货物单元存货操作和m₂(0<m₂≤n）个货物单元取货操作，单一任务式指令周期指堆垛机一次行程只完成m(0<m≤n)个货物单元的存货或取货操作。指令周期是多载具自动化存取系统运作的最小单元，同时也是提高存取系统进出库效率的基本优化单元。每个指令周期几乎都将面临选择存取货位及货位访问顺序设计（拣选路径）问题，对基本单元内对应优化问题的研究将是提高存取系统整体效率的基础。本文同时考虑存取货位分配和拣选路径规划两个优化问题，以最小化指令周期内存取货物的时间距离为目标进行集成优化研究。

2 数学模型

2.1 基本假设

考虑单元负载式(unit-load)自动化存取系统，以托盘为存取单元，货物从同一出口进出，进出货口(input/output point，I/O point)位于货架左下方，每个货位只能存放一个托盘单一种类的货物，货架上货位具有相同尺寸，每个托盘都可以存放货架上任一货位；堆垛机有n个载具(n≥2)，各个载具的操作互相独立，堆垛机在水平方向上和垂直方向上同时运动，假设水平方向和垂直方向均做匀速运动，速度已知且为常数，不受堆垛机载物与否影响；不考虑堆垛机在货位处取货和存货(pickup/deposit)的时间；系统存货队列和取货队列无容量限制，规划时间内存货队列和取货队列货物种类已知，且两个队列无相同种类货物，否则直接从存货队列将货物取走，不用进入存储区，存货队列和取货队列的指令均按照先到先服务（FCFS）的原则处理。

2.2 符号定义

根据规划时间内存取货队列情况，按照FCFS规则划分指令周期集合，不失一般性，任选集合中任一指令周期j作为研究对象，假设单位时间内取货队列长度为LR，存货队列长度为LS，则，其中是指令周期总个数；为便于建模，补充定义如下符号：
I为货物种类集合，数量N^I,索引i, i’；L为货位集合，数量N^L，索引k,k’,l，其中货位0代表I/O；n为堆垛机载具数量；为指令周期j执行前空货位集合；为指令周期j执行前存储货物i的货位集合，；S_j为指令周期j内需存货物集合；R_j为指令周期j内需取货物集合，满足；AL_j为指令周期j内可能访问到的货位集合，；c_kl为货位k到货位l的时间距离，；(W_k,H_k)为货位k的坐标，，（0,0）代表I/O；w为相邻货位水平方向距离；h为相邻货位垂直方向距离；v_x为堆垛机水平方向速度；v_y为堆垛机垂直方向速度；T(cc_j)为堆垛机完成指令周期j的行程时间；q_klj为在j指令周期内，访问完货位k后在访问货位l前堆垛机的负载量；d_kj为j指令周期货位k可存货的数量；p_kj为j指令周期货位k 可取货的数量，其中，系统为单元式负载，负载量1代表1货物单元。
集成优化模型的决策变量为，取1表示指令周期j内，货物i存放在货位k处，，否则取0；，取1表示指令周期j内，从货位处取出货物，，否则取0；，取1表示指令周期j内，访问货位k后立即访问货位l。另外为了建模方便，设置补充变量，取1表示货位k在指令周期j内将被访问，，其中满足。

2.3 数学模型

在任一指令周期j（复合式或单一任务式指令周期均可）内，多载具AS/RS存取货位分配和路径规划的确定属于组合优化问题，可抽象为下述整数规划模型，待存取货位确定后，模型即转化为求解一个混合考虑存货和取货的TSP/PD(Travel Salesman Problem with Pickups and Deliveries)问题。该模型类似于宏观层面的配送中心选址-路径问题(Location Routing Problem，简称LRP)，但货位的备选集合的规模较LRP更大且更复杂，路径问题需考虑存货取货两种操作，其约束条件也较LRP只考虑取货操作情况更严格。
目标函数约束条件
                  
                  
                 
        
               
               


             
           
             
两个货位间的时间距离采用切比雪夫距离表示为：
其中约束（1）和（2）确保指令周期j内指定一个空货位供货物存放，约束（3）确保指令周期j内从一个存有货物i’的货位上取货以满足取货需求，约束（4）确保指令周期j 内只访问被分配的存取货位，约束（5）（6）确保被分配的存取货位全部遍历到，约束（7）使访问某一货位（I/O除外）后，必须要从该货位离开，约束（8）反映堆垛机访问货位l后所载货物数量的变化，约束（9）确保使堆垛机从I/O点出发时的载货量满足指令周期内的存货需求，约束（10）确保堆垛机返回I/O点的载货量满足指令周期内取货需求，约束（11）保证堆垛机在运行过程中负载不超过其最大负载限制。
单位时间根据存取货队列情况划分的指令周期集合中，上述模型在每一个指令周期都需求解一次，相邻指令周期序列中空货位和存货货位集合会发生不断的更新，模型中货位的初始分布状态由上一次指令周期模型的求解结果决定，但限于篇幅，多指令周期的优化将另文描述，本文只集中在基本优化单元中单个指令周期的货位分配和路径规划的集成优化上。
TSP/PD和LRP已被证明为NP-hard问题，上述模型嵌套TSP/PD，而且约束较LRP更加严格，虽然现实多载具系统配置的载具数量有限（一般为2-6个），TSP/PD节点数的规模较小，存在采用精确算法求解TSP/PD问题的可能性，但是对货位分配阶段大规模禁忌搜索中每一个可行解精确求解一个TSP/PD问题，其计算代价将大大增加，另外上述集成优化模型需要考虑货位分配优化和拣选路径优化之间的反馈关系，因此单独采用货位指派算法和路径规划算法也难以有效求解，本文设计两阶段的禁忌搜索（Tabu Search）算法进行求解，通过两阶段禁忌搜索的反馈获得多载具AS/RS货位分配和拣选路径的最优方案。

3 算法实现

禁忌算法是求解组合优化问题的性能较优的启发式算法，其主要思想是用禁忌表记录已经到达过的局部最优点或达到局部最优的过程，在下次搜索中不再搜索这些点，以跳出局部最优点，以提高算法性能，最终达到全局最优。其中两阶段禁忌算法是适用于集成优化问题的多阶段启发式算法，已成功应用求解配送中心选址－路径问题^[11]和集装箱码头卸货堆存位置选择－集卡调度问题^[12]，其算法思想有效反映了不同优化层面的反馈作用关系。
本文设计两阶段禁忌搜索算法求解多载具AS/RS货位分配和拣选路径集成优化模型，算法流程如图1。货位分配阶段，通过禁忌算法搜索货物的存取货位分配方案，基于货位分配优化方案，在路径规划阶段，执行另一禁忌算法求解货位访问的最优路径，在路径优化结果基础上计算指令周期的总行程时间，并将此结果反馈到货位分配优化阶段，从而影响货位分配优化阶段的禁忌搜索过程，通过两阶段搜索过程的互相反馈获得模型最优解。下面对两阶段禁忌搜索算法的几个关键技术作一介绍。

图1 两阶段禁忌算法流程

3.1 初始解的构建

货位分配阶段禁忌算法的初始解从可行解集中通过随机方法生成，以“空货位集合＋取货货位集合1＋取货货位集合2＋···”序列的0-1码形式表示货位分配方案；路径规划阶段的禁忌算法初始解则通过改进的最近邻点法（Nearest Neighbor，简称NN）生成，在改进的最近邻点法中，每次的搜索范围由是否存在空载具决定，有空载具最近邻点从空货位和待取货物货位的并集中搜寻，无空载具则只能从空货位集合中搜寻。

3.2 货位分配阶段的邻域搜索策略

由于货位分配涉及存取货位的选择，如果采用简单货位交换方法生成邻域，势必会产生大量的不可行解，影响算法的执行，本文设计一种基于片段的货位交换方法来生成当前解的邻域，例如3载具AS/RS指令周期内需要存放A，B，C货物各一，取出D，E，F货物各一，货位分配方案采用“空货位集合＋存放货物D货位集合＋存放货物E货位集合＋存放货物F货位集合”序列的0-1码表示，其中可行解应该满足空货位序列中三个码位为“1”，表示选择三个空货位，存放货物D，E，F货位序列中各有一个码位为“1”，从四个片段中以一定概率选择某一片段，在片段内进行0-1交换来构造货位分配阶段的邻域，以同时满足解的可行性和搜索覆盖面，邻域规模视备选货位分配备选集合规模而定，去除邻域中被禁忌的对象，生成候选集合，采用改进的NN方法评价候选集合中解的性能，选择最优货位分配方案作为本次迭代的最优解，同时更新货位分配阶段的禁忌表，另外设置货位分配阶段允许无改进迭代次数的阈值MaxNonImp_L，当连续迭代次数达到MaxNonImp_L时，解的性能仍无改进，货位分配阶段的邻域搜索终止。

3.3 路径规划阶段的邻域搜索策略

货位分配方案每次更新后，路径规划阶段要在现有货位分配方案基础上，搜索其最优的货位访问路径方案。路径规划阶段采用交换货位顺序方法构造当前解的邻域，即已选货位集合中两个货位进行对换，由于存取货操作并行存在，需对邻域的解作可行性验证，剔除不满足堆垛机载货容量约束的不可行解，同样设置路径规划阶段允许无改进迭代次数的阈值MaxNonImp_R，当连续迭代次数达到MaxNonImp_R时，解的性能仍无改进，路径规划阶段的邻域搜索终止，整个两阶段禁忌算法也同时终止。

3.4 禁忌表

货位分配阶段和路径规划阶段均选择解本身作为禁忌对象，禁忌表由矩阵表示，矩阵的每一行代表禁忌对象，行标代表禁忌长度，每迭代一次，矩阵各行上移一位，代表对应禁忌长度减一，原首行解禁忌解除，将新加入禁忌对象写入尾行，禁忌长度的选择有赖于问题规模和禁忌表存储所需内存空间的考量，一般货位分配阶段备选货位集合规模较大，可选15-20较长禁忌长度为宜，路径规划阶段可行解集合规模较小，可选5-10较短禁忌长度为宜。实际计算中，为提高计算效率，可对禁忌表参数动态调整，多次搜索后没有改进时，可以适当增加禁忌表的长度，当所有解均被禁忌后，采用基于评价值的特赦规则，其中货位分配阶段采用改进的NN方法对解进行评价，路径规划阶段则直接计算行程时间评价，选取评价较优的解，提前解除禁忌。

4 算例分析

假设相邻货位水平方向间距w=1.5 m，垂直方向间距h=1.5 m，堆垛机水平方向速度v_x=2 m/s，垂直方向的速度为v_y=0.5 m/s，选择40（5层×8列）、80（8层×10列）、120（10层×12列）、160（10层×16列）和200（10层×20列）五种货架货位数规模，选择2-6 载具数量，存货取货所涉及的货物共20种，初始货位分布随机生成，其中每种算例方案取10组计算，结果取10组平均值，货位分配阶段允许最大无改进迭代次数MaxNonImp_L=100，禁忌表长度取20，路径规划阶段允许最大无改进次数MaxNonImp_R=100，禁忌表长度取5，采用Matlab 7.0为计算仿真工具，处理器AMD 2.30 GHz和内存1GB的个人计算机作为计算平台进行数值实验。
选择3载具AS/RS，对不同货位规模的两阶段禁忌算法进行仿真实验，结果如表1，结果表明与初始解相比，两阶段禁忌算法所得的行程时间有明显改善，改进程度平均达到60%，算法的计算时间随着货位规模的增大而缓慢增加，但都能够在合理时间内有效收敛，可以满足多载具AS/RS实际操作中的调度决策需求。
表1 两阶段禁忌搜索算法计算结果

货位数	初始行程时间/s	两阶段禁忌算法得到的行程时间/s	两阶段禁忌算法的计算时间/s
40	34.12	15.97	4.82
80	49.27	17.32	4.97
120	56.17	22.05	5.04
160	56.70	23.25	5.17
200	69.22	24.75	5.21

取10层12列共120货位规模的货架，对不同载具数量的两阶段禁忌算法进行仿真实验，结果如表2，结果表明算法在不同载具数量情况下均能有效改进解的性能，改进程度则随载具数量的增加有所降低，2载具时改进64%，6载具时只有49%，但改进效果仍然明显，随着载具数量增多，算法计算时间显著增加，这与存取货的周期变长及搜索复杂性大大增加有关，但计算时间均处在可承受范围内。
表2 载具数量对两阶段禁忌搜索算法的影响

载具数	初始行程时间/s	两阶段禁忌算法得到的行程时间/s	两阶段禁忌算法的计算时间/s
2	45.52	18.82	2.93
3	57.82	22.27	5.03
4	59.70	29.77	7.39
5	72.97	34.20	9.97
6	79.20	40.05	12.88

为检验本文模型和算法集成优化的性能，取3载具AS/RS，针对不同货位规模，对货位分配－拣选路径分别优化方法和本文的集成优化方法进行仿真比较，其中分别优化方法中货位分配采用遗传算法，最大迭代100代，拣选路径采用改进NN法，比较结果如表3。结果表明无论货位规模大小，两阶段禁忌算法在计算结果性能上和计算速度上都全面优于分别优化方法，计算结果最大改进程度达到23.22％，计算时间的改进程度随着货位规模增大快速增加，最大改进甚至达到90.70%。比较结果有效验证了集成优化模型和算法的优越性，为多载具AS/RS实际作业调度提供了决策工具。
表3 两阶段禁忌算法与分别优化法比较

货位数	分别优化法		两阶段禁忌算法			两阶段禁忌算法较分别优化法的改进程度
	行程时间/s	计算时间/s	行程时间/s	计算时间/s		行程时间		计算时间
40	17.70	6.03	15.90		4.79	10.17%	20.56%
80	22.27	12.45	17.10		5.01	23.22%	59.76%
120	25.27	19.12	22.27		4.98	11.87%	73.95%
160	29.02	32.05	24.15		5.07	16.78%	84.18%
200	27.82	55.46	25.87		5.16	7.01%	90.70%

5 结论

多载具AS/RS指令周期内可访问多个货位进行存取货操作，统一考虑货位分配和拣选路径才能有效缩短行程时间，提高系统整体进出库效率。集成优化模型中优化问题互相嵌套增加了模型复杂性，本文设计两阶段禁忌算法对模型求解，求解过程体现了两个优化问题的相互反馈关系。两阶段禁忌算法在不同货位规模和载具数量下能够显著改善解的质量，而且与分别优化方法相比，能够将行程时间平均降低15%左右，进而相应提高系统出入库效率。未来应该进一步对规划时间内的多指令周期动态货位分配和拣选路径进行优化，以便于多载具AS/RS实际作业调度中灵活使用。

参考文献  (References)
 [1] 柳赛男, 柯映林, 李江雄,等. 基于调度策略的自动化仓库系统优化问题研究[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.(in Chinese).
 [2] 商允伟, 裘聿皇, 刘长有. 自动化仓库货位分配优化问题研究[J]. 计算机工程与应用, 2004(26): 16-21.
SHANG Yunwei, QIU Yuhuang, LIU Changyou. Optimization of goods locations assignment of automated warehouse [J]. Computer Engineering and Applications, 2004(26): 16-21.(in Chinese).
 [3] 肖建, 郑力. 检修备品库的货位优化模型[J]. 清华大学学报:自然科学版, 2008, 48(11): 1883-1886.
XIAO Jian, ZHENG Li. Slotting optimization model for overhaul warehouses[J]. Journal of Tsinghua University:Science and Technology, 2008, 48,(11): 1883-1886.(in Chinese).
 [4] XIAO Jian, ZHENG Li. A correlated storage location assignment problem in a single-block-multi- aisles warehouse considering BOM information[J]. International Journal of Production Research, 2010, 48(5): 1321-1338.
 [5] Lee M. A storage assignment policy in a man-on-board automated storage/retrieval system[J]. International Journal of Production Research, 1992, 30(10): 2281.
 [6] 贾煜亮, 缪立新. 自动化立体仓库中货位实时分配优化问题研究[J]. 北京交通大学学报:社会科学版, 2007, 6(4): 18-24.
JIA Yuliang, MIAO Lixin. Optimization of real-time storage location assignment in automated storage and retrieval system[J]. Journal of Beijing Jiaotong University:Social Science Edition, 2007, 6,(4): 18-24.(in Chinese).
 [7] Chen Lu, Langevin A, Riopel 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.
 [8] Tanaka S. A hybrid algorithm for the input/output scheduling problem of multi-shuttle AS/RSs[C]//Proc Society of Instrument and Control Engineers Annual Conference 2007. Kagawa,Japan: IEEE Press, 2007:2643-2648.
 [9] Dooly D. R, Lee H. F. A shift-based sequencing method for twin-shuttle automated storage and retrieval systems.[J]. IIE Transactions, 2008, 40(6): 586-594.
[10] Potrc I, Lerher T, Kramberger J, et al. Simulation model of multi-shuttle automated storage and retrieval systems[J]. Journal of Materials Processing Technology, 2004, 157-158(20): 236-244.
[11] Liu S. C, Lee S. B. A two-phase heuristic method for the multi-depot location routing problem taking inventory control decisions into consideration[J]. The International Journal of Advanced Manufacturing Technology, 2003, 22(11): 941-950.
[12] 曾庆成, 杨忠振. 集装箱码头卸船作业调度方案的两阶段禁忌搜索算法[J]. 交通运输工程学报, 2007, 7(2): 109-112.
ZENG Qingcheng, YANG Zhongzhen. Two-phase tabu search algorithm of unloading operation scheduling project in container wharf[J]. Journal of Traffic and Transportation Engineering, 2007, 7,(2): 109-112.(in Chinese).
 



本文编号：4150