基于两阶段混合算法的四向穿梭式密集仓储系统货位分配优化

doi:10.16182/j.issn1004731x.joss.24-0039

摘要/Abstract

摘要：

为了解决四向穿梭车式密集仓储系统货位分配中存在的货位密集分布、穿梭车容易拥堵等问题，结合四向穿梭式密集仓储系统货位分布的特点，将货位进行栅格化处理，构建了以货架稳定性、出入库效率及设备使用均衡为目标建立货位分配模型；针对该模型设计了一种两阶段混合算法：第一阶段通过引入爬山算法改进非支配排序遗传算法的局部搜索策略，求解一组Pareto前沿集；第二阶段由K-means对Pareto前沿集进行剪枝。通过仿真实验对模型和算法的有效性进行分析，结果表明本方案与目标赋予权重的方案相比，设备使用均衡、货架稳定性、出入库效率目标分别优化了3.1%，4.5%和3.4%，所提出的两阶段混合算法的求解结果与速度均优于非支配排序遗传算法。

关键词: 货位分配, 多目标优化, 非支配排序遗传算法, 爬山算法, K-means

Abstract:

To address issues such as the dense distribution of storage locations and the potential congestion of shuttle vehicles in the four-way shuttle dense storage system, a grid-based approach to the storage location distribution is developed. A location allocation model is then constructed with the goals of ensuring shelf stability, improving warehousing efficiency, and balancing equipment utilization. A two-stage hybrid algorithm is designed for the model. In the first stage, the local search strategy of non-dominant sequencing genetic algorithm(NSGA-II) is enhanced by incorporating the hill climbing algorithm to address a set of Pareto front sets. In the second stage, the Pareto front set is pruned using K-means. Simulation experiments are used to analyze the effectiveness of the model and algorithm. Results indicate significant optimizations in equipment usage balance (3.1%), shelf stability (4.5%), and warehousing efficiency (3.4%) compared to the target weighting scheme. The solution results and speed of the proposed two-stage hybrid optimization algorithm outperform those of the NSGA-II.

Key words: allocation of cargo locations, multi-objective optimization, non-dominant sequencing genetic algorithm, hill climbing algorithm, K-means

中图分类号:

TP391.9

吴自松,苌道方,盖宇春 . 基于两阶段混合算法的四向穿梭式密集仓储系统货位分配优化[J]. 系统仿真学报, 2025, 37(5): 1234-1245.

Wu Zisong,Chang Daofang,Gai Yuchun . Optimization of Cargo Location Allocation in Four-way Shuttle Warehousing System Based on Two-stage Hybrid Algorithm[J]. Journal of System Simulation, 2025, 37(5): 1234-1245.

图/表 13

图1

图2

图3

图4

图5

图6

图7

表1

表2

表3

图8

图9

表4

参考文献 22

1	占翔南,徐立云,凌旭峰等.多深度四向穿梭车仓储系统调度优化[J].计算机集成制造系统,2022,28(08):2496-2507.
	Zhan Xiangnan, Xu Liyun, Ling Xufeng, et al. Scheduling Optimization of Multi-depth Four-way Shuttle Storage System[J].Computer Integrated Manufacturing Systems,2022,28(08):2496-2507.
2	韩东亚, 陈然, 余玉刚, 等. 自动化立体仓库中出入库任务顺序与出库位置选择集成优化研究[J]. 中国管理科学, 2020, 28(10): 156-164.
	Han Dongya, Chen Ran, Yu Yugang, 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.
3	黄鹏, 姚锡凡, 胡晓阳, 等. 面向大规模立体仓库货位分配问题的两阶段混合优化算法[J]. 计算机集成制造系统, 2022, 28(8): 2481-2495.
	Huang Peng, Yao Xifan, Hu Xiaoyang, et al. Two-stage Hybrid Optimization Algorithm for Large-scale Automated Warehouse Storage Location Assignment Problem[J]. Computer Integrated Manufacturing Systems, 2022, 28(8): 2481-2495.
4	蔡安江, 叶康, 郭师虹, 等. 双向式自动化立体仓库货位分配优化[J]. 计算机集成制造系统, 2022, 28(12): 4046-4054.
	Cai Anjiang, Ye Kang, Guo Shihong, et al. Optimization of Storage Allocation in Two-way Automated Warehouse[J]. Computer Integrated Manufacturing Systems, 2022, 28(12): 4046-4054.
