Este trabalho apresenta a implementação de um roteador global de circuitos integrados capaz de tratar os problemas de roteamento atuais, utilizando como referência para avaliação os circuitos de benchmark publicados durante as competições de roteamento global realizadas no ACM International Symposium on Physical Design 2007 e 2008. O roteador global desenvolvido utiliza como ferramenta principal a técnica de ripup and reroute associada às técnicas de roteamento monotônico e maze routing, ambas com grande histórico de uso nas ferramentas acadêmicas descritas também neste trabalho. O desenvolvimento da ferramenta também possui características diferenciadas e únicas, com um novo método de ordenamento das redes durante a fase de rip-up and reroute. Para a geração dos resultados foram definidas duas versões diferentes da ferramenta, sendo estas duas versões analisadas com duas diferentes técnicas de construção das árvores de roteamento, gerando no total quatro configurações da ferramenta. Como decisão de projeto, a versão principal utilizada no desenvolvimento e discussão dos resultados é a versão que prioriza a qualidade do roteamento, utilizando MSTs para construção das árvores de roteamento. Os resultados mostram que o roteador global desenvolvido é capaz de gerar resultados com boa qualidade mesmo sem fazer uso de técnicas de identificação de áreas de congestionamento, sem otimizações pós-roteamento e sem nenhuma forma de ajuste (tuning) para os diferentes circuitos de benchmark, apesar de ainda ter tempo de execução acima dos apresentados por outras ferramentas acadêmicas. O foco durante o processo de desenvolvimento e implementação da ferramenta foram os circuitos mais recentes, entretanto a ferramenta obteve ótimos resultados também para os circuitos publicados no ISPD 1998, gerando soluções com qualidade similar ou melhor que as reportadas na literatura. A diferença dos resultados deste trabalho em relação aos melhores resultados dos roteadores globais com código disponível, para circuitos 3D lançados no ISPD 2008 é de, em média, 1,78%1 na métrica de comprimento de fio sem considerar o custo das vias e de 15,56% considerando o custo da via como uma unidade de comprimento de fio (ISPD 2008), para a versão voltada a qualidade de roteamento. Já para a versão da ferramenta que busca a convergência o mais rápido possível a diferença foi de 3,39% e 16,32%, respectivamente. As maiores diferenças são encontradas nos circuitos mais difíceis de gerar uma solução sem violações. Isso mostra como as técnicas de identificação de região podem contribuir tanto para uma convergência mais rápida quanto para evitar que fios passem por rotas desnecessárias durante a fase de negociação. Na métrica que avalia as vias como custo de uma unidade de comprimento, os resultados obtidos apresentam em média 18,67% maior comprimento de fio que os melhores resultados da literatura, sendo que dois circuitos com solução sem violações2 apresentam resultado com violações utilizando a ferramenta desenvolvida neste trabalho. / This work describes the implementation of an integrated circuit global router capable of handling the current routing problems, using as a reference the evaluation of benchmark circuits from the two global routing contests held in ISPD 2007 and 2008. The developed global router uses rip-up and reroute as the main technique associated with monotonic and maze routing techniques, both with large history of use in academic tools, also described in this work. The tool also has distinctive and unique characteristics, with a new method of net ordering during the rip-up and reroute stage. In order to generate the results were defined two different versions of the tool analyzed with two different techniques of routing tree construction, generating a total of four configurations. As a design decision, the major version used in the development and discussion of results is the version that prioritizes the routing quality, using MSTs for tree construction. The results show that the global router developed is able to generate good results even without making use of techniques to identify congestion areas, without post-routing optimizations and without any form of tuning for the different benchmark circuits, despite having run time above other academic tools. The focus during the development and implementation of the tool were the newer circuits, however the tool also obtained excellent results for the circuits released in ISPD 1998, generating solutions with similar quality or better than those reported in the literature. The difference in the results of this work over the best results generated with the available code global routers for 3D circuits released in ISPD 2008 is, on average, 2.53% in wirelength metric without considering the cost of vias and 18.34% considering the cost of the vias as one wirelength unit (ISPD 2008), for the best routing quality version. As for the version of the tool that seeks convergence as soon as possible the difference was 3.82% and 17.03%, respectively. The largest differences were found in the most difficult circuits to generate a solution without violations. This shows how the techniques of congested region identification can contribute to both a faster convergence and to avoid unnecessary wire detours during the negotiation phase. In the metric that evaluates the cost of vias as one wirelength unit, the results show an average of 22.5% greater wirelength than the best results found in literature. Also, the developed global router was unable to find a violation free solution for two circuits that are known to have a violation free solution3.

