基于改进A*算法的四向穿梭车系统出库翻箱优化

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

摘要/Abstract

摘要：

四向穿梭车存储系统是一种基于穿梭车的新型存储和检索系统，能够满足电商环境下海量订单对极高出入库能力的要求。双端进出库端口设置能够释放四向库的性能，按序取货能够提升出库效率，系统多深位的特点会导致检索过程中的翻箱操作，因此，选择合适的翻箱落位操作来减少总翻箱次数至关重要。针对四向穿梭车仓储系统中有限制条件的有序双端出库翻箱问题，以最小化翻箱次数为目标，设计启发式上界和估值函数来改进A^*算法求得最优解。在不同系统布局下生成大量算例进行数值实验。结果表明，与基于最优巷道规则的启发式算法HEUR相比，改进A^*算法在翻箱次数上平均减少16.62%；在相同规模下，矩形布局能够进一步减少翻箱次数；双端相比单端出库布局能够平均减少70.43%翻箱次数。随着系统规模增大，算法优化效果更好，存储密度与翻箱次数的负相关性逐渐减弱。

关键词: 四向穿梭车系统, 翻箱, 双端取货, 启发式上界, 改进A^*算法

Abstract:

A new type of storage and retrieval system based on shuttles， known as the four-way shuttle storage system， is introduced， which is assured to meet the high demand for inbound and outbound capabilities for massive orders in e-commerce environments. The performance of the four-way shuttle system can be enhanced by the establishment of dual-end inbound and outbound ports， and outbound efficiency can be improved through sequential picking. The feature of the system having multiple depth could cause relocation during the retrieval process. It starts from practical application scenarios in this paper. The existing research mainly focuses on the congestion issues related to single-end entry and exit in traditional automated warehouses， as well as the relocation problem of container yards. Therefore， in a dual-end output four-way shuttle system， the selection of suitable relocation and landing operations to minimize the total number of relocations is deemed critical.The shortest path approach is adopted in this paper to address the ordered dual-end outbound relocating problem with limited conditions in the four-way shuttle storage system， aiming to minimize the number of relocations. The state of each block after each relocation operation is treated as a node， and heuristic upper bounds and evaluation functions are designed to enhance the A^* algorithm for finding the optimal solution to the shortest path problem.Numerical experiments were performed on a large scale， with various system layouts generated in different test cases. The results indicate that the improved A^* algorithm， when compared to the heuristic algorithm HEUR based on the optimal lane rules， reduced the average number of relocations by 16.62%. The number of relocations can be further reduced by rectangular layouts under the same scale， and the number of relocations can be decreased by an average of 70.43% with a dual-end outbound layout compared to a single-end outbound layout. The algorithm's optimization effect improves as the system size increases， and the negative correlation between storage density and the number of relocations gradually weakens.

Key words: four-way shuttle system, relocation, dual-end outbound, heuristic upper bound, improved A^* algorithm

中图分类号:

TP273

马云峰,盛聪,杨习杰, 等. 基于改进A^*算法的四向穿梭车系统出库翻箱优化[J]. 中国管理科学, 2025, 33(11): 93-102.

Yunfeng Ma,Cong Sheng,Xijie Yang, et al. Optimization of Outbound Relocating for Four-way Shuttle System Based on Improved A^* Algorithm[J]. Chinese Journal of Management Science, 2025, 33(11): 93-102.

图/表 12

图1

图2

图3

图4

表1

算法中使用的符号说明"

符号	说明
$N$	托盘总数
$r$	巷道索引，巷道集合 $R = 1,2, …, S$ ， $∀ r ∈ R$ ，S表示巷道总数
$u$	深位索引，深位集合 $U = 1,2, …, T$ ，
	$∀ u ∈ U$ ，T表示深位总数
$L$	仓库的状态，初始状态用L₀表示，经过n次翻箱操作后的仓库状态为L_n
γ	开放集合，用于存放每个路径节点的所有可行步骤
θ	封闭集合，用于存放经过评估函数估值后选择的最佳步骤，每个节点的最佳步骤都存入θ后最终组成最短路径

表1

图5

图6

图7

表2

图8

图9

图10

参考文献 25

[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]	田彬，吴颖颖，吴耀华，等. “四向车”拣选系统订单排序优化［J］. 机械工程学报， 2019， 55（18）： 225-232.
	Tian B， Wu Y Y， Wu Y H， et al. Order sequencing optimization for “four-way” shuttle based order picking system［J］. Journal of Mechanical Engineering， 2019， 55（18）： 225-232.
[3]	秦彩云，吴颖颖，吴耀华，等. 两种多层穿梭车系统的性能比较分析［J］.机械工程学报，2020，56（20）： 255-264.
	Qin C Y， Wu Y Y， Wu Y H， et al. Comparative analysis of performance for two kinds of automated vehicle storage/retrieval systems［J］. Journal of Mechanical Engineering， 2020， 56（20）： 255-264.
[4]	李佳，何非，谢刚伟，等. 四向穿梭车式密集仓储入库货位分配方法研究［J］. 计算机工程与应用， 2023， 59（24）： 328-335.
	Li J， He F， Xie G W， et al. Research on location allocation of four-way shuttle storage and retrieval system［J］. Computer Engineering and Applications， 2023， 59（24）： 328-335.
[5]	隋振，吴涛，唐志国，等. 四向穿梭车仓储系统的多订单任务调度优化［J］. 吉林大学学报（理学版）， 2022， 60（2）： 332-342.
	Sui Z， Wu T， Tang Z G， et al. Multi-order task scheduling optimization of four-way shuttle storage system［J］. Journal of Jilin University （Science Edition）， 2022， 60（2）： 332-342.
