自动存储和检索系统中混合货物包装和货物位置分配的集成优化外文翻译资料

Integrated Optimization of Mixed Cargo Packing and Cargo Location Assignment in Automated Storage and Retrieval Systems

Bin Lei, Zhaoyuan Jiang, and Haibo Mu

To improve the delivery efficiency of automated storage and retrieval system, the problem of the integrated optimization of mixed cargo packing and cargo location assignment is addressed. An integrated optimization model of mixed cargo packing and location assignments with the shortest time for the stacker in a certain historical period is established and is transformed into a conditional packing problem. An improved hybrid genetic algorithm based on a group coding method is designed to solve the problem. When the initial population is generated, a new heuristic algorithm is designed to improve the convergence speed of the genetic algorithm considering the correlation and frequency of the goods outbound. A heuristic algorithm for a two-dimensional rectangular-packing problem is designed to determine whether a variety of goods can be mixed in packing. Taking actual data from an automated storage and retrieval system for an aviation food company as an example, the established model and design algorithm are verified and the influence of changes in the outbound delivery orders on the optimization result is analyzed. Te results show that compared to the method of separate storage of goods based on cube-per-order index rules and a phased optimization method of mixed storage of goods, an integrated optimization method of mixed cargo packing and location assignment can improve the outbound delivery efficiency of the stacking machine by 11.43-25.98% and 1.73-5.51%, respectively, and reduce the cargo location used by 50-55% and 0-10%, respectively. The stronger the correlation of the goods leaving a warehouse, the greater the potential of the design method in this paper to improve the efficiency of the stacker.

1. Introduction

In recent years, with the rapid development of e-commerce, intelligent manufacturing, air transportation, and other fields, higher requirements have been proposed for the input–output efficiencies of warehouses and logistics. Automated storage and retrieval systems (AS/RSs) are widely used in various industries for storage. Cargo packing and storage location assignments are essential links in the operation of an AS/RS. When a container stores only one type of goods (known as “separate cargo packing”), the cargo packing is optimized mainly to increase the loading rate of the container and reduce the number of used containers, without much impact on the outbound efficiency of AS/RS. In practical applications, an outbound delivery order often contains a variety of goods. If goods that are often in the same outbound delivery order are mixed and stored in the same container, it can greatly improve the outbound efficiency of the AS/RS. In logistics storage, the probability that two different items are required by the same order is defined as the outbound correlation. Separate cargo packing and cargo location assignment are not strong and can be optimized separately.Mixed packing and cargo location assignment are strongly correlated, which has a great impact on the efficiency of AS/RS. Therefore, the integrated optimization of mixed cargo packing and cargo location assignment must be studied.

The bin-packing problem (BPP) is an overall layout scheme for optimizing the loading of small items into large containers. BPP achieves certain optimization goals under certain constraints. In 1831, Gauss first raised the issue of packing problems, which he called layout problems [1]. The BPP can be divided into one-dimensional, two-dimensional, and three-dimensional cases based on the dimensions of the loaded goods and containers. In AS/RS, to facilitate access, when the goods are mixed and packed, they cannot be stacked. Therefore, whether a variety of goods can be mixed and loaded into the feed bin depends on whether the bottom surface of multiple goods can be loaded into the bottom of the feed bin, which is a two-dimensional packing problem. Te two-dimensional packing problem, as a typical combinatorial optimization problem, has inspired many studies, which have focused on mathematical models or algorithms. Cui [2] proposed a branch and bound algorithm to solve the identical item-packing problem. Polyakovskiy et al. [3] proposed a guided search of the delivery date for the two-dimensional packing problem with hybrid feasibility constraints. Lodi et al. [4] proposed a partial-enumeration algorithm for the two-dimensional packing problem with truncation constraints. He et al. [5] used the tree-search method to iterate and optimize the algorithm results and proposed the best-of-ft algorithm for solving the two-dimensional packing problem. Wei et al. [6] proposed the least-wasted-first algorithm to solve rectangular-packing problem. Shang et al. [7] proposed a heuristic optimal residual-space algorithm based on the idea of making the placement of small rectangles tighter and the remaining space smoother; the three stages were space division, placement-position selection, and optimal solution searching. Tomas and Chaudhari [7] proposed a hyperheuristic algorithm based on a genetic algorithm to solve the two-dimensional packing problem. In the existing research on two-dimensional packing problems, the vast majority of optimization targets are minimizing the quantity of bins used and the main optimization goal of maxed cargo packing in AS/RS is to achieve the highest outbound efficiency. Gao [8] used a clustering method to store a variety of drug combinations in one bin. The shuttle could select a variety of drugs from one bin, thereby improving picking efficiency. Gao only studied the mixed packing problem of drug varieties but did not consider the limitation of the quantity of drugs in stock.

The optimization problem of cargo location assignment for AS/RS has received a significant amount of a

剩余内容已隐藏，支付完成后下载完整资料

自动存储和检索系统中混合货物包装和货物位置分配的集成优化

