Esta tese estuda a implementação de heurísticas e da metaheurística scatter search (SS) em um problema de roteirização de veículos com frota heterogênea, janelas de tempo e entregas fracionadas (Heterogeneous Fleet Vehicle Routing Problem with Time Windows and Split Deliveries – HFVRPTWSD). O HFVRPTWSD é uma combinação do problema de roteirização com frota heterogênea (HFVRP), problema de roteirização de veículos com janelas de tempo (VRPTW) e problema de roteirização com entregas fracionadas (VRPSD). O problema é baseado em um único depósito, a demanda dos clientes pode ser maior que a capacidade dos veículos e, além das restrições de janelas de tempo, há também restrições de capacidade dos veículos e restrições quanto ao tipo de veículo. O VRPSD foi introduzido na literatura por Dror e Trudeau em 1989. No problema de roteirização de veículos com entregas fracionadas, cada cliente pode ser abastecido por mais de um veículo, enquanto no problema clássico de roteirização de veículos (VRP), cada cliente é atendido por um único veículo. Desta forma, para o VRPSD, além dos roteiros de entrega, deve-se determinar a quantidade entregue a cada cliente em cada veículo. Todos os problemas de roteirização com entregas fracionadas encontrados na literatura (VRPSD e suas extensões) têm como característica frota homogênea. O problema estudado neste trabalho difere, portanto, de todos os problemas de roteirização com entregas fracionadas da literatura, pois tem, como característica, frota heterogênea. O mesmo raciocínio vale para problemas de roteirização de veículos com frota heterogênea. Os modelos são aplicados em uma rede de varejo no Brasil que é abastecida a partir de um centro de distribuição. A rede compõe um total de 519 lojas distribuídas em 12 estados do país. As heurísticas e a metaheurística scatter search também são aplicadas em três conjuntos de problemas encontrados na literatura (SOLOMON, 1987; HO E HAUGLAND, 2004; LIU E SHEN, 1999), com o objetivo de avaliar o desempenho dos algoritmos para cada problema. O problema consiste em determinar, a cada dia, como alocar os caminhões às lojas, a quantidade de carga em cada caminhão a ser entregue em cada uma das lojas, qual o melhor roteiro e o tempo de início de atendimento do primeiro cliente da rota, de forma a minimizar o custo total de distribuição, garantindo que a demanda das lojas seja atendida e as demais restrições do problema sejam respeitadas. Para a resolução do VRPSD e suas extensões, a única metaheurística encontrada na literatura foi busca tabu. Para o problema de roteirização com frota heterogênea e suas extensões, foram implementadas apenas as metaheurísticas busca tabu e BATA (Back-Tracking Adaptative Threshold Accepting). As estratégias de solução propostas no presente trabalho consistem na implementação de heurísticas construtivas e da metaheurística scatter search. As soluções iniciais de SS são obtidas através da implementação de quatro heurísticas construtivas: heurística de economias, heurística de inserção seqüencial baseada nas idéias de Solomon (1987), heurística de inserção seqüencial baseada nas idéias de Ho e Haugland (2004) e adaptação da heurística de inserção seqüencial de Dullaert et al. (2002). Para o caso real, foi possível uma redução no custo total da frota comparado com a solução atual da empresa. Para algumas instâncias dos três conjuntos de problemas da literatura, os algoritmos apresentaram resultados similares ou superiores às melhores soluções encontradas. / This thesis studies the implementation of heuristics and scatter search (SS) metaheuristic in a Heterogeneous Fleet Vehicle Routing Problem with Time Windows and Split Deliveries (HFVRPTWSD). The HFVRPTWSD is a combination of Heterogeneous Fleet Vehicle Routing Problem (HFVRP), Vehicle Routing Problem with Time Windows (VRPTW) and Vehicle Routing Problem with Split Deliveries (VRPSD). The problem is based in a single depot, the demand of each client can be greater than the vehicle’s capacity and beyond the time windows constraints, and there are also constraints on the vehicle capacity and vehicles type. The VRPSD was introduced in the literature by Dror e Trudeau in 1989. In the split deliveries vehicle routing problem, each client can be supplied by more than one vehicle; while in a classic vehicle routing problem (VRP) each client is supplied by only one vehicle. Thus, for the VRPSD, besides the delivery routes, the amount to be delivered to each client in each vehicle must also be determined. All the split delivery vehicle routing problems researched in the literature (VRPSD and its extensions) have as a characteristic the homogeneous fleet. Therefore, the problem studied differs from the split deliveries vehicle routing problems of the literature because it has a heterogeneous fleet. The same reasoning can be applied in heterogeneous fleet vehicle routing problem. The models will be applied in a retail market in Brazil that is supplied by a distribution center. The market has 519 stores distributed in 12 Brazilian states. The heuristics and the scatter search metaheuristic will also be applied in three benchmark problems (SOLOMON, 1987; HO AND HAUGLAND, 2004; LIU AND SHEN, 1999), aiming to evaluate the design of the algorithms for each problem. The problem consists in determining, each day, how to allocate the trucks to the stores, the amount to be delivered in each truck to each client, which one is the best route and the initial time for attending the first client, with the aim of minimizing the total distribution cost, attending the clients’ demand and respecting all the problem’s constraints. For the VRPSD and its extensions, the only metaheuristic implemented in the literature was tabu search. For the heterogeneous fleet vehicle routing problem and its extensions, only the tabu search and BATA (Back-Tracking Adaptative Threshold Accepting) metaheuristics have been implemented. The strategies proposed here consist in the implementation of constructive heuristics and the scatter search metaheuristic. The initial solutions of SS are obtained with the implementation of four constructive heuristics: saving heuristics, sequential insertion heuristic based on the ideas of Solomon (1987), sequential insertion heuristic based on the ideas of Ho e Haugland (2004) and adaptation of the sequential insertion heuristic of Dullaert et al. (2002). For the real case, it was possible to reduce the total fleet cost, when comparing to the actual solution. At some instances of the three benchmark problems, the algorithms presented similar or better results when compared to the best solutions in the literature.

