Fornecedores necessitam atender a demanda de seus clientes da forma mais adequada possível e mantendo a qualidade de seu serviço, porém em muitos casos essa demanda é desconhecida. Esse problema pode ser modelado como um problema de roteirização e estoque com demanda estocástica o qual inclui o controle de estoque, transporte do produto e decisões de agendamento da entrega. Existem vários trabalhos na literatura para resolver esse problema, porém nenhum deles lida com janela de tempo de atendimento, capacidade máxima de estoque tanto no cliente quanto no depósito e o nível de confiança de atendimento individualizado para cada cliente. O objetivo principal deste trabalho é propor um novo algoritmo baseado em otimização matemática para lidar com esse problema mais realista. Além disso, este trabalho tem como objetivo secundário melhorar o algoritmo de estado da arte baseado em otimização matemática, visando encontrar soluções com um menor tempo computacional e custo. Foram realizados experimentos com instâncias sintéticas com 15 até 50 clientes, as quais são geradas aleatoriamente, e com uma instância real, baseada na experiência profissional no mercado empresarial e em cenários reais de distribuição na cidade de São Paulo / Providers need to supply the demand of their clients as optimally as possible and maintaining the quality of their service, however in many cases this demand is unknown. This problem can be modeled as a inventory routing problem with stochastic demand, which includes inventory control, product transportation and delivery scheduling decisions. There are several papers in the literature to solve this problem, but none of them deals with service time window, maximum stock capacity for both the customer and the depot and individualized confidence level for each costumer. The main objective of this work is to propose a new algorithm based on mathematical optimization to deal with this more realistic problem. In addition, this work has as secondary objective to improve the state of the art algorithm based on mathematical optimization, aiming to find solutions with a lower computational time and cost. Experiments were performed with synthetic instances with 15 to 50 clients, which are randomly generated, and with a real instance, based on professional experience in the business market and in real distribution scenarios in the city of São Paulo

Este trabalho apresenta uma análise sobre a Arquitetutra PCE (Path Computation Element), como alternativa para o roteamento inter-domínios em redes heterogêneas, ou seja, em ambientes onde ocorre a integração do domínio óptico, das redes de transporte ópticas, com o domínio eletrônico, das redes convencionais, tratando inclusive com questões de qualidade de transmissão do sinal óptico, ou QoT (Quality of Transmission). Os objetivos e o funcionamento do mecanismo do PCE em redes integradas são detalhados. São apresentados também os conceitos e definições das redes ópticas, bem como seus principais elementos, a proposta de interconexão das mesmas com as redes convencionais provendo uma rede única e integrada, o papel dos planos de controle, e os principais mecanismos de roteamento. A análise do PCE foi direcionada para o comportamento do principal protocolo utilizado na sua arquitetura, denominado PCE Protocol. De forma mais específica, foi realizada a análise de suas mensagens de requisição de rotas e das mensagens de respostas a estas requisições, e sua interferência no tráfego dos enlaces das redes onde são introduzidas. A partir daí é apresentada uma proposta de extensão de parâmetros para o protocolo PCE Protocol, com o objetivo de atender necessidades específicas de QoT, baseado em estudos das particularidades das características das transmissões ópticas. A partir destas definições, foram realizadas análises adicionais a fim de verificar o impacto com relação ao tráfego gerado em enlaces de diferentes larguras de banda, com a definição original do protocolo, e com a extensão proposta, permitindo uma comparação entre ambos. / This thesis presents an analysis of Path Computation Element Architecture (PCE) as an alternative to be implemented in heterogeneous network inter-domain routing, in other words, environments where optical domains are integrated with the electronic domains of conventional networks. Also, the ability of PCE to manage issues regarding the transmission quality of the optical signal, the QoT (Quality of Transmission), is presented. Objectives and functionality of the PCE mechanism in integrated networks is detailed. Concepts and definitions regarding optical networks and their main elements, the aim of interconnection with conventional networks to build a unified and integrated network, the role of control planes, and the main routing mechanisms are also presented. The analysis of the PCE was focused on the behavior of its main protocol, called PCE Protocol. Specifically, the analysis was performed on both its request and response messages, in addition, the interference in the traffic of the links where these messages had been introduced was also analyzed. Afterwards, an extension of the PCE Protocol parameters was proposed based on the study of optical transmission characteristics, with the aim of meeting specific QoT requirements. From these definitions, further analyses of the impact on the traffic in links with different bandwidths were performed, using the PCE protocol, with and without the proposed extension, allowing a comparison between them.

