IRREGULAR PLACEMENT PROBLEM - Solved with a 2-Level Algorithm and Collision Free Region

André Kubagawa Sato, Thiago de Castro Martins, Marcos de Sales Guerra Tsuzuki

2011

Abstract

The two-dimensional irregular open dimension packing problem is a combinatorial optimization problem that searches a layout for a given set of irregular items within a rectangular container so that no item overlaps with other items or protrudes from the container, where each irregular item is not necessarily convex. The container has a fixed width, while its length can change so that all items are placed in it. The objective is to find a layout of the set of polygons that minimizes the length of the container. The proposed algorithm constructively creates layouts from an ordered list of items and a placement heuristic. The placement determines the collision free region (represents the set of translations to create a feasible layout) for the item to be placed. It is shown that the collision free region must be calculated using non-regularized Boolean operations, as contours of no-fit polygons should be ignored. The proposed algorithm to solve the placement problem has two levels, in the internal level the container has fixed dimensions, and the external level reduces or increases the variable dimension. The placement heuristic searches for degenerated vertices and edges as they represent local maximum compaction. Computational comparisons on benchmark problems show that the proposed algorithm generated highly competitive solutions. Moreover, our algorithm updated some best known results.

Paper Citation

in Harvard Style

Kubagawa Sato A., de Castro Martins T. and de Sales Guerra Tsuzuki M. (2011). IRREGULAR PLACEMENT PROBLEM - Solved with a 2-Level Algorithm and Collision Free Region . In Proceedings of the 8th International Conference on Informatics in Control, Automation and Robotics - Volume 1: ICINCO, ISBN 978-989-8425-74-4, pages 79-84. DOI: 10.5220/0003521900790084

in Bibtex Style

@conference{icinco11,
author={André Kubagawa Sato and Thiago de Castro Martins and Marcos de Sales Guerra Tsuzuki},
title={IRREGULAR PLACEMENT PROBLEM - Solved with a 2-Level Algorithm and Collision Free Region},
booktitle={Proceedings of the 8th International Conference on Informatics in Control, Automation and Robotics - Volume 1: ICINCO,},
year={2011},
pages={79-84},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0003521900790084},
isbn={978-989-8425-74-4},
}

in EndNote Style

TY - CONF
JO - Proceedings of the 8th International Conference on Informatics in Control, Automation and Robotics - Volume 1: ICINCO,
TI - IRREGULAR PLACEMENT PROBLEM - Solved with a 2-Level Algorithm and Collision Free Region
SN - 978-989-8425-74-4
AU - Kubagawa Sato A.
AU - de Castro Martins T.
AU - de Sales Guerra Tsuzuki M.
PY - 2011
SP - 79
EP - 84
DO - 10.5220/0003521900790084