An optimal and a heuristic algorithm for the single-item retrieval problem in puzzle-based storage systems with multiple escorts

Puzzle-based storage systems consist of densely stored unit loads on a square grid. The problem addressed in this paper is to retrieve a stored unit load from a puzzle-based storage using the minimum number of item moves. While previous research contributed optimal algorithms for only up to two empty locations (escorts), our approach solves configurations where multiple empty locations are arbitrarily positioned in the grid. The problem is formulated as a state space problem and solved to optimality using an exact search algorithm. To reduce the search space, we derive bounds on the number of eligible empty locations and develop several search-guiding estimate functions. Furthermore, we present a heuristic variant of the search algorithm to solve larger problem instances. We evaluate both solution algorithms on a large set of problem instances. Our computational results show that the algorithms clearly outperform existing approaches where they are applicate and solve more general configurations, which could not be solved to optimality before. The heuristic variant efficiently yields high-quality solutions for significantly larger instances of practically relevant size.     

A heuristic travel time model for random storage systems using closest open location load dispatching

A heuristic method is proposed for estimating travel times in unit load random storage systems where incoming loads are dispatched to the closest available storage positions. A queuing model representation is used where servers correspond to storage positions and the service rate is based on the turnover distribution of stored loads. The resultant state distribution is applied to approximate storage position occupancy probabilities useful for generating storage and retrieval travel time estimates. Computational results suggest that the heuristic procedure yields smaller errors in random storage travel time estimates than alternative models.     

Travel-time models and fill-grade factor analysis for double-deep multi-aisle AS/RSs

Double-deep multi-aisle automated storage/retrieval systems are increasingly applied for storing and retrieving unit loads, with advantages of increased space utilisation, reduced number of aisles and improved efficiency of storage rack (S/R) machines. In such systems, the retrieval process may consist of the rearrangement of blocking loads, based on the assumptions of uniformly distributed storage locations and random storage policy. We formulate analytical travel-time models of both single- and dual-command cycles under three rearrangement rules. We validate the analytical travel-time models by simulation and conduct numerical experiments to analyse the effect of the number of aisles an S/R machine serves, the fill-grade factor and the command cycles on the expected travel time of the S/R machine. The results show that the expected travel time of the S/R machine is increasing with the increase in the number of aisles an S/R machine serves and the increase in the fill-grade factor, and dual command cycle outperforms single-command cycle in terms of cycle time. To deal with the trade-off between the storage space cost and the operational cost of the S/R machine, we develop a decision model for finding an optimal fill-grade factor to minimise the total cost. We find the condition when an optimal fill-grade factor exists and show how to calculate it. Based on the decision model, we compare the performance of double-deep multi-aisle automated storage/retrieval system (AS/RSs) and single-deep single-aisle AS/RSs. The results show that double-deep multi-aisle AS/RSs outperform single-deep single-aisle AS/RSs in terms of total cost, although double-deep multi-aisle AS/RSs need more storage locations.     

冰蓄冷系统优化蓄冷策略的探讨

本文提出了优化蓄冷策略的理念,该策略与其它运行策略相比,其优势在于它将负荷特点、电价结构等多方面因素考虑了进去,通过该策略计算得出的设备容量可以满足设计日负荷的需要,同时可以使年相当投资费用为最小.并以具体负荷为基础,非常详细的分析了优化蓄冷策略所涉及的各种问题的计算,而且通过计算机程序描绘出各种关系图,以便于清楚的掌握各种量的变化关系.     

Application of storage consolidation intervals to approximate random storage transaction times with closest open location load dispatching

A new modelling approach is proposed for estimating storage/retrieval transaction times in warehouse systems using random storage and closest open location load dispatching. The method is based on estimating intervals between consolidations of the active storage envelope defined by the most remote occupied storage position in a warehouse. This enables the calculation of the expected number of interspersed storage vacancies within the storage envelope which can then be applied in transaction time calculations. Computational results for test problems suggest that the method performs well relative to alternative procedures reported in the literature.     

Propagation of unit location uncertainty in dense storage environments

Dense storage systems provide high-space utilisation; however, because not all units are immediately accessible, selectively offloading units can require shifting of other stored units in order to access the requested unit. Given an initial certainty in unit location, a discrete time Markov Chain is developed to quantify the growth of unit location uncertainty as a function of retrieval requests. As the first to mathematically model uncertainty propagation in dense storage operations, metrics are developed to analyse the model. A theoretical understanding of the relationship among storage density, retrieval times and unit location uncertainty is provided. Finally, a case study using inventory and load plan data from a military application illustrates how the developed models can be used by managers to evaluate selective offloading policies and layouts.     

Rack shape and energy efficient operations in automated storage and retrieval systems