Este trabalho estuda a implementação do sistema de Quorum associado ao algoritmo epidêmico Gossip, a implementação de um novo algoritmo de economia de energia - o PWSave - e o protocolo de roteamento AODV em um cenário com e sem falhas de uma rede ad hoc com mobilidade. Optou-se por implementar este trabalho em um ambiente de simulação, dado que a modelagem matemática da associação do Gossip, Quorum e PWSave com os 80 nós - quantidade de nós escolhida para o ambiente de simulação - apresentaria maior complexidade e demora ao abranger todas as variáveis de ambiente desse conjunto de soluções para cada nó presente na rede. A rotina de programação - com o uso de loops para os trabalhos repetitivos - presente no ambiente de simulação permite que os experimentos sejam efetuados mais rapidamente e com menor probabilidade de erros. Os estudos [1], [2] demonstraram, respectivamente, que soluções abrangendo o algoritmo epidêmico Gossip e o sistema de compartilhamento de dados Quorum apresentam resultados favoráveis para uma rede ad hoc com alta mobilidade. Em [1] é apresentado um cenário muito próximo ao implementado neste trabalho, com a utilização do algoritmo Gossip ao protocolo de roteamento Ad-Hoc On-Demand Distance Vector (AODV). Os parâmetros analisados foram os mesmos, a saber: routes requests (RREQ), perda de pacote, vazão e latência. Os resultados do cenário simulado mostram uma diminuição no número de RREQs em uma rede ad hoc, e os demais parâmetros, medidos no ambiente de simulação, são pouco afetados. De acordo com [2] constata-se que há um aumento da resiliência e da vazão da rede e uma menor sobrecarga causada pela distribuição da informação na rede ad hoc pelo sistema de Quorum. A associação do algoritmo Gossip com o sistema de Quorum resultou em uma diminuição considerável de RREQs e perda de pacotes, mas o parâmetro de consumo de energia, que deve ser um fator importante em uma rede ad hoc e/ou uma rede sensor, não apresentou nenhuma melhora. Portanto, foi implementada uma solução adicional ao Gossip e ao Quorum, com o desenvolvimento de um novo algoritmo de economia de energia denominado de PWSave, no simulador Glomosim com o protocolo de roteamento AODV. O PWSave é responsável pelo adormecimento dos nós da rede que não estejam processando informações, ou seja, os nós, no momento do adormecimento, não poderão trocar dados ou auxiliar na formação de rotas da rede. O PWSave associado ao Gossip e ao sistema de Quorum apresenta resultados que refletem ma diminuição no consumo de energia próxima a 10% em comparação com a solução da associação do Gossip com o sistema de Quorum sem a implementação de PWSave. Os resultados da simulação mostram que a associação de Gossip, Quorum e PWSave acarreta uma redução no número de RREQs e na taxa de perda de pacotes sem degradar muito características de fluxo e latência, além de propiciar uma considerável economia no consumo de energia. / This work studies the implementation of the Quorum system associated with the Gossip algorithm, the implementation of a new power saving algorithm - the PWSave - and the routing protocol AODV in a scenario with and without failures of an ad hoc network with mobility. It has been chosen to implement this work in an environment of simulation, because the mathematical modeling of the association of Gossip, Quorum and PWSave with 80 nodes - number of nodes that has been chosen for the simulation environment - would present a higher complexity and delay to address all environment variables of the solutions set for each node present in the network. The programming routine - with the use of loops for the repetitive works - present in the simulation environment allows the experiments to be performed faster and with less probability of errors. The studies [1], [2] have shown, respectively, that solutions covering the Gossip epidemic algorithm and the system for sharing data Quorum show favorable results for an ad hoc network with high mobility. In [1] is presented a scenario very close to that implemented in this work, using the Gossip algorithm associated to the routing protocol Ad-Hoc On-Demand Distance Vector (AODV). The parameters analyzed were the same: routes requests (RREQ), packet loss, throughput and latency. The simulated scenario results show a decrease in the number of RREQs in an ad hoc network, and the other parameters, measured in the simulation environment, are little afected. According to [2] it is noted that there is an increase in the resilience and throughput of the network and a lower overload caused by the distribution of the information in the ad hoc network by the Quorum system. The association of the Gossip algorithm with the Quorum system resulted in a considerable decrease of RREQs and packet loss, but the parameter of energy consumption, which is an important factor in an ad hoc network and/or a sensor network, shows no improvement. Therefore, an additional solution was associated to the Gossip and to the Quorum, with the development of a new power saving algorithm named PWSave, in the simulator Glomosim with the routing protocol AODV. The PWSave is responsable for the sleeping state of the network nodes when they are not processing information: the nodes at the time of sleep cannot exchange data or assist in the building of network routes. The PWSave associated with the Gossip and Quorum system provides a decrease of the energy consumption close to 10% compared to the association solution of the Gossip with the Quorum system without the PWSave implementation. The results of simulation show that the association of the Gossip, Quorum and PWSave produces a reduction in the number of RREQs and in the rate of packets loss without degrading much the throughput and latency characteristics, providing a considerable energy consumption economy.