O projeto ISAM apresenta uma plataforma para o desenvolvimento e a execução de aplicações pervasivas. O ambiente de execução proposto na arquitetura ISAM, denominado ISAMpe (ISAM pervasive environment), foi concebido para ser implantado em escala global, com elevado número de componentes. Esses componentes podem ser móveis ou fixos e podem apresentar limitações em seus recursos computacionais. Muitas das aplicações pervasivas que podem ser executadas no ISAMpe têm necessidade de um serviço de disseminação capaz de distribuir informações de um produtor para um grande número de consumidores. Esta dissertação apresenta um serviço de disseminação de informações para a arquitetura ISAM, denominado DIMI (Disseminador Multicast de Informações). O DIMI apresenta uma arquitetura de multicast no nível de aplicação. O DIMI propõe um algoritmo de formação da topologia de disseminação que tem o objetivo de alcançar maior escalabilidade pelo alívio de sobrecarga em participantes específicos do canal, durante os momentos em que houver um grande número de novos consumidores querendo iniciar o consumo simultaneamente. No seu ambiente-alvo, o ISAMpe, o DIMI também oferece suporte à desconexão planejada, permitindo que dispositivos computacionais com limitações de conectividade participem da disseminação, e ainda oferece suporte à mobilidade de usuários. A topologia de comunicação do DIMI adapta-se às condições da rede física subjacente a ela, de acordo com critérios específicos da aplicação que utilizar o serviço. Os resultados obtidos com a simulação de alguns aspectos do funcionamento do DIMI e com a execução do protótipo do mesmo validam os argumentos usados para justificar a necessidade e a forma de construção do serviço. / The ISAM project presents a platform to the development and to the execution of pervasive applications. The execution environment proposed by the ISAM architecture, named ISAMpe (ISAM pervasive environment) was conceived to be deployed on global scale, having a large number of components. These components may be mobile or static and may present computational resource limitations. Many of the pervasive applications that may be executed on the ISAMpe need a dissemination service capable of distribute information from one producer to many consumers. This dissertation presents a information dissemination service for the ISAM architecture, named DIMI (Multicast Information Disseminator - Disseminador Multicast de Informações). DIMI presents an application-level multicast architecture. DIMI proposes an algorithm to create the dissemination topology which objective is to achieve scalability through the relief of overload on specific participants of the channel, during the moments where many new consumers want to start consumption simultaneously. Inside its target-environment, DIMI also offer support to user mobility and to planned disconnection, allowing resource limited computational devices to be participants of the dissemination. DIMI's dissemination topology adapt itself to the conditions of fabric network, accordingly to applications' criteria. The results obtained with the simulation of some DIMI's characteristics and with prototipation validate the arguments used to justify the necessity and the way of construction of the service.