Energy efficiency has become a primary goal to be pursued for sustainable logistics. In automated storage and retrieval systems this leads to revise the traditional control policies aimed at picking time minimisation and to pay more attention to rack configuration, which has been not a research concern from the time-based perspective. Proper models for energy calculation should be developed by introducing new factors neglected in time analysis, such as the weight of unit loads and the differentiation of shifts along the horizontal and vertical axis as regard energy requirements, due to different contribution of gravity, inertia and friction. In this study, a classification of racks based on system height is proposed in order to select the proper crane specifications needed to compute the torque to be overcome by motors to serve a given location within a rack. An overall optimisation model based on Constraint Programming hybridised with Large Neighborhood Search is developed, allowing the joint application of the best control policies for storage assignment and sequencing both for time and energy-based optimisation, as well as the introduction of multiple weight unit loads and energy recovery. Simulations analysis is performed in order to assess the impact of the rack shape on energy saving. Results show how, regardless the demand curve and the optimisation objective, the best performances in terms of energy efficiency are reached by the intermediate height rack shapes, while the lower ones outperform when considering travel time performance.     

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.     

Travel time models for deep-lane unit-load autonomous vehicle storage and retrieval system (AVS/RS)

Autonomous vehicle storage and retrieval systems use vehicles that move horizontally along rails within the storage racks, while vertical movements are provided by lifts. The solution proposed in this paper addresses a particular system configuration that works with multiple deep storage lanes that are widely used in the food and beverage industry, characterised by large volumes of products of limited variety. The generic deep lane is single item, i.e. one stock keeping unit, and single batch, i.e. one production lot, thereby affecting the performance of the system in terms of storage capacity utilisation and throughput. Determining the number and depth of the lanes is crucial to aid the design and control of such a storage system. The aim of this paper was to support the design of AVS/RSs though a set of original analytic models for the determination of the travelled distance and time for single-command and dual-command cycles given alternative layout configurations. The models are validated by simulation and exemplified with a real-warehousing case study. The paper presents useful guidelines for the configuration of the system layout including the determination of the optimal shape ratio and the length of the lanes.     

A decision model to determine the number of shuttles in a tier-to-tier SBS/RS

Shuttle-based storage and retrieval systems (SBS/RSs), which are designed to increase throughput capacity and flexibility, are a type of automated storage and retrieval system used for lightweight loads. SBS/RSs can increase throughput capacity by using multiple shuttles and elevators as storage and retrieval machines (SRMs). They can also facilitate improvements in flexibility since they are able to adjust the number of SRMs according to transaction demands. Thus, determining the number of shuttles is an important issue in tier-to-tier SBS/RSs. In this paper, a decision model to determine the number of shuttles is proposed. The model is based on the travel time model, and it considers parameters such as the physical configuration, velocity profile and the probability that the shuttle operates a dual command. Finally, the throughput capacity from the travel time model is compared with that from a simulation-based approach in order to verify the effects of the model. In addition, a critical discussion regarding the characteristics of the tier-to-tier system is provided.     

An optimisation model and its effective beam search heuristics for floor-storage warehousing systems

This paper presents an optimisation model and its effective solution technique using beam search heuristic for floor-storage warehousing systems. For a floor-storage system, storage can be accessed from the top of stacks only. The objective is to minimise the number of re-handling operations by optimally determining the storage location and by grouping products for each customer that fit a given sequence for receiving and retrieving operations. An integer programming model is formulated and an approximate solution technique based on the beam search method is proposed to solve the problem by incorporating effective heuristics to reduce the search space using future receiving and retrieving requests. The effectiveness of the proposed method is demonstrated for industrial warehousing problems in a steel plant with 58 storage areas involving more than 3000 retrieving operations. The proposed solution method is shown to be more efficient than the traditional branch-and-bound method for solving integer programming problems.     

Picking strategies to the two‐carousel‐single‐server system in an automated warehouse

Abstract

An automatic storage system comprised of two storage carousel conveyors and a retrieval apparatus integrated by computers has been considered in this paper. The order picking problem for such a two‐carousel‐single‐server system is presented here. The retrieval time is analyzed by a two‐stage solution procedure for the scheduling sequence of retrieving items from the system in order to satisfy an order requirement. The analytical results can be directly applied for the scheduling of the carousel storage system.     

Analysis of storage assignment policies in less than unit load warehousing systems

Analytical models for the analysis of item location policies in unit load storage and retrieval systems are extended to less than unit load warehousing systems. The models are used to compare dedicated storage using cube per order index item dispatching and randomized storage using closest open location item dispatching with respect to total item space requirements, orderpicking cycle times and system responsiveness. Despite a number of computational limitations, it is argued that the models provide practical tools for analysis of less than unit load systems prior to development of simulation-based models or for validation of simulation-generated model results. The application of the models are demonstrated for a sample problem.     