Este trabalho foi motivado pela necessidade de otimização nos serviços de entregas urbanas combinados com o alto custo de implantação e customização da maioria dos pacotes disponíveis comercialmente, que muitas empresas se defrontam, na expectativa de obtenção de respostas rápidas e eficientes, numa base diária. Geralmente a utilização destes software requerem grandes investimentos de tempo e recursos. Os custos operacionais do transporte de cargas têm experimentado um aumento expressivo devido a fatores que, de uma forma ou de outra, impedem o fluxo eficiente dos veículos na rede, tomando evidente a necessidade de ferramentas flexíveis e efetivas. Vários estudos encontrados na literatura revelaram que fatores como restrições de circulação e velocidades nos arcos têm contribuído para aumentar distâncias de percursos e a frota de veículos. Geralmente, estas rotas são planejadas de forma simplificada, utilizando um fator de correção, que fornece uma solução aproximada. Um SIG foi objeto de estudo na operação de entregas urbanas, de forma a atingir os objetivos deste trabalho. O estudo de caso abordou os serviços de entregas de bebidas na cidade de São Carlos, onde foi aplicada a heurística de economias de Clarke & Wright implementadas no software TransCAD 3.2. Foram feitas diversas simulações, comparando os resultados das distâncias em rede com os valores das distâncias estimadas, como também com as distâncias percorridas pela empresa distribuidora. / This research was motivated by the necessity of optimization of urban delivery services and the high cost of implementation and customization of most routing packages commercially available. Moreover, the companies expect to obtain fast and efficient answers on a daily base. The use of some routing software generally requires significant investments of time and other resources. The operational costs of freight transport have had a remarkable increase due to factors which somehow restraint the efficient flow of the vehicles in a network, leading to the need of flexible and effective tools. Several studies in the literature have revealed that factors such as restrictions of circulation and speed on network contribute to increase the travel distances and the fleet size. Generally, these routes are planned in a simplified way, using a correction factor to get an approximated solution. This research has considered the use of Geographical Information Systems as a tool to achieve better results for routing delivery services. The case study was the delivery service of beverages in the city of São Carlos. The Clarke & Wright\'s heuristic of economies was irnplemented in the TransCAD 3.2 software. Several simulations were carried out, comparing the results of route length, considering network and estimated distances, as well as the real one traveled by the delivery company\'s vehicles.