Cada vez mais empilhadeiras robóticas são utilizadas para a tarefa de transporte em indústrias e armazéns. O gerenciamento dessas empilhadeiras é a chave para um sistema de transporte eficiente visando maximizar sua taxa de transferência. Um dos principais problemas na operação desses sistemas é a decisão de roteamento das empilhadeiras dentro dos depósitos. Este trabalho propõe um algoritmo de roteamento com a capacidade de realizar a otimização das rotas em tempo-real. Na computação da rota são considerados o desvio de obstáculos, as dimensões e as propriedades físicas das empilhadeiras, pois uma trajetória calculada deste ponto de referência está livre de colisões durante a execução do roteamento. Para realizar os testes foram utilizados os softwares Player/Stage, os quais permitem que simulações do funcionamento do sistema de roteamento sejam realizadas antes que os algoritmos sejam testados em robôs reais. Através dos testes simulados, analisou-se a capacidade de locomoção das empilhadeiras referente ao calculo da melhor rota no ambiente proposto, com o intuito de melhorar o ganho de performance no planejamento de trajetória. / Forklift robots have been increasingly used in transport tasks in industries and warehouses. The key to an efficient transport system is held by a sound management of these forklifts that aim to maximize the transference rate. One of the main problems faced by the transportation systems is routing decision for forklifts within warehouse. The present paper proposes a routing algorithm to calculate optimal routes in real time. Therefore, its computation takes into account obstacle avoidance, the dimension and physical properties of the forklifts, since the calculated path regarding the routing is conflict-free. Simulations were carried out using the software Player/Stage before the algorithms were tested in a real robot. Simulated tests were analyzed in order to observe the locomotion ability of forklifts regarding calculation of the best route in the environment proposed to improve the trajectory planning performance will be assessed.

O projeto ISAM apresenta uma plataforma para o desenvolvimento e a execução de aplicações pervasivas. O ambiente de execução proposto na arquitetura ISAM, denominado ISAMpe (ISAM pervasive environment), foi concebido para ser implantado em escala global, com elevado número de componentes. Esses componentes podem ser móveis ou fixos e podem apresentar limitações em seus recursos computacionais. Muitas das aplicações pervasivas que podem ser executadas no ISAMpe têm necessidade de um serviço de disseminação capaz de distribuir informações de um produtor para um grande número de consumidores. Esta dissertação apresenta um serviço de disseminação de informações para a arquitetura ISAM, denominado DIMI (Disseminador Multicast de Informações). O DIMI apresenta uma arquitetura de multicast no nível de aplicação. O DIMI propõe um algoritmo de formação da topologia de disseminação que tem o objetivo de alcançar maior escalabilidade pelo alívio de sobrecarga em participantes específicos do canal, durante os momentos em que houver um grande número de novos consumidores querendo iniciar o consumo simultaneamente. No seu ambiente-alvo, o ISAMpe, o DIMI também oferece suporte à desconexão planejada, permitindo que dispositivos computacionais com limitações de conectividade participem da disseminação, e ainda oferece suporte à mobilidade de usuários. A topologia de comunicação do DIMI adapta-se às condições da rede física subjacente a ela, de acordo com critérios específicos da aplicação que utilizar o serviço. Os resultados obtidos com a simulação de alguns aspectos do funcionamento do DIMI e com a execução do protótipo do mesmo validam os argumentos usados para justificar a necessidade e a forma de construção do serviço. / The ISAM project presents a platform to the development and to the execution of pervasive applications. The execution environment proposed by the ISAM architecture, named ISAMpe (ISAM pervasive environment) was conceived to be deployed on global scale, having a large number of components. These components may be mobile or static and may present computational resource limitations. Many of the pervasive applications that may be executed on the ISAMpe need a dissemination service capable of distribute information from one producer to many consumers. This dissertation presents a information dissemination service for the ISAM architecture, named DIMI (Multicast Information Disseminator - Disseminador Multicast de Informações). DIMI presents an application-level multicast architecture. DIMI proposes an algorithm to create the dissemination topology which objective is to achieve scalability through the relief of overload on specific participants of the channel, during the moments where many new consumers want to start consumption simultaneously. Inside its target-environment, DIMI also offer support to user mobility and to planned disconnection, allowing resource limited computational devices to be participants of the dissemination. DIMI's dissemination topology adapt itself to the conditions of fabric network, accordingly to applications' criteria. The results obtained with the simulation of some DIMI's characteristics and with prototipation validate the arguments used to justify the necessity and the way of construction of the service.