O presente trabalho trata da determinação de um roteiro ótimo de separação manual de peças em armazéns, buscando a minimização da distância total percorrida. São considerados armazéns com dois corredores transversais localizados em suas extremidades, os quais conectam todos os corredores de separação, perpendiculares aos corredores transversais e paralelos entre si. O problema abordado é prático e comum a várias empresas, com impacto nos custos operacionais e relevância para a assertividade em relação aos itens coletados. Ainda assim, o tema é pouco explorado nos estudos de roteirização disponíveis em língua portuguesa e muitas empresas optam por confiar a criação das rotas aos próprios separadores. O método escolhido é baseado em programação dinâmica e foi aplicado na roteirização de listas de separação relacionadas a subconjuntos do produto final, na roteirização de grupos aleatórios de peças, e no estudo do impacto do número de corredores de separação no comprimento das rotas, totalizando 184 experimentos. A forma de avaliação do algoritmo foi comparar as rotas por ele criadas com aquelas criadas pelos separadores. Conclui-se que quanto mais complexa for a rota, maiores serão os ganhos da seqüência de coletas proposta pelo sistema em comparação com aquelas criadas por processos subjetivos. Concluiu-se também que o número de corredores a ser visitado é o fator que mais influencia no comprimento da rota a ser percorrida. Ainda, o algoritmo é flexível e genérico para ser utilizado em qualquer armazém com dois corredores transversais, independente da política de localização ou separação adotada e, por sua facilidade de implementação e utilização, representa uma alternativa de roteirização eficiente e de baixo custo para pequenas e médias empresas. Finalmente, tem-se um algoritmo que pode ser utilizado também como ferramenta gerencial e de simulação visto que pode ser configurado para diferentes leiautes e diferentes tamanhos listas de separação. / The present work deals with the shortest route creation for a low-level pickers-to-part warehouse, intending to minimize the total traveled distance. The considered warehouse has two traversing aisles, located in its extremities, connecting all of the picking aisles and perpendicularly set in relation to them. The proposed problem is practical and common to several companies, impacting their operational costs and important for mis picking reduction. Nevertheless, that theme is little explored among routing studies in Portuguese language and several companies still opt to trust the routes to be subjectively prepared by their own pickers. The proposed solution method is based on dynamic programming and it was applied in the routing of picking lists related to subsets of final products, random groups of items, and in the study of the impact that picking aisle quantity has on the total length of the routes, totaling 184 experiments. The proposed algorithm was evaluated comparing the routes prepared by it with those created by the pickers. Results show that the more complex the route is, the higher the earnings of the algorithm utilization in relation to the subjective processes will be. Besides it shows that the number of corridors to be visited is the main influence to the length of the route. Still, the algorithm is flexible and generic to be used at any warehouse with two traverse corridors, independent of the locating police or separation strategy adopted. Furthermore the algorithm implementation easiness and use support it to be an efficient low cost routing alternative for small and average size companies.