摘要：为提高自动化仓储检索系统的配送效率，本文提出了混合货物包装与货位分配的集成优化问题。建立了某历史时期堆垛机混货包装和最短时间位置分配的综合优化模型，并将其转化为条件包装问题。针对这一问题，设计了一种改进的基于群编码的混合遗传算法。在初始种群生成时，考虑到货物出站的相关性和频率，设计了一种新的启发式算法来提高遗传算法的收敛速度。针对二维矩形包装问题，设计了一种启发式算法，用于确定包装中是否可以混装各种货物。以某航空食品公司自动化存储与检索系统的实际数据为例，验证了所建立的模型和设计算法，分析了出站交货单变化对优化结果的影响。结果表明，与基于多维数据集/订单索引规则的分阶段货物存储方法和分阶段货物混合存储优化方法相比，混合货物包装和位置分配的综合优化方法可以提高堆垛机的出站交货效率11.43-25.98%和1.73-5.51%。分别减少50-55%和0-10%的货位使用。本文所提出的设计方法对提高堆垛机的效率具有较大的潜力。

一、背景介绍

近年来，随着电子商务、智能制造、航空运输等领域的快速发展，对仓库和物流的投入产出效率提出了更高的要求。自动化存储和检索系统（AS/RSS）广泛应用于各个行业的存储。货物包装和存储位置分配是AS/RS操作中的重要环节。当一个集装箱只存储一种货物（称为“单独货物包装”）时，货物包装的优化主要是为了提高集装箱的装载率和减少已用集装箱的数量，而不会对出站效率产生太大影响。A/R的有效性。在实际应用中，出站交货单通常包含多种货物。如果经常在同一个出站交货单中的货物混合存放在同一个集装箱中，可以大大提高AS/RS的出站效率。在物流仓储中，将同一订单需要两个不同项目的概率定义为出站相关性。单独的货物包装和货位分配不强，可以单独优化，混合包装和货位分配具有很强的关联性，这对AS/RS的效率有很大的影响，因此必须研究混合货物包装和货位分配的集成优化问题。

装箱问题（BPP）是一种优化小物件装入大型集装箱的总体布局方案。BPP在一定的约束条件下实现了一定的优化目标。1831年，Gauss首先提出了包装问题，他称之为布局问题^[1]。根据装载货物和集装箱的尺寸，BPP可分为一维、二维和三维。在AS/RS中，为了方便进出，货物混合包装时，不能堆放。因此，各种货物能否混装进料仓取决于多个货物的底面能否装进料仓的底面，这是一个二维的包装问题。二维包装问题作为一个典型的组合优化问题，引起了许多研究的关注，主要集中在数学模型或算法上。Cui[2]提出了一种分支定界算法来解决同一项目包装问题。Polaykovskiy等人^[3]提出了一个带有混合可行性约束的二维包装问题的交货期的引导搜索。Lodi等^[4]针对具有截断约束的二维包装问题，提出了一种局部枚举算法。He等^[5]采用树搜索法对算法结果进行迭代和优化，提出了求解二维包装问题的最佳FT算法。Wei等^[6]提出了求解矩形包装问题的最小浪费优先算法。Shang等^[7]提出了一种启发式最优残差空间算法，其思想是使小矩形的放置更紧密，剩余空间更平滑；这三个阶段分别是空间划分、放置位置选择和最优解搜索。Tomas和Chaudhari[7]提出了一种基于遗传算法的超启发式算法来解决二维包装问题。在现有的二维包装问题研究中，绝大多数优化目标是尽量减少使用的箱子数量，而AS/RS中最大化货物包装的主要优化目标是达到最高的出站效率。Gao[8]使用聚类方法将多种药物组合存储在一个箱子中。穿梭机可以从一个仓中选择多种药物，从而提高采摘效率。Gao只研究了药品品种的混合包装问题，没有考虑库存药品数量的限制。

AS/RS的货位分配优化问题受到了广泛的关注，许多学者主要从货物周转效率、出站货物交付相关性、货架稳定性、多载体AS/RS、多端口AS/R等角度对货位分配进行了优化研究。和动态货位分配。Heskett[9]提出了每订单多维数据集索引（COI）规则。COI是指所需的货位存储空间除以单位时间内货物的出站交货频率。商品的COI越大，商品应该越接近出口。Lee 等[10]假设订单通常包含两种以上的货物，并且这些货物通常存储在不同的位置。他们设计了一种优于COI规则的新的启发式方法。Sadiq [11]研究了仓库货位的动态分配规律，提出了一种基于物料类别的货位重新分配启发式算法，从而减少了货位重新分配时间和出站交货拣货时间。Song等人 [12]研究了多端口接入类型AS/RS，对货物位置分配和指令序列排序进行了全面的分析和研究。Yang等[13]在改进的2N命令周期模式下，探讨了多梭式自动存储/检索系统中位置分配和排序的综合优化问题。存储和检索（S/R）位置分配和S/R请求排序决策是共同考虑的问题。建立了一个整数二次规划模型来描述这一综合优化问题。近年来，AS/RS的主要研究方向是货位分配和指令序列的集成优化。然而，对于混合货物包装和货位分配的综合优化问题，目前还没有研究。在AS/RS中，货物包装和货物位置分配。

