O empacotamento irregular de fita é um grupo de problemas na área de corte e empacotamento, cuja aplicação é observada nas indústrias têxtil, moveleira e construção naval. O problema consiste em definir uma configuração de itens irregulares de modo que o comprimento do contêiner retangular que contém o leiaute seja minimizado. A solução deve ser válida, isto é, não deve haver sobreposição entre os itens, que não devem extrapolar as paredes do contêiner. Devido a aspectos práticos, são admitidas até quatro orientações para o item. O volume de material desperdiçado está diretamente relacionado à qualidade do leiaute obtido e, por este motivo, uma solução eficiente pressupõe uma vantagem econômica e resulta em um menor impacto ambiental. O objetivo deste trabalho consiste na geração automática de leiautes de modo a obter níveis de compactação e tempo de processamento compatíveis com outras soluções na literatura. A fim de atingir este objetivo, são realizadas duas propostas de solução. A primeira consiste no posicionamento sequencial dos itens de modo a maximizar a ocorrência de posições de encaixe, que estão relacionadas à restrição de movimento de um item no leiaute. Em linhas gerais, várias sequências de posicionamentos são exploradas com o objetivo de encontrar a solução mais compacta. Na segunda abordagem, que consiste na principal proposta deste trabalho, métodos rasterizados são aplicados para movimentar itens de acordo com uma grade de posicionamento, admitindo sobreposição. O método é baseado na estratégia de minimização de sobreposição, cujo objetivo é a eliminação da sobreposição em um contêiner fechado. Ambos os algoritmos foram testados utilizando o mesmo conjunto de problemas de referência da literatura. Foi verificado que a primeira estratégia não foi capaz de obter soluções satisfatórias, apesar de fornecer informações importantes sobre as propriedades das posições de encaixe. Por outro lado, a segunda abordagem obteve resultados competitivos. O desempenho do algoritmo também foi compatível com outras soluções, inclusive em casos nos quais o volume de dados era alto. Ademais, como trabalho futuro, o algoritmo pode ser estendido de modo a possibilitar a entrada de itens de geometria genérica, o que pode se tornar o grande diferencial da proposta. / Irregular nesting belongs to the area of cutting and packing problems and are employed in the textile, wood and shipbuilding industries. The problem consists in determining a configuration for a set of irregular items which minimizes the length of the rectangular container in which the layout is located. The solution must be feasible, i.e., items must not overlap nor protrude the container walls. Due to practical reasons, up to four orientations are allowed for an item. The volume of wasted material is directly affected by the quality (density) of the layout. Thus, an efficient solution produces a positive economic and environmental impact. In this work, the objective is to automatically obtain layouts such that their density and the performance of the algorithm are competitive with other solutions in literature. So as to achieve this goal, two approaches are proposed. The first method uses a special sequential placement heuristic such that the algorithm maximizes exact placements, which consist of constrained positions for items. In general terms, a search is performed in the placement sequence in order to obtain a compact layout. In the second approach, which is the main subject of this work, raster methods are employed to guide the translation of items, which are free to move within the layout, and may overlap other items. The method is based on overlap minimization techniques, in which the objective is to eliminate the overlap in a fixed dimensions container. Both algorithms were tested using benchmark problems from the literature. The first strategy yielded unsatisfactory results, though it provided important information about the properties of exactly fitting placements. On the other hand, the main approach was able to produce competitive solutions. The performance was also compatible with other solutions, even in cases which the data volume was high. Moreover, as a future work, an extension for the algorithm can be developed such that items with generic geometry can be considered, which would be an important advance in research terms.

