A cross-entropy method for optimising robotic automated storage and retrieval systems

In this paper, we consider a robotic automated storage and retrieval system (AS/RS) where a Cartesian robot picks and palletises items onto a mixed pallet for any order. This robotic AS/RS not only retrieves orders in an optimal sequence, but also creates an optimal store ready pallet of any order. Adapting the Travelling Salesman Problem to warehousing, the decision to be made includes finding the optimal sequence of orders, and optimal sequence of items inside each order, that jointly minimise total travel times. In the first phase, as a control problem, we develop an avoidance strategy for the robot (or automatic stacker crane) movement sequence. This approach detects the collision occurrence causing unsafe handling of hazardous items and prevents the occurrence of it by a collision-free robot movement sequence. Due to the complexity of the problem, the second phase is attacked by a Cross-Entropy (CE) method. To evaluate the performance of the CE method, a computational analysis is performed over various test problems. The results obtained from the CE method are compared to those of the optimal solutions obtained using CPLEX. The results indicate high performance of the solution procedure to solve the sequencing problem of robotic AS/RSs.     

Retrieval sequencing for unit-load automated storage and retrieval systems with multiple openings

Automated storage and retrieval systems (AS/RS) have made a dramatic impact on material handling and inventory control in warehouses and product systems. A unit-load AS/RS is generic and other AS/RS represent its variations. In this paper, we study a problem of sequencing retrieval requests in a unit-load AS/RS. In a unit-load AS/RS, there are usually multiple openings and a unit-load can be stored in any opening. Given a list of retrieval requests and the locations of openings, this problem seeks a sequence of dual cycles that minimizes total travel time taken by a storage/retrieval machine. Previous researchers believed that this problem is computationally intractable and provided greedy-style heuristic algorithms. In this paper, we present an algorithm that combines the Hungarian method and the ranking algorithm for the assignment problem with tour-checking and tour-breaking algorithms. We show that this algorithm finds either a verified optimal or near-optimal solution quickly for moderate size problems. Using this algorithm, we also evaluate the effectiveness of the existing simple heuristics. Computational results are reported.     

Sequencing the storages and retrievals for flow-rack automated storage and retrieval systems with duration-of-stay storage policy

Sequencing of storages and retrievals is an important topic in the automated storage and retrieval system (AS/RS), which largely influences the throughput performance and the operational cost of an AS/RS. In this paper, the problem of sequencing the storages and retrievals in a flow-rack AS/RS with duration-of-stay storage policy is analysed and a two-step heuristic called the grouping-matching method is proposed for minimising the total travel time of operations. The proposed grouping-matching method assigns unit-loads into groups in the grouping step and matches groups and bins of flow rack in the matching step. Two grouping heuristics are designed for the grouping step. The matching subproblem is formulated as an assignment to be solved. Simulation experiments are conducted to evaluate the effectiveness and efficiency of the grouping-matching method and the two grouping heuristics used for the grouping subproblem.     

Relative pre-positioning of storage/retrieval machines in automated storage/retrieval systems to minimize maximum system response time

In this paper, the problem of pre-positioning a storage/retrieval (S/R) machine in an automated storage/retrieval system (AS/RS) when the machine is idle is addressed. The objective of the pre-positioning strategy is to minimize the maximum response time to service incoming requests into the AS/RS. A model is developed under the operating condition that each machine can serve one or multiple dedicated aisle(s) of the system. The aisles are assumed to exist in the same region of the AS/RS and thus form a valid order storage/retrieval zone. A solution algorithm for determining the optimal dwell point or location is developed. The paper assumes a dynamic environment where orders arrive over time and are to be serviced by the S/R machine. A dwell point or strategic point to pre-position the machine is to be determined whenever the S/R machine becomes idle in anticipation of an incoming service request. A numerical example is provided to demonstrate how the technique can be used in an actual production setting to improve the overall order turnaround time.     

Allocating Items to an Automated Storage and Retrieval System

