Meta-heuristic Algorithms for Nesting Problem of Rectangular Pieces

Risultato della ricerca: Article

1 Citazione (Scopus)

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%.
Lingua originaleEnglish
pagine (da-a)291-296
Numero di pagine6
RivistaProcedia Engineering
Volume183
Stato di pubblicazionePublished - 2017

Fingerprint

Heuristic algorithms
Industry

All Science Journal Classification (ASJC) codes

  • Engineering(all)

Cita questo

Meta-heuristic Algorithms for Nesting Problem of Rectangular Pieces. / Lo Valvo, Ernesto.

In: Procedia Engineering, Vol. 183, 2017, pag. 291-296.

Risultato della ricerca: Article

@article{eccb3f8b07ce4c0aac1084b6468c4e8d,
title = "Meta-heuristic Algorithms for Nesting Problem of Rectangular Pieces",
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{\%}.",
author = "{Lo Valvo}, Ernesto",
year = "2017",
language = "English",
volume = "183",
pages = "291--296",
journal = "Procedia Engineering",
issn = "1877-7058",
publisher = "Elsevier BV",

}

TY - JOUR

T1 - Meta-heuristic Algorithms for Nesting Problem of Rectangular Pieces

AU - Lo Valvo, Ernesto

PY - 2017

Y1 - 2017

N2 - 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%.

AB - 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%.

UR - http://hdl.handle.net/10447/242922

UR - http://www.sciencedirect.com/science/article/pii/S1877705817315461

M3 - Article

VL - 183

SP - 291

EP - 296

JO - Procedia Engineering

JF - Procedia Engineering

SN - 1877-7058

ER -