• JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
 
  Bookmark and Share
 
 
Master's Dissertation
DOI
https://doi.org/10.11606/D.3.2011.tde-28022011-151901
Document
Author
Full name
André Kubagawa Sato
E-mail
Institute/School/College
Knowledge Area
Date of Defense
Published
São Paulo, 2011
Supervisor
Committee
Tsuzuki, Marcos de Sales Guerra (President)
Carvalho, Jonas de
Martins, Thiago de Castro
Title in Portuguese
Proposta de algoritmo para a determinação da região livre de colisão e sua aplicação na solução de leiautes bidimensionais irregulares com recozimento simulado.
Keywords in Portuguese
Empacotamento
Otimização
Recozimento simulado
Abstract in Portuguese
O problema de empacotamento consiste em arranjar um conjunto de itens em um contêiner, a fim de maximizar sua utilização. Este campo de estudos tem impacto em diversas indústrias, incluindo as indústrias têxtil, moveleira e naval. Neste trabalho, dois problemas de empacotamento de itens irregulares são estudados. O primeiro, chamado primal, é o caso em que os itens possuem rotação livre e o contêiner de dimensões fixas pode ser representado por um polígono qualquer, podendo ser não convexo. O segundo problema, denominado dual, consiste em posicionar os itens, que possuem apenas algumas orientações possíveis, em um contêiner retangular em que uma das dimensões é considerada infinita. Assim, o objetivo é obter o menor contêiner, variando a dimensão não fixa, no qual todos os itens podem ser posicionados sem sobreposição. Em ambos problemas, a solução é representada por uma lista ordenada de itens e uma regra de posicionamento é aplicada para se obter o leiaute. Neste caso, sobreposições não são permitidas. Para se garantir leiautes factíveis (sem sobreposição), é adotado o conceito de região livre de colisão. A região livre de colisão representa todas as translações possíveis para inserir um novo item em um contêiner com itens já posicionados. A região livre de colisão é obtida através de operações Booleanas envolvendo polígonos de obstrução e de posicionamento interno. Devido às propriedades dos conceitos envolvidos, o cálculo da região livre de colisão deve ser feito utilizando operações Booleanas não regularizadas. Um novo algoritmo de operação Booleana não regularizada de união e subtração é desenvolvido a partir da implementação de um algoritmo de operações Booleanas regularizadas. Um algoritmo de recozimento simulado é utilizado para controlar a posição, o ângulo (ou orientação) e a seqüência dos itens. Cada item só pode ser posicionado no vértice da região livre de colisão. Com a finalidade de melhorar o desempenho computacional do algoritmo, um método de paralelização do cálculo da região livre de colisão é proposto. Para comparação, são adotados dois algoritmos seriais. Através dos resultados, é possível afirmar que o algoritmo primal foi capaz de resolver problemas do tipo quebra-cabeça, incluindo contêineres convexos e com furos. O algoritmo apresentou melhora significativa no desempenho quando comparado com trabalhos anteriores. Para o caso dual foi proposto um algoritmo de dois níveis, em que o externo controla o comprimento do contêiner e o interno é semelhante ao primal. Este algoritmo foi testado com problemas existentes na literatura e apresentou soluções competitivas, obtendo alguns leiautes mais compactos. A paralelização apresentou ganho de desempenho apenas nos problemas com grande número de itens. Foi constatado que o custo computacional de operações Booleanas não regularizadas é fortemente dependente do número de vértices e intersecções dos polígonos de entrada da operação.
Title in English
Algorithm for the determination of the collision freee region and its application for the two-dimensional irregular packing problem using simulated annealing.
Keywords in English
Optimization
Packing problems
Simulated annealing
Abstract in English
The irregular shape packing problem is an optimization problem that consists of arranging items on a container in order to maximize the utility rate of the sheet stock. This work investigates two problems. In the first problem, the single bin packing, the items can rotate freely and the container with fixed dimension can be any polygon, convex or non-convex. The second problem, the open dimension problem, consists of arranging items that have few admissible orientations in a container with fixed width and variable length. The objective is to find a feasible layout of the set of items that minimizes the length of the container. The solution is always represented as an ordered list of items to be packed and a placement heuristic is applied in order to generate a layout. To ensure feasible layouts, the concept of collision free region is adopted. It represents all the positions that a new item can be placed inside the container, without colliding with already placed items. The collision free region is obtained through non manifold Boolean operations applied to no-fit polygon and the inner-fit polygon. The simulated annealing algorithm controls the position, rotation and placement order of the items. Each item is is exclusively placed on collision free region's vertex. To improve the computational cost performance of the algorithm, a parallelization method to determine the collision free region is proposed. The speed of this algorithm is compared with two different serial methods of determing the collision free region. From the results, it can be observed that the solutions for the single bin packing problem are very competitive with previous works and can achieve optimal solution for puzzles with irregular shaped containers and containers with holes. The algorithm for the open dimension has two hierarchical levels: a core level with a simulated annealing algorithm, and the external level controlling the container length. This algorithm was tested with literature problems and obtained very competitive results, some which are more compact. The results showed that the parallelized version is better than the sequential approach only for datasets with very large number of items. The computational cost of the non manifold Boolean operation algorithm is strongly dependent on the number of vertices and intersections of the original polygons.
 
