Orientadores: Marcia Aparecida Gomes Ruggiero, Antonio Carlos Moretti / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica / Made available in DSpace on 2018-08-11T07:33:43Z (GMT). No. of bitstreams: 1 Sakamori_Momoe_M.pdf: 494316 bytes, checksum: ffa8a12071e05ab6083c917588e53797 (MD5) Previous issue date: 2008 / Resumo: Neste trabalho resolvemos um problema de corte unidimensional não-linear para minimizar o número de objetos processados, setup e desperdício. O termo não-linear representa o setup da máquina de corte. Resolvemos o problema utilizando o pacote MINOS e obtemos a solução inteira através de um procedimento heurístico. Como o número de padrões de corte pode ser muito grande, propomos uma geração de colunas modificada, que usa os multiplicadores de Lagrange do problema não-linear ao invés das variáveis duais do problema de programação linear padrão. Além disso, propomos um novo processo de geração de colunas utilizando um problema da mochila não-linear como subproblema para gerar colunas promissoras / Abstract: In this work we solve a nonlinear unidimensional cutting-stock problem to minimize the number of objects processed, setup and trim loss. The nonlinear term represents the setup of the cutting machine. We solve the problem using the MINOS package and obtain the integer solution through a heuristic procedure. Since the number of cutting patterns can be very high, we propose a modified column generation that uses the Lagrange multipliers of the nonlinear problem instead the dual variables of the standard linear programming problem. Also, we propose a new column generation process using a nonlinear knapsack problem as the subproblem to generate pro_table columns / Mestrado / Pesquisa Operacional / Mestre em Matemática Aplicada

Orientador: Arnaldo Vieira Moura / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-12T05:42:28Z (GMT). No. of bitstreams: 1 Scaraficci_RafaelAugusto_M.pdf: 1073556 bytes, checksum: 1831ea71ef0edfbf5da96e257b81bbfc (MD5) Previous issue date: 2008 / Resumo: Este trabalho de mestrado procurou estudar e resolver um problema real de planejamento e escalonamento de atividades de colheita e de transporte de madeira. Trata-se de um problema típico de grandes empresas do setor de celulose e papel. Ele consiste em planejar, para um horizonte de curto prazo, a colheita de madeira em diferentes áreas florestais e também o transporte da madeira colhida para uma unidade de produção de celulose e papel. O planejamento das atividades florestais considera um conjunto complexo de restrições operacionais, que envolvem, por exemplo, a organização das áreas florestais, propriedades da madeira cortada, a organização das equipes de colheita e a degradação das estradas com as chuvas. Neste projeto, desenvolvemos e analisamos algumas estratégias algorítimas híbridas baseadas em princípios da metaheurística GRASP (Greedy Randomized Adaptive Search Procedure) combinada com elementos de memória de longo prazo, métodos de recombinação de soluções e também modelos lineares. Testes computacionais mostraram que nossas estratégias são robustas e capazes de produzir soluções de alta qualidade em um curto intervalo de tempo. / Abstract: This thesis aimed at studying and solving a planning and scheduling problem stemming from forest harvest and wood transportation activities. Our approach treated a real problem faced by large pulp and paper companies in Brazil. It consists in planning, for a short-term horizon, the harvesting operations in different forest areas and the transportation of the logs to a processing unit, while satisfying a complex set of constraints, which includes constraints related to the structure of the harvest areas, some properties of the logs, the organization of the harvest teams and the degradation of dirt roads during rainy periods. In this research, we developed and evaluated some hybrid algorithmic strategies based on some principles of the GRASP (Greedy Randomized Adaptive Search Procedure), combined with advanced techniques such as long term memory, solution recombination methods and linear models. Computational tests proved that our strategies are robust and able to produce high quality solutions in a short amount of time. / Mestrado / Mestre em Ciência da Computação