[pt] O Capacitated Vehicle Routing Problems (CVRP) é uma versão seminal do problema de roteamento de veículos, um clássico problema em Pesquisa Operacional. Introduzido por Dantzig e Ramser, o CVRP generaliza o Traveling Salesman Problem (TSP) e o Bin Packing Problem (BPP). Problemas de roteamento aparecem em diversas aplicações no mundo real, geralmente no contexto de diminuição de custos, emissão de poluentes ou energia dentro das atividades relacionadas ao transporte. De fato, estes custos podem ficar entre 5 por cento e 20 por cento do custo total do produto. Por isto, qualquer economia nos custos de roteamento pode ser relevante. O CVRP é definido da seguinte maneira: dado um conjunto de n mais 1 localidades - um depósito e n clientes - as distâncias entre cada par de localidades, as demandas inteiras associadas a cada cliente e a capacidade do veículo, quer se obter um conjunto de rotas que comecem no depósito, visitem cada cliente apenas uma vez e retornem ao depósito. A distâncias percorrida deve ser mínima e a soma das demandas dos clientes presentes em cada rota não pode exceder a capacidade do veículo. Este trabalho considera que o número de veículos disponíveis é conhecido. Algoritmos no estado da arte para encontrar e provar que uma solução é ótima, para o CVRP, calculam seus limites inferiores através de geração de colunas e depois os melhoram com a adição de planos de corte. As colunas geradas podem ser rotas elementares, onde obrigatoriamente cada cliente é visitado somente uma vez, ou uma relaxação desta obrigação com o uso de q-rotas ou ng-rotas, que diferem apenas em como é permitido que um cliente seja revisitado dentro de uma mesma rota. Já os cortes são classificados como robustos, aquele que são definidos sobre as variáveis dos arcos, e não robustos (ou fortes), que são os definidos sobre as variáveis do problema mestre da geração de colunas. O termo robusto, usado acima, se refere a como a adição do corte modifica a eficiência da resolução do problema de pricing. Além do descrito acima, o algoritmo exato mais eficiente para o CVRP usa muitos elementos, o que torna sua replicação uma tarefa difícil e longa. O objetivo deste trabalho é determinar o quão bom são os limites inferiores obtidos com geração de colunas de ng-rotas usando apenas cortes de capacidade e os recentes subset row cuts de memória limitada. Além disto, é avaliado o ganho conseguido com a consideração deste tipo de corte forte e as combinações com outras técnicas, como por exemplo, Decremental Space State Relaxation (DSSR), Completion Bounds, ng-rotas e cortes de capacidade sobre a formulação de Set Partitioning. Extensos experimentos computacionais são apresentados em conjunto com a análise dos resultados obtidos. / [en] The Capacitated Vehicle Routing Problem (CVRP) is the seminal version of the vehicle routing problem, a classical problem in Operational Research. Introduced by Dantzig e Ramser, the CVRP generalizes the Traveling Salesman Problem (TSP) and the Bin Packing Problem (BPP). In addition, routing problems arise in several real world applications, often in the context of reducing costs, polluent emissions or energy within transportation activities. In fact, the cost with transportation can be roughly estimated to represent 5 per cent to 20 per cent of the overall cost of a delivered product. This means that any saving in routing can be much relevant. The CVRP is stated as follows: given a set of n plus 1 locations - a depot and n customers - the distances between every pair of locations, integer demands associated with each customer, and a vehicle capacity, we are interested in determining the set of routes that start at the depot, visits each customer exactly once and returns to the depot. The total distance traveled by the routes should be minimized and the sum of the demands of customers on each route should not exceed the vehicle capacity. This work considers that the number of available vehicles is given. State of the art algorithms for finding and proving optimal solutions for the CVRP compute their lower bounds through column generation and improving it by adding cutting planes. The columns generated may be elementary routes, where customers are visited only once, or relaxations such as q-routes and the more recent ng-routes, which differ on how they allow repeating customers along the routes. Cuts may be classified as robust, those that are defined over arc variables, and non-robust (or strong), those that are defined over the column generation master problem variables. The term robust used above refers to how adding the cut modifies the efficiency of solving the pricing problem. Besides the description above, the most efficient exact algorithms for the CVRP use too many elements turning its replication a hard long task. The objective of this work is to determine how good can be lower bounds computed by a column generation algorithm on ng-routes using only capacity cuts and a family of strong cuts, the limited memory subset row cuts. We assess the leverage achieved with the consideration of this kind of strong cuts and its combination with others techniques like Decremental Space State Relaxation (DSSR), Completion Bounds, ng-Routes and Capacity Cuts over a Set Partitioning formulation of the problem. Extensive computational experiments are presented along with an analysis of the results obtained.

