Nesting problems consist of placing multiple items onto larger shapes finding a good arrangement. The goal of the nesting process is to minimize the waste of material. It is common to assume, as in the present work, that the stock sheet has fixed width and infinite height, since in the real world a company may have to cut pieces from a roll of material. The complexity of such problems is often faced with a two-stage approach, so-called “hybrid algorithm”, combining a placement routine and a meta-heuristic algorithm. Starting from a given positioning sequence, the placement routine generates a non-overlapping configuration. The encoded solution is manipulated and modified by the meta-heuristic algorithm to generate a new sequence that brings to a better value of the objective function (in this case the height of the strip). The proposed method consists in placing the rectangles inside a strip and in combining the meta-heuristic algorithms with the No Fit Polygon algorithm. The software has been developed in Python language using proper libraries to solve the meta-heuristic techniques (Inspyred) and the geometric problems (Polygon). The results show the effectiveness of the proposed method; moreover, with regard to problems reported in literature employed as benchmark of the nesting algorithms, the degree of occupation values (Efficiency Ratio, ER) are shown to be higher than 90%.

Lo Valvo, E. (2017). Meta-heuristic Algorithms for Nesting Problem of Rectangular Pieces. PROCEDIA ENGINEERING, 183, 291-296 [10.1016/j.proeng.2017.04.041].

Meta-heuristic Algorithms for Nesting Problem of Rectangular Pieces

LO VALVO, Ernesto
2017

Abstract

Nesting problems consist of placing multiple items onto larger shapes finding a good arrangement. The goal of the nesting process is to minimize the waste of material. It is common to assume, as in the present work, that the stock sheet has fixed width and infinite height, since in the real world a company may have to cut pieces from a roll of material. The complexity of such problems is often faced with a two-stage approach, so-called “hybrid algorithm”, combining a placement routine and a meta-heuristic algorithm. Starting from a given positioning sequence, the placement routine generates a non-overlapping configuration. The encoded solution is manipulated and modified by the meta-heuristic algorithm to generate a new sequence that brings to a better value of the objective function (in this case the height of the strip). The proposed method consists in placing the rectangles inside a strip and in combining the meta-heuristic algorithms with the No Fit Polygon algorithm. The software has been developed in Python language using proper libraries to solve the meta-heuristic techniques (Inspyred) and the geometric problems (Polygon). The results show the effectiveness of the proposed method; moreover, with regard to problems reported in literature employed as benchmark of the nesting algorithms, the degree of occupation values (Efficiency Ratio, ER) are shown to be higher than 90%.
Settore ING-IND/16 - Tecnologie E Sistemi Di Lavorazione
17th International Conference on Sheet Metal, SHEMET17
Palermo
10-12 Aprile 2017
17
http://www.sciencedirect.com/science/article/pii/S1877705817315461
Lo Valvo, E. (2017). Meta-heuristic Algorithms for Nesting Problem of Rectangular Pieces. PROCEDIA ENGINEERING, 183, 291-296 [10.1016/j.proeng.2017.04.041].
File in questo prodotto:
File Dimensione Formato  
1-s2.0-S1877705817315461-main.pdf

accesso aperto

Descrizione: Articolo su rivista
Tipologia: Versione Editoriale
Dimensione 160.71 kB
Formato Adobe PDF
160.71 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/10447/242922
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 5
  • ???jsp.display-item.citation.isi??? 5
social impact