Orientador: Cid Carvalho de Souza / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-23T17:56:16Z (GMT). No. of bitstreams: 1 Assis_IgorRibeirode_M.pdf: 5116531 bytes, checksum: 151d5c4293cb869d16ddf4c6f7bb8992 (MD5) Previous issue date: 2013 / Resumo: Aplicações desse problema incluem: máquina de controle numérico, inspeção automática e roteamento. Esta dissertação estuda soluções para o problema do recorte. Propomos um modelo de programação linear inteira e a partir deste desenvolvemos um algoritmo exato. Descrevemos um algoritmo 3.75 aproximado da literatura e propomos algumas melhorias heurísticas para o mesmo. Abandonando as garantias teóricas, projetamos duas heurísticas: a primeira utiliza uma ideia gulosa bastante simples complementada por técnicas da meta-heurística GRASP, especificamente aleatorização e busca local; e a segunda resolve um problema de cobertura mais simples e cuja sua solução pode ser adaptada para o problema original. Por fim propomos uma série de vizinhanças executadas em uma fase de busca local, que dada uma solução, faz mudanças locais que reduzem o custo do tour. As implementações dos algoritmos descritos são analisadas experimentalmente utilizando um benchmark de instâncias que construímos e deixamos público para comparações futuras / Abstract: In the orthogonal milling with turn costs problem is given an orthogonal polygon P that may contain holes. Our goal is to find a closed polygonal curve made of horizontal and vertical segments which when traversed by a unit square, the covered area is exactly P. Turn costs are assigned to direction changes and the objective is to minimize the sum of turn costs. This problem arises in many applications including: numerically controlled (NC) machining, automatic inspection and routing. This dissertation studies solutions for the milling problem. We propose an integer linear programming model and from which an exact algorithm is proposed. A 3.75- approximate algorithm from the literature is described for which heuristic improvements are proposed. Lifting the theoretical guarantees we project two heuristics: the first is based in a simple greedy idea supplemented with techniques of the GRASP meta-heuristic, specifically, randomization and local search; the latter solves a simpler covering problem whose its solution is adapted for the original problem. Finally, we propose a series of neighborhoods run in a local search step where, local changes are made to the solution such that the tour cost is reduced. All described algorithms are implemented and evaluated experimentally using a benchmark of instances that we built and made public for future comparisons / Mestrado / Ciência da Computação / Mestre em Ciência da Computação

Orientador: Antonio Carlos Moretti / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatística e Computação Cientifica / Made available in DSpace on 2018-08-04T09:51:10Z (GMT). No. of bitstreams: 1 SallesNeto_LuizLeduinode_D.pdf: 2686631 bytes, checksum: 6929a985654c561695159e4b4fc6ebb7 (MD5) Previous issue date: 2005 / Resumo: Neste trabalho apresentamos um novo método para minimizar o número de objetos processados e o número de padrões distintos (setup) num problema de corte unidimen-sional. Suavizamos a função objetiva, inteira e não linear proposta por Haessler em 1975. Para gerar os padrões de corte utilizamos inicialmente uma heurística (SHP de-senvolvida por Haessler), e posteriormente adaptamos o método de geração de colunas de Gilmore e Gomory para este modelo não-linear. Palavras-Chaves: Problema de corte de estoque; Geração de colunas; Setup; Heurística; Programação Não-Linear / Abstract: In this work we introduce a new method to minimize both the number of processed objects and the number of nonzeros cutting patterns (Le., setup) in an one-dimensional cutting stock problem. To do so, we smooth the discontinuous nonlinear function used in Haessler(1975) to represent both objectives: the number of objects and setup number. To generate the cutting patterns we use the Gilmore&Gomory strategy with a starting basis given by the method SHP (Sequential Heuristic Procedure) developed by Haessler. Keywords: Cutting stock problem; Column generation; Heuristic; Setup; Nonlinear programming / Doutorado / Matematica Aplicada / Doutor em Matemática Aplicada

