GEOMETRICAL MODELS AND ALGORITHMS FOR IRREGULAR SH

文件名称: GEOMETRICAL MODELS AND ALGORITHMS FOR IRREGULAR SHAPES PLACEMENT

所属分类: 其它

开发工具:

文件大小: 11mb

下载次数: 0

上传时间: 2019-03-16

提供者: nestin******

下载 (11mb)

不能下载？报告错误

详细说明：This thesis addresses the Irregular Piece Placement problem, also known as Nesting problem, while focusing on the resolution of real world instances with continuous rotations. The real world instances are considered very large instances containing many pieces with very complex outlines, where continuous rotations may be desired. The Nesting problem is presented, with a description of its characteristics, identifying the main challenges, and related problems. This is done through a literature review, considering the geometric representations and common solution approaches that are normally used, in order to identify possible paths to explore, and confirm its inherent difficulty in being efficiently tackled, specially when dealing with continuous rotationsFACULDADE DE ENGENHARIA DA UNIVERSIDADE DO PORTO Geometrical Models and algorithms for Irregular Shapes placement Problems Pedro filipe monteiro rocha U. PORTO FEUP FACULDADE DE ENGENHARIA UNIVERSIDADE DO PORTO Doctoral Program in Informatics Engineering Supervisor: A. Miguel gomes Co-Supervisor: Rui rodrigues Julho de 2014 c)Pedro Filipe monteiro Rocha, 2014 Geometrical Models and algorithms for Irregular Shapes Placement problems Pedro Filipe monteiro rocha Doctoral Program in Informatics Engineering Julho de 2014 Abstract This thesis addresses the Irregular Piece Placement problem, also known as Nesting problem while focusing on the resolution of real world instances with continuous rotations The real world instances are considered very large instances containing many pieces with very complex outlines where continuous rotations may be desired. The Nesting problem is presented, with a description of its characteristics, identifying the main challenges, and related problems. This is done through a literature review, considering the geometric representations and common solution approaches that are normally used, in order to identify possible paths to explore, and confirm its inherent difficulty in being efficiently tackled, specially when dealing with continuous rotations The geometric component of the Nesting problems is addressed by using a novel algorithm that generates Circle Covering representations based on the medial Axis skeleton of a piece. This iterative algorithm enables control over the approximation error, which allows managing the trade off between the quality of circle covering representation and the total number of circles. This algorithm allows producing coverings with different levels of quality, and with different types of covering, depending on the characteristics of the Nesting problem where they will be used, which have a significant impact on the feasibility of the final solution and in the tightness of the layout The solution approach is based on Non-Linear Programming models, from which several for mulations were made, taking into account the size of the problem being addressed. These models fully support continuous rotations, and can produce feasible solutions with an acceptable com putational cost. In order to tackle large instances, extensions to the NLP models are done, br aggregating constraints by type, and implementing other tweaks to reduce computational cost In order to address issues with high computational cost layout solutions with insufficient qual- ity, and very large instances, three approaches are proposed. The first uses a two-step compaction process, where the nlp model uses low resolution in the first step, and high resolution in the second. The second approach uses a two-phase compaction process, where in the first phase bi pieces are compacted, considering certain parameters, and holes are created between the pieces and in the second phase, the small pieces remaining are assigned and placed in the holes created in the first phase, and all compacted together. The last approach uses a multi-step approach, where pieces are separated in groups, and compacted into the layout in a sequential order, forming layers of pieces. These approaches show very promising results, being able to address the Nesting prob lem with continuous rotations, considering their purpose. If these approaches are combined they can be used to improve results of currently existing approaches Resumo Esta tese aborda o problema de posicionamento de pecas Irregulares, tambem conhecido como problema de Nesting, focado na resolugao de instancias reais destes problemas, considerando rotacoes continuas O problema de Nesting e apresentado com uma descrisao das suas caracteris- ticas, identificando os desafios principais e problemas relacionados. Isto e feito atraves de uma revisao da literatura actual considerando representacoes gcometricas e metodos de resolucao mais utilizados, com o objective de identificar possiveis oportunidades que possam ser exploradas de forma a abordar o problema de Nesting com rotacoes livres de forma mais eficiente A componente gcometrica do problema de Nesting e abordado com recurso a um novo algo ritmo que cria uma representacao baseada em cobertura por circulos, feita a partir de um esqueleto topologico de cada peca. Este algoritmo iterativo permite ter controlo sobre o erro de aproximacao da peca, permitindo lidar com o compromisso entre a qualidade de representagao e o numero total de circulos produzido. Este algoritmo permite tambem produzir coberturas com niveis de qual idade distintos, assim como tipos de cobertura de circulos diferentes, orientados para problemas especificos de Nesting, produzindo um impacto significativo na admissibilidade da solucao final e na qualidade de compactagao O metodo de resolugao utiliza modelos de programasao nao-linear, que foram obtidos atraves de diferentes formulagoes matematicas do problema, tendo em conta o tamanho do problema a ser abordado. Estes modelos matematicos suportam rotacoes livres, conseguindo produzir solugoes admissiveis com um custo computacional razoavel. De forma a poder lidar com instancias de Nesting de grande tamanho, foram feitas extensoes aos modelos matematicos para reduzir o custo computacional, atraves da agregacao de restricoes Para poder lidar com varios problemas relacionados com alto custo computacional, solucoes com qualidade insuficiente e instancias de tamanho muito grande, foram propostas tres aborda a primeira utiliza um processo de compactagao baseado em duas etapas, que utiliza res- lucao baixa na primeira etapa, e uma resolucao alta na segunda, de forma a compactar depressa e ajustar as pecas com qualidade. a segunda abordagem usa duas fases, compactando as pecas grandes na primeira fase, criando buracos no cspaco entre as pesas grandes. Na segunda fasc as pecas pequenas sao atribuidas e colocadas nos buracos, sendo todas as pecas compactadas de seguida. a terceira, e ultima abordagem utiliza varias etapas separando inicialmente as pecas em grupos distintos, e compactando-as numa ordem sequencial, formando camadas de pesas, per- mitindo compacter grandes problemas com custo computacional reduzido Estas abordagens apresentam resultados muito promissores, conseguindo abordar problemas de Nesting com rotacoes continuas tendo em conta as suas vantagens individuais. Combinando estas abordagens, ou aplicando-as de uma forma specifica, pode melhorar os resultados de abor dagens existentes

(系统自动生成,下载前可以参看下载内容)