.png){kind=icon}
.png){kind=icon}
Return
An improved differential evolution algorithm combined with vector NFP and mixed-integer programming for solving 2D irregular layout problem
.png){kind=icon}
PRE
AI
DOI：10.1016/j.eswa.2025.129621.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
The two-dimensional irregular layout problem, which involves placing convex or non-convex components within a confined boundary without overlaps, is NP-complete and widely encountered in industrial applications such as glass cutting, garment manufacturing, and packaging. To overcome the limitations of existing methods in computational efficiency and material utilization, we propose a new hybrid algorithm IDE-V-NFP-MIP: (1) An improved differential evolution (IDE) algorithm combines the memory mechanism to guide the crossover and mutation operations; (2) A vector No-Fit Polygon (V-NFP) algorithm effectively handles complex geometric constraints, including voids and degradation; (3) A mixed-integer programming (MIP) model ensures accurate layout and non-overlapping constraints. Experimental results demonstrate superior performance: IDE ranked first in CEC2022 Friedman tests, while practical applications show 22.10% reduction in board length and 41.47% improvement in filling rate. The framework successfully handles real-world garment cutting applications and large-scale problems up to 1,280 polygons, demonstrating significant improvements in both computational efficiency and solution quality for industrial layout optimization. The source code for the algorithm is available at https://github.com/xhj-6/IDE-V-NFP-MIP .
Journal
IF:
7.5
Papers:
2.9W
Citations:
10.2W