在AS/RS中，货物包装和货位分配是两个相互关联的工作阶段。因此，必须将这两个阶段的优化结合起来，以提高出库效率。在本研究中，我们考虑了这两个阶段之间的关系，并考虑了混合货物包装过程中每个货物底面尺寸和数量的限制。基于某一历史时期的出站交货单数据，建立了以最小化堆垛机出站交货时间为目标的混合货物包装与货位分配的综合优化模型。此外，设计了一种混合遗传算法来求解该模型，并利用实例数据验证了该模型和算法的有效性。

表1：样品出站交货数据

二、问题描述

下面的简单示例说明了混合货物包装和位置分配的集成优化。

本文所研究的AS/RS被假定为一种道路堆放类型。堆垛机只有一辆车，每个位置只能存放一个货柜。

假设有1、2、3类货物，则某一时期的出站货物数据如表1所示。出站作业分小批出库，及时补货，不缺货。三种货物中的任何两种都可以混装在一个集装箱内，但是三种货物不能同时装在一个集装箱内。堆垛机只执行出站作业。堆垛机的备用位置在入口，堆垛机执行一次出站操作的时间包括从入口到取货位置的运行时间、取货时间、从取货位置到入口的运行时间和交货时间。

假设有A、B、C三个货位，堆垛机分别在80、85、90秒内完成这些货位的出站交货，货物包装的树型和货位分配策略如下。（1）货物分开包装，出站交货频率高的货物位于仓库出口附近。（2）混货。货物包装和位置分配分别进行优化。交货相关性高的货物存储在一起，交货频率高的货物位于仓库出口附近。（3）货物混装，货物包装和货位分配综合优化，尽量减少两个时间段的总运行时间。在这些不同的存储策略下，出站货物交付时间如表2所示。

表2显示，在第一阶段的策略1下，堆垛机的出站操作次数由出站货物-1交货次数 出站货物-2交货次数 出站货物-3交货次数给出，即80 60 20=160（次）。交货时间为出站交货1次times;出站交货到A处时间＋出站交货2次times;出站交货到B处时间＋出站交货3次times;出站交货到C处时间，为80times;80 60times;85 20times;90=13300（s）。周期2的TE数据也可以类似地获得。

根据策略2，由于货物1和3同时存储在位置A，因此第一阶段堆垛机的出站操作次数为出站货物1交货次数 出站货物2交货次数 出站货物3交货次数-货物1和3同时出站的次数，即80 60 20-10=150（次）。交货时间为外运货物-交货次数1times;外运至A地点的交货时间 外运货物-交货次数2times;外运至B地点的交货时间 外运货物-交货次数3times;外运至A地点的交货时间-货物1和3同时装船的次数times;到A地点的出站交货时间，即：

80times;80 60times;85 20times;90minus;10times;80=12300（s）。周期2的数据也可以类似地获得。

在策略3下，通过参考策略2下的计算方法，得出堆垛机的出站操作次数和工作时间。

分析表2，在第1和第2阶段，堆垛机在策略1下运行的时间最长。在第一阶段，堆垛机在策略2下运行的时间最短，而在第二阶段，堆垛机在策略3下运行的时间最短。在策略3下，两个周期的总工作时间最短。

上面的例子表明，混合包装可以显著缩短堆垛机的出货工作时间。因此，对混合货物包装和位置分配的阶段性优化并不一定会导致混合货物包装和位置分配问题的最优存储解决方案和集成优化。

表2：不同仓储策略下出境货物交货时间的比较

三。假设和建模

3.1。假设。为了简化模型，对系统提出了以下合理假设：

（1）AS/RS由多条车道组成，每条车道相对独立，有单独的堆垛机和进出口通道；

（2）每个货位可以存放各种货物；

（3）每件货物的最小包装单位为矩形平行六面体；

（4）货物包装时，其底面与集装箱底面正交，货物的高度方向与集装箱的高度方向一致；

（5）混装、包装时，将同一种货物集中存放；

（6）容器底部被认为是两个尺寸坐标系，长边为X轴，宽边为Y轴；

（7）每次进境交付的每一种货物的数量，少于该种货物在一个地点的最大储存能力；

（8）及时补货，出境交货时无缺货；

（9）货位规格相同；

（10）货物运输的出入口在车道第0列第1层；

（11）出境货物在一定期间内交付的相关性和频率相对一致。

3.2。符号定义。模型中的符号定义如下。

n指仓库货物的品种数。

m是指货物仓储的空位数量。即使mle;n的入库货物也可以存放在仓库中。

p 是指一个记录中某一时期的出站交货单数量。

N_i 是指货物库存中最小包装单位的最大库存量i(i= 1, 2, ...,n)。

V_i指货物库存中最小包装单位的体积i(i= 1, 2, ...,n)。

W_i是指货物库存中最小包装单位的重量i(i= 1, 2, ...,n)。

l_i 是指货物库存中最小包装单位的长度i(i= 1, 2, ...,n)。

w_i 是指货物库存中最小包装单位的宽度i(i= 1, 2, ...,<em

剩余内容已隐藏，支付完成后下载完整资料</em

资料编号：[19449]，资料为PDF文档或Word文档，PDF文档可免费转换为Word