To reduce material handling costs, distribution centers purchase automated storage and retrieval systems (AS/RS). It is often the case that the capacity of the AS/RS is insufficient to store all items. The distribution center must then decide which items to assign to the AS/RS and in what quantities they will be stored. In this paper, we develop a heuristic procedure to solve this problem. A priori and a posteriori tests of the data for the optimality of this heuristic procedure are provided. The proposed procedure is testedwith data gathered fr oma naval supply center.     

Closed form models for determining the optimal dwell point location in automated storage and retrieval systems

This paper examines the problem of where a storage/retrieval machine should reside, or dwell, when an automated storage and retrieval system (AS/RS) becomes idle to minimize the expected value of the next transaction time. After a review of the relevant literature on AS/RS dwell point strategies, this paper proposes several analytical models of these expected response times of the AS/RS based on the relative locations of the input and output ports of the AS/RS. It uses a continuous rack approximation to provide analytical models of the dwell point location problem. These models provide closed form solutions for the dwell point location in an AS/RS. Extensions are made to consider AS/RS with a variety of configurations including multiple input and output ports. These models not only provide solutions to the dwell point location problem, but they provide considerable insight into the nature of this problem, which is particularly valuable when the requirements facing the AS/RS are uncertain.     

Travel time models for double-deep automated storage and retrieval systems

In this paper new analytical travel time models for the computation of cycle times for unit-load double-deep automated storage and retrieval systems (in continuation double-deep AS/RS) are presented. The proposed models consider the real operating characteristics of the storage and retrieval machine and the condition of rearranging blocking loads to the nearest free storage location during the retrieval process. With the assumption of the uniform distributed storage rack positions and the probability theory, the expressions of the single and modified dual command cycle have been determined. The proposed models enable the calculation of the mean cycle time for single and dual command cycles, from which the performance of the double-deep AS/RS can be evaluated. A simulation model of the selected double-deep AS/RS has been developed to compare the performances of the proposed analytical travel time models. The numerical analyses show that with regard to the examined type of double-deep AS/RS with a different fill-grade factor, the results of the proposed analytical travel time models correlate with the results of simulation models of double-deep AS/RS.     

Analytical models for analysis of automated warehouse material handling systems

Automated storage and retrieval systems (AS/RSs) and autonomous vehicle storage and retrieval systems (AVS/RSs) are two competing technologies for the handling, storage and retrieval of unit-loads in the reserve section of an automated warehouse. In this paper, we model variants of the two systems as an open queuing network (OQN) and use an existing tool for the analysis of OQNs, called the manufacturing system performance analyser (MPA), for analysing the performance of the AS/RS and AVS/RS. Experimental results are provided to show that MPA is a better choice than simulation to quickly evaluate alternate configurations of the two systems. We use MPA to answer a series of design questions for AS/RS and AVS/RS design conceptualisation.     

自动化存取系统控制优化研究综述

控制优化是提高自动化存取系统效率的有效途径。对比分析了自动化存取系统控制优化策略在生产和配送领域的应用特点,指出生产领域自动化存取系统控制优化主要关注货物出库的实时性,而配送领域则更关注货物出入库的总体平衡。调研了货位分配、停靠点策略、存取指令排序、订单批次化等主要控制优化问题的国内外研究成果,分析了自动化存取系统控制优化未来的研究方向。     

Sequencing approaches for multiple-aisle automated storage and retrieval systems

Automated storage and retrieval systems (AS/RS) are used in high velocity distribution centres to provide accurate and fast order processing. While almost every industrial system is comprised of many aisles, most of the academic research on the operational aspects of AS/RS is devoted to single-aisle systems, probably due to the broadly accepted hypothesis proposing that an m aisles system can be modelled as m 1-aisle independent systems. In this article, we present two multi-aisles sequencing approaches and evaluate their performance when all the aisles are managed independently first, and then in a global manner. Computational experiments conducted on a multi-aisle AS/RS simulation model clearly demonstrate that a multi-aisle system cannot be accurately represented by multiple single-aisle systems. The numerical results demonstrate that, when dealing with random storage, globally sequencing multi-aisle AS/RS leads to makespan reductions ranging from 14 to 29% for 2- and 3-aisle systems, respectively.     