Orientador: Romis Ribeiro de Faissol Attux / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Elétrica e de Computação / Made available in DSpace on 2018-08-24T08:30:47Z (GMT). No. of bitstreams: 1 Prampero_PauloSergio_D.pdf: 3050716 bytes, checksum: 33c3c108ea130c45777796b01de4e4ef (MD5) Previous issue date: 2014 / Resumo: Os algoritmos de otimização podem possuir características de busca local, global e multimodal. Em termos simples, os algoritmos de busca local procuram refinar uma solução inicial encontrada, promovendo a sua movimentação para o ótimo local dominante em sua vizinhança. Já os algoritmos de busca global possuem estratégias para escapar de ótimos locais, e, desta forma conseguem movimentar seus pontos de forma mais ampla pelo espaço de busca. Por fim, algoritmos multimodais procuram encontrar os vários ótimos no espaço de busca. Neste trabalho foi proposto um algoritmo de otimização multimodal, baseado em PSO, com duas inovações: o raio de repulsão com controlador de passo, e o armazenamento da região promissora. O algoritmo foi chamado de MPSO (Magnetic Particle Swarm Optimization), e possui apenas um parâmetro de configuração, o número de partículas. Ele apresentou resultados bastante interessantes nos experimentos comparativos realizados, tanto em funções benchmark quanto em uma aplicação prática. A segunda proposta foi uma metodologia de busca baseada em clusterização. Nesta metodologia, a modificação proposta translada os centroides das posições de representantes dos clusters, obtidas originalmente pelos algoritmos de clusterização clássicos, para uma região promissora no cluster, ou seja, para uma região melhor avaliada pela função objetivo, que será maximizada ou minimizada. Desta forma, a metodologia toma a forma de um operador que pode ser utilizado como pré-processador de algoritmos de otimização clássicos, sendo capaz de introduzir diversidade na população inicial, o que, como mostram os experimentos realizados, melhorou os resultados obtidos. Outras possibilidades de aplicação da ideia também são expostas e avaliadas / Abstract: Optimization algorithms have local, global and multimodal search features. In simple terms, a local search algorithm refines an initial solution by moving it towards an optimal dominant place in its neighborhood. Global search algorithms have strategies to escape from local optima, and thus can move their points more broadly throughout the search space. Finally, multimodal algorithms seek to find several global optima in the search space. In this thesis, we propose a multimodal optimization algorithm based on PSO with two innovations: the repulsion radius with step controller and the storage of promising search directions. The algorithm was named MPSO (Magnetic Particle Swarm Optimization) and has only one configuration parameter, the number of particles. It led to consistent results in benchmark-based comparative experiments and in a practical application. The second proposal was a clustering-based optimization methodology. This proposal moves the centroids from a position representative of a cluster, originally obtained by classical clustering algorithms, to a promising region in terms of an objective function to be maximized or minimized . The methodology was implemented in the form of an operator used as a pre-processor to traditional optimization algorithms. It introduced diversity in the initial population, which, as shown by the experiments,led to significant performance improvements. Other possibilities of applying this new idea are also discussed in the text / Doutorado / Engenharia de Computação / Doutor em Engenharia Elétrica

Orientadores: Antônio Carlos Moretti, Luiz Leduíno de Salles Neto / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matemática, Estatística e Computação / Made available in DSpace on 2018-08-24T09:32:59Z (GMT). No. of bitstreams: 1 Barbosa_Flavia_M.pdf: 1252901 bytes, checksum: de4922d29a8982eb9c6ffc2cb33004f3 (MD5) Previous issue date: 2014 / Resumo: O comércio internacional é profundamente dependente do transporte marítimo e por isso, os portos tem sido forçados a investir em infra-estrutura e logística. Nesse contexto, o presente trabalho aborda o Problema de Alocação de Berços: como alocar navios a berços em um dado horizonte de planejamento de modo a minimizar os custos operacionais. No Brasil, a companhia Vale é responsável pela exportação da matéria-prima minério de ferro utilizado na fabricação do aço. Assim, será proposto métodos que otimizem suas operações portuárias, mais especificamente para o Terminal de Praia Mole no Porto de Tubarão. Para tanto, dois modelos matemáticos e duas heurísticas serão implementadas. Os modelos, adaptados de casos existentes na literatura, são executados com o CPLEX e os resultados obtidos são comparados para que a melhor opção seja encontrada / Abstract: The international trading is highly subordinate on maritime transport and therefore, the ports have been forced to invest in groundwork and logistics. In this context, this work addresses the Berth Allocation Problem: how to allocate ships to berths in a given planning horizon so that the operational costs are minimized. In Brasil, the Vale company é responsible for the export of raw iron ore used in steel manufacuring. Thus, it will be proposed methods to optimize their port operations, more specifically to the Praia Mole Terminal at the Tubarão Port. For this purpose, two mathematical models and two heuristics were implemented. Mathematical models, adapted from literature cases are executed with GLPK and CPLEX and the results obtained are compared so that the best option is found / Mestrado / Matematica Aplicada / Mestra em Matemática Aplicada