O componente de planejamento faz parte do projeto de desenvolvimento dos veículos autônomos, e é responsável por gerar rotas para o sistema como um todo. Em aplicações em que o veículo deve visitar pontos em intervalos de tempo pré-determinados, o componente de planejamento se enquadra em um problema de roteirização conhecido da literatura, denominado problema de roteirização de veículos com janelas de tempo. Tal problema é uma generalização do problema clássico de roteirização de veículos classificado no grupo de problemas NP-Hard. Esse trabalho apresenta uma proposta de solução para o problema baseada na metaheurística algoritmo genético. Os cromossomos foram representados pela ordem de atendimento dos clientes sem delimitadores de rota. Para quebrar os cromossomos em rotas, foi utilizado um procedimento adaptado baseado em Prins (2004). A população inicial se constitui por uma parte construída com cromossomos criados aleatoriamente e outra parte construída através da heurística de inserção I1 de Solomon (1987), com quatro formas diferentes de inserir o primeiro cliente de cada rota. Na fase de recombinação, foram utilizados quatro tipos de crossover: uniforme, dois pontos, heurístico e PMX, e um operador de mutação baseado em uma busca heurística. A cada geração foram aplicados princípios de elitismo e pós-otimização utilizando a heurística -interchange de Osman (1993). O algoritmo foi testado nos conjuntos C1, C2, R1, R2, RC1 e RC2 de Solomon (1987) e os resultados foram comparados com os melhores resultados encontrados na literatura. / The planning component is a part of autonomous vehicle development project and it is responsible to generate routes for the system as a whole. In applications which vehicle must to visit way points at predetermined intervals of time, the planning component fits into a routing problem known in the literature called routing problem with time windows. This problem is a generalization of the classical vehicle routing problem classified in the group of NP- Hard problems. This thesis presents a solution proposal to problem based on genetic algorithm metaheuristic. Chromosomes were represented by the order of serving customers without delimiters route. To split the chromosomes on routes, it is used a procedure adapted based on Prins (2004). The initial population is constituted by two parts: one with randomly created chromosomes and another constructed through the insertion heuristic I1 of Solomon (1987), with four different ways of insertion of the first customer of each route. In the recombination step, four types of crossover were used: uniform, two points, heuristic, and PMX, and a mutation operator based on heuristic search. In each generation it is applied principles of elitism and postoptimization using the -interchange heuristic of Osman (1993). The algorithm was tested on the sets C1, C2, R1, R2, RC1 and RC2 of Solomon (1987) and the results were compared with the best results found in the literature.