O presente trabalho discorre sobre o uso da metaheurística do Recozimento Simulado (Simulated Annealing) na otimização do planejamento de sistemas regionais de tratamento de efluentes e na sua expansão da capacidade. O primeiro modelo desenvolvido trata da otimização espacial de um sistema regional: dadas fontes de efluentes e locais potenciais para instalação de estações de tratamento, o modelo busca a configuração regional de menor custo. O modelo é composto de duas fases: a primeira é um modelo hidráulico que valida a rede proposta através da solução da equação universal de perda de cargas e uma otimização por Recozimento, visto haver inúmeras soluções, já que a rede pode ter qualquer sentido de fluxo. Esta otimização hidráulica visa minimizar o bombeamento do sistema. A segunda fase compreende a otimização do sistema regional, onde novas configurações e/ou alterações de diâmetros são testadas. Esta segunda otimização também é resolvida via Recozimento com o intuito de minimizar o custo do sistema. O segundo modelo trata da expansão da capacidade do sistema: o período de planejamento é dividido em duas etapas. O Recozimento é aplicado nas duas etapas. Soluções propostas para a segunda etapa são passo a passo testadas para a primeira etapa, de modo que o resultado espelhe uma otimização de todo o período. O uso intenso do Recozimento e de simulações na obtenção de soluções iniciais e candidatas leva a um tempo de processamento bastante elevado, especialmente no caso do Modelo Dinâmico. Os modelos foram testados em uma bacia exemplo obtida da literatura e também na bacia do rio Barigui, na Região Metropolitana de Curitiba. Foram desenvolvidas funções de custo para interceptores, estações elevatórias e estações de tratamento de efluentes com base em dados de obras efetuadas na Região Metropolitana de Curitiba. O uso da metaheurística do Recozimento Simulado provou ser um caminho interessante para a otimização de sistemas regionais tais como de tratamento de efluentes. Estudos adicionais são necessários no sentido de se obter um modelo hidráulico de maior eficiência computacional, um número maior de testes com os parâmetros do Recozimento e funções de custo mais abrangentes, especialmente quanto a custos de operação e manutenção. / This study is concerned with the use of the metaheuristic Simulated Annealing for the optimal planning of regional effluent systems and its capacity expansion. The first model deals with the spatial optimization of the system: given a network where some nodes represent effluent sources and other nodes represent the location of possible sewage treatment plants, the model seeks the minimum cost configuration. The first module of the model verifies the hydraulic viability of proposed configurations, by solving the universal equation of head loss. This is also done via annealing since there is a multitude of solutions because any flow direction is allowed. The second part of the model consists of trying different candidate solutions for the network, by means of changing its configurations and/or diameters and looking for the lowest cost solution. The second model deals with the capacity expansion of the system. The planning horizon is divided in two parts. Each solution for the second period is tested also for the first period, thus providing a global minimum for the entire planning period. The use of annealing coupled with intensive use of simulation results in large processing times, especially for the dynamic model. The models were tested for a network available in the literature and also in the Barigui river basin, in the Metropolitan Region of Curitiba, PR. Cost equations were derived for conveyance systems, lifting stations and wastewater treatment plants. The use of Simulated Annealing proved to be an interesting tool for the planning and optimization of regional systems such as the ones here studied. Further studies are recommended such as a mix of the two hydraulic models developed, seeking for the improvement of computational time. Additional testing of the annealing parameters are also needed and O&M cost functions should be detailed.

Orientador: Hermano de M. F. Tavares / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-07-23T05:35:49Z (GMT). No. of bitstreams: 1 Quaglia_EduardoJose_M.pdf: 10132769 bytes, checksum: 6ce6a2a144791123a2d212d4b2700313 (MD5) Previous issue date: 1997 / Resumo: O setor de telecomunicações tem apresentado altos índices de crescimento, motivando o aparecimento de novas tecnologias. Na área da transmissão aparece a tecnologia SDH (Hierarquia Digital Síncrona), substituindo a PDH (Hierarquia Digital Plesiócrona), que passou a oferecer uma série de melhorias quanto à gerência, retirada/inserção de canais dos agregados e segurança de rede. Esta tecnologia permite a utilização de novas estruturas, os anéis e cadeias, que requerem planejamento criterioso para a sua instalação. O planejamento da rede de telecomunicações é dividido em fases. A que define oconjunto de equipamentos de transmissão, a topologia lógica da rede e o roteamento das demandas entre centros de fios é denominada Enfeixamento. Este trabalho apresenta um modelo de otimização para esta fase do planejamento. É um Problema Linear Inteiro Misto (PLIM) com variáveis inteiras (facilidades) e reais (fluxos nos caminhos). Caracteriza-se como um problema de fluxo multiproduto implementado na abordagem de fluxo por caminho. A técnica de otimização utilizada foi o branch-and-bound. A construção de uma ferramenta computacional, dedicada à montagem da formulação matemática, permitiu a aplicação deste modelo a redes reais, cujos resultados fazem parte do conteúdo deste trabalho. O programa resolvedor utilizado foi o CPLEX / Abstract: Telecommunications has experimented high growth rates, causing a rapid development of new technologies. In the transmission area, the SDH technology (Synchronous Digital Hierarchy) replaces the PDH technology (Plesyochronous Digital Hierarchy), offering several improvements in management, channels add-dropping on the main stream and network security. The SDH technology allows the utilization of new structures, the rings and chains, that need perceptive planning for their installation. The telecommunication network planning is divided in several phases. The one that defines the transmission equipment set, the network logical topology and the demand routing among central offices is named "Bundling". This work presents an optimization model for the "Bundling" phase. It is a Mixed Integer Linear Problem with integer variables (facilities) and real variables (flow on path). It can be defined as a multi-commodity flow problem implemented in path flow approach. The optimization technique used was the branch-and-bound. The kernel of this work is a computer program that produces a mathematical model suited for the CPLEX solver. Results from real problems are presented at the end of the work / Mestrado / Mestre em Engenharia Elétrica

