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

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

Abstract

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

CLC Number:

TP273

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.

Figures/Tables 12

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

References 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.

Related Articles 15

[1]	Qin Zhang, Peng Xu, Zhigeng Fang, Sifeng Liu. Periodic Maintenance Model of Parallel Critical System for Major Equipment to Prevent the Failure During the Operation Process [J]. Chinese Journal of Management Science, 2025, 33(10): 67-75.
[2]	Guiqin Xue, Xianlong Ge. Study on Two-stage Dynamic Vehicle Scheduling Optimization Considering the Proactive Category [J]. Chinese Journal of Management Science, 2024, 32(12): 164-172.
[3]	Zheng Wang,Peng Lu,Xiangpei Hu. Method of Locating Racks in Mobile-Rack Warehousing System [J]. Chinese Journal of Management Science, 2024, 32(8): 84-94.
[4]	Tieke Li,Yixuan Su,Wenxin Zhang,Bailin Wang. Interval Multi-objective Optimal Scheduling for Steelmaking-continuous Casting with Processing Time Uncertainty [J]. Chinese Journal of Management Science, 2024, 32(8): 95-106.
[5]	Guohua Wu. Based on Hub-Spoke Network a Practice Heuristic Algorithm Applied to Airline Fleet Assignment [J]. Chinese Journal of Management Science, 2024, 32(1): 158-167.
[6]	Hai-yu WANG. Economic-statistical Optimization Design of Dynamic $n p x$ Control Chart Based on Simply Inspection [J]. Chinese Journal of Management Science, 2023, 31(9): 205-213.
[7]	ZHAI Meng-yue, WANG Zheng, LI Yan-tong, HU Xiang-pei. Research on the Problem of Allocating Commodity Storage Locations in a Mobile-rack Storage System [J]. Chinese Journal of Management Science, 2023, 31(3): 167-176.
[8]	LIU Lang, , WANG Hui, HUANG Dong-hong. The Buy-back Contract of Supplier Risk Aversion under the Asymmetric Information of Sales Cost [J]. Chinese Journal of Management Science, 2023, 31(1): 158-167.
[9]	WU Jiang-hua, JIANG Fan. Vertical Information Acquisition and Horizontal Information Sharing Strategy in a Supply Chain [J]. Chinese Journal of Management Science, 2021, 29(8): 161-173.
[10]	CAO Xiao-ning, WANG Yong-ming, XUE Fang-hong, LIU Xiao-bing. Coordination Strategies for Dual-channel Supply Chain of Fresh Agricultural Products Considering the Fresh-keeping Effort of Supplier [J]. Chinese Journal of Management Science, 2021, 29(3): 109-118.
[11]	LIU Lang, WU Shuang-sheng, SHI Wen-qiang. Research on Emergency Quantity Discount Contract with Stochastic Price under Asymmetric Information [J]. Chinese Journal of Management Science, 2018, 26(3): 169-176.
[12]	ZHANG Han-jiang, YU Hua-ying, LI Cong-ying. Incentive Contract Design and Optimization Of Government Subsidies Policy in the Closed-loop Supply Chain [J]. Chinese Journal of Management Science, 2016, 24(8): 71-78.
[13]	XING Xi-wen, MAO Jun, ZHANG Rui, JIN Zhi-hong. Optimization of Container Loading/unloading Integrated Scheduling in a Container Terminal Based on Hybrid Flowshop [J]. Chinese Journal of Management Science, 2014, 22(10): 97-105.
[14]	JIN Peng, ZUO Chun-rong, YANG Shan-lin, MA Hua-wei. Cutting Stock Problem and Transportation Problem Collaboration Optimization Modeling [J]. Chinese Journal of Management Science, 2013, (2): 91-97.
[15]	LIU Chun-ling, LI Ji-zi, MENG Bo. Research on H_∞ Control of Bullwhip in Cluster Supply Chains Based on Cooperation between Two Single Chains [J]. Chinese Journal of Management Science, 2007, 15(1): 41-46.

系统布局	空位数	改进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

Optimization of Outbound Relocating for Four-way Shuttle System Based on Improved A^* Algorithm

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 12

References 25

Related Articles 15

Metrics

Comments

Recommended 0

Optimization of Outbound Relocating for Four-way Shuttle System Based on Improved A* Algorithm

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 12

References 25

Related Articles 15

Metrics

Comments

Recommended 0

Optimization of Outbound Relocating for Four-way Shuttle System Based on Improved A^* Algorithm