• 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
 
 
Doctoral Thesis
DOI
10.11606/T.3.2007.tde-07082007-165358
Document
Author
Full name
Thiago de Castro Martins
E-mail
Institute/School/College
Knowledge Area
Date of Defense
Published
São Paulo, 2007
Supervisor
Committee
Tsuzuki, Marcos de Sales Guerra (President)
González Lima, Raúl
Mueller, Jennifer Lynn
Steffen Junior, Valder
Takase, Fábio Kawaoka
Title in Portuguese
Estudo do recozimento simulado e do polígono de obstrução aplicados ao problema de empacotamento rotacional de polígonos irregulares não-convexos em recipientes fechados.
Keywords in Portuguese
Empacotamento
Otimização
Recozimento simulado
Abstract in Portuguese
Este trabalho trata da proposta de um processo de otimização para o problema do posicionamento rotacional e translacional de formas irregulares em recipientes de dimensões fixas baseado em heurísticas probabilísticas sem o uso de penalização externa. Para tanto, é empregado o polígono de obstrução, acoplado a uma heurística baseada no Recozimento Simulado. O comportamento discreto da função custo em problemas com recipientes de dimensões limitadas foi mitigado através de uma heurística de "desempate", que busca diferenciar soluções com valores idênticos através de uma estimativa de quão próxima está uma determinada solução de conseguir encaixar uma forma não-encaixada em seu leiaute. A comparação de resultados deste trabalho com resultados publicados na literatura comprova a validade da abordagem aqui adotada.
Title in English
Study of simulated annealing and no-fit polygon applied to the rotational packing problem of irregular non-convex polygons in closed containers.
Keywords in English
No-fit polygon
Packing problem
Simulated annealing
Abstract in English
This work deals with the proposal of an optimization process for the packing problem with free translations and rotations of irregular shapes on containers with limited dimensions based on probabilistic heuristics without use of extern penalty techniques. For such, the no-fit polygon is used, coupled with an heuristic based on Simulated Annealing. The discrete behavior of the objective function in problems with limited containers is mitigated by a "tie breaker" heuristic that sorts solutions with identical values by estimating how close a given solution is of fitting an unplaced shape on its layout. The comparison of these work's results with results published on the literature validates the approach here adopted.
 
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.
tese.pdf (1.82 Mbytes)
Publishing Date
2007-08-21
 