Orientadores: Pedro Sergio de Souza, Cid Carvalho de Souza / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-07-23T06:12:54Z (GMT). No. of bitstreams: 1 Ribeiro_WesleyElias_M.pdf: 3030614 bytes, checksum: 36a45d851a8415069c93b66b7f8b80da (MD5) Previous issue date: 1997 / Resumo: Esta dissertação trata do Problema do Caixeiro Viajante Coletor de Prêmios (Prize Collecting Traveling Salesman Problem-PCTSP). Este problema é uma generalização do bastante conhecido Problema do Caixeiro Viajante (Traveling Salesman Problem - TSP), em que o caixeiro viajante não precisa visitar, necessariamente, todas as cidades, mas um número suficiente delas para a obtenção de um prêmio mínimo. Além disso, sua função objetivo é dada pela minimização do comprimento da rota adicionada às penalidades pagas por cidades não visitadas. A formulação do PCTSP foi feita com base em uma aplicação prática do problema, o escalonamento de equipamentos em uma indústria siderúrgica. O presente trabalho apresenta um estudo de algoritmos heurísticos disponíveis na literatura do problema. São, então, apresentadas novas heurísticas de construção e melhoria de soluções desenvolvidas para o PCTSP, e é efetuada uma comparação com o algoritmo de melhor garantia de desempenho encontrado na literatura. Este trabalho também compreende o desenvolvimento de um Time Assíncrono para o PCTSP. Times Assíncronos compreendem uma abordagem meta-heurística já aplicada com sucesso a diversos outros problemas de Otimização Combinatória. Seu princípio básico é a combinação sinérgica de diversos algoritmos (agentes), comunicando-se através de memórias compartilhadas. O Time Assíncrono foi implementado de forma distribuída, utilizando-se o pacote PVM (Parallel Virtual Machine), baseado em troca de mensagens. Para os testes foram geradas aleatoriamente diversas instâncias de tamanhos variados, e, para efeito de comparação, foram obtidos limites inferiores para estas instâncias utilizando-se o pacote de programação linear/inteira Cplex, aplicado a relaxações do problema desenvolvidas / Abstract: This dissertation deals with the Prize Collecting Traveling Salesman Problem (PCTSP). This problem is a generalization of the well-known Traveling Salesman Problem (TSP), where the salesman does not need to visit all the cities, but has to visit enough cities in order to obtain a minimum prize. Besides that, the objective function is given by the minimization of the tour lenght plus the penalties paid for unvisited cities. The formulation of the PCTSP was made based on a pratical application of the problem, the scheduling of production units in a steel plant. The present work presents a study of the heuristic algorithms available in the literature about the problem. It then shows new construction and improvement heuristics developed for the PCTSP, and presents a comparison between those new heuristics and the best performance guarantee algorithm found in the literature. This work also presents a Asynchronous Team developed for the PCTSP. Asynchronous Teams are a meta-heuristic approach already succesfully applied to many other Combinatorial Optimization problems. Its basic principle is the sinergic combination of many algorithms (agents), communicating through shared memories. The Asynchronous Team was implemented using distributed processing, by using the message-passing based PVM (Parallel Virtual Machine) package. Many instances of different sizes were randomically generated, and, for comparison, lower bounds for these instances were calculated using the Cplex linear /integer programming package, applied to relaxations of the problem / Mestrado / Mestre em Ciência da Computação