5	Wang Yanyan, Man Rongjun, Zhao Wanmeng, et al. Storage Assignment Optimization for Fishbone Robotic Mobile Fulfillment Systems[J]. Complex & Intelligent Systems, 2022, 8(6): 4587-4602.
6	Jiang Wei, Liu Jiyin, Dong Yun, et al. Assignment of Duplicate Storage Locations in Distribution Centres to Minimise Walking Distance in Order Picking[J]. International Journal of Production Research, 2021, 59(15): 4457-4471.
7	Guerriero F, Pisacane O, Rende F. Comparing Heuristics for the Product Allocation Problem in Multi-level Warehouses Under Compatibility Constraints[J]. Applied Mathematical Modelling, 2015, 39(23/24): 7375-7389.
8	李佳, 何非, 谢刚伟, 等. 四向穿梭车式密集仓储入库货位分配方法研究[J]. 计算机工程与应用, 2023, 59(24): 328-335.
	Li Jia, He Fei, Xie Gangwei, et al. Research on Location Allocation of Four-way Shuttle Storage and Retrieval System[J]. Computer Engineering and Applications, 2023, 59(24): 328-335.
9	陈雷, 程江峰, 朱永怀, 等. 多任务纺织立库货位分配与任务序列优化方法[J]. 计算机集成制造系统, 2023, 29(4): 1371-1385.
	Chen Lei, Cheng Jiangfeng, Zhu Yonghuai, et al. Multi-task Textile Stereoscopic Warehouse Location Allocation and Task Sequence Optimization Method[J]. Computer Integrated Manufacturing Systems, 2023, 29(4): 1371-1385.
10	Yan Bo, Yan Chang, Long Feng, et al. Multi-objective Optimization of Electronic Product Goods Location Assignment in Stereoscopic Warehouse Based on Adaptive Genetic Algorithm[J]. Journal of Intelligent Manufacturing, 2018, 29(6): 1273-1285.
11	Hakim Nadir Bessenouci, Sari Zaki, Ghomri Latéfa. Metaheuristic Based Control of a Flow Rack Automated Storage Retrieval System[J]. Journal of Intelligent Manufacturing, 2012, 23(4): 1157-1166.
12	付建林, 丁国富, 张剑, 等. 基于响应面和NSGA-Ⅱ的AGV系统多目标优化配置[J]. 系统仿真学报, 2022, 34(5): 994-1002.
	Fu Jianlin, Ding Guofu, Zhang Jian, et al. Multi-objective Optimization Configuration of AGV System Based on Response Surface and NSGA-Ⅱ[J]. Journal of System Simulation, 2022, 34(5): 994-1002.
13	田彬, 吴颖颖, 吴耀华, 等. "四向车"拣选系统订单排序优化[J]. 机械工程学报, 2019, 55(18): 225-232.
	Tian Bin, Wu Yingying, Wu Yaohua, et al. Order Sequencing Optimization for "Four-way" Shuttle Based Order Picking System[J]. Journal of Mechanical Engineering, 2019, 55(18): 225-232.