Orientador: Arnaldo Vieira Moura / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-06T15:19:37Z (GMT). No. of bitstreams: 1 Pereira_RomuloAlbuquerque_M.pdf: 1452483 bytes, checksum: 19f11b532a512f1e86efa79195a4e8ce (MD5) Previous issue date: 2005 / Resumo: Este trabalho de mestrado procurou estudar e resolver um problema real de escalonamento das atividades de desenvolvimento de poços de petróleo em alto mar. Uma versão mais simples deste mesmo problema foi provada ser NP- difícil. Nosso estudo se concentrou no problema real enfrentado pela Petrobrás, com todas suas características e nuances. Antes que locais promissores de bacias petrolíferas sejam efetivamente desenvolvidos em poços de petróleo produtivos, é necessário realizar diversas atividades de perfuração, completarão e interligação nesses locais. O escalonamento dessas atividades deve satisfazer várias restrições conflitantes e buscar a maximização da produção de petróleo em um dado horizonte de tempo. O problema foi atacado em duas etapas: uma sem considerar o deslocamento de recursos e outra considerando-os. Para tal, adotamos a estratégia Greedy Randomized Adaptive Search Procedure (GRASP) e incorporamos várias técnicas específicas para obter melhor desempenho e qualidade da solução final. Os resultados são comparados com outros produzidos por uma ferramenta computacional baseada em Programação por Restrições (PR). Esta última, já em uso e bem aceita na empresa, foi desenvolvida pela Petrobrás. Resultados comparativos realizados em instâncias reais indicam que a implementação GRASP supera a ferramenta de PR produzindo soluções com expressivos aumentos de produção / Abstract: This dissertation aimed at studying and solving a real world scheduling problem. We deal with the scheduling of offshore oil well development activities. A simpler version of this same problem was proved to be in NP-hard. Our approach treats this problem as faced by Petrobras, with all its characteristics and details. Before promising locations at petroliferous basins become productive oil wells, it is often necessary to complete activities of drilling, completion and interconnection at these locations. The scheduling of such activities must satisfy several conflicting constraints and aim at the maximization of oil production. The problem was solved in two parts: one without considering resource displacements and other taking into account such displacements. For such, we used a Greedy Randomized Adaptive Search Procedure (GRASP) metaheuristic and used several techniques and variants in order to obtain more efficiency and produce better solutions. The results are compared with schedules produced by a well-accepted constraint programming implementation. Computational experience on real instances indicates that the GRASP implementation is competitive, outperforming the constraint programming implementation / Mestrado / Otimização Combinatoria / Mestre em Ciência da Computação

