Study on bin relocation problem during outbound operation in intelligent forklift-based dense storage system

doi:10.3785/j.issn.1008-973X.2025.10.003

Journal of ZheJiang University (Engineering Science)

2025, Vol. 59

Issue (10): 2023-2033 DOI: 10.3785/j.issn.1008-973X.2025.10.003

Study on bin relocation problem during outbound operation in intelligent forklift-based dense storage system

Zilong LI1,2(

),Tianjian CHENG3,Bo JIN4,Wenming CHENG1,2,Yilun CAO1,2,Peng GUO1,2,*(

)

1. School of Mechanical Engineering, Southwest Jiaotong University, Chengdu 610031, China
2. Technology and Equipment of Rail Transit Operation and Maintenance Key Laboratory of Sichuan Province, Chengdu 610031, China
3. Faculty of Geosciences and Engineering, Southwest Jiaotong University, Chengdu 611756, China
4. College of Management, Shenzhen University, Shenzhen 518055, China

Download:

HTML

PDF(1107KB) HTML
Export: BibTeX | EndNote (RIS)

Abstract

The bin relocation problem during outbound operations was studied to improve the operational efficiency of the intelligent forklift-based dense storage system. A mathematical programming model was developed with defined constraints, aiming to minimize the number of bin relocations. A heuristic method was proposed to generate bin relocation strategies rapidly. A method for obtaining the lower bound was provided, and a branch-and-bound algorithm was constructed to achieve the theoretically optimal solution. Numerical experiments were conducted based on numerous instances generated under different storage area layouts and retrieval volumes. Results showed that both the heuristic method and the branch-and-bound algorithm were highly efficient for small-scale cases. For medium and large-scale cases, the heuristic method promptly generated reasonably feasible solutions, while the branch-and-bound algorithm effectively optimized the initial relocation scheme within a short timeframe, yielding near-optimal solutions. Compared with random relocation strategies, the branch-and-bound algorithm reduced the number of relocations by an average of 43.32%, verifying the effectiveness and practicability of the algorithm. A performance analysis of different warehousing equipment revealed that forward-moving forklifts reduced the number of relocations by an average of 8.59% compared to ordinary forklifts.

Key words： intelligent forklift-based dense storage system bin relocation problem mathematical programming model heuristic method branch-and-bound algorithm

Received: 06 September 2024 Published: 27 October 2025

CLC:

TP 391

Fund: 教育部人文社科项目（21YJC630034）；国家自然科学基金青年科学基金资助项目（72101160）.

Corresponding Authors: Peng GUO E-mail: 2548383665@qq.com;pengguo318@swjtu.edu.cn

	Service
	E-mail this article
	Add to my bookshelf
	Add to citation manager
	E-mail Alert
	RSS
	Articles by authors
	Zilong LI
	Tianjian CHENG
	Bo JIN
	Wenming CHENG
	Yilun CAO
	Peng GUO

Cite this article:

Zilong LI,Tianjian CHENG,Bo JIN,Wenming CHENG,Yilun CAO,Peng GUO. Study on bin relocation problem during outbound operation in intelligent forklift-based dense storage system. Journal of ZheJiang University (Engineering Science), 2025, 59(10): 2023-2033.

URL:

https://www.zjujournals.com/eng/10.3785/j.issn.1008-973X.2025.10.003 OR https://www.zjujournals.com/eng/Y2025/V59/I10/2023

智能叉车密集仓储系统料框出库翻箱问题研究

为了提高智能叉车密集仓储系统作业效率，针对出库作业时的料框翻箱问题，以最小化料框翻箱次数为目标，定义相关约束条件并构建数学规划模型，提出快速求解料框翻箱方案的启发式方法. 给出该问题下界的计算方法，构建分支定界算法以求得理论最优解. 在堆料区布局和出库量不同的情况下，随机生成大量算例进行数值分析. 计算结果表明，在小规模算例中，启发式方法和分支定界算法都具有高效求解能力；在中大规模算例中，启发式方法能够快速获得较为合理的可行解，分支定界算法能够在较短时间内对初始翻箱方案进行优化并给出近似最优解. 相比随机翻箱策略，分支定界算法在翻箱次数上平均减少了43.32%，验证了该算法的有效性和实用性. 通过对比不同仓储设备的性能发现，前移式叉车比普通叉车平均减少了8.59%的翻箱次数.