[6]	马云峰，杨习杰，余玉刚，等. 考虑并行移动的PBS系统取货时间最优改进［J］. 中国管理科学， 2022，DOI：10.16381/j.cnki.issn1003-207x.2022.0495 .
	Ma Y F， Yang X J， Yu Y G， et al. Optimal improvement of delivery time in PBS system considering parallel movement［J］. Chinese Journal of Management Science， 2022，DOI：10.16381/j.cnki.issn1003-207x.2022.0495 .
[7]	Chen X， Yang P， Shao Z. Simulation-based time-efficient and energy-efficient performance analysis of an overhead robotic compact storage and retrieval system［J］. Simulation Modelling Practice and Theory， 2022， 119： 102560.
[8]	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.
[9]	Chen Z， Li X， Gupta J N D. A bi-directional flow-rack automated storage and retrieval system for unit-load warehouses［J］. International Journal of Production Research， 2015， 53（14）： 4176-4188.
[10]	Zou B， Xu X， Gong Y， et al. Modeling parallel movement of lifts and vehicles in tier-captive vehicle-based warehousing systems［J］. European Journal of Operational Research， 2016， 254（1）： 51-67.
[11]	Boysen N， Boywitz D， Weidinger F. Deep-lane storage of time-critical items： One-sided versus two-sided access［J］. OR Spectrum， 2018， 40（4）： 1141-1170.
[12]	Xu L， Liu C， Zhan X， et al. Task scheduling for tier-to-tier four-way shuttle warehousing system［J］. Procedia CIRP， 2021， 104： 1083-1088.
[13]	何昕杰，周少武，张红强，等. 基于改进遗传算法的四向穿梭车系统订单排序优化［J］. 系统仿真学报， 2021， 33（9）： 2166-2179.
	He X J， Zhou S W， Zhang H Q， et al. Order sorting optimization for four-way shuttle system based on improved genetic algorithm［J］. Journal of System Simulation， 2021， 33（9）： 2166-2179.
[14]	张经天，马莹，翁迅，等. 四向穿梭车系统的提升机调度优化［J］.北京邮电大学学报，2022， 45（1）：19-25+81.
	Zhang J T， Ma Y， Weng X， et al. Optimization of lifts scheduling for four-way shuttle systems［J］. Journal of Beijing University of Posts and Telecommunications， 2022， 45（1）： 19-25+81.
[15]	余嘉雄，白红星. 基于改进A^*算法的四向穿梭车路径规划［J］. 机械与电子， 2022， 40（7）： 54-60.
	Yu J X， Bai H X. Four-way shuttle vehicle path planning based on improved a^* algorithm［J］. Machinery & Electronics， 2022， 40（7）： 54-60.
[16]	Caserta M， Schwarze S， Voß S. A mathematical formulation and complexity considerations for the blocks relocation problem［J］. European Journal of Operational Research， 2012， 219（1）： 96-104.
[17]	Zehendner E， Caserta M， Feillet D， et al. An improved mathematical formulation for the blocks relocation problem［J］. European Journal of Operational Research， 2015， 245（2）： 415-422.
[18]	Tanaka S， Voß S. An exact algorithm for the block relocation problem with a stowage plan［J］. European Journal of Operational Research， 2019， 279（3）： 767-781.
[19]	Bacci T， Mattia S， Ventura P. A branch-and-cut algorithm for the restricted Block Relocation Problem［J］. European Journal of Operational Research， 2020， 287（2）： 452-459.
[20]	Borjian S， Galle V， Manshadi V H， et al. Container relocation problem： Approximation， asymptotic，and incomplete information［EB/OL］.（2015-10-07）［2023-09-11］..
[21]	da Silva Firmino A， de Abreu Silva R M， Times V C. An exact approach for the container retrieval problem to reduce crane’s trajectory［C］//Proceedings of 2016 IEEE 19th International Conference on Intelligent Transportation Systems （ITSC）， Rio de Janeiro， Brazil，November 1-4， IEEE， 2016： 933-938.
[22]	Tierney K， Pacino D， Voß S. Solving the pre-marshalling problem to optimality with A* and IDA［J］. Flexible Services and Manufacturing Journal， 2017， 29（2）： 223-259.
[23]	Hottung A， Tanaka S， Tierney K. Deep learning assisted heuristic tree search for the container pre-marshalling problem［J］. Computers & Operations Research， 2020， 113： 104781.
[24]	Boysen N， Briskorn D， Meisel F. A generalized classification scheme for crane scheduling with interference［J］. European Journal of Operational Research， 2017， 258（1）： 343-357.
[25]	Hart P E， Nilsson N J， Raphael B. A formal basis for the heuristic determination of minimum cost paths［J］. IEEE Transactions on Systems Science and Cybernetics， 1968， 4（2）： 100-107.

系统布局	空位数	改进A^*		A^*		HEUR		GAP(%)
系统布局	空位数	AR	T(秒)	AR	T(秒)	AR	T(秒)	GAP(%)
5×5	4	4.99	0.02	4.99	0.02	5.46	0.00	8.61
	7	3.37	0.01	3.37	0.01	3.72	0.00	9.41
6×6	5	9.40	3.55	9.40	5.08	10.95	0.00	14.16
	8	7.14	1.32	7.14	1.88	8.34	0.00	14.39
7×7	6	14.93	94.80	14.93	172.00	18.13	0.01	17.65
	9	12.54	61.73	12.54	113.15	15.48	0.00	19.00
8×8	12	16.70	3906.36	-	-	22.50	0.02	25.78
	16	12.68	2112.26	-	-	16.67	0.02	23.94