Orientadores: Antonio Carlos Moretti, Margarida Pinheiro Mello / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica / Made available in DSpace on 2018-08-11T15:01:14Z (GMT). No. of bitstreams: 1 Oliveira_WashingtonAlvesde_M.pdf: 1986709 bytes, checksum: fa0dfb8c33d0fe5dd13eeced37d3b4ee (MD5) Previous issue date: 2008 / Resumo: Nesta dissertação estudamos um aspecto do problema de planejamento do pratulhamento urbano preventivo: a construção de rotas a serem percorridas pelos veículos da força policial no patrulhamento preventivo. De modo geral, a elaboração de rotas visa garantir uma boa visibilidade para o patrulhamento, de modo a proporcionar sensação de segurança para a população, permitir o atendimento rápido em caso de ocorrências, fazer vigilância de determinados estabelecimentos (hospitais, escolas, etc.). O planejamento deve levar em conta os recursos disponíveis, normalmente o número de veículos, visar agilidade e uma distribuição equânime de trabalho. O produto final é um módulo computacional capaz de automaticamente gerar rotas atendendo um dado conjunto de especificações, que possa ser utilizado pelos departamentos responsáveis pela segurança pública. Para tanto, fizemos uma adaptação do modelo para o Problema de Rotas de Cobertura multi-veículo (m-PRC). Este modelo consiste em um programa linear inteiro cujo tamanho e complexidade torna inviável a aplicação de métodos exatos para sua solução. Soluções subótimas são obtidas aplicando-se as heurísticas propostas por M. Hachicha et. al. (2000), e outras contribuídas por nós. Neste modelo alguns pontos geográficos devem ser obrigatoriamente visitados, enquanto outros devem ficar suficientemente próximos das rotas traçadas. Procuramos gerar rotas de tamanho menor possível, para que cada circuito seja percorrido um maior número de vezes durante o turno de serviço. As heurísticas foram implementadas em MATLAB e sua validação, assim como a do modelo, foi feita através da resolução de problemas gerados aleatoriamente. Além disso, obtivemos dados relativos à cidade de Vinhedo, S.P., e formulamos rotas para patrulhamento preventivo pela Guarda Civil Municipal. Os resultados são promissores, e a análise das soluções obtidas será utilizada para aprimorar o modelo / Abstract: In this text we study one aspect of the urban community policing: routine patrol route planning. We seek routes that guarantee visibility, as this has a sizable impact on the community's perceived safety and allows for quick emergency responses, and that provide surveillance of public buildings (e.g., hospitals, schools). The planning is restricted to the availability of vehides and strives to achieve balanced and short routes. We construct a computerized module, capable of automatic generation of routes for a given vehide fieet and lists of sites that must be visited. Such a module could be of interest to Police, Public Safety Departments, Municipal Service Agencies. The module implements an adaptation of the model for the multi-vehicle covering tour problem. It constitutes an integer program whose size and complexity makes the use of an exact method impractical. Suboptimal solutions are obtained with several heuristics, some by M. Hachicha et. al. (2000), and others of our own devising. In this model a set of locations must be visited, whereas another subset must be close enough to the planned routes. The heuristics aim to construct short routes so that one could make several rounds during a work shift. The implementation was done in MATLAB and its validation, as well as the model's, was based on the solution of randomly generated problems. Furthermore, data from the city of Vinhedo, SP, was obtained and tentative routes planned for the patroling of a choice of locations by the Municipal Guard. Their appraisal by the personnel in charge of the route planning will, without a doubt, help us improve the model and heuristics / Mestrado / Pesquisa Operacional / Mestre em Matemática Aplicada

