考虑并行移动的PBS系统取货时间最优改进

doi:10.16381/j.cnki.issn1003-207x.2022.0495

摘要/Abstract

摘要：

基于拼图的存储系统（puzzle-based storage system，PBS系统），是一种新兴的密集存储系统，系统内每个存储单元模块或者是空的或者存有货物，每个货物可以移动到相邻的空货位中。在单步移动假设下，现有的精确算法和启发式算法已经实现了取货过程中的移动步数最小，但却未能有效优化取货时间这一影响系统吞吐量的关键指标。针对多空位PBS系统单任务取货问题，在现有算法解的基础上，设计了基于并行移动的最优算法，即保持移动成本不变的前提下减少取货过程的时间消耗。在不同系统布局下通过大量算例进行了数值实验，结果发现：并行移动在取货时间上平均优化10%以上，随着系统规模的增大，优化的比例逐渐增加，但其边际值是递减的；非目标货物的移动次数和空位实际使用数量是影响并行移动的主要因素；算法在中小规模问题中表现出良好的计算性能。

关键词: 自动化仓库, PBS系统, 取货时间, 并行移动, 最优算法

Abstract:

Puzzle-based storage （PBS） is an emerging compact storage system where each cell is empty oroccupied by an item， and each item can be moved to its adjacent empty cells. Under the single-load movement assumption， some existing exact and heuristic algorithms have enabled the minimum number of moves for the single-item retrieval problem in a puzzle-based storage system with multiple escorts （SRPME）. Nevertheless，they failed to effectively optimize the retrieval time， which is a critical indicator of system throughput.

In this article， both movement cost and retrieval time are taken into account in the SRPME. Based on a solution obtained by the existing algorithms for solving the single-item retrieval problem in PBS system with multiple escorts， an optimal algorithm considering parallel movement is designed， that is， to reduce the moving time of the item retrieval while keeping the number of item-moves unchanged. The proposed algorithmis based on the idea of implicit enumeration， and it only judges the parallelism between the first move of each escort during each iteration.

Extensive numerical experiments are used to evaluate the impact of parallel movement and the algorithm’s performance， where the system size of the instances ranged from 4×4 to 30×30. The results show that the parallel movement saves an overall of more than 10% in retrieval time， and the number of O-move and the actual number of escorts used are the main factors affecting parallel movement.The average optimization ratio increases as the size of the system grows， while its marginal value decreases. The proposed method has good computational performance in small to medium-size issues， which can be seen as a good choose in a large variety of future applications of the PBS systems.

Key words: automated warehouse, puzzle-based storage system, retrieval time, parallel movement, optimalalgorithm

中图分类号:

F273

马云峰,杨习杰,余玉刚, 等. 考虑并行移动的PBS系统取货时间最优改进[J]. 中国管理科学, 2026, 34(1): 212-220.

Yunfeng Ma,Xijie Yang,Yugang Yu, et al. Optimal Improvement of Retrieval Time for PBS System by Considering Parallel Movement[J]. Chinese Journal of Management Science, 2026, 34(1): 212-220.

图/表 10

图1

表1

图2

图3

图4

图5

表2

小规模算例的数值实验结果"

$m × n$	$G$	$A M V$	$A R T$	$A O R T$ (%)	$A C T$ (s)	$m × n$	$G$	$A M V$	$A R T$	$A O R T$ (%)	$A C T$ (s)
4×4	3995	9.26	8.25	10.48	0.0009	4×4	400	7.23	6.43	9.93	0.0005
5×5	8176	12.56	11.23	10.14	0.0010	5×5	700	10.03	8.72	11.91	0.0006
6×6	19225	15.75	14.13	9.87	0.0016	6×6	1000	12.89	11.23	12.60	0.0010
7×7	5500	18.14	16.16	10.02	0.0021	7×7	1400	15.49	13.44	13.14	0.0013
8×8	1750	20.23	17.88	10.37	0.0027	8×8	1900	18.43	15.93	13.91	0.0017
9×9	1050	23.16	20.30	10.98	0.0037	9×9	2400	20.77	17.97	14.09	0.0022
10×10	900	26.06	23.05	10.36	0.0050	10×10	2900	23.50	20.35	14.19	0.0031

表2

表3

中到大规模算例的数值实验结果"

$m × n$	$G$	$A M V$	$A R T$	$A O R T$ (%)	$A C T$ (s)	$m × n$	$G$	$A M V$	$A R T$	$A O R T$ (%)	$A C T$ (s)
10×10	500	24.40	21.40	13.42	0.0047	22×22	500	54.35	46.17	17.21	0.5791
12×12	500	28.55	24.77	13.91	0.0091	24×24	500	59.82	50.99	16.39	1.1202
14×14	500	33.81	29.00	15.34	0.0204	26×26	500	64.08	54.59	16.40	2.1231
16×16	500	38.86	33.15	15.80	0.0536	28×28	500	69.79	59.54	16.68	3.6864
18×18	500	42.91	36.53	16.00	0.1104	30×30	500	76.63	64.95	17.12	6.8289
20×20	500	48.85	41.37	16.73	0.3024

表3

图6

图7

参考文献 19

[1]	Boysen N， de Koster R， Weidinger F. Warehousing in the e-commerce era： A survey［J］. European Journal of Operational Research， 2019， 277（2）： 396-411.
[2]	Azadeh K， De Koster R， Roy D. Robotized and automated warehouse systems： Review and recent developments［J］.Transportation Science，2019，53（4）： 917-945.
[3]	韩东亚，陈然，余玉刚，等. 自动化立体仓库中出入库任务顺序与出库位置选择集成优化研究［J］. 中国管理科学， 2020， 28（10）： 156-164.
	Han D Y， Chen R， Yu Y G， et al. Joint optimization of order sequence and pick position in an AS/RS with multiple in-the-aisle pick positions［J］. Chinese Journal of Management Science， 2020， 28（10）： 156-164.