Submitted by Nayara Passos (nayara.passos@ufpe.br) on 2015-03-11T19:28:27Z No. of bitstreams: 2 TESE Crishane Azevedo Freire.pdf: 2913439 bytes, checksum: 6da007914a1bc532cd0681ed751d6e4c (MD5) license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) / Made available in DSpace on 2015-03-11T19:28:27Z (GMT). No. of bitstreams: 2 TESE Crishane Azevedo Freire.pdf: 2913439 bytes, checksum: 6da007914a1bc532cd0681ed751d6e4c (MD5) license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) Previous issue date: 2014 / Os Peer Data Management Systems (PDMS) são sistemas que permitem o gerenciamento de dados estruturados e semiestruturados em ambientes Ponto-a-Ponto (P2P). Nestes sistemas, cada ponto corresponde a uma fonte de dados cujo esquema representa os dados que se deseja compartilhar na rede. Pontos estão conectados por meio de mapeamentos (correspondências semânticas entre os esquemas dos pontos) estabelecendo uma vizinhança semântica entre eles. O processamento de consultas é reconhecido como o principal serviço que um PDMS pode prover. Uma etapa importante deste processo está relacionada ao roteamento da consulta, ou seja, a habilidade do sistema de identificar, selecionar e fazer o encaminhamento da consulta ao melhor conjunto de pontos capazes de respondê-la. A cada encaminhamento a consulta precisa ser reformulada, ou seja, reescrita de acordo com o esquema do ponto destino. Na reformulação, termos (conceitos e/ou propriedades utilizados na formulação da consulta) podem ser perdidos por não possuírem correspondentes exatos no esquema do ponto destino. Neste caso, estratégias de reformulação que usam expansão buscam melhorar a consulta adicionando novos termos com o objetivo de tornar a consulta mais abrangente e evitar a ausência de resultados. Ao longo do roteamento, termos perdidos ou adicionados, a cada reformulação, podem levar à perda semântica da consulta original. Neste trabalho apresentamos a SemRouting, uma abordagem para o roteamento de consultas em PDMS baseada no uso de aspectos semânticos e de qualidade. A abordagem SemRouting compreende uma estratégia para identificação e seleção do melhor conjunto de pontos, um modelo para representação das informações semânticas e de qualidade e uma estratégia para análise e preservação da semântica da consulta original durante o roteamento. Para avaliação da abordagem, experimentos foram realizados e os resultados discutidos e apresentados. A análise dos resultados produzidos nos experimentos mostra que as estratégias adotadas na abordagem SemRouting confirmam as hipóteses levantadas nesta tese em relação à preservação semântica da consulta e à seleção do melhor conjunto de pontos durante o roteamento da consulta. Palavras-chave: Roteamento Semântico de Consulta. Informação Semântica. Qualidade da Informação. Peer Data Management System.

Made available in DSpace on 2014-06-12T16:00:14Z (GMT). No. of bitstreams: 2 arquivo6093_1.pdf: 741570 bytes, checksum: fdadc967604851f84c712755a38b8051 (MD5) license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5) Previous issue date: 2007 / A alocação de veículos para uma determinada demanda de consumidores, espalhados geograficamente, está sujeita a uma explosão combinatória de possibilidades, devido às infinitas alternativas de escalonamento. Esta característica impossibilita, para grandes demandas, o tratamento deste problema por algoritmos exatos, ou seja, aqueles que buscam com garantia a solução ótima do problema. Em contrapartida, existem os métodos heurísticos, que são capazes de resolver tais problemas de forma satisfatória, mas não garantindo que a solução alcançada seja a melhor possível. Esta dissertação apresenta, como principal contribuição, um Sistema Híbrido (SH) para o conhecido Problema de Roteamento de Veículos com Janela de Tempo (PRVJT). Este SH é composto dos métodos (i) Recozimento Simulado Não Monotônico (RSNM), (ii) Subida na Encosta (SE) e (iii) Reinício Aleatório (RA). Os métodos foram combinados visando promover a diversificação e a intensificação na busca por soluções do PRVJT. Como contribuição secundária, este trabalho apresenta um arcabouço de métodos estatísticos que é capaz de ajustar parâmetros de sistemas estocásticos para otimização de desempenho. Os resultados dos experimentos realizados com o modelo proposto foram comparados com cada um dos melhores resultados individuais, alcançados anteriormente, pelos diferentes algoritmos conhecidos, para toda a base de dados de Solomon. Os resultados obtidos pelo SH se mostraram relevantes, tendo o método superado ou igualado 37 das 56 instâncias testadas, caracterizando o SH como um método eficaz e robusto no tratamento do PRVJT