Orientador: Candido Ferreira Xavier de Mendonça Neto / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-11-01T11:47:37Z (GMT). No. of bitstreams: 1 Nascimento_HugoAlexandreDantasdo_M.pdf: 3105105 bytes, checksum: 1db649275d731767fbcb044c4fb5008c (MD5) Previous issue date: 1997 / Resumo: Desenho de Grafos é uma área recente que trata do desenvolvimento de técnicas e de algoritmos para construir representações geométricas de grafos, atendendo, em geral, a critérios estéticos. A atividade de desenhar grafos implica em muitas dificuldades; entre elas, verificamos que a satisfação de alguns critérios estéticos envolve freqüentemente problemas NP-difíceis e que, em muitos casos, os critérios são conflitantes entre si. Em função disso, heurísticas têm sido desenvolvidas e amplamente utilizadas para obter bons desenhos. No presente trabalho, descrevemos uma nova abordagem para desenhar grafos, que se baseia na combinação de heurísticas utilizando um tipo de organização de agentes conhecido como Time Assíncrono. A abordagem é capaz de produzir desenhos melhores do que as heurísticas isoladas, e é flexível pois pode ser aplicada para trabalhar com muitos critérios estéticos e com várias classes de grafos / Abstract: Graph Drawing is a new area that deals with the development of techniques and algorithms whose major concern is the geometric representations of graphs. These geometric representations must follow a set of aesthetic criteria in a "nice" way. The activity of drawing graphs run into many dificulties, for example: the problem of satisfying some aesthetic criteria is often NP-hard and, in mostcases, there are some conflitcs among the criteria. This justifies the wide use of heuristics to produce good drawings. In this work we show a new approach to draw graphs. This approach focuses on the combination of different heuristics in a specific organization of agents, called Asynchronous Team. The approach achieves better drawings than the heuristics alone, and it can be applied to work with severa! aesthetic criteria for drawing many classes of graphs / Mestrado / Mestre em Ciência da Computação

Submitted by ANTONE DOS SANTOS BENEDITO null (antone@ibb.unesp.br) on 2017-02-06T16:05:53Z No. of bitstreams: 1 dissertação_biometria.pdf: 1924167 bytes, checksum: 521f0878b97aaa77f37c723cac82b19f (MD5) / Approved for entry into archive by LUIZA DE MENEZES ROMANETTO (luizamenezes@reitoria.unesp.br) on 2017-02-09T18:07:57Z (GMT) No. of bitstreams: 1 benedito_as_me_bot.pdf: 1924167 bytes, checksum: 521f0878b97aaa77f37c723cac82b19f (MD5) / Made available in DSpace on 2017-02-09T18:07:57Z (GMT). No. of bitstreams: 1 benedito_as_me_bot.pdf: 1924167 bytes, checksum: 521f0878b97aaa77f37c723cac82b19f (MD5) Previous issue date: 2016-02-29 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / Neste trabalho, apresentamos uma estratégia para estimação de parâmetros de um modelo matemático não-linear de equações diferenciais ordinárias, que descreve a dinâmica populacional de mosquitos da Dengue, para o qual há dados disponíveis para as fases aquática e alada. Para estimar um conjunto de parâmetros biológicos desconhecidos, uma função custo envolvendo tais parâmetros é minimizada por meio do método Levenberg −Marquardt (LM). O principal interesse foi ajustar o modelo aos dados levando em conta os parâmetros estimados. Os resultados das simulações numéricas mostram a eficácia da técnica de estimação de parâmetros acoplada ao LM. A comparação entre a solução numérica e os dados comprova a eficiência do código no ajuste dos dados, consonante com estimativas apresentadas na literatura. / In this work we describe a study of parameters estimation technique applied to nonlinear model of ordinary differential equations. This model describes the population dynamics of dengue mosquitoes where the data about water andwinged phases are available. In particular, we are interested in estimate a set of unknown biological parameters. For this purpose a cost function involving the parameters to be estimated was defined. To minimize this function a routine based on Levenberg − Marquardt (LM) algorithm was developed. Our main aim was to fit the model to the data taking into account the parameters estimated. The results from numerical simulations show effectiveness of parameters estimation technique coupled with LM algorithm. The comparison between numerical solution and available data demonstrates the efficiency of code in data fit. Our estimates are according to estimates exhibited in literature.