[4]	刘兵兵，孙李波，余玉刚. 仓储、物流与供应链管理研究新进展［J］. 中国科学技术大学学报， 2017， 47（2）： 176-187.
	Liu B B， Sun L B， Yu Y G. Recent advances on researches of warehousing， logistics and supply chain management［J］. Journal of University of Science and Technology of China， 2017， 47（2）： 176-187.
[5]	Gue K R， Kim B S. Puzzle-based storage systems［J］. Naval Research Logistics （NRL），2007，54（5）： 556-567.
[6]	Zaerpour N， Yu Y， de Koster R B M. Storing fresh produce for fast retrieval in an automated compact cross-dock system［J］. Production and Operations Management， 2015， 24（8）： 1266-1284.
[7]	Yalcin A， Koberstein A， Schocke K O. Motion and layout planning in a grid-based early baggage storage system［J］. OR Spectrum， 2019， 41（3）： 683-725.
[8]	Siddique P J， Gue K R， Usher J S. Puzzle-based parking［J］. Transportation Research Part C： Emerging Technologies， 2021， 127： 103112.
[9]	Kota V R， Taylor D， Gue K R. Retrieval time performance in puzzle-based storage systems［C］//Proceedings of the 2010 Industrial Engineering Research Conference， Peachtree Corners， GA， USA， June 5-9，2010.
[10]	Kota V R， Taylor D， Gue K R. Retrieval time performance in puzzle-based storage systems［J］. Journal of Manufacturing Technology Management， 2015， 26（4）： 582-602.
[11]	Yalcin A， Koberstein A， Schocke K O. An optimal and a heuristic algorithm for the single-item retrieval problem in puzzle-based storage systems with multiple escorts［J］. International Journal of Production Research， 2019， 57（1）： 143-165.
[12]	Ma Y， Chen H， Yu Y. An efficient heuristic for minimizing the number of moves for the retrieval of a single item in a puzzle-based storage system with multiple escorts［J］. European Journal of Operational Research， 2022， 301（1）： 51-66.
[13]	He J， Liu X， Duan Q， et al. Reinforcement learning for multi-item retrieval in the puzzle-based storage system［J］. European Journal of Operational Research， 2023， 305（2）： 820-837.
[14]	Bukchin Y， Raviv T. A comprehensive toolbox for load retrieval in puzzle-based storage systems with simultaneous movements［J］. Transportation Research Part B： Methodological， 2022， 166： 348-373.
[15]	郭鹏辉，肖飞，贾正荣，等. 多模块网格仓储系统最优循环拣选方法［J］. 电机与控制应用， 2021， 48（5）： 93-98.
	Guo P H， Xiao F， Jia Z R， et al. An optimal cyclic picking method for multi-module grid-based storage system［J］. Electric Machines & Control Application， 2021， 48（5）： 93-98.
[16]	郭鹏辉，贾正荣，肖飞，等. 一类多模块网格存储系统分散式控制方法［J］.控制与决策，2022， 37（2）： 438-444.
	Guo P H， Jia Z R， Xiao F， et al. Decentralized control method for multi-module grid-based storage system［J］. Control and Decision， 2022， 37（2）： 438-444.
[17]	Guo P， Xiao F， Rui W， et al. A two-stage path planning method for the rearrangement problem in modular puzzle-based storage system［J］. Mathematical Problems in Engineering， 2021， 2021（1）： 6626569.
[18]	Yu H， Yu Y， de Koster R. Dense and fast： Achieving shortest unimpeded retrieval with a minimum number of empty cells in puzzle-based storage systems［J］. IISE Transactions， 2023， 55（2）： 156-171.
[19]	Garey M R， Johnson D S， Sethi R. The complexity of flowshop and jobshop scheduling［J］. Mathematics of Operations Research， 1976， 1（2）： 117-129.

研究者	优化目标	基本假设	问题类型	最优性	主要研究方法和特点
Gue和Kim^[5]	移动步数	单步移动块移动	单空位位置固定多空位位置固定	最优启发	最早提出PBS理论单空位问题的最优解析解以及位置固定的多空位问题的动态规划算法和启发式算法
Kota等^[9]	移动步数	单步移动	多空位随机分布	最优	多空位问题的整数规划模型，只适用极小规模的问题
Kota等^[10]	移动步数	单步移动	两空位随机分布多空位随机分布	最优启发	2个空位问题的最优解析解多空位问题的启发算法
Yalcin等^[11]	移动步数	单步移动	多空位随机分布	最优启发	基于A*的最优算法用于小规模问题针对大规模问题的启发算法
Ma等^[12]	移动步数	单步移动	多空位随机分布	启发	多空位问题的高效高精度算法，根据求解精度和速度要求，可以通过算法预留的参数设置成多种算法复杂度
Bukchin和Raviv^[14]	移动步数和取货时间	并行移动和块移动	多空位随机分布	最优启发	适用于空位较多时的整数规划和空位较少时的动态规划算法，基于动态规划解的启发式算法只适用于较小规模问题，更多地依赖于离线计算的结果
Yu等^[18]	取货时间	并行移动和块移动	多空位随机分布	最优	利用4个~5个空位实现目标货位无障碍移动，需要大量的并行移动和块移动，这个过程往往需要更高的取货成本
本文	移动步数和取货时间	并行移动	多空位随机分布	最优	在最小化移动步数的基础上，通过并行移动优化取货时间算法在中小规模问题中具有良好的性能，同时也能求解大规模问题