On sequencing policies for unit-load automated storage and retrieval systems

Automated Storage and Retrieval System (AS/RS) performance highly depends on the characteristics of the mechanical equipment. However, once the system has been physically implemented, achieving its maximum efficiency depends on the way the system is operated. This paper shows that request sequencing (i.e. planning the order in which storage and retrieval requests are performed) is of paramount importance in AS/RS performance. This paper reviews and adapts the most popular storage and sequencing policies to dynamic contexts, and then it proposes a ‘sequencing mathematical model’ (SMM) to simultaneously solve the sequencing and storage location problems. Extensive computational results based on a thorough simulation experiment plan confirm that performing the requests in the right sequence can have a positive impact on AS/RS performance. Our results show that the proposed SMM regularly outperforms other methods. When used in a dynamic context, the proposed SMM may yield up to a 25% reduction in average travel-time compared to the situation where a no-sequencing method is applied.     

在线自动化立体仓库的库位分配方法及其实证研究

库位分配方法是影响立体仓库系统性能和作业效率的一个重要因素。本文结合在线自动化立体仓库系统(AS／RS)实例，分析了在线自动化立体仓库的主要作业需求，提出了一种应用存储特征码进行库位分配的方法。为了检验方法的可行性和有效性，编制程序进行仿真，并以随机库位分配方法作为对比，结果表明应用存储特征码的库位分配方法比随机库位分配方法可显著减少出入库的作业时间。     

Performance evaluation of In-Deep Class Storage for Flow-Rack AS/RS

This article presents a new storage-retrieval method called In-Deep Class Storage, designed for Flow-Rack AS/RS. Class-based storage is a well-known method that has an extensive literature; our method is based on the fact that it is more efficient to dedicate the front layers of each bin to the class of the most popular items rather than dedicating whole bins close to the drop-off station. Clearly, this idea is not trivial to implement due to the dynamic behaviour of such racks. Thus, two separate algorithms have been defined, one for storage and one for retrieval, enabling dynamic use of our approach, with the only hypothesis of a Pareto distribution of item demand. This article presents a simulation study designed to compare the performance of random storage and retrieval with the use of the algorithms. This study shows a significant improvement of the expected retrieval delay, the main performance indicator selected for the study.     

ECONOMIC DESIGN OF REFRIGERATED AUTOMATED STORAGE AND RETRIEVAL SYSTEMS

The objective of this paper is the development of a design model for refrigerated automated storage and retrieval systems (R-AS/RS). Compared with ordinary unit-load AS/RS, the R-AS/RS under this study has several different design and operating characteristics: (I) greater emphasis is placed on the storage function and so it has a double-depth lane in the storage rack; (2) cooling units are required to maintain a cold temperature environment in the system; (3) the maximum number of storage orders handled per unit time is limited by the system capacity. Considering the above characteristics, the design problem is formulated as a non-linear mixed integer programming problem in which the cost of the system is minimized. The decision variables are the storage volume, the number of storage and retrieval (S/R) machines, the type and number of cooling units, and the physical configuration of the building. A case problem is solved to illustrate the model.     

Intelligent control schemes for automated storage and retrieval systems

A new information system approach to the operational controls of automated storage and retrieval systems (AS/RS) is developed and examined. This approach is based on artificial intelligence, state-operator framework for problem solving. Gradually increasing the information level, several operational goal functions are identified for an industrial unit-load food produce AS/RS. These functions use real-time statistical interpolations to select the desired storage and retrieval bins. As a result the AS/RS response adapts itself to stochastic perturbations in the system conditions. Experimental evaluations using multiple variance analysis technique and detailed simulations have shown that the proposed dynamic approach is superior to the common industrial control method currently used in those industrial systems characterized by batch arrivals (and retrievals) of the UL's and non-stationary demand patterns, These evaluations further suggest that improved performance is realized with the increase in the information level. The operational control scheme developed in this paper appears to be an excellent control alternative for unit-load AS/RSs. This is due to its limited computational requirements and the augmented productivity as demonstrated here for a real case study.     