Com o crescente aumento das funcionalidades dos circuitos integrados, existe um aumento consequente da complexidade do projeto dos mesmos. O fluxo de projeto de circuitos integrados inclui em um de seus passos o roteamento, que consiste em criar fios que interconectam as células do circuito. Devido à complexidade, o roteamento é dividido em global e detalhado. O roteamento global de circuitos VLSI é uma das tarefas mais complexas do fluxo de síntese física, sendo classificado como um problema NP-completo. Neste trabalho, além de realizar um levantamento de trabalhos que utilizam as principais técnicas de paralelismo com o objetivo de acelerar o processamento do roteamento global, foram realizadas análises nos arquivos de benchmark do ISPD 2007/08. Com base nestas análises foi proposto um método que agrupa as redes para então verificar a existência de dependência de dados em cada grupo. Esta verificação de dependência de dados, que chamamos neste trabalho de colisor, tem por objetivo, criar fluxos de redes independentes umas das outras para o processamento em paralelo, ou seja, ajudar a implementação do roteamento independente de redes. Os resultados demonstram que esta separação em grupos, aliada com a comparação concorrente dos grupos, podem reduzir em 67x o tempo de execução do colisor de redes se comparada com a versão sequencial e sem a utilização de grupos. Também foi obtido um ganho de 10x ao comparar a versão com agrupamentos sequencial com a versão paralela. / With the increasing of the functionality of integrated circuits, there is a consequent increase in the complexity of the design. The IC design flow includes the routing in one of its steps, which is to create wires that interconnect the circuit cells. Because of the complexity, routing is divided into global and detailed. The global routing of VLSI circuits is one of the most complex tasks in the flow of physical synthesis and it's classified as an NP-complete problem. In this work, a parallel computing techniques survey was applied to the VLSI global routing in order to accelerate the global routing processing analyzes. This analyzes was performed on the ISPD 2007/08 benchmark files. We proposed a method that groups the networks and then check for data dependence in each group based on these analyzes. This data dependency checking, we call this checking of collider, aims to create flow nets independent of each other for processing in parallel, or help implement the independent routing networks. The results demonstrate that this separation into groups, together with the competitor comparison of groups, can reduce 67x in the collider networks runtime compared with the sequential release and without the use of groups. It was also obtained a gain of 10x when comparing the version with sequential clusters with the parallel version.

Submitted by Matheus Alves Bulhoes (matheus.bulhoes@ufpe.br) on 2015-05-12T14:36:25Z No. of bitstreams: 2 license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) Dissertação_Luis_Final.pdf: 2794061 bytes, checksum: ca38ae8cdb5e52a8b28f84163a66bc6b (MD5) / Made available in DSpace on 2015-05-12T14:36:25Z (GMT). No. of bitstreams: 2 license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) Dissertação_Luis_Final.pdf: 2794061 bytes, checksum: ca38ae8cdb5e52a8b28f84163a66bc6b (MD5) Previous issue date: 2014-08-29 / Redes emergenciais são redes móveis utilizadas em cenários de catástrofes onde os meios de transmissão convencionais estão usualmente comprometidos. Neste contexto o estabelecimento de uma MANET (Mobile Ad Hoc Network) é a solução mais indicada para suprir a comunicação entre as equipes de resgate e organizações competentes. Atualmente existe uma gama de trabalhos que, através de simulações, avaliam o desempenho de protocolos de roteamento em cenários variados, alguns de desastres. O cenário apresentado por este trabalho é específico de uma situação de desastre, similar a uma ocorrência de deslizamento de terra. Acontecimentos como esse criam um ambiente com características particulares e, o roteamento usado deveria suprir da melhor forma esses fatores únicos. Portanto, este trabalho apresentou uma hipótese que o roteamento baseado em zonas pode ser a melhor escolha para o cenário proposto. Foi desenvolvido um novo protocolo com base no já existente Zone Routing Protocol e comparado através de métricas de desempenho com os protocolos AODV e DSDV, além do próprio ZRP. Ainda, objetivando modelar uma mobilidade mais condizente com a apresentada pelas equipes de resgate, foi desenvolvida uma adaptação do "disaster mobility model" para junto com o cenário sumarizar as características únicas desse ambiente e gerar simulações mais realistas. As simulações foram feitas com uma variação do número de nós entre os cenários, e a comparação dos protocolos foi analisada pelos valores atingidos por eles nas simulações em métricas de desempenho. Os resultados mostraram que o novo protocolo foi bastante superior ao seu original em todas as métricas, atingindo também um desempenho semelhante ou melhor que o AODV e o DSDV em packet delivery ratio, end to end delay e routing overhead. Dessa forma, concluiu-se que o novo protocolo desenvolvido alcançou seu objetivo, se tornando, entre os protocolos testados, uma opção viável para roteamento em redes emergenciais críticas.