WARNING: The material described below relates to works resulting from this thesis or dissertation. The contents of these works are the author's responsibility.
  • Martins, T. C., and Tsuzuki, M. S. G. Placement Over Containers with Fixed Dimensions Solved with Adaptive Neighborhood SImulated Annealing [doi:10.2478/v10175-010-0129-9]. Bulletin of the Polish Academy of Sciences. Technical Sciences [online], 2009, vol. 57, p. 273-280.
  • Martins, T. C., and Tsuzuki, M. S. G. Rotational placement of irregular polygons over containers with fixed dimensions using simulated annealing and no-fit polygons [doi:10.1590/S1678-58782008000300005]. Journal of the Brazilian Society of Mechanical Sciences and Engineering [online], 2008, vol. 30, p. 196-203.
  • Sato, A. K., Martins, T. C., and Tsuzuki, M. S. G. An Algorithm for the Strip Packing Problem Using Collision Free Region and Exact Fitting Placement [doi:10.1016/j.cad.2012.03.004]. Computer Aided Design [online], 2012, vol. 44, p. 766-777.
  • Sato, A. K., Tsuzuki, M. S. G., and Martins, T. C. Collision free region determination by modified polygonal Boolean operations [doi:10.1016/j.cad.2013.03.003]. Computer Aided Design [online], 2013, vol. 45, p. 1029-1041.
  • Martins, T. C., and Tsuzuki, M. S. G. Applying the Simulated Annealing to the Problem of Positioning Rotational Non Convex Polygons. In XVIII Congresso Brasileiro de Engenharia Mecânica, Ouro Preto, 2005. Proceedings of XVIII Congresso Brasileiro de Engenharia Mecânica. : ABCM, 2005.
  • Martins, T. C., and Tsuzuki, M. S. G. Comparison of Deterministic Heuristics and Simulated Annealing for the Rotational Placement Problem over Containers with Fixed Dimensions [doi:10.3182/20090603-3-RU-2001.00258]. In 13th IFAC Symposium on Information Control Problems in Manufacturing, Moscow, 2009. Preprints of the 13th IFAC Symposium on Information Control Problems in Manufacturing. : IFAC, 2009.
  • Martins, T. C., and Tsuzuki, M. S. G. Irregular Rotational Placement of Shapes Over Non-Convex Containers with Fixed Dimensions [doi:10.3182/20070523-3-ES-4908.00027]. In IMS2007 IFAC Workshop on Intelligent Manufaturing Systems, Alicante, 2007. Preprints of IFAC Workshop on Intelligent Manufacturing Systems. : IFAC, 2007.
  • Martins, T. C., and Tsuzuki, M. S. G. Simulated Annealing Applied to the Rotational Polygon Packing [doi:10.3182/20060517-3-FR-2903.00249]. In INCOM2006 - 12th IFAC/IFIP/IFORS/IEEE/IMS Symposium Information Control Problems in Manufacturing, Saint-Etienne, 2006. Preprints of the 12th IFAC/IFIP/IFORS/IEEE/IMS Symposium Information Control Problems in Manufacturing. : IFAC, 2006.
  • Martins, T. C., and Tsuzuki, M. S. G. Simulated Annealing Applied to the Simultaneous Placement of Multiple Polygons [doi:10.4271/2004-01-3272]. In SAE BRASIL 2004, São Paulo, 2004. SAE TECHNICAL PAPER SERIES 2004-01-3448 E., 2004.
  • Martins, T. C., and Tsuzuki, M. S. G. Simulated Annealing with Adaptive Neighborhood Aplied to the Placement Over Containers with Fixed Dimensions [doi:10.3182/20081205-2-CL-4009.00020]. In 9th IFAC Workshop on Intelligent Manufacturing Systems (IMS08), Szczecin, 2008. Proceedings of the 9th IFAC Workshop on Intelligent Manufacturing Systems. : IFAC, 2008.
  • Martins, T. C., and Tsuzuki, M. S. G. Solving Irregular Rotational Knapsack Problems [doi:10.1109/ISDA.2007.57]. In Seventh International Conference on Intelligent Systems Design and Applications, Rio de Janeiro, 2007. Proceedings of the 7th International Conference on Intelligent Systems Design and Applications.Los Alamitos, Estados Unidos : IEEE Computer Society Press, 2007.
  • Martins, T. C., e Tsuzuki, M. S. G. Aplicando o Recozimento Simulado ao Problema do Posicionamento Rotacional de Polígonos Não-Convexos. In CBA 2004 - Congresso Brasileiro de Automática, Gramado, 2004. Anais do Congresso Brasileiro de Automática., 2004. Dispon?vel em: http://congressos.eletro.ufrgs.br/cba2004/store/CD/cba2004/pdf/1201.pdf.
  • Sato, A. K., et al. Determination of Translations to Create Layouts with Exact Placements for Two Moveable Items [doi:10.3182/20120523-3-RO-2023.00097]. In 14th IFAC Symposium on Information Control Problems in Manufacturing, Bucareste, 2012. Proceedings of the 14th IFAC Symposium on Information Control Problems in Manufacturing.Bucareste : IFAC, 2012.
  • 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. Collision Free Region Determined Using Non-Regularized Boolean Operation and its Application in the Irregular Placement Problem [doi:10.2316/P.2012.777-026]. In The 15th IASTED International Conference on Artificial Intelligence and Soft Computing, Napoles, 2012. Proceedings of the IASTED International Conference (2012) Artificial Intelligence and Soft Computing ASC.Alberta : IASTED, 2012.
  • 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. Parallel Layout Construction Algorithm for Irregular Shape Packing Problems [doi:10.1109/SCIS-ISIS.2012.6505041]. In The 6th International Conference on Soft Computing and Intelligent Systems, Kobe, 2012. Proceedings of the 6th International Conference on Soft Computing and Intelligent Systems.Kobe : IEEE, 2012.
  • 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.
All rights of the thesis/dissertation are from the authors
Centro de Informática de São Carlos
Digital Library of Theses and Dissertations of USP. Copyright © 2001-2019. All rights reserved.