自动存取系统及其仿真分析

自动存取系统是一种新的存取系统,其效率取决于库位地址的分配方式、存取方式以及堆垛机的运行方式等特性。自动存取系统相对于传统存取方式有优点也有缺点。其效率主要采用通过率来评价。对此,提出了用数学模型的方法来仿真分析,给出了模型的一些相应参数、重要假设和理论结果。最后,对一个实例运用Ａｗｅｓｉｍ软件仿真,给出仿真结果。     

Routing problem under the shared storage policy for unit-load automated storage and retrieval systems with separate input and output points

In this study the routing problem for unit-load automated storage and retrieval systems (AS/RSs) with separate input and output points is considered under the shared storage policy. The problem is to find an optimal travel route of a S/R (storage and retrieval) machine to process given storage and retrieval requests so that the total travel time is minimised, where the input and output points are possibly separate and the shared storage policy is assumed. We first give two types of formulations as 0–1 integer linear programming problems corresponding to two types of dwell point settings: the dwell point is the input point and the output point. Next, we propose a simple but efficient exact solution algorithm based on the formulations that utilises a general MILP (Mixed Integer Linear Programming) solver. Its efficiency is then demonstrated by numerical experiments. Instances with 400 items (200 for each storage and retrieval) are solved within 100 s.     

Expected travel time and optimal boundary formulas for a two-class-based automated storage/retrieval system

Our paper studies a two-class-based rectangular-in-time automated storage/ retrieval system (AS/RS). We present explicit formulas for the optima! boundary of the two storage areas as well as for the expected single command cycle time for an optimally designed rack. In the basic model each crane handles a single aisle. These formulas provide the designer with a full picture of the quantitative effects of the various factors (i.e., access frequencies of the two storage areas, and dimensions of the rack) on the optimal boundary of the two storage areas and the achievable cycle lime in the warehouse. We also develop expected travel time formulas for the dual command AS/RS with two-class-based storage policies and obtain the optimal boundary with a one-dimensional search procedure. Similar developments (i.e., expected travel time formulas and optimal boundary search procedures) are discussed for AS/RS with a single command policy but with each crane handling multiple aisles.     

Improvement of AS/RS performance using design and application of common zone

Minimization of overall queue length in AS/RS is studied in this research. In general, class-based storage policy is recommended for overall AS/RS operation, but it has a rack shortage problem under demand variation. To resolve this problem, an area along the board of two classes in AS/RS racks is allocated and is named the common zone. This zone is designed to handle the rack shortage problem associated with the items in a particular class under class-based storage policy. Thirty percent common zone size is determined as the most favorable allocation among various sizes through simulation experiments. This particular size common zone policy is compared with other well-known policies such as class-based, relocation, and random storage policy. These four operation policies under three different levels of workloads with demand variations are simulated. Crane moving time, rack shortages, delay times as well as throughputs are checked for the policy evaluation.     

Designing an optimal turnover-based storage rack for a 3D compact automated storage and retrieval system

Compact, multi-deep (3D) automated storage and retrieval systems (AS/RS) are becoming increasingly popular for storing products. We study such a system where a storage and retrieval (S/R) machine takes care of movements in the horizontal and vertical directions of the rack, and an orthogonal conveying mechanism takes care of the depth movement. An important question is how to layout such systems under different storage policies to minimize the expected cycle time. We derive the expected single-command cycle time under the full-turnover-based storage policy and propose a model to determine the optimal rack dimensions by minimizing this cycle time. We simplify the model, and analytically determine optimal rack dimensions for any given rack capacity and ABC curve skewness. A significant cycle time reduction can be obtained compared with the random storage policy. We illustrate the findings of the study by applying them in a practical example.