Submitted by Maykon Nascimento (maykon.albani@hotmail.com) on 2015-08-03T18:18:50Z No. of bitstreams: 2 license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Roteamento sensível ao contexto em redes de sensores sem fio. Uma abordagem baseada em regras de aplicação para o protocolo RPL.pdf: 1746170 bytes, checksum: 7293ea85d09a8c011b6f38ae51b024de (MD5) / Approved for entry into archive by Elizabete Silva (elizabete.silva@ufes.br) on 2015-08-17T19:10:23Z (GMT) No. of bitstreams: 2 license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Roteamento sensível ao contexto em redes de sensores sem fio. Uma abordagem baseada em regras de aplicação para o protocolo RPL.pdf: 1746170 bytes, checksum: 7293ea85d09a8c011b6f38ae51b024de (MD5) / Made available in DSpace on 2015-08-17T19:10:23Z (GMT). No. of bitstreams: 2 license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Roteamento sensível ao contexto em redes de sensores sem fio. Uma abordagem baseada em regras de aplicação para o protocolo RPL.pdf: 1746170 bytes, checksum: 7293ea85d09a8c011b6f38ae51b024de (MD5) Previous issue date: 2015 / Este trabalho apresenta um serviço de reconfiguração dinâmica para Redes de Sensores sem Fio. O trabalho inclui o projeto e a definição de uma arquitetura conceitual que suporta a coleta de uma variedade de informações contextuais e provê uma abstração alto nível para especificação de roteamento sensível ao contexto através de reconfiguração de métricas de roteamento e parâmetros de comunicação. O objetivo da infraestrutura proposta é possibilitar a criação de regras que adaptem o comportamento da rede em tempo de execução, em função dessas informações contextuais. Uma implementação da arquitetura para o protocolo RPL e o sistema operacional Contiki foi realizada, mostrando a viabilidade da abordagem proposta. / This work presents a dynamic reconfiguration service for wireless sensor networks. The work includes the design and definition of a conceptual architecture that supports collecting a variety of contextual information and provides a high level abstraction for context-sensitive routing specification through reconfiguration of routing metrics and communication parameters. The objective of the proposed infrastructure is enabling the creation of rules that change the network's behavior at run time, in the light of these contextual information. An implementation of the architecture for the RPL Protocol and the Contiki operating system was performed, showing the feasibility of the proposed approach.