14	何昕杰, 周少武, 张红强, 等. 基于改进遗传算法的四向穿梭车系统订单排序优化[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.
15	袁福龙, 朱建平. 基于改进蚁群算法的移动机器人最优路径规划[J]. 现代制造工程, 2021(7): 38-47, 65.
	Yuan Fulong, Zhu Jianping. Optimal Path Planning of Mobile Robot Based on Improved Ant Colony Algorithm[J]. Modern Manufacturing Engineering, 2021(7): 38-47, 65.
16	蔡安江, 薛晓飞, 郭师虹, 等. 两端式自动化立体仓库布局堆垛机调度[J]. 中国机械工程, 2019, 30(6): 735-741.
	Cai Anjiang, Xue Xiaofei, Guo Shihong, et al. Stacker Scheduling of Layouts for Automatic Warehouses with Double Ended[J]. China Mechanical Engineering, 2019, 30(6): 735-741.
17	Ju Xinglong, Chen V C P, Rosenberger J M, et al. Fast Knot Optimization for Multivariate Adaptive Regression Splines Using Hill Climbing Methods[J]. Expert Systems with Applications, 2021, 171: 114565.
18	Yu Jingjing, Voß Stefan, Song Xiangqun. Multi-objective Optimization of Daily Use of Shore Side Electricity Integrated with Quayside Operation[J]. Journal of Cleaner Production, 2022, 351: 131406.
19	李树勋, 连超, 潘伟亮, 等. 基于改进NSGA-Ⅱ算法的安全阀动态特性分析及优化[J]. 振动与冲击, 2023, 42(13): 66-74.
	Li Shuxun, Lian Chao, Pan Weiliang, et al. Dynamic Characteristics Analysis and Optimization of Safety Valve Based on Improved NSGA-Ⅱ Algorithm[J]. Journal of Vibration and Shock, 2023, 42(13): 66-74.
20	唐艺军, 王艳灵, 孙浩强. 基于改进NSGA-Ⅱ算法的高维多目标柔性冲压车间生产调度优化[J]. 锻压技术, 2023, 48(11): 204-211.
	Tang Yijun, Wang Yanling, Sun Haoqiang. Production Scheduling Optimization on High Dimensional Multi-objective Flexible Stamping Workshop Based on Improved NSGA-Ⅱ Algorithm[J]. Forging & Stamping Technology, 2023, 48(11): 204-211.
21	付建林, 丁国富, 张剑, 等. 基于响应面和NSGA-Ⅱ的AGV系统多目标优化配置[J]. 系统仿真学报, 2022, 34(5): 994-1002.
	Fu Jianlin, Ding Guofu, Zhang Jian, et al. Multi-objective Optimization Configuration of AGV System Based on Response Surface and NSGA-Ⅱ[J]. Journal of System Simulation, 2022, 34(5): 994-1002.
22	邰彬, 黄杨珏, 沈开程, 等. 基于指标加权K-means++算法的分布式光伏功率波动平抑控制方法[J]. 武汉大学学报(工学版), 2023, 56(11): 1413-1424.
	Tai Bin, Huang Yangjue, Shen Kaicheng, et al. Smoothing Control Method of Distributed Photovoltaic Power Fluctuation Based on the Index Weighted K-means++ Algorithm[J]. Engineering Journal of Wuhan University, 2023, 56(11): 1413-1424.

参数	值
货架列数/排数/层数	10/10/8
货位长度/宽度/高度/m	1/1/1
各层穿梭车的数量	4
提升机平均提升速度/(m/s)	1.2
穿梭车平均行驶速度/(m/s)	1.5
四向穿梭车装载时间/s	5
四向穿梭车卸载时间/s	3
第z层入库平台1坐标	(0，4，z)
第z层入库平台2坐标	(0，8，z)
第z层出库平台1坐标	(11，8，z)
第z层出库平台2坐标	(11，8，z)

序号	设备使用均衡	货架稳定性	出入库效率	序号	设备使用均衡	货架稳定性	出入库效率
1	27.12	2.77	3 680.25	14	26.24	2.69	3 726.05
2	26.15	2.71	3 700.34	15	26.77	2.70	3 717.21
3	26.15	2.70	3 709.28	16	26.96	2.73	3 688.78
4	26.38	2.67	3 741.72	17	26.46	2.73	3 684.76
5	26.46	2.76	3 676.91	18	26.38	2.74	3 680.15
6	26.84	2.79	3 662.09	19	26.69	2.76	3 668.12
7	27.10	2.80	3 669.28	20	26.91	2.77	3 663.03
8	26.32	2.78	3 654.04	21	26.32	2.77	3 659.02
9	26.91	2.79	3 659.93	22	26.91	2.77	3 666.53
10	26.64	2.79	3 650.43	23	★26.15	2.72	3 679.32
11	26.53	2.73	3 694.71	24	26.64	2.80	★3 647.74
12	26.53	2.74	3 688.33	25	26.22	★2.66	3 744.17
13	26.31	2.67	3 733.06

方案	设备使用均衡	货架稳定性	出入库效率
优化/%	3.1	4.5	3.4
Pareto(2)	26.15	2.71	3 700.34
目标权重	26.98	2.84	3 832.31

货物数量	算例编号	NSGA-II				NSGAII-HC-K-means
货物数量	算例编号	F₁	F₂	F₃	T/s	F₁	P₁/%	F₂	P₂/%	F₃	P₃/%	T/s
150	1	28.32	2.78	3 868.40	8.99	28.21	0.40	2.50	10.17	3 607.12	6.75	7.27
	2	28.76	2.47	3 860.92	9.32	27.30	5.06	2.36	4.41	3 514.57	8.97	7.09
	3	28.10	2.60	3 974.07	8.91	26.96	4.07	2.49	4.14	3 581.40	9.88	7.27
	4	29.45	2.69	3 872.53	10.07	27.01	8.27	2.55	5.15	3 708.65	4.23	6.74
	5	27.38	3.08	4 120.30	9.69	25.54	6.71	2.69	12.77	3 725.49	9.58	6.92
	平均	29.02	2.72	3 939.24	9.39	27.00	6.96	2.52	7.35	3 627.45	7.91	7.06
250	1	37.87	3.02	6 893.69	23.90	35.59	6.02	2.66	12.01	6 206.25	9.97	19.13
	2	36.03	3.05	7 182.01	22.86	34.83	3.34	2.85	6.59	6 392.46	10.99	18.48
	3	35.90	3.20	7 089.62	22.93	34.16	4.86	2.86	10.67	6 484.02	8.54	18.20
	4	32.31	3.48	7 170.92	24.96	30.87	4.46	3.07	11.79	6 597.85	7.99	18.76
	5	36.55	3.08	6 584.00	25.35	35.45	3.01	2.91	5.38	6 383.47	3.05	18.66
	平均	35.82	3.17	6 984.05	24.00	34.18	4.58	2.87	9.46	6 412.81	8.18	18.65
400	1	44.35	3.32	11 028.44	39.75	41.09	7.35	3.12	6.13	10 837.76	1.73	28.24
	2	49.45	3.61	10 979.17	35.05	45.34	8.31	3.16	12.47	10 905.67	0.67	28.08
	3	42.60	3.62	11 252.15	40.95	39.31	7.73	3.38	6.74	11 186.12	0.59	28.40
	4	49.83	3.17	10 880.54	41.69	47.61	4.46	3.13	1.12	10 865.10	0.14	28.42
	5	49.84	3.10	11 896.61	40.46	46.70	6.30	3.05	1.75	10 738.75	9.73	28.42
	平均	47.43	3.36	11 207.38	39.58	44.01	7.21	3.17	5.65	10 906.68	2.68	28.31

[1]	顾文斌, 卿洁瑕, 方杰, 刘斯麒. 改进混合优化算法求解多目标IPPS问题[J]. 系统仿真学报, 2025, 37(5): 1197-1209.
[2]	陈静, 杨国威, 张昭冲, 王伟. 基于时空多视野注意残差网络的城市区域交通流量预测[J]. 系统仿真学报, 2025, 37(3): 607-622.
[3]	李兆彬, 叶军, 周浩岩, 汪一心, 韩宇贞. 融合变异萤火虫算法的三支聚类方法[J]. 系统仿真学报, 2025, 37(3): 646-656.
[4]	王科, 官思佳, 殷希彦, 李西兴, 唐红涛. 基于混合遗传禁忌搜索算法的混流装配线平衡优化研究[J]. 系统仿真学报, 2025, 37(1): 167-182.
[5]	黄智钦, 卢恬英, 陈哲毅. 面向大规模IoT系统的多无人机部署与协作卸载[J]. 系统仿真学报, 2025, 37(1): 25-39.
[6]	李飞行, 邢立宁, 周宇. 基于多目标演化优化的SVM对抗仿真测试算法[J]. 系统仿真学报, 2024, 36(9): 2016-2031.
[7]	李二超, 张生辉. 基于DMOEA-APTC算法的无人机在线航迹规划[J]. 系统仿真学报, 2024, 36(9): 2086-2099.
[8]	张闻强, 王晓萌, 张晓晓, 张国辉. 集配一体化车辆路径规划的混合进化多目标优化[J]. 系统仿真学报, 2024, 36(8): 1914-1928.
[9]	蒋权, 魏静萱. 用于动态柔性作业车间调度的实时调度方法[J]. 系统仿真学报, 2024, 36(7): 1609-1620.
[10]	邓明君, 胡辛瑕, 李响, 徐丽萍. 基于车速引导和感应控制的干线协调优化方法[J]. 系统仿真学报, 2024, 36(6): 1309-1321.
[11]	温廷新, 关婷誉. 考虑能耗和运输的有限缓冲区混合流水车间调度[J]. 系统仿真学报, 2024, 36(6): 1344-1358.
[12]	赵嘉, 赖智臻, 吴润秀, 崔志华, 王晖. 层级引导的增强型多目标萤火虫算法[J]. 系统仿真学报, 2024, 36(5): 1152-1164.
[13]	王昱博, 胡成玉, 龚文引. 基于帕累托前沿关系求解约束多目标优化问题[J]. 系统仿真学报, 2024, 36(4): 901-914.
[14]	余翔, 邓千锐, 段思睿, 姜陈. 一种多无人机协同优先覆盖搜索算法[J]. 系统仿真学报, 2024, 36(4): 991-1000.
[15]	曾少达, 刘海林. 5G室内分布系统规划建模及优化算法[J]. 系统仿真学报, 2024, 36(3): 659-672.