O presente trabalho discorre sobre o uso da metaheurística do Recozimento Simulado (Simulated Annealing) na otimização do planejamento de sistemas regionais de tratamento de efluentes e na sua expansão da capacidade. O primeiro modelo desenvolvido trata da otimização espacial de um sistema regional: dadas fontes de efluentes e locais potenciais para instalação de estações de tratamento, o modelo busca a configuração regional de menor custo. O modelo é composto de duas fases: a primeira é um modelo hidráulico que valida a rede proposta através da solução da equação universal de perda de cargas e uma otimização por Recozimento, visto haver inúmeras soluções, já que a rede pode ter qualquer sentido de fluxo. Esta otimização hidráulica visa minimizar o bombeamento do sistema. A segunda fase compreende a otimização do sistema regional, onde novas configurações e/ou alterações de diâmetros são testadas. Esta segunda otimização também é resolvida via Recozimento com o intuito de minimizar o custo do sistema. O segundo modelo trata da expansão da capacidade do sistema: o período de planejamento é dividido em duas etapas. O Recozimento é aplicado nas duas etapas. Soluções propostas para a segunda etapa são passo a passo testadas para a primeira etapa, de modo que o resultado espelhe uma otimização de todo o período. O uso intenso do Recozimento e de simulações na obtenção de soluções iniciais e candidatas leva a um tempo de processamento bastante elevado, especialmente no caso do Modelo Dinâmico. Os modelos foram testados em uma bacia exemplo obtida da literatura e também na bacia do rio Barigui, na Região Metropolitana de Curitiba. Foram desenvolvidas funções de custo para interceptores, estações elevatórias e estações de tratamento de efluentes com base em dados de obras efetuadas na Região Metropolitana de Curitiba. O uso da metaheurística do Recozimento Simulado provou ser um caminho interessante para a otimização de sistemas regionais tais como de tratamento de efluentes. Estudos adicionais são necessários no sentido de se obter um modelo hidráulico de maior eficiência computacional, um número maior de testes com os parâmetros do Recozimento e funções de custo mais abrangentes, especialmente quanto a custos de operação e manutenção. / This study is concerned with the use of the metaheuristic Simulated Annealing for the optimal planning of regional effluent systems and its capacity expansion. The first model deals with the spatial optimization of the system: given a network where some nodes represent effluent sources and other nodes represent the location of possible sewage treatment plants, the model seeks the minimum cost configuration. The first module of the model verifies the hydraulic viability of proposed configurations, by solving the universal equation of head loss. This is also done via annealing since there is a multitude of solutions because any flow direction is allowed. The second part of the model consists of trying different candidate solutions for the network, by means of changing its configurations and/or diameters and looking for the lowest cost solution. The second model deals with the capacity expansion of the system. The planning horizon is divided in two parts. Each solution for the second period is tested also for the first period, thus providing a global minimum for the entire planning period. The use of annealing coupled with intensive use of simulation results in large processing times, especially for the dynamic model. The models were tested for a network available in the literature and also in the Barigui river basin, in the Metropolitan Region of Curitiba, PR. Cost equations were derived for conveyance systems, lifting stations and wastewater treatment plants. The use of Simulated Annealing proved to be an interesting tool for the planning and optimization of regional systems such as the ones here studied. Further studies are recommended such as a mix of the two hydraulic models developed, seeking for the improvement of computational time. Additional testing of the annealing parameters are also needed and O&M cost functions should be detailed.

Dissertação (mestrado) - Pontifícia Universidade Católica do Paraná, Curitiba, 2008 / Bibliografia: f. 88-100 / O algoritmo de otimização através de nuvem de partículas (PSO) é uma técnica metaheurística desenvolvida recentemente e pertence a categoria de técnicas inteligentes baseadas em enxames. Os enxames inteligentes são conceitos inspirados no comportamento so / Abstract: The particle swarm optimization (PSO) algorithm is a recently developed metaheuristic technique and belongs to the category of swarm intelligence techniques. The swarm intelligence concepts are inspired by the social behavior of flocking animals

