Research on Hybrid Solution Algorithm for Layout Problem of Rectangular Parts with Multiple Constraints

doi:10.16182/j.issn1004731x.joss.22-1258

Abstract

Abstract:

A hybrid algorithm based on a cutting and matching algorithm and an improved ant colony algorithm was proposed to solve the layout problem of rectangular parts in the process of wood and glass blanking. A layout optimization model was established to maximize the mean square utilization and the remaining processing time; the ant colony algorithm was used as the layout sequence algorithm to determine the layout sequence of some parts and meet the processing time constraint. In order to improve the search efficiency of the ant colony algorithm, an adaptive pheromone updating strategy was proposed, and a hybrid mutation strategy based on genetic mutation and 2-opt mutation was introduced to enhance the local search capability. For the arrangement of parts on the workblank, in order to improve the mean square utilization of the workblank and meet the guillotine constraint, a cutting and matching algorithm was proposed to optimize the layout of rectangular parts. Finally, the improved algorithm was compared with other optimization algorithms by international standard test cases and actual enterprise cases, and the effectiveness of the proposed hybrid algorithm was verified.

Key words: layout of rectangular parts, ant colony algorithm, guillotine, multiple constraints, hybrid mutation strategy

CLC Number:

TP391.9

Liu Ye, Ji Weixi, Su Xuan, Zhao Hongxuan. Research on Hybrid Solution Algorithm for Layout Problem of Rectangular Parts with Multiple Constraints[J]. Journal of System Simulation, 2024, 36(3): 743-755.

Figures/Tables 15

Fig. 1

Fig. 2

Fig. 3

Fig. 4

Fig. 5

Fig. 6

Fig. 7

Fig. 8

Fig. 9

Table 1

Fig. 10

Table 2

Table 3

Table 4

Table 5

References 17

1	Ortmann Frank G, Ntene Nthabiseng, H van Vuuren Jan. New and Improved Level Heuristics for the Rectangular Strip Packing and Variable-sized Bin Packing Problems[J]. European Journal of Operational Research, 2010, 203(2): 306-315.
2	张怀宇, 杨根科, 白杰. 二维Strip Packing问题的嵌套启发式算法[J]. 系统仿真学报, 2012, 24(8): 1601-1605, 1623.
	Zhang Huaiyu, Yang Genke, Bai Jie. Nested Heuristic Algorithm for Two-dimensional Strip Packing Problem[J]. Journal of System Simulation, 2012, 24(8): 1601-1605, 1623.
3	张子成. 基于矩形拼接的"一刀切"矩形排样优化设计[J]. 现代制造工程, 2018(4): 103-107, 157.
	Zhang Zicheng. Optimal Design of Rectangular Layout Based on Rectangular Mosaic with Guillotine Constraints[J]. Modern Manufacturing Engineering, 2018(4): 103-107, 157.
4	刘诚, 孙远升, 花军, 等. 基于遗传-贪心混合搜索的人造板下料算法[J]. 林业工程学报, 2021, 6(4): 127-133.
	Liu Cheng, Sun Yuansheng, Hua Jun, et al. Cutting of Wood-based Panel Based on Genetic Greedy Hybrid Search[J]. Journal of Forestry Engineering, 2021, 6(4): 127-133.