关键词： 智能叉车密集仓储系统, 料框翻箱问题, 数学规划模型, 启发式方法, 分支定界算法

Fig.1 Warehouse layout diagram of intelligent forklift-based dense storage system

Fig.2 Stockpiling status diagram of bins in storage yard

Fig.3 Diagram of outbound route selection

Tab.1 Definition of model symbols for bin relocation problem in intelligent forklift-based dense storage system

Tab.2 Solution results and runtime of two algorithms for medium and small-scale cases

Tab.3 Solution results and runtime of two algorithms for large-scale cases

Fig.4 Performance comparison of four relocation methods across different-sized cases

Fig.5 Performance comparison of two types of warehouse equipment across different-sized cases


[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 doi: 10.1016/j.ejor.2018.08.023

[2]	李勇昭 2022年中国仓储业发展回顾与2023年展望[J]. 中国储运, 2023, (4): 21- 23 LI Yongzhao Review of the development of China’s warehousing industry in 2022 and prospects for 2023[J]. China Storage and Transport, 2023, (4): 21- 23

[3]	易兵. 中国智能仓储发展与趋势展望 [R]//中国仓储与配送协会. 2022年中国仓储配送行业发展报告. 北京: 中国商业出版社, 2022: 79–94.

[4]	周亚勤, 汪俊亮, 吕志军, 等密集仓储环境下多AGV/RGV调度方法研究[J]. 机械工程学报, 2021, 57 (10): 245- 256 ZHOU Yaqin, WANG Junliang, LÜ Zhijun, et al Research on multi-AGV/RGV scheduling method in intensive storage environment[J]. Journal of Mechanical Engineering, 2021, 57 (10): 245- 256 doi: 10.3901/JME.2021.10.245

[5]	何昕杰, 周少武, 张红强, 等基于改进遗传算法的四向穿梭车系统订单排序优化[J]. 系统仿真学报, 2021, 33 (9): 2166- 2179 HE Xinjie, ZHOU Shaowu, ZHANG Hongqiang, 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

[6]	余嘉雄, 白红星基于改进A算法的四向穿梭车路径规划[J]. 机械与电子, 2022, 40 (7): 54- 60 YU Jiaxiong, BAI Hongxing Four-way shuttle vehicle path planning based on improved A algorithm[J]. Machinery and Electronics, 2022, 40 (7): 54- 60

[7]	KÜBLER P, GLOCK C H, BAUERNHANSL T A new iterative method for solving the joint dynamic storage location assignment, order batching and picker routing problem in manual picker-to-parts warehouses[J]. Computers and Industrial Engineering, 2020, 147: 106645 doi: 10.1016/j.cie.2020.106645

[8]	AZADEH K, DE KOSTER R, ROY D Robotized and automated warehouse systems: review and recent developments[J]. Transportation Science, 2019, 53 (4): 917- 945 doi: 10.1287/trsc.2018.0873

[9]	张牧仁, 项前, 吕志军, 等面向低能耗的密集仓储货位分配优化[J]. 东华大学学报: 自然科学版, 2023, 49 (5): 88- 96 ZHANG Muren, XIANG Qian, LYU Zhijun, et al Optimization of storage location assignment in compact storage and retrieval system for low energy consumption[J]. Journal of Donghua University: Natural Science, 2023, 49 (5): 88- 96

[10]	马云峰, 盛聪, 杨习杰, 等. 基于改进A*算法的四向穿梭车系统出库翻箱优化[EB/OL]. (2023–10–09)[2024–01–09]. https://doi.org/10.16381/j.cnki.issn1003-207x.2023.0911.

[11]	许丽丽, 詹燕, 鲁建厦, 等四向穿梭车仓储系统复合作业调度优化[J]. 浙江大学学报: 工学版, 2023, 57 (11): 2188- 2199 XU Lili, ZHAN Yan, LU Jiansha, et al Compound operation scheduling optimization in four-way shuttle warehouse system[J]. Journal of Zhejiang University: Engineering Science, 2023, 57 (11): 2188- 2199

[12]	占翔南, 徐立云, 凌旭峰, 等多深度四向穿梭车仓储系统调度优化[J]. 计算机集成制造系统, 2022, 28 (8): 2496- 2507 ZHAN Xiangnan, XU Liyun, LING Xufeng, et al Scheduling optimization of multi-deep four-way shuttle warehousing system[J]. Computer Integrated Manufacturing Systems, 2022, 28 (8): 2496- 2507

[13]	ROY D, KRISHNAMURTHY A, HERAGU S, et al Queuing models to analyze dwell-point and cross-aisle location in autonomous vehicle-based warehouse systems[J]. European Journal of Operational Research, 2015, 242 (1): 72- 87 doi: 10.1016/j.ejor.2014.09.040

[14]	CARLO H J, VIS I F A, ROODBERGEN K J Storage yard operations in container terminals: literature overview, trends, and research directions[J]. European Journal of Operational Research, 2014, 235 (2): 412- 430 doi: 10.1016/j.ejor.2013.10.054

[15]	LEHNFELD J, KNUST S Loading, unloading and premarshalling of stacks in storage areas: survey and classification[J]. European Journal of Operational Research, 2014, 239 (2): 297- 312 doi: 10.1016/j.ejor.2014.03.011

[16]	KIM K H, HONG G P A heuristic rule for relocating blocks[J]. Computers and Operations Research, 2006, 33 (4): 940- 954 doi: 10.1016/j.cor.2004.08.005

[17]	ZHU W, QIN H, LIM A, et al Iterative deepening A* algorithms for the container relocation problem[J]. IEEE Transactions on Automation Science and Engineering, 2012, 9 (4): 710- 722 doi: 10.1109/TASE.2012.2198642

[18]	TANAKA S, TAKII K A faster branch-and-bound algorithm for the block relocation problem[J]. IEEE Transactions on Automation Science and Engineering, 2016, 13 (1): 181- 190 doi: 10.1109/TASE.2015.2434417

[19]	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 doi: 10.1016/j.ejor.2011.12.039

[20]	EXPÓSITO-IZQUIERDO C, MELIÁN-BATISTA B, MORENO-VEGA J M An exact approach for the blocks relocation problem[J]. Expert Systems with Applications, 2015, 42 (17/18): 6408- 6422

[21]	ESKANDARI H, AZARI E Notes on mathematical formulation and complexity considerations for blocks relocation problem[J]. Scientia Iranica E, 2015, 22 (6): 2722- 2728

[22]	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 doi: 10.1016/j.ejor.2015.03.032

[23]	JOVANOVIC R, VOß S A chain heuristic for the blocks relocation problem[J]. Computers and Industrial Engineering, 2014, 75: 79- 86 doi: 10.1016/j.cie.2014.06.010

[24]	JIN B, ZHU W, LIM A Solving the container relocation problem by an improved greedy look-ahead heuristic[J]. European Journal of Operational Research, 2015, 240 (3): 837- 847 doi: 10.1016/j.ejor.2014.07.038

[25]	杨小明, 周云鹏, 耿志康, 等基于规则集定向搜索算法的装船翻箱问题[J]. 计算机集成制造系统, 2023, 29 (3): 1040- 1054 YANG Xiaoming, ZHOU Yunpeng, GENG Zhikang, et al Loading relocation problem based on rule set based beam search algorithm[J]. Computer Integrated Manufacturing Systems, 2023, 29 (3): 1040- 1054

[26]	张艳伟, 蔡梦蝶基于逆向强化学习的装船时堆场翻箱智能决策[J]. 同济大学学报: 自然科学版, 2021, 49 (10): 1417- 1425 ZHANG Yanwei, CAI Mengdie An inverse reinforcement learning method for container relocation in container terminal yard during loading[J]. Journal of Tongji University: Natural Science, 2021, 49 (10): 1417- 1425

[27]	JIN B, TANAKA S An exact algorithm for the unrestricted container relocation problem with new lower bounds and dominance rules[J]. European Journal of Operational Research, 2023, 304 (2): 494- 514 doi: 10.1016/j.ejor.2022.04.006

[1]	Zhengxin TU,Jinghua XU,Shuyou ZHANG. Rehabilitation exoskeleton customized design of kinematic joint based on cone programming reconstruction[J]. Journal of ZheJiang University (Engineering Science), 2025, 59(10): 2005-2013.

[2]	Pengzhi LIN,Ming’en ZHONG,Kang FAN,Jiawei TAN,Zhiqiang LIN. Traffic scene perception algorithm based on cross-task bidirectional feature interaction[J]. Journal of ZheJiang University (Engineering Science), 2025, 59(9): 1784-1792.

[3]	Wenhu HUANG,Xing ZHAO,Liang XIE,Haoran LIANG,Ronghua LIANG. Contrastive learning-based sound source localization-guided audio-visual segmentation model[J]. Journal of ZheJiang University (Engineering Science), 2025, 59(9): 1803-1813.

[4]	Jizhong DUAN,Haiyuan LI. Multi-scale parallel magnetic resonance imaging reconstruction based on variational model and Transformer[J]. Journal of ZheJiang University (Engineering Science), 2025, 59(9): 1826-1837.

[5]	Chaoqun DONG,Zhan WANG,Ping LIAO,Shuai XIE,Yujie RONG,Jingsong ZHOU. Lightweight YOLOv5s-OCG rail sleeper crack detection algorithm[J]. Journal of ZheJiang University (Engineering Science), 2025, 59(9): 1838-1845.

[6]	Zhenming LV,Shaojiang DONG,Jingyao HE,Jinlong YANG,Jiawei ZHANG. Underwater bridge pier crack image generation based on improved CycleGAN[J]. Journal of ZheJiang University (Engineering Science), 2025, 59(9): 1846-1855.

[7]	Xuan MENG,Xueying ZHANG,Ying SUN,Yaru ZHOU. EEG emotion recognition based on electrode arrangement and Transformer[J]. Journal of ZheJiang University (Engineering Science), 2025, 59(9): 1872-1880.

[8]	Yicong GAO,Yuejin WANG,Yilei CHEN,Hao ZHENG,Jianrong TAN. Gait matching method of rehabilitation training for exoskeleton considering embodied cognition[J]. Journal of ZheJiang University (Engineering Science), 2025, 59(8): 1557-1564.

[9]	Zhuguo ZHOU,Yujun LU,Liye LV. Improved YOLOv5s-based algorithm for printed circuit board defect detection[J]. Journal of ZheJiang University (Engineering Science), 2025, 59(8): 1608-1616.

[10]	Yue HOU,Qianhui LI,Peng YUAN,Xin ZHANG,Tiantian WANG,Ziwei HAO. Scalable traffic image auto-annotation method based on contrastive learning[J]. Journal of ZheJiang University (Engineering Science), 2025, 59(8): 1634-1643.

[11]	Xuejun ZHANG,Shubin LIANG,Wanrong BAI,Fenghe ZHANG,Haiyan HUANG,Meifeng GUO,Zhuo CHEN. Source code vulnerability detection method based on heterogeneous graph representation[J]. Journal of ZheJiang University (Engineering Science), 2025, 59(8): 1644-1652.

[12]	Yishan LIN,Jing ZUO,Shuhua LU. Multimodal sentiment analysis based on multi-head self-attention mechanism and MLP-Interactor[J]. Journal of ZheJiang University (Engineering Science), 2025, 59(8): 1653-1661.

[13]	Yahong ZHAI,Yaling CHEN,Longyan XU,Yu GONG. Improved YOLOv8s lightweight small target detection algorithm of UAV aerial image[J]. Journal of ZheJiang University (Engineering Science), 2025, 59(8): 1708-1717.

[14]	Jiarui FU,Zhaofei LI,Hao ZHOU,Wei HUANG. Camouflaged object detection based on Convnextv2 and texture-edge guidance[J]. Journal of ZheJiang University (Engineering Science), 2025, 59(8): 1718-1726.

[15]	Rongtai YANG,Yubin SHAO,Qingzhi DU. Structure-aware model for few-shot knowledge completion[J]. Journal of ZheJiang University (Engineering Science), 2025, 59(7): 1394-1402.

Viewed

Full text

Abstract

Cited

Shared

Discussed