Made available in DSpace on 2014-06-12T15:52:15Z (GMT). No. of bitstreams: 1 license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5) Previous issue date: 2009 / Conselho Nacional de Desenvolvimento Científico e Tecnológico / O surgimento de interfaces de rede sem-fio de baixo custo no mercado e o crescimento na demanda por dispositivos móveis (como Smartphones, PDAs, Internet Tablets e Laptops) permitiram a criação de cenários onde serviços de rede para usuários móveis possam existir sem nenhuma infra-estrutrutura pré-configurada. No entanto, a interoperabilidade entre tais redes, que são dinâmicas e heterogêneas, é atualmente objeto de pesquisa. Várias pesquisas na área de redes ad hoc sem-fio tem focado em uma única tecnologia sem-fio, baseada no padrão IEEE 802.11, onde os nós da rede são vistos de maneira plana (2D), ou seja, como elementos homogêneos, identificados apenas por endereços IP, não levando em consideração seus perfis de hardware e tecnologias de rede. Desta forma, pesquisas envolvendo mais de uma tecnologia de rede encontram-se em estágios iniciais. Novas propostas são necessárias para estes cenários, que são cada vez mais comuns, envolvendo múltiplos dispositivos com múltiplas interfaces de rede (multi-homed). Este trabalho propõe o protocolo de roteamento 3D, direcionado a cenários onde há heterogeneidade de dispositivos e tecnologias de rede. O objetivo do protocolo de roteamento proposto é prover mecanismos para a interoperabilidade de redes ad hoc heterogêneas, considerando outra dimensão de informações, aqui denominada de terceira dimensão (3D), que consiste em agregar mais informações, como informações de contexto, recursos dos dispositivos e interfaces de rede, ao processo de roteamento. Para isto, o protocolo considera os seguintes aspectos fundamentais: o processo de bootstrapping da rede heterogênea e dos nós, a construção e disseminação de informações de ciência de contexto entre os nós, e a atribuição de papéis específicos para determinados nós da rede. A avaliação do protocolo é feita através de experimentos em um test-bed real, utilizando um protótipo da implementação do protocolo, num cenário composto de dispositivos móveis como Smartphones OpenMoko, Internet Tablets N810 da Nokia e Laptops, possuindo tecnologias Bluetooth e 802.11, executando versões embarcadas do sistema operacional Linux

Vehicular Ad Hoc Network (VANET) is a sub class of mobile ad hoc networks. VANET provides wireless communication among vehicles and vehicle to road side equipments. The communication between vehicles is used for safety, comfort and for entertainment as well. The performance of communication depends on how better the routing takes place in the network. Routing of data depends on the routing protocols being used in network. In this study we investigated about different ad hoc routing protocols for VANET. The main aim of our study was to identify which ad hoc routing method has better performance in highly mobile environment of VANET. To measure the performance of routing protocols in VANET, we considered two different scenarios i.e. city and highway. Routing protocols were selected carefully after carrying out literature review. The selected protocols were then evaluated through simulation in terms of performance metrics i.e. throughput and packet drop. After simulation results, we used MATLAB to plot the graph to compare the results of selected routing protocols with each other. Moreover, we computed the sum of output from each scenario to clearly present the difference in results. From results, we observe that A-STAR shows better performance in form of high throughput and low packet drop as compare to AODV and GPSR in city environment, while GPSR shows better performance as compare to AODV in both highway and city environment of VANET. Based on the results of performance metrics in different environments of VANET, we realized that position based routing method of VANET outperformed the traditional ad hoc topology based routing. However, it is hard to provide any universal routing protocol that can deal with all the various environments of VANET. The selection of a single routing protocol is hard in VANET because the protocol performance depends on vehicle speed, driving environment etc. That may vary from one environment of network to another.

