A heuristic approach based on shape similarity for 2D irregular cutting stock problem

作者：Xu, Yanxin^*; Yang, Genke; Pan, Changchun

来源：Communications in Computer and Information Science, 2013, 355: 275-283.

DOI：10.1007/978-3-642-37105-9_31

• Bench-mark problems
• Cutting stock problem
• Fourier descriptors
• Grid approximations
• High-quality solutions
• Shape similarity
• Special interest groups
• Two-dimensional cutting stocks

Cutting stock problem is an important problem that arises in a variety of industrial applications. This research constructs an irregular-shaped nesting approach for two-dimensional cutting stock problem. The techniques of shape similarity are utilized, drawn from computer vision and artificial intelligence. These techniques enable the approach to find potential matches of the unplaced pieces within the void regions of the sheet, and thus the packing density and the performance of solutions are highly improved. The proposed approach is able to deal with complex shapes in industrial application and achieve high-quality solution with shorter computational time. We evaluate the proposed method using 15 established benchmark problems available from the EURO Special Interest Group on Cutting and Packing. The results demonstrate the effectiveness and high efficiency of the proposed approach.

• 出版日期2013
• 单位上海交通大学