WARNING - Viewing this document is conditioned on your acceptance of the following terms of use:
This document is only for private use for research and teaching activities. Reproduction for commercial use is forbidden. This rights cover the whole data about this document as well as its contents. Any uses or copies of this document in whole or in part must include the author's name.
Publishing Date
2011-04-19
 
WARNING: The material described below relates to works resulting from this thesis or dissertation. The contents of these works are the author's responsibility.
  • Sato, A. K., et al. Translational Placement Using Simulated Annealing and Collision Free Region with Parallel Processing [doi:10.1109/INDUSCON.2010.5740071]. In 9th IEEE/IAS International Conference on Industry Applications, São Paulo, 2010. Proceedings of the 9th IEEE/IAS International Conference on Industry Applications.São Paulo : IEEE, 2010.
  • Sato, A. K., Martins, T. C., and Tsuzuki, M. S. G. A Simulated Annealing Based Algorithm with Collision Free Region for the Irregular Shape Packing Problem [doi:10.3182/20110828-6-IT-1002.00563]. In 18th IFAC Wold Congress, Milão, 2011. Proceedings of the 18th IFAC Wold Congress.Milão : IFAC, 2011.
  • Sato, A. K., Martins, T. C., and Tsuzuki, M. S. G. Irregular Placement Problem Solved with a 2-Level Algorithm and Collision Free Region. In 8th International Conference on Informatics in Control, Automation and Robotics, Noordwijkerhout, 2011. Proceedings of the 8th International Conference on Informatics in Control, Automation and Robotics., 2011.
  • Sato, A. K., Martins, T. C., and Tsuzuki, M. S. G. Rotational Placement using Simulated Annealing and Collision Free Region [doi:10.3182/20100701-2-PT-4011.00041]. In 10th IFAC Workshop on Intelligent Manufacturing Systems, Lisboa, 2010. 10th IFAC Workshop on Intelligent Manufacturing Systems (Preprints). : IFAC, 2010.
  • Sato, A. K., Martins, T. C., e Tsuzuki, M. S. G. Proposta de Algoritmo para o Problema de Empacotamento Bidimensional Utilizando Dois Níveis e Recozimento Simulado. In X Simpósio Brasileiro de Automação Inteligente, São João del Rei, 2011. Anais do X Simpósio Brasileiro de Automação Inteligente.São Paulo : SBA, 2011.
  • Sato, A. K., Martins, T. C., e Tsuzuki, M. S. G. Recozimento Simulado Aplicado ao Posicionamento Rotacional Utilizando Regiões Livres de Colisão. In XVIII Congresso Brasileiro de Automática, Bonito, 2010. Anais do XVIII Congresso Brasileiro de Automática.Bonito : SBA, 2010.
All rights of the thesis/dissertation are from the authors
CeTI-SC/STI
Digital Library of Theses and Dissertations of USP. Copyright © 2001-2024. All rights reserved.