Fully distributed systems offer the highest level of freedom for the users. For this reason, in today’s Internet, it is recorded that more than 50% of the packets moving in and out belong to this type of network. Huge networks of this kind are built on the top of DHTs, which follow a more structured communication compared to the other small peer-to-peer networks. Although nature always favors freedom and independ-ence, security issues force consumers to set up their network in a cen-trally controlled manner. One of security threats posed on such net-works is lookup attacks. A lookup attacks are kind of attacks which targets on disrupting the healthy routing process of the DHTs. Even though the freedom of peer-to-peer networks comes at the cost of securi-ty, it is quite attainable to make the network more secure, especially, it is quite achievable to gain performance on this level of attack according to the experiments carried out in this thesis. The secure routing techniques introduced have been found to outperform those without the techniques under investigation. The simulation performed for default Chord overly and the modified Chord, yielded interesting results, for dropper nodes, random lookup routs and colluding sub-ring attacks.

The multi-net Global Routing Problem (GRP) in VLSI physical design is a problem of routing a set of nets subject to limited resources and delay constraints. Various state-of-the-art routers are available but their main focus is to optimize the wire length and minimize the over ow. However optimizing wire length do not necessarily meet timing constraints at the sink nodes. Also, in modern nano-meter scale VLSI process the consideration of process variations is a necessity for ensuring reasonable yield at the fab. In this work, we try to nd a fundamental strategy to address the timing-driven Steiner tree construction (i.e., the routing) problem subject to congestion constraints and process variation. For congestion mitigation, a gradient based concurrent approach (over all nets) of Erzin et. al., rather than the traditional (sequential) rip-and-reroute is adopted in or- der to propagate the timing/delay-driven property of the Steiner tree candidates. The existing sequential rip-up and reroute methods meet the over ow constraint locally but cannot propagate the timing constraint which is non-local in nature. We build on this approach to accommodate the variation-aware statistical delay/timing requirements. To further reduce the congestion, the cost function of the tree generation method is updated by adding history based congestion penalty to the base cost (delay). Iterative use of the timing-driven Steiner tree construction method and history based tree construction procedure generate a diverse pool of candidate Steiner trees for each net. The gradient algorithm picks one tree for each net from the pool of trees such that congestion is e ciently controlled. As the technology scales down, process variation makes process dependent param- eters like resistance, capacitance etc non-deterministic. As a result, Statistical Static Timing Analysis or SSTA has replaced the traditional static timing in nano-meter scale VLSI processes. However, this poses a challenge regarding the max/min-plus algebra of Dijkstra like approximation algorithm that builds the Steiner trees. A new approach based on distance between distributions for nding maximum/minimum at the nodes is presented in this thesis. Under this metric, the approximation algorithm for variation aware timing driven congestion constrained routing is shown to be provably tight and one order of magnitude faster than existing approaches (which are not tight) such as the MVERT. The results (mean value) of our variation aware router are quite close to the mean of the several thousand Monte Carlo simulations of the deterministic router, i.e the results converge in mean. Therefore, instead of running so many deterministic Monte Carlo simulations, we can generate an average design with a probability distribution reasonably close to that of the actual behaviour of the design by running the proposed statistical router only once and at a small fraction of the computational e ort involved in physical design in the nano regime VLSI. The above approximation algorithm is extended to local routing, especially non- Manhattan lambda routing which is increasingly being allowed by the recent VLSI tech- nology nodes. Here also, we can meet delay driven constraints better and keep related wire lengths reasonable.

Capability to route can be considered one of key features of modern multipurpose operating system, which HelenOS aims to be. Goal of this master thesis is to explore current HelenOS routing capabilities, enhance them and empower HelenOS with BIRD. Thanks to BIRD, HelenOS will become a routing operating system, that is aware of its surroundings and is capable of dynamic adaptation to changes in network, it is part of.