Relative positioning of a load extractor for a storage carousel

The use of carousels in manufacturing for the storage of work-in-process items is very common. A major reason for the popular use of carousels is to store work-in-process items closer to the workstations and therefore minimize handling and the time taken to satisfy an item retrieval request from storage. Although carousel load retrieval times are considerably less than those of normal warehouses, the average response time can be further improved through proper prepositioning of the load extractor machine in anticipation of storage/retrieval requests. Two models are presented in this paper to strategically preposition the extractor machine when idle to minimize the system response time. In the first model the emphasis is on preposition of the extractor machine to minimize the maximum system response time when the extractor machine becomes idle. In contrast, the emphasis on the second model is to preposition the machine to minimize the expected system response time when the machine becomes idle. Two modes of carousel operation, (a) unidirectional rotation capability and (b) bidirectional rotation capability, are considered. Solution procedures based on mathematical models are developed to obtain optimal solutions. The developed procedures can be embedded in a carousel controller and used for on-line control and prepositioning of the extractor machine to improve the carousel system's operational efficiency. Computer simulation is performed under various traffic rates and storage methods to analyze the system performance under these two prepositioning strategies and one other traditional carousel prepositioning strategy commonly in use today. An on-line control architecture to implement the proposed prepositioning strategies is also presented.     

The impact of dwell point policy in an Automated Storage/Retrieval System

Automated storage and retrieval systems (AS/RS) are devices that allow intensive storage of materials. They can improve the supply chain performance, assuring more available volume for storage, lower labour costs and higher handling throughput of warehousing. Furthermore, the automated control allows the probability of errors in storage and retrieval to be minimised, along with the probability of product damage during movements. The purpose of the paper is to find the best solution in order to find the optimal dwell point policy, among different rules, able to minimise the travel time and distance travelled by stacker cranes, and consequently warehousing costs. An original and innovative model was developed in order to investigate the dwell point position for random allocation of unit loads. A software platform was developed to validate the proposed model by computer simulations. The performance of the system was analysed in a parametric/continuous way, varying at the same time the number of spans and levels, the height of the input/output point and the interval between requested missions. The results show that the developed model allowed convenience areas to be identified among the policies in which the travel time, distance travelled, and consequently warehousing costs are minimised, by varying different parameters.     

Multi-shuttle automated storage/retrieval systems

Multi-shuttle automated storage/retrieval systems have been developed for use in factories and distribution centers because they are more efficient than single-shuttle systems (owing to less empty travel). This improved efficiency results in more agile support (flexible response, less waiting time, etc.) for the production system the storage/retrieval system serves. In this paper we develop analytical models to estimate the throughput in multi-shuttle systems. Throughput improvements greater than 100% are illustrated when triple-shuttle systems are compared with single-shuttle systems.     

Belt-conveyor based efficient parallel storage system design and travel time model analysis

This paper presents a belt-conveyor based parallel storage system (PSS). Compared with the conventional AS/RS, it has advantages including more efficient utilisation of storage space, and faster storage and retrieval of products. The PSS consists of three components: the automated retrieval system (ARS), the automated storage system (ASS) and the compact storage rack (CSR). In the ARS, a vertical screw conveyor is used to facilitate the vertical movement of the unit loads, while a powered belt-conveyor is used for the horizontal dimension. Additionally, a powered conveyor system enables motion along the depth dimension, meaning each lane in the CSR is connected to several storage cells. Horizontal belt-conveyor and powered conveyor in the lane constitute cross-belt which causes the parallel process. On the other side of the rack, a unit load lift, a RGV lift, several rail-guided vehicles and a buffer rack constitute the ASS. Based on the system, we formulate separate travel-time models for ARS and ASS, under the assumption of randomised, uniformly distributed storage rack positions. Computer simulation with Matlab is used to validate the models, and optimise the automated storage system.     

苗绣纹样搜索中草图和文本检索的认知负荷对比研究

目的 为了探究一种更高效的苗绣纹样检索方式,通过对手绘草图检索及文本检索过程中的认知负荷来进行对比研究。方法 首先通过构建认知负荷信息检索过程模型,对5个认知阶段的平均认知负荷及所需时间进行实验对比;其次通过眼动指标(持续注视时间、眼球扫视振幅、眼球直径)及NASA-TLX评估对两种检索过程的认知负荷进行分析;最后基于眼动追踪得到可视化眼动数据(热点图、注视轨迹)验证是否符合检索任务需求。结论 基于手绘草图的图形检索方式更适合于苗绣纹样检索,通过主、客观融合对比实验验证了草图检索的高效性,同时也验证了眼动追踪和NASA_TLX具有相关性,能更有效地进行认知负荷测量。     

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.     

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.