Submitted by Elizabete Silva (elizabete.silva@ufes.br) on 2015-10-02T19:38:15Z No. of bitstreams: 2 license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) PLANEJAMENTO DA LOGÍSTICA DE SUPRIMENTO DE PLATAFORMAS OFFSHORE POR MEIO DE UM MODELO MATEMÁTICO 2L-CVRP COM FROTA HETEROGÊNEA E EQUILÍBRIO NÁUTICO.pdf: 4092400 bytes, checksum: 2f3e443433630154f11373b75d34eaa9 (MD5) / Approved for entry into archive by Morgana Andrade (morgana.andrade@ufes.br) on 2016-01-07T14:51:32Z (GMT) No. of bitstreams: 2 license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) PLANEJAMENTO DA LOGÍSTICA DE SUPRIMENTO DE PLATAFORMAS OFFSHORE POR MEIO DE UM MODELO MATEMÁTICO 2L-CVRP COM FROTA HETEROGÊNEA E EQUILÍBRIO NÁUTICO.pdf: 4092400 bytes, checksum: 2f3e443433630154f11373b75d34eaa9 (MD5) / Made available in DSpace on 2016-01-07T14:51:32Z (GMT). No. of bitstreams: 2 license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) PLANEJAMENTO DA LOGÍSTICA DE SUPRIMENTO DE PLATAFORMAS OFFSHORE POR MEIO DE UM MODELO MATEMÁTICO 2L-CVRP COM FROTA HETEROGÊNEA E EQUILÍBRIO NÁUTICO.pdf: 4092400 bytes, checksum: 2f3e443433630154f11373b75d34eaa9 (MD5) Previous issue date: 2015 / CAPES / O petróleo é um importante recurso no mundo atual e sua exploração no Brasil se baseia, sobretudo, na exploração em águas profundas, para a qual são implantadas plataformas offshore. Como estas plataformas estão distantes da costa brasileira e isoladas, é fundamental planejar a logística de suprimento, que inclui, entre outros elementos, as embarcações de apoio offshore, as quais são responsáveis por abastecer as plataformas e constituem um recurso caro. Nos sistemas logísticos, é essencial planejar e gerenciar as atividades de transportes de cargas, pois os custos relativos ao transporte representam uma grande parcela dos custos logísticos totais. Portanto, no contexto analisado, é importante minimizar os custos de transporte por meio de um eficiente planejamento dos navios de suprimento. Nesse sentido, há dois aspectos centrais na gestão de distribuição logística: problemas de roteamento de veículos, usados para determinar a rota ótima, e problemas de carregamento, usados para definir a melhor maneira de carregar mercadorias dentro dos veículos utilizados no transporte. Visando a criação de rotas e a arrumação bidimensional de cargas, foi proposto na literatura o Problema de Roteamento de Veículos Capacitados com Restrições de Carregamento Bidimensional (Capacitated Vehicle Routing Problem with Two-dimensional Loading Constraints – 2L-CVRP). Esta dissertação tem por objetivo propor um modelo matemático de Programação Linear Inteira Mista baseado no 2L-CVRP aplicado ao planejamento da logística de suprimento de plataformas offshore para criar rotas considerando o equilíbrio náutico e a melhor arrumação das cargas no convés, denominado Weight Balance Two-Dimensional Loading Heterogeneous Fleet Vehicle Routing Problem (WB2L-HFVRP). Este modelo se diferencia por considerar frota heterogênea e utilizar uma função objetivo que visa minimizar o número de navios, a distância navegada e a diferença entre os pesos distribuídos entre os bordos do navio. Testes em instâncias baseadas em dados reais da Petrobras foram feitos no CPLEX 12.6 e mostraram uma redução de até 25% em relação à distância real navegada. / Oil is an important resource in today's world and its exploitation in Brazil is based mainly on deepwater exploration, for which offshore platforms are deployed. As these platforms are isolated and distant from the Brazilian coast, it is essential to plan the supply logistics, which includes, among other elements, the offshore support vessels, which are responsible for supplying the platforms and are an expensive resource. On logistics systems, is essential to plan and manage the activities of freight transport, because the transport costs represent a large portion of total logistics costs. Therefore, in the analyzed context, it is important to minimize transportation costs through efficient planning of the supply vessel. In this sense, there are two central aspects in the management of logistics distribution: Vehicle Routing Problems, used to determine the optimal route, and Loading Problems, used to define the best way of carrying goods in vehicles used for transport. Aiming to create routes and the two-dimensional storage of cargo, has been proposed in the literature the Capacitated Vehicle Routing Problem with Two-dimensional Loading Constraints (2L-CVRP). This essay aims to propose a mathematical model of Mixed Integer Linear Programming based on 2L-CVRP applied to planning the supply logistics of offshore platforms to create routes considering the nautical balance and better storage of cargo on deck, named Weight Balance Two-Dimensional Loading Heterogeneous Fleet Vehicle Routing Problem (WB2L-HFVRP). This model differs from other models because it considers heterogeneous fleet and uses a objective function that aims to minimize the number of ships, sailed distance, and the difference between the weights distributed between the sides of the ship, the nautical balance. Tests on instances based on real data from Petrobras were made in CPLEX 12.6 and showed a reduction of up to 25% compared to the actual sailed distance.

