A general heuristic for two-dimensional nesting problems with limited-size containers

Abstract

Cutting raw-material into smaller parts is a fundamental phase of many production processes. These operations originate raw-material waste that can be minimised. These problems have a strong economic and ecological impact and their proper solving is essential to many sectors of the economy, such as the textile, footwear, automotive and shipbuilding industries, to mention only a few. Two-dimensional (2D) nesting problems, in particular, deal with the cutting of irregularly shaped pieces from a set of larger containers, so that either the waste is minimised or the value of the pieces actually cut from the containers is maximised. Despite the real-world practical relevance of these problems, very few approaches have been proposed capable of dealing with concrete characteristics that arise in practice. In this paper, we propose a new general heuristic (H4NP) for all 2D nesting problems with limited-size containers: the Placement problem, the Knapsack problem, the Cutting Stock problem, and the Bin Packing problem. Extensive computational experiments were run on a total of 1100 instances. H4NP obtained equal or better solutions for 73% of the instances for which there were previous results against which to compare, and new benchmarks are proposed.

Keywords:

• cutting
• packing
• nesting problems
• heuristics
• optimisation

Notes

No potential conflict of interest was reported by the authors.

Additional information

Funding

This research was supported by CAPES, CNPq (409043/2016-8) and FAPESP (2013/07375-0, 2016/01860-1) from Brazil. This work was also supported by project ‘NORTE-01-0145-FEDER-000020’ that is financed by the North Portugal Regional Operational Programme (NORTE 2020), under the PORTUGAL 2020 Partnership Agreement, and through the European Regional Development Fund (ERDF).