Submitted by Marco Antônio de Ramos Chagas (mchagas@ufv.br) on 2017-02-02T17:10:41Z No. of bitstreams: 1 texto completo.pdf: 1372371 bytes, checksum: e21c73e29ad9a1b730b3b0e4adaaff46 (MD5) / Made available in DSpace on 2017-02-02T17:10:41Z (GMT). No. of bitstreams: 1 texto completo.pdf: 1372371 bytes, checksum: e21c73e29ad9a1b730b3b0e4adaaff46 (MD5) Previous issue date: 2016-07-06 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / O Problema de Roteamento de Veículos (PRV) é um problema clássico de Otimização Combinatória bastante estudado na literatura devido a sua importância prática. O PRV Periódico (PRVP), abordado neste trabalho, é uma variante do PRV no qual um conjunto de clientes devem ser visitados uma ou mais vezes para atender suas demandas durante um horizonte de tempo composto de vários dias. Os dias de visita/atendimento não são fixados a priori. Uma lista de dias possíveis (agenda de visitas) é associada a cada cliente. O objetivo é determinar os dias de visita de cada cliente e as rotas dos veículos para cada dia do horizonte de tal maneira que a distância total de percurso dos veículos e os custos associados com utilização dos mesmos sejam minimizados. O PRVP é um problema que pertence à classe NP-difícil. Neste trabalho, para resolvê-lo, são desenvolvidos três métodos de otimização: Proximity Search (PS), Ite- rated Local Search (ILS) e Particle Swarm Optimization (PSO). PS é um método genérico que faz uso do modelo de Programação Inteira do problema para melhorar iterativamente uma solução inicial. Em vez de modificar as restrições do modelo com o objetivo de reduzir o espaço de busca, o PS modifica a função objetivo do modelo para tornar a busca mais fácil. Os métodos ILS e PSO são meta-heurísticas de busca em vizinhança e populacional/evolutiva, respectivamente. Os desempenhos dos métodos propostos são analisados em instâncias de pequeno e grande porte geradas neste trabalho, e também em instâncias disponíveis na literatura. O desempenho do PS é comparado com o solver CPLEX, que resolve o modelo original do problema. As meta-heurísticas desenvolvidas são comparadas entre si e também são comparadas com algumas heurísticas da literatura. Os experimentos computacionais mostram que os métodos propostos são eficientes, competitivos e rápidos. / The Vehicle Routing Problem (VRP) is a classic problem of Combinatorial Optimi- zation extensively studied in the literature because of its practical importance. The Periodic VRP (PVRP), discussed in this work, is a variant of VRP in which a group of customers should be visited one or more times to meet their demands over a time horizon composed of several days. The days to visit a customer are not initially fixed. A possible list of days (visits schedule) is associated with each customer. The objective problem is to determine the set of days to visit each customer and determine the routes of the vehicles for each day of the planning horizon such that the total distance of the vehicle route and costs associated with use of them are minimized. The PVRP is a problem that belongs to the NP-hard class. In this work, three optimization methods are developed to solve the problem: Proximity Search (PS), Iterated Local Search (ILS) and Particle Swarm Optimization (PSO). PS is a generic method that makes use of the Integer Programming Problem model to iteratively improve an initial solution. Instead of modifying the model restrictions intended to reduce the search space, the PS changes the objective function to make the search easier. The ILS and PSO methods are meta-heuristic search in the neighborhood and population / evolutionary, respectively. The performances of the proposed methods are analyzed using small and large instances generated in this work, and also for instances available in the literature. The performance of PS is compared with CPLEX solver, which solves the original problem formulation. The developed meta-heuristics are compared to each other and are also compared with some heuristics from the literature. The computational experiments show that the proposed methods are efficient, competitive and fast.

Submitted by Reginaldo Soares de Freitas (reginaldo.freitas@ufv.br) on 2017-02-10T15:29:30Z No. of bitstreams: 1 texto completo.pdf: 2736980 bytes, checksum: f41dd8d979519bbcc7b9d7350c591432 (MD5) / Made available in DSpace on 2017-02-10T15:29:30Z (GMT). No. of bitstreams: 1 texto completo.pdf: 2736980 bytes, checksum: f41dd8d979519bbcc7b9d7350c591432 (MD5) Previous issue date: 2016-09-21 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / In this study we apply single-objective and bi-objective parallel heuristics to solve broad and realistic formulations of the travel planning problem. Given a travel time window and a set of destinations with their corresponding dwelling times, the goal of our single-objective approach is to find a route that produces a budget travel’s itinerary, involving flights, hotels and departure/arrival times. In turn, our bi-objective approach adds a complexity level in the problem’s formulation once we are seeking for a Pareto set of detailed travel itineraries, which are both cost and time efficient. When the sequence of cities is fixed, the single-objective version of the problem is commonly modeled in literature as a time-dependent network and the best itinerary is computed using shortest path algorithms. However, in this study, finding the order of cities that minimizes the total cost, and besides that, a set of good trade-off solutions, are also goals. Therefore, our single-objective formulation stands for a TDSPP (Time Dependent Shortest Path Problem) embedded in the TSP (Travel Salesman Problem) whereas our bi-objective formulation stands for a TDSPP embedded in a bi-objective TSP. On the first formulation we apply an ILS (Iterated Local Search) heuristic and on the second formulation we apply the NSGA-II (Nondominated Sorting Genetic Algorithm II) framework. For performance assessing, the results of both heuristics were compared to the results of corresponding exact methods with no time constraints. All test cases simulate realistic travel itineraries and run upon real-world travel data collected in advance, besides having to comply with an execution threshold of approximately 1 minute. For 285 single-objective test cases, our ILS heuristic was able to reach solutions in average less than 4.1% divergent from an exact implementation, besides reaching the optimal solution in about 30% of the test cases. In turn, for 180 bi-objective test cases, our NSGA-II implementation was able to reach an approximated solution in average up to 8% divergent from an exact implementation. / Nesse trabalho são aplicadas heurísticas paralelas mono-objetivas e bi-objetivas para solucionar formulações abrangentes e realistas do problema de planejamento de viagens. Dado o intervalo de tempo que uma viagem pode ocorrer e um conjunto de destinos com seus respectivos tempos de permanência, a abordagem mono-objetiva procura determinar um itinerário de baixo custo que compreenda voos, hotéis e horários de partida/chegada. Por sua vez, a abordagem bi-objetiva adiciona complexidade a formulação do problema, uma vez que pretende determinar o conjunto Pareto de itinerários de viagem capazes de equilibrar custo e tempo. Quando a sequência de cidades é fixa, a versão mono-objetiva do problema é comumente modelada na literatura como uma rede dependente do tempo e o melhor itinerário é calculado usando algoritmos de caminho míınimo. Contudo, nesse trabalho, determinar a ordem de visitação das cidades também é um objetivo. Portanto, a formulação mono-objetiva proposta representa um TDSPP (Time Dependent Shortest Path Problem) incorporado ao TSP (Travel Salesman Problem) e a formulação bi-objetiva representa um TDSPP incorporado em um TSP bi-objetivo. Na primeira formulação foi aplicada a heurística ILS (Iterated Local Search) e na segunda formulação o framework NSGA-II (Nondominated Sorting Genetic Algorithm II). Os resultados de ambas as heurísticas foram comparados com os resultados produzidos por métodos exatos executados sem restrições temporais. Todos os casos de teste simulam itinerários de viagem realistas e foram executados em um banco de dados de viagens e hospedagens coletadas com antecedência. Além disso, independentemente da abordagem utilizada, estabeleceu-se que o tempo de execução de cada caso deve ser de aproximadamente 1 minuto. A heurística ILS proposta para a versão mono-objetiva do problema foi executada em 285 instâncias e alcançou, em média, soluçõoes no máximo 4.1% divergentes de uma implementa ̧ao exata, além de atingir a melhor solução em cerca de 30% dos casos de teste. Por sua vez, o framework NSGA-II foi capaz de produzir soluções no máximo 8% divergentes da implementação exata para 180 instâncias.