5	Liu Ya, Chu Chengbin, Wang Kanliang. A Dynamic Programming-based Heuristic for the Variable Sized Two-dimensional Bin Packing Problem[J]. International Journal of Production Research, 2011, 49(13): 3815-3831.
6	Hong Shaohui, Zhang Defu, Lau H C, et al. A Hybrid Heuristic Algorithm for the 2D Variable-sized Bin Packing Problem[J]. European Journal of Operational Research, 2014, 238(1): 95-103.
7	Wei Lijun, Wee Chong Oon, Zhu Wenbin, et al. A Goal-driven Approach to the 2D Bin Packing and Variable-sized Bin Packing Problems[J]. European Journal of Operational Research, 2013, 224(1): 110-121.
8	Martin Mateus, Morabito Reinaldo, Munari Pedro. A Bottom-up Packing Approach for Modeling the Constrained Two-dimensional Guillotine Placement Problem[J]. Computers & Operations Research, 2020, 115: 104851.
9	Gardeyn Jeroen, Wauters Tony. A Goal-driven Ruin and Recreate Heuristic for the 2D Variable-sized Bin Packing Problem with Guillotine Constraints[J]. European Journal of Operational Research, 2022, 301(2): 432-444.
10	Bennell J A, Lai Soon Lee, Potts C N. A Genetic Algorithm for Two-dimensional Bin Packing with Due Dates[J]. International Journal of Production Economics, 2013, 145(2): 547-560.
11	Arbib Claudio, Marinelli Fabrizio, Pizzuti Andrea. Number of bins and Maximum Lateness Minimization in Two-dimensional Bin Packing[J]. European Journal of Operational Research, 2021, 291(1): 101-113.
12	Liu Qiang, Cheng Huibing, Tian Tian, et al. Algorithms for the Variable-sized Bin Packing Problem with Time Windows[J]. Computers & Industrial Engineering, 2021, 155: 107175.
13	Stodola Petr, Michenka Karel, Nohel Jan, et al. Hybrid Algorithm Based on Ant Colony Optimization and Simulated Annealing Applied to the Dynamic Traveling Salesman Problem[J]. Entropy, 2020, 22(8): 884.
14	Stodola Petr, Otřísal Pavel, Hasilová Kamila. Adaptive Ant Colony Optimization with Node Clustering Applied to the Travelling Salesman Problem[J]. Swarm and Evolutionary Computation, 2022, 70: 101056.
15	胡蓉, 陈文博, 钱斌, 等. 学习型蚁群算法求解绿色多车场车辆路径问题[J]. 系统仿真学报, 2021, 33(9): 2095-2108.
	Hu Rong, Chen Wenbo, Qian Bin, et al. Learning Ant Colony Algorithm for Green Multi-depot Vehicle Routing Problem[J]. Journal of System Simulation, 2021, 33(9): 2095-2108.
16	Yan Yuzhe, Sohn H S, Reyes G. A Modified Ant System to Achieve Better Balance Between Intensification and Diversification for the Traveling Salesman Problem[J]. Applied Soft Computing, 2017, 60: 256-267.
17	Ebadinezhad Sahar. DEACO: Adopting Dynamic Evaporation Strategy to Enhance ACO Algorithm for the Traveling Salesman Problem[J]. Engineering Applications of Artificial Intelligence, 2020, 92: 103649.

规模	毛坯使用种类数	毛坯使用个数	利用率≥90%	利用率≥95%
小	6	7	6	6
中	6	27	23	20
大	6	68	61	59

数据集	IACA-CM	GDRR	BFS	HHA
平均值	95.83	95.76	87.43	94.33
M1	95.3	96.8	91.2	96.8
M2	95.5	94.4	81.0	91.4
M3	96.7	96.1	90.1	94.8

数据集	IACA-CM	GDRR	BFS	HHA
平均值	85.18	83.03	68.18	76.89
Ⅰ	92.8	88.5	78.5	83.7
Ⅱ	93.8	93.1	73.2	92.7
Ⅲ	86.8	84.5	70.2	75.0
Ⅳ	88.2	87.4	70.0	84.0
Ⅴ	83.0	81.7	66.2	71.6
Ⅵ	85.2	86.3	64.2	82.5
Ⅶ	84.8	81.2	65.5	73.4
Ⅷ	83.7	80.3	67.0	73.8
Ⅸ	66.1	60.8	54.2	55.7
Ⅹ	87.4	86.5	75.8	81.5

数据集	IACA-CM	GDRR	BFS	HHA
平均值	91.00	90.90	70.30	86.86
Nice25i	89.4	99.6	55.6	90.0
Nice50i	90.7	87.5	60.5	79.6
Nice100i	88.9	84.2	64.3	77.9
Nice200i	85.0	85.7	72.4	83.2
Nice300i	89.3	87.0	75.3	84.5
Nice400i	89.0	88.9	73.4	86.4
Nice500i	89.7	87.5	76.9	86.6
Path25i	92.9	100	62.2	94.5
Path50i	92.3	96.2	67.1	90.0
Path100i	93.3	91.2	69.7	87.4
Path200i	92.1	89.3	76.5	87.1
Path300i	94.7	91.3	76.3	90.5
Path400i	93.2	90.9	78.4	89.9
Path500i	93.5	93.3	75.6	88.4

数据集	IACA-CM	GDRR	BFS	HHA
KBH-L1	95.3	90.6	76.3	86.0
KBH-L2	90.7	89.5	69.5	77.2
KBH-L3	93.4	90.4	76.8	87.5
KBH-L4	91.8	88.2	70.0	83.1
KBH-L5	94.1	91.0	79.1	86.3
KBH-L6	93.0	86.9	71.7	79.7
KBH-L7	93.2	90.5	78.9	89.6
KBH-L8	95.7	92.0	77.5	89.7
KBH-L9	94.5	88.2	68.6	87.3
KBH-L10	96.5	91.8	72.5	90.2