O aumento da capacidade dos Sistemas sobre Silício (SoCs do inglês, Systemon-Chip) tem levado Redes Intrachip (NoCs do inglês, Network on-Chip) a serem utilizadas como interface de comunicação de Módulos de Processamento de sistemas complexos, e particularmente em Sistemas Dinamicamente Reconguráveis a serem implementados sobre FPGAs com capacidade de reconguração parcial. Algumas estratégias de reconguração geram cenários com NoCs irregulares e indiretas, fato que força o sistema a atualizar o seu algoritmo de roteamento afim de se evitar problemas de comunicação de dados, como deadlock e livelock. O presente trabalho apresenta uma NoC Dinamicamente Recongurável (DRNoC do inglês, Dynamically Recongurable Newtwork on-Chip) utilizando o Algoritmo de Roteamento Ordenado por Dimensão Flexibilizado (FDOR do inglês, Flexible Dimension Order Routing) que se caracteriza principalmente sua simplicidade, baixa complexidade e ser livre de deadlock. No presente trabalho, foi implementada a ferramenta DRSimGen, que gera código VHDL da arquitetura da NoC associada, para ser utilizado com aplicações específicas com reconfiguração parcial dinâmica que requeiram comunicações paralelas entre seus módulos de processamento. Esta ferramenta gera os roteadores, módulos de processamento, além de um Sistema de Controle de Reconguração Parcial Dinâmica que pode ser utilizado junto com o Sistema de Reconguração do algoritmo de roteamento baseado em FDOR, já desenvolvido por outros anteriormente. A ferramenta também gera componentes de testbench para a simulação do sistema, baseados na técnica de Chaveamento Dinâmico de Circuitos; são utilizadas chaves de isolação para emularos processos de reconguração parcial dinâmica. Os resultados destes experimentos ajudaram a determinar o comportamento desejado do sistema. Também foram feitas simulações da implementação do FDOR em descrição de alto nível, com a finalidade de determinar seu desempenho na transferência de dados que ajudarão a definir o posicionamento dos módulos de processamento sobre a estrutura da rede. Os resultados dos experimentos tem demonstrado a viabilidade desta estratégia, levando à conclusão que o algoritmo FDOR é uma solução adequada para DRNoCs. / The increased capacity of Systems on-Chip (SoCs) has led Networks on-Chip (NoC) to be used as communication interface for processing modules of complex systems, and particularly in Dynamically Recongurable Systems to be implemented over partially recongurable FPGAs. Some reconguration strategies work on irregular and indirect NoCs, fact that forces the system to update its routing algorithm in order to avoid data communication problems, such as deadlockandlivelock. ThispaperpresentsaDynamicallyRecongurableNoC(DRNoC)using Flexible Dimension Order Routing Algorithm (FDOR), mainly characterized by its simplicity, low complexity and deadlock freedom In this work, the DyAFNoC tool was implemented, to generate the VHDL code of the associated NoC architecture to be used with specic applications with dynamic partial reconguration that require parallel communications between their processing modules. This tool generates routers, processing modules, and also a Partial Dynamic Reconguration Control System that can be used with the FDOR-based Reconguration System, developed elsewhere. The tool also generates testbench components for the system simulation, based on the Dynamic Circuit Switching technique that uses isolation switches to emulate the dynamic partial reconguration processes. The results of these experiments have helped to determine the desired system behavior. Simulations of the FDOR implementation were also made in high level descriptioninordertodetermineitsdatatransferperformancethatwillhelptodeneplacement of the processing modules over the network structure. The experiments results have demonstrated the feasibility of this strategy, leading to the conclusion that the FDOR algorithm is a suitable solution for DRNoC.