Orientador: Cid Carvalho de Souza / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-20T15:20:18Z (GMT). No. of bitstreams: 1 Oliveira_Lucasde_M.pdf: 1308997 bytes, checksum: cc147cd3d3c9f50c61a48d83579b6c49 (MD5) Previous issue date: 2012 / Resumo: Esta dissertação tem como foco a investigação experimental de algoritmos exatos, aproximativos e heurísticos aplicados na resolução do chamado problema do corredor de comprimento mínimo (PCCM). No PCCM recebemos um polígono retilinear P e um conjunto de polígonos retilineares menores formando uma subdivisão S planar conexa de P. Uma solução para este problema, também chamada de corredor, é formada por um conjunto conexo de arestas de S, e tal que cada face interna em S possui pelo menos um ponto em sua borda que pertence a alguma aresta deste conjunto. O objetivo então é encontrar um corredor tal que a soma total dos comprimentos das arestas seja a menor possível. Trata-se de um problema NP-difícil com aplicações em áreas diversas, tais como telecomunicações, engenharia civil e projeto de circuitos VLSI. O PCCM pode ser reduzido polinomialmente a um problema em grafos denominado problema da árvore de Steiner com grupos (PASG). Considerando esta transformação, estudamos e implementamos dois métodos aproximativos, um método exato de branch-and-cut, e um método heurístico baseado na metaheurística GRASP combinada com um evolutionary path relinking (GRASP+EPR). Além disso, propomos três heurísticas de busca local que visam melhorar a qualidade de soluções do PASG. Instâncias do PCCM foram geradas aleatoriamente, nas quais aplicamos os métodos implementados. Analisamos os resultados, e apresentamos as situações onde é interessante utilizar cada método. Verificamos que o método branch-and-cut foi capaz de encontrar soluções ótimas para instâncias que julgamos ser de grande porte em tempos computacionalmente aceitáveis. O melhor algoritmo aproximativo obteve corredores que na média têm comprimento 17% maior que o comprimento ótimo. Se combinarmos este algoritmo com as heurísticas de melhoria propostas este percentual cai para a média de 3,5%. Finalmente, o GRASP+EPR consome mais tempo que este algoritmo aproximativo, entretanto, o comprimento dos corredores obtidos por ele é em média 0,9% maior que o comprimento ótimo / Abstract: This dissertation focuses on the experimental investigation of exact, approximation and heuristic algorithms applied to solve the so-called minimum length corridor problem (MLCP). In the MLCP we receive a rectilinear polygon P and a set of minor rectilinear polygons forming a connected planar subdivision S of P. A solution for this problem, also called corridor, is formed by a set of connected edges of S, and such that each inner face of S has at least one point on its your border which belongs to an edge in this set. The goal is to find a corridor such that the sum of lengths of the edges is as small as possible. This is an NP-hard problem with applications in several areas such as telecommunications, civil engineering and design of VLSI circuits. The MLCP can be polynomially reduced to a graph problem known as group Steiner tree problem (GSTP). Based on this transformation, we studied and implemented two approximation methods, an exact branch-and-cut method, and a heuristic method based on the metaheuristic GRASP combined with an evolutionary path relinking (GRASP+EPR). Furthermore, we propose three local search heuristics to improve the quality of GSTP solutions. MLCP instances were randomly generated, in which we apply the methods implemented. We analyzed the results, and present situations where it is interesting to use each method. We found that the branch-and-cut has been able to find optimal solutions for instances that we consider to be large in acceptable computational times. The best approximation algorithm obtained corridors having average length 17% higher than the optimum length. If we combine this algorithm with the improvement heuristics proposed this percentage drops to an average of 3.5%. Finally, the GRASP+EPR spent more time than this approximation algorithm, however, the length of the corridors obtained by the method is, on average, 0.9% higher than the optimum length / Mestrado / Ciência da Computação / Mestre em Ciência da Computação

Orientador: Arnaldo Vieira Moura / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-09T20:48:39Z (GMT). No. of bitstreams: 1 Ferber_DanielFelix_M.pdf: 2571168 bytes, checksum: 373e2b3bb3f1ca3735beb4c4303dc5d9 (MD5) Previous issue date: 2007 / Resumo: O principal objetivo deste trabalho é a elaboração de heurísticas para auxiliar no projeto de cabeamento de redes telefônicas. O cabeamento será tratado desde os armários de distribuição até as caixas terminais. O auxílio de uma ferramenta computacional especializada no projeto de novas redes telefônicas abre caminhos para a minimização de custos e também reduz sensivelmente o tempo de planejamento. Inicialmente, estuda-se o problema para se obter uma especificação minuciosa, acompanhada de um modelo matemático. Com estas informações, desenvolve-se diferentes estratégias para algoritmos baseados na heurística GRASP, e compara-se os resultados experimentais obtidos / Abstract: The main goal of these studies is the design of heuristics to support the planning of wire cabling on a phone network. The cabling will be handled from the central distribution point to terminal boxes. The assistance of a computational tool specialized in the design of phone networks raises new opportunities for cost reduction and decreases considerably the time spent designing the network. The problem is first studied in order to achieve a detailed specification with a mathematical model. Based on this information, several different strategies are laid out based on a heuristic called GRASP and the experimental results are compared. / Mestrado / Otimização Combinatoria / Mestre em Computação