Submitted by Fernanda Rodrigues de Lima (fernanda.rlima@ufpe.br) on 2018-09-26T21:14:47Z No. of bitstreams: 2 license_rdf: 811 bytes, checksum: e39d27027a6cc9cb039ad269a5db8e34 (MD5) DISSERTAÇÃO Amanda Bezerra Matias.pdf: 4592043 bytes, checksum: d499cc6efd57d6bf1a0a2937f13592b8 (MD5) / Approved for entry into archive by Alice Araujo (alice.caraujo@ufpe.br) on 2018-10-01T15:24:42Z (GMT) No. of bitstreams: 2 license_rdf: 811 bytes, checksum: e39d27027a6cc9cb039ad269a5db8e34 (MD5) DISSERTAÇÃO Amanda Bezerra Matias.pdf: 4592043 bytes, checksum: d499cc6efd57d6bf1a0a2937f13592b8 (MD5) / Made available in DSpace on 2018-10-01T15:24:42Z (GMT). No. of bitstreams: 2 license_rdf: 811 bytes, checksum: e39d27027a6cc9cb039ad269a5db8e34 (MD5) DISSERTAÇÃO Amanda Bezerra Matias.pdf: 4592043 bytes, checksum: d499cc6efd57d6bf1a0a2937f13592b8 (MD5) Previous issue date: 2017-06-22 / CAPES / No Brasil, a PNRS – Política Nacional de Resíduos Sólidos aborda alternativas para melhorar o gerenciamento dos resíduos sólidos urbanos, uma delas é estabelecer a implementação de programas de reciclagem. Muitos municípios enfrentam desafios em adaptar o modelo de coleta convencional para a modalidade de coleta seletiva. Diante dessa dificuldade esta pesquisa teve como objetivo propor a localização de novos pontos para a instalação e redistribuição de contentores de armazenamento de materiais recicláveis, conhecidos por PEV – Pontos de Entrega Voluntária, aplicando Tecnologias da Geoinformação. Partiu-se da hipótese que, ao adotar a instalação de PEV em áreas mais próximas as residências a população passará a intensificar a sua participação no que tange a separação e armazenamento de materiais recicláveis. A metodologia consistiu: na caracterização das áreas mais adequadas para a instalação dos PEV, na estimativa de distribuição dos pontos por meio da quantidade de pontos necessários para cada bairro e nas análises de distância a partir de algoritmo de roteamento. A primeira etapa da metodologia foi a criação de um Modelo de Dados Espaciais para a representação dos elementos geográficos aplicados ao problema de localização e a sua implementação em um Sistema de Gerenciamento de Banco de Dados. A segunda etapa foi a definição das áreas de praças, parques e alguns estabelecimentos comerciais como sendo as áreas mais adequadas para a instalação dos PEV. A terceira etapa foi o cálculo da quantidade de PEV necessária para cada bairro que levou em consideração uma estimativa da quantidade de resíduos potencialmente recicláveis coletados semanalmente. A quarta etapa consistiu na geração de uma rede topológica e na execução do algoritmo de roteamento Dijkstra para calcular a menor distância entre as residências e as áreas propícias a instalação de PEV. Dos resultados da pesquisa foram propostos 34 PEV distribuídos pelos 23 bairros da zona centro da área urbana da cidade de Teresina. Desta pesquisa observou-se que a proposta de localização para a instalação de novos PEV, utilizando Tecnologia da Geoinformação para representar os elementos geográficos e aplicar análises espaciais no apoio a tomada de decisão, obteve bons resultados e conseguiu alcançar uma cobertura de mais de 80%. / In Brazil, the National Solid Waste Policy (PNRS) addresses alternatives to improve the management of urban solid waste, one of which is to establish the implementation of recycling programs. Many municipalities face challenges in adapting the conventional collection model to the selective collection mode. Faced with this difficulty, this research aimed to propose a methodology for the definition of the location of points for the installation of containers of storage of recyclable materials, known as VDP - Voluntary Delivery Points, applying Geoinformation Technologies. Starting from the hypothesis that, by adopting the installation of VDP in areas closer to the residences, the population will intensify its participation in the separation and storage of recyclable materials. The methodology consisted: at characterization of the most suitable areas for the installation of the VDP, in the estimation of the distribution of the points by means of the number of points required for each neighborhood and in the distance analysis from a routing algorithm. The first step of the methodology was the creation of a Spatial Data Model for the representation of the geographical elements applied to the localization problem and its implementation in a Database Management System. The second stage was the definition of the areas of squares, parks and some commercial establishments as being the most suitable areas for the installation of the VDP. The third step was to calculate the amount of VDP needed for each neighborhood that took into account an estimate of potentially recyclable waste collected weekly. The fourth step consisted in the generation of a topological network and in the execution of the Dijkstra routing algorithm to calculate the shortest distance between the residences and the propitious areas for the installation of VDP. As a result of the research, 34 VDP were distributed in the 23 neighborhoods of the central zone, urban area of the city of Teresina. The research allowed to observe that the location proposal for the installation of VDP, using Geoinformation Technology to represent the geographic elements and to apply spatial analysis to support decision making, reached a coverage of more than 80% of the study area.

Submitted by Pedro Barros (pedro.silvabarros@ufpe.br) on 2018-06-26T22:34:30Z No. of bitstreams: 2 license_rdf: 811 bytes, checksum: e39d27027a6cc9cb039ad269a5db8e34 (MD5) DISSERTAÇÃO Ademir Oliveira Santos.pdf: 1332774 bytes, checksum: 97f3be79d5e03e57a8eebe8183f21e2d (MD5) / Made available in DSpace on 2018-06-26T22:34:30Z (GMT). No. of bitstreams: 2 license_rdf: 811 bytes, checksum: e39d27027a6cc9cb039ad269a5db8e34 (MD5) DISSERTAÇÃO Ademir Oliveira Santos.pdf: 1332774 bytes, checksum: 97f3be79d5e03e57a8eebe8183f21e2d (MD5) Previous issue date: 2017-02-21 / CAPES / O problema de roteamento de veículos tem grande importância dentro da logística e cadeia de suprimentos, pois tem como finalidade o desenho de rotas ótimas para ser usado por uma frota de veículos destinados a atender a um conjunto de clientes com o menor custo possível. O objetivo deste trabalho é desenvolver e aplicar o problema de roteamento de veículos com janelas de tempo envolvendo questões ambientais, atividades de manutenção preventiva e algumas restrições relativas à jornada de trabalho do condutor (ECOPRVMP) no contexto de uma empresa nacional que atua no transporte graneleiro. Para tanto, foram desenvolvidos dois modelos de Programação Linear Inteira Mista. O modelo ECOPRVPM 1 proposto é implementado e aplicado em um exemplo disponibilizado na literatura, de forma a permitir sua validação. Em seguida, o modelo ECOPRVMP 2 é testado em um exemplo real, no contexto de transporte logístico de grãos no Centro-Oeste brasileiro. Os modelos matemáticos são resolvidos de forma exata por meio de uma ferramenta que aplica o método Branch-and-Cut. Além da ordem de visitação dos fornecedores / clientes por cada veículo, sabe-se em que trechos devem ser realizadas atividades de manutenção preventiva, respeitando-se os intervalos previamente definidos (por exemplo, estabelecidos pelo fabricante dos veículos). Ainda, as rotas encontradas minimizam o custo com emissões e atendem a restrições da jornada do condutor. Dessa maneira, os resultados computacionais obtidos para os testes realizados mostram a consistência dos modelos propostos de roteamento de veículos apresentados, que são mais abrangentes sob a perspectiva da sustentabilidade do que os tradicionalmente utilizados. / The vehicle routing problem has great importance within the logistics and supply chain, as it aims at designing optimal routes to be used by a fleet of vehicles that has to meet a set of customers at the lowest possible cost. The objective of this work is to develop and apply the vehicle routing problem with time windows involving environmental issues, preventive maintenance activities and some restrictions related to the driver's hours of service regulations (ECOPRVMP) in the context of a national company that operates in bulk transportation. Therefore, two models of Mixed-Integer Linear Programming are developed. The proposed ECOPRVPM 1 model is implemented and applied to an example provided in the literature, in order to allow its validation. Next, the ECOPRVMP 2 model is tested in a real example, in the context of logistic grain transport in the Brazilian Midwest. The mathematical models are exatly solved by means of a tool that applies the Branch-and-Cut method. In addition to the order of visitation of suppliers / customers by each vehicle, the solution provides in what parts of the route preventive maintenance activities should be carried out, respecting the intervals previously defined (for example, established by the vehicle manufacturer). Yet, the routes minimize the cost of emissions and meet constraints of the driver's hours of service regulations. Thus, the computational results obtained for the tests performed show the consistency of the proposed vehicle routing proposed models, which are more comprehensive under the perspective of sustainability than those traditionally used.

Orientador: Flávio Keidi Miyazawa / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-16T14:13:04Z (GMT). No. of bitstreams: 1 Azevedo_BrunoLuisPiresde_M.pdf: 1384772 bytes, checksum: 48aa7ca2380aaa03fd6375cb9b35aebc (MD5) Previous issue date: 2009 / Resumo: Nesta dissertação apresentamos um algoritmo exato para o Problema de Roteamento de Veículos Capacitados com Restrições Bidimensionais. Este combina o problema de carregar um conjunto de itens bidimensionais em veículos com o problema de minimizar o custo total de transporte. Existem várias aplicações práticas para este problema, dado que em muitas situações os itens não podem ser empilhados por diversas razões. Propomos um algoritmo exato baseado em uma abordagem branch-and-cut. Sete desigualdades válidas para o Problema de Roteamento de Veículos Capacitados foram adaptadas e utilizadas. As restrições de empacotamento são garantidas através de um algoritmo exato. Também apresentamos uma nova heurística de empacotamento bidimensional. Exploramos duas variantes do problema, as versões seqüencial e irrestrita. Para ambos os casos, consideramos os itens possuirem orientação fixa. Efetuamos testes computacionais e comparamos os resultados obtidos com a abordagem exata, para o caso seqüencial, apresentada por Iori, Salazar-González e Vigo. Observamos resultados satisfatórios e nove instâncias da literatura foram resolvidas à otimalidade pela primeira vez. Como o caso irrestrito ainda não havia sido abordado de modo exato, apresentamos também as soluções de cinqüenta instâncias nunca resolvidas à otimalidade / Abstract: We present an exact algorithm for the Vehicle Routing Problem with Two-dimensional Loading Constraints. This problem combines the problems of loading vehicles with two-dimensional items and minimizing transportation costs. It has many practical applications, since in many cases items can not be stacked on top of each other. We propose an exact algorithmbased on a branch-and-cut approach. Seven valid inequalities for the the Capacitated Vehicle Routing Problems were modified and used. The packing constraints are imposed by an exact algorithm. We also present a new heuristic for two-dimensional packing. We explored two variants of the problem, the sequential and the unrestricted cases. For both variants we assume the items to have fixed orientation. We performed computational tests and compared the results with the exact approach by Iori, Salazar-González and Vigo for the sequential case. We found the results to be satisfactory and nine instances from the literature were solved to optimality for the first time. Since the unrestricted case haven't been tested so far by an exact algorithm, we also present the solutions for fifty instances never solved to optimality before / Mestrado / Teoria da Computação / Mestre em Ciência da Computação

Submitted by Alex Sandro R?go (alex@ifpb.edu.br) on 2016-09-01T13:13:28Z No. of bitstreams: 1 Roteamento_Multicrit?rio_em_Redes_?pticas_El?sticas_Din?micas.pdf: 8307684 bytes, checksum: 3263d912f9c96f9db995812743d57cdc (MD5) / Approved for entry into archive by Alex Sandro R?go (alex@ifpb.edu.br) on 2016-09-01T13:13:52Z (GMT) No. of bitstreams: 1 Roteamento_Multicrit?rio_em_Redes_?pticas_El?sticas_Din?micas.pdf: 8307684 bytes, checksum: 3263d912f9c96f9db995812743d57cdc (MD5) / Made available in DSpace on 2016-09-01T13:13:52Z (GMT). No. of bitstreams: 1 Roteamento_Multicrit?rio_em_Redes_?pticas_El?sticas_Din?micas.pdf: 8307684 bytes, checksum: 3263d912f9c96f9db995812743d57cdc (MD5) Previous issue date: 2014-07 / As redes ?pticas de n?cleo s?o respons?veis pelo transporte de um tr?fego com taxas de bits vari?veis, gerado por servi?os distintos. Esse tr?fego ir? aumentar consideravelmente ? curto prazo, e as redes ?pticas de n?cleo ter?o de ser capazes de fornecer largura de banda para dar suporte a esse aumento. V?rios estudos em diversas ?reas j? est?o sendo realizados para a implementa??o de uma rede flex?vel que aumentar? a efici?ncia do espectro ?ptico. Entre as ?reas em desenvolvimento, pode-se destacar os algoritmos de roteamento, pela import?ncia destes algoritmos na implementa??o de uma rede ?ptica eficiente. O roteamento em redes ?pticas ? considerado um problema complexo, devido a diversos fatores que podem influenciar a escolha desta rota, diminuindo a efici?ncia das redes. Nesse contexto, h? uma necessidade de evolu??o das t?cnicas de roteamento que definem a m?trica utilizada para a escolha da rota. Uma solu??o vi?vel para diminuir essa complexidade ? o uso de abordagens que utilizam v?rios crit?rios para definir essa m?trica. O objetivo desta Disserta??o ? propor um m?todo para obten??o de uma m?trica para ser utilizado em t?cnicas de roteamento para redes ?pticas el?sticas din?micas. Utilizase para isso duas abordagens multicrit?rio: Teoria da Utilidade Multiatributo e l?gica Fuzzy. Para a defini??o dessa m?trica s?o utilizados os crit?rios, n?mero de enlaces na rota e quantidade de espa?o dispon?vel no espectro. Para comparar o roteamento utilizando a m?trica multicrit?rio, com as t?cnicas de roteamento tradicionais, s?o apresentados resultados de simula??es realizadas em tr?s topologias de redes distintas: NSFNET, Torus e Anel. Estes resultados s?o comparados com o algoritmo de caminho mais curto, Dijkstra, utilizando como m?trica a quantidade de enlaces na rota. Al?m disso, o desempenho da abordagem multicrit?rio Teoria da Utilidade Multiatributo ? analisado tamb?m pela varia??o dos pesos atribu?dos a cada crit?rio. Na abordagem da l?gica Fuzzy, ? utilizado o m?todo de Mamdani para a modelagem matem?tica que define como ? calculado o custo da rota. Os resultados das simula??es foram analisados para avaliar o impacto dos sistemas no desempenho das redes, estas simula??es mostram que uma abordagem multicrit?rio pode ser mais eficiente do que algoritmos que utilizam um ?nico crit?rio. Esta Disserta??o busca mostrar que o desempenho satisfat?rio de um algoritmo de roteamento utilizando como m?trica uma abordagem multicrit?rio, principalmente para redes ?pticas el?sticas, depende de v?rios fatores como o tipo de topologia da rede, o tr?fego e principalmente os crit?rios selecionados para implementa??o da t?cnica para escolha da rota, que satisfa?a a necessidade de um roteamento eficiente em redes ?pticas.