Submitted by Livia Mello (liviacmello@yahoo.com.br) on 2016-09-16T12:55:52Z No. of bitstreams: 1 DissAAAD.pdf: 1563807 bytes, checksum: cd9db1180896a8d853b8d7cd4c694860 (MD5) / Approved for entry into archive by Marina Freitas (marinapf@ufscar.br) on 2016-09-21T18:31:23Z (GMT) No. of bitstreams: 1 DissAAAD.pdf: 1563807 bytes, checksum: cd9db1180896a8d853b8d7cd4c694860 (MD5) / Approved for entry into archive by Marina Freitas (marinapf@ufscar.br) on 2016-09-21T18:31:28Z (GMT) No. of bitstreams: 1 DissAAAD.pdf: 1563807 bytes, checksum: cd9db1180896a8d853b8d7cd4c694860 (MD5) / Made available in DSpace on 2016-09-21T18:31:33Z (GMT). No. of bitstreams: 1 DissAAAD.pdf: 1563807 bytes, checksum: cd9db1180896a8d853b8d7cd4c694860 (MD5) Previous issue date: 2016-02-29 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / In this dissertation we address the vehicle routing problem with time windows and multiple deliverymen, a variant of the vehicle routing problem that involves the additional decision of the crew size definition of the vehicles, besides scheduling and routing decisions. This problem arises in the distribution of goods in highly congested urban areas, where due to the relatively long service times, it may be difficult to serve all clients during regular working hours. Given this difficulty, an alternative consists in including the deliverymen assignment decision, which leads to extra costs in addition to travel and vehicle costs. The objective is to define routes to serve customer clusters minimizing the number of vehicles used, the number of allocated deliverymen and the traveled distance. In this study, we develop different solution methods to solve this problem. Initially, we present two metaheuristic approaches, which are based on Iterated Local Search and Large Neighborhood Search. Then we propose hybrid methods, combining these metaheuristics with a branch-price-and-cut method. Computational experiments using instances from the literature confirm the efficiency of the solution methods developed for the problem. / Nesta dissertação aborda-se o problema de roteamento de veículos com janelas de tempo e múltiplos entregadores, uma variante do problema de roteamento de veículos recentemente proposta na literatura que, além das decisões de programação e roteamento, envolve a determinação do tamanho da tripulação de cada veículo. Esse problema surge na distribuição de bens em centros urbanos congestionados em que, devido aos tempos de serviço relativamente longos, pode ser difícil atender a todos os clientes durante o horário normal de trabalho. Diante dessa dificuldade, uma alternativa consiste em incluir a designação de entregadores extras, o que gera custos adicionais aos custos tradicionais de deslocamento e utilização de veículos. Neste problema, o objetivo é definir rotas para atender grupos de clientes minimizando o número de veículos usados, o número total de entregadores designados e a distância total percorrida. Para tratar o problema, são desenvolvidos diferentes métodos de solução. Inicialmente, são apresentadas duas abordagens metaheurísticas baseadas em Busca Local Iterada e Busca em Vizinhança Grande. Posteriormente, são propostos métodos híbridos de solução a partir da combinação dessas metaheurísticas com um método branch-price-and-cut. Experimentos computacionais usando instâncias encontradas na literatura confirmam a eficiência dos métodos de solução desenvolvidos para o problema.

Made available in DSpace on 2015-05-08T14:53:38Z (GMT). No. of bitstreams: 1 arquivototal.pdf: 3056611 bytes, checksum: e73001b52f3f37e092e742b4d599ce04 (MD5) Previous issue date: 2014-02-14 / Conselho Nacional de Desenvolvimento Científico e Tecnológico / This dissertation deals with the Pollution-Routing Problem (PRP), a Vehicle Routing Problem (VRP) with environmental considerations, recently introduced in the literature by Bekta ¸s e Laporte (2011). The objective is to minimize operational and environmental costs while respecting route-load constraints and service time windows. Costs are based on driver wages and fuel consumption, which depends on many factors, such as travel distance and vehicle load. Vehicle speeds are additional decision variables of the problem which complement routing decisions. They impact the total cost, the travel times between the locations, and thus the set of feasible routes. We propose a hybrid method that combines a local search-based metaheuristic with an exact approach and a recursive speed-optimization algorithm. Moreover, two other green VRP variants, the Fuel Consumption VRP (FCVRP) and the Energy Minimizing VRP (EMVRP), are addressed. The results obtained compare very favorably with those found in the literature, and many new improved solutions are reported. / Esta dissertação lida com o Pollution-Routing Problem (PRP), i.e. um Problema de Roteamento de Veículos (PRV) com considerações ambientais, recentemente introduzido na literatura por Bekta¸s e Laporte (2011). O objetivo consiste na minimização dos custos operacionais e ambientais, respeitando as restrições de carga dos veículos e janelas de tempo dos clientes. O custo é baseado no salário dos motoristas e no consumo de combustível, que depende de diversos fatores, como distância percorrida e carga transportada. As velocidades dos veículos são variáveis de decisão adicionais que complementam as decisões de roteamento. Tais velocidades interferem diretamente no custo total, nos tempos de viagem, bem como no conjunto de rotas viáveis. Uma abordagem híbrida que combina uma metaheurística baseada em busca local com uma abordagem exata e um algoritmo recursivo para otimizar as velocidades é proposta para solucionar o problema. Além do PRP, outras duas variantes do PRV com considerações ambientais são tratadas: o PRV considerando consumo de combustível e o PRV com minimização de energia. Os resultados obtidos se mostraram bastante favoráveis quando comparados com os melhores da literatura, e diversas soluções melhoradas são reportadas.