Two-echelon vehicle routing problems which contain synchronization between vehicles can be deeply impacted by time uncertainty, because one vehicle's delay can propagate to other vehicles. In this paper, we evaluate the deterministic solution of such a problem based on simulated travel time scenarios. The information obtained by simulation is incorporated in the optimization procedure iteratively. Computational results show that the degree of synchronization in an instance is directly correlated with the potential improvements by reoptimization. We present findings on the number of travel time scenarios required to obtain a representative picture of the stochastic solutions. In addition, we demonstrate that time dependent travel times can be aggregated on a city-wide level and linearized as a function of free flow times without major loss of reliability.

O presente trabalho aborda a questão da interligação de poços de petróleo às plataformas de produção com a utilização de embarcações do tipo Pipe Laying Support Vessels (PLSVs). O objetivo do estudo é a maximização da curva de produção de óleo no período analisado, o que passa pelo melhor aproveitamento da frota de PLSVs contratada. São consideradas as especificidades da situação como, por exemplo, as restrições técnicas de cada embarcação para as atividades necessárias, a disponibilidade dos PLSVs, materiais para interligação e a já ocorrência da fase precedente, denominada completação. Considerando todo este conjunto de características do problema, desenvolveu-se uma formulação de Programação Linear Inteira Mista com pontos inovadores em relação à literatura, especialmente no que diz respeito ao incremento da curva de produção por conta da operação de poços injetores e ao declínio natural de poços produtores com o passar do tempo. Como os resultados obtidos nos testes da formulação matemática mostraram-se satisfatórios para pequenas instâncias, mas de alta complexidade computacional para um número grande de atividades, foram elaboradas duas versões de uma heurística construtiva adequada para a resolução de problemas de maior porte. Levando em consideração as mesmas características do problema que foram usadas na etapa de formulação matemática, puderam ser elaborados os algoritmos e suas devidas programações computacionais. A partir disso, foram realizados testes de pequeno porte para verificar a robustez dos algoritmos quanto aos seus comportamentos. Por fim, houve a comparação do caso completo, onde foram aplicadas as heurísticas, com o que ocorreu na situação real, tendo o resultado deste presente estudo apresentado um relevante ganho. / This research presents a real case of connection of oil wells in subsea environment to the production platforms with the use of ships of the type PLSV - Pipe Laying Support Vessels. The objective of this study is to maximize the oil production curve in the horizon considered, which is due to the best exploitation of the outsourced fleet. Specificities of the situation are considered like, for example, technical constraints of each vessel for the required activities, the availability of the PLSVs, materials for connection and the end of the previous phase, called completion. Considering all this set of the problem characteristics, it was developed a Mixed-Integer Linear Programming (MILP) formulation with innovative aspects in relation to the literature, especially with respect to the increase of the production curve due to the operation of injector wells and to the natural decline of producer wells during their operation, in the course of time. As the results obtained in the tests of the mathematical formulation were satisfactory for small instances, but with a high computational time for a great number of activities, two suitable constructive heuristics were elaborated for the resolution of larger problems. Numerical experiments were conducted, in small scale, to verify the robustness of the algorithms. Next, the proposed methods were applied to a real case of an oil company and relevant gains were observed.

O problema de roteirização periódica de veículos pode ser considerado como uma generalização do problema clássico de roteirização devido a duas características próprias: um período de planejamento maior que um dia, em que os veículos fazem diversas viagens, e freqüências de visitas associadas a pontos a serem servidos. Esse tipo de problema pode ter muitas aplicações práticas. Atualmente, algumas indústrias automobilísticas brasileiras já utilizam um sistema de coleta que se baseia na idéia de roteirização periódica, com a finalidade de reduzir o estoque de peças. Assim como os problemas originais de roteirização de veículos, o problema aqui tratado é também difícil de ser resolvido, sendo impossível o uso de algoritmos exatos para a obtenção de uma solução ótima para o tamanho de problemas encontrados na prática. Isso motivou o estudo, que direcionou seus esforços na exploração de novas estratégias de solução para esse problema através de novas abordagens, de modo que houvesse um aumento na qualidade de soluções e uma diminuição do tempo de processamento computacional. Dois procedimentos diferentes foram propostos para a alocação dos clientes aos dias de visitas: uma heurística de inserção seqüencial que visa equilibrar os esforços dos diferentes dias do período de planejamento, e uma heurística baseada em algoritmos genéticos. As rotas diárias são construídas através da utilização do algoritmo de economias de Clarke e Wright, que permite a obtenção de boas soluções em tempos de processamento curtos. Experimentos computacionais são realizados para a avaliação da eficiência de cada uma das heurísticas propostas através da utilização de benchmarks retirados da literatura e problemas-teste gerados aleatoriamente, e os resultados são também comparados aos anteriormente mostrados na literatura. / The period vehicle routing problem can be viewed as a generalization of the classic vehicle routing problem due to two singular features: a planning period longer than one day in which vehicles make several trips and frequencies of visit associated to points to be serviced. This type of problem may arise in different practical applications. Nowadays, some Brazilian automaker industries are already utilizing a collect system based on the idea of the period routing in order to reduce parts inventory. Similarly to the original vehicle routing problem, the period vehicle routing problem is also hard to solve, making it impossible to use exact in order to obtain an optimal solution for problem sizes found in practice. This motivated this research study, which directed its efforts to the exploration of new strategies of solution through new reasoning, leading to an increase in the quality of the solution and a decrease in the computational processing time. The proposed heuristics are composed of three consecutive stages: (i) assigning customers to days of visit while respecting their given frequencies, (ii) building routes that serve all customers assigned to each day of the planning horizon, and (iii) improving the obtained solution. Despite the distinction between the stages, we managed to take into consideration the integration among the three decisions. Two different procedures were proposed to the assignment of customers to days of visit: a sequential insertion heuristic that aims to balance the workload among different days in the time horizon, and a heuristic based on genetic algorithms. The daily routes are then constructed by using the Clarke and Wright\'s savings algorithm, which allows good solutions to be obtained in short processing times. Computational experiments are made in order to evaluate the efficiency of each proposed heuristic using both benchmark problem sets from the literature and randomly generated problems as well, and the results are compared to the previously reported in the literature.

The performance of many protocols and applications of Vehicular Ad hoc Networks (VANETs), depends on vehicles obtaining enough fresh information on the status of their neighbouring vehicles. This should be fulfilled by exchanging Basic Safety Messages (BSMs) also called beacons using a shared channel. In dense vehicular conditions, many of the beacons are lost due to channel congestion. Therefore, in such conditions, it is necessary to control channel load at a level that maximizes BSM dissemination. To address the problem, in this thesis algorithms for adaptation of beaconing to control channel load are proposed. First, a position-based routing protocol for VANETs is proposed and the requirement of adaptive beaconing to increase the performance of the protocol is indicated. The routing protocol is traffic-aware and suitable for city environments and obtains real-time traffic information in a completely ad hoc manner without any central or dedicated control, such as traffic sensors, roadside units, or information obtained from outside the network. The protocol uses an ant-based algorithm to find a route that has optimum network connectivity. Using information included in small control packets called ants, vehicles calculate a weight for every street segment that is proportional to the network connectivity of that segment. Ant packets are launched by vehicles in junction areas. To find the optimal route between a source and destination, a source vehicle determines the path on a street map with the minimum total weight for the complete route. The correct functionality of the protocol design has been verified and its performance has been evaluated in a simulation environment. Moreover, the performance of the protocol in different vehicular densities has been studied and indicated that in dense vehicular conditions the performance of the protocol degrades due to channel load created by uncontrolled periodic beaconing. Then, the problem of beaconing congestion control has been formulated as non-cooperative games, and algorithms for finding the equilibrium point of the games have been presented. Vehicles as players of the games adjust their beacon rate or power or both, based on the proposed algorithms so that channel load is controlled at a desired level. The algorithms are overhead free and fairness in rate or power or both rate and power allocation are achieved without exchanging excess information in beacons. Every vehicle just needs local information on channel load while good fairness is achieved globally. In addition, the protocols have per-vehicle parameters, which makes them capable of meeting application requirements. Every vehicle can control its share of bandwidth individually based on its dynamics or requirements, while the whole usage of the bandwidth is controlled at an acceptable level. The algorithms are stable, computationally inexpensive and converge in a short time, which makes them suitable for the dynamic environment of VANETs. The correct functionality of the algorithms has been validated in several high density scenarios using simulations.

Li Fengjun. / Thesis submitted in: July 2004. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2005. / Includes bibliographical references (leaves 83-84). / Abstracts in English and Chinese. / Abstract --- p.i / Acknowledgments --- p.v / Table of Contents --- p.vi / List of Figures --- p.viii / List of Tables --- p.ix / Chapter Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Motivations of this work --- p.1 / Chapter 1.2 --- Network Fairness Issue --- p.3 / Chapter 1.3 --- Our Contribution --- p.4 / Chapter 1.4 --- Organization of the Thesis --- p.5 / Chapter Chapter 2 --- Background of Fairness Index --- p.7 / Chapter 2.1 --- The Model --- p.7 / Chapter 2.2 --- Definitions of Fairness Index --- p.9 / Chapter 2.3 --- General Existence and Uniqueness Properties of Perfectly Fair Solution --- p.12 / Chapter 2.4 --- Properties in Specific Network Topologies --- p.16 / Chapter 2.4.1 --- Uniform Routing Networks --- p.16 / Chapter 2.4.2 --- Single Routing Node Networks --- p.20 / Chapter Chapter 3 --- Extension of the Fairness Index --- p.22 / Chapter 3.1 --- A Single Routing Node Network Example --- p.22 / Chapter 3.2 --- The Max-Min Fairness Index --- p.27 / Chapter 3.3 --- Von Neumann Equilibrium Index --- p.29 / Chapter Chapter 4 --- Distributed Low Bit Rate Algorithm --- p.36 / Chapter 4.1 --- Distributed Controller --- p.36 / Chapter 4.2 --- Convergence of the Low Bit Rate Distributed Algorithm --- p.39 / Chapter 4.3 --- Experiment Results --- p.49 / Chapter 4.4 --- Heuristic Iterative Algorithm --- p.53 / Chapter Chapter 5 --- Fairness Index Based Routing --- p.57 / Chapter 5.1 --- Routing Protocol Basics --- p.58 / Chapter 5.1.1 --- Static Routing and Dynamic Routing --- p.58 / Chapter 5.1.2 --- Routing Metrics --- p.59 / Chapter 5.1.3 --- Distance Vector and Link State --- p.60 / Chapter 5.1.4 --- Shortest Path Routing Algorithm --- p.62 / Chapter 5.2 --- Minimum Delay Routing --- p.63 / Chapter 5.3 --- Fairness Index Based Routing --- p.66 / Chapter 5.3.1 --- Problem Formulation --- p.66 / Chapter 5.3.2 --- Cost Function --- p.69 / Chapter 5.3.3 --- Implementing Fairness Index Based Routing --- p.71 / Chapter 5.3.4 --- Experiment and Analysis --- p.73 / Bibliography --- p.82

Orientador: Jefferson Nascimento de Oliveira / Resumo: O estudo do comportamento de corpos hídricos propicia a obtenção de informações relevantes à bacia hidrográfica e ao meio pertencente a ela, resultando em diversos benefícios, não só do ponto de vista econômico, onde através de operação otimizada de reservatórios de água pode-se obter um maior aproveitamento para geração de energia hidrelétrica, abastecimento, irrigação ou outros fins, mas também subsidia o planejamento e a tomada de decisões com a relação à mitigação de riscos hidrodinâmicos, como o mapeamento de zonas potencialmente inundáveis e a detecção de áreas sujeitas a maiores riscos relacionados às inundações. Neste trabalho foi desenvolvido um modelo operacional simplificado para propagação de vazões, baseado no modelo Muskingum-Cunge-Todini, e realizado comparações dos resultados com o modelo hidrodinâmico completo HEC-RAS. Os modelos foram aplicados em trechos do rio Tocantins, entre os municípios de Peixe –TO e Bom Jesus do Tocantins–TO. Os resultados obtidos apresentaram similaridade entre o HEC-RAS e o modelo desenvolvido. / Abstract: The study of the behavior of water bodies supports relevant information to the hydrographic basin and to the means belonging to it, resulting in several benefits. Not only from the economic point of view, where, through an optimized operation of water reservoirs, can be obtained greater use for hydroelectric power generation, water supply, irrigation, or other purposes, but subsidizes planning and decision-making about hydrodynamic risk mitigation, such as mapping potentially floodable areas and the detection of areas subjected to higher risks of floods. In this work a simplified operating model for flow propagation was developed, based on the Muskingum-Cunge-Todini model, and comparisons of the results with the complete hydrodynamic model HEC-RAS were performed. The models were applied in stretches of the Tocantins river, between the municipalities of Peixe – and Bom Jesus do Tocantins-TO. The results obtained showed similarity between HEC-RAS and the developed model. / Mestre

In this research work we propose a 3D node deployment strategy by carefully considering the unique characteristics of underwater acoustic communication as well as 3D dynamic nature of UWSN. This strategy targets 3D UWSN and not only improves the routing protocol performance significantly in terms of end to end delay and energy consumption but also provides reliability in data transmission. This strategy has been developed step by step from a single line of vertical communication to an effective 3D node deployment for UWSN. Several simulation experiments were carried out after adding different features to the final design to observe their impact on the overall routing performance. Finally, it is verified that this design strategy improves the routing performance, provides reliability to the network and increases network lifetime. Furthermore, we compared our results to the random node deployment in 3D, which is commonly used for analysing the performance of UWSN routing protocols. The comparison results verified our effective deployment design and showed that it provides almost 150% less end-to-end delay and almost 25% less energy consumption to the random deployment. It also revealed that by increasing the data traffic, our 3D node deployment strategy has no loss of data due to several back-up paths available, which is in contrast to random node deployment, where the packet loss occurs by increasing the data traffic. Improving the routing performance by carefully analysing the impact of 3D node deployment strategy and ensuring full sensing, transmission and back-up coverage in a highly unpredictable underwater environment, is a novel approach. Embedding this strategy with any networking protocol will improve its performance significantly.

O transporte de cargas desempenha um papel fundamental nos sistemas logísticos uma vez que possibilita o fluxo de produtos entre os elementos dos canais de distribuição, além de representar um elevado percentual de participação nos custos logísticos totais. Desse modo, a eficiência dos serviços de transporte depende diretamente de um adequado processo de planejamento em nível estratégico, tático e operacional. O transporte rodoviário, em particular, apresenta em nível operacional, problemas de elevada complexidade como a roteirização e o carregamento de veículos. Durante os últimos 50 anos estes problemas vêm sendo objeto de intensos estudos e desenvolvimentos, porém de forma separada, conduzindo a resultados difíceis de serem implementados nas situações práticas, devido à grande interdependência existente entre roteirização e carregamento de veículos. A resolução integrada destes dois problemas é recente na literatura, o que abre um campo bastante promissor para novos desenvolvimentos. Assim, esta tese tem como objetivo propor uma abordagem integrada de resolução para o problema de roteirização e carregamento de veículos onde, além das restrições de carregamento tridimensionais, as restrições de tempo de ciclo e distribuição de peso nos eixos são consideradas. Este modelo adota uma abordagem aproximativa que combina o uso de heurísticas para construção dos carregamentos com a metaheurística de Busca Tabu para melhoria dos roteiros de entrega. Para execução dos testes computacionais é proposto um conjunto de 12 instâncias que buscam simular situações práticas encontradas nas operações de entrega feitas por empresas de transporte e prestadores de serviços logísticos. A partir desse conjunto de instâncias são construídos cenários que avaliam o uso de diferentes tipos de veículos e os respectivos custos operacionais. Testes complementares realizados com um conjunto de 27 instâncias disponíveis na literatura, demonstram a capacidade do modelo proposto de atingir boas soluções em um tempo de processamento aceitável. / Freight transportation plays a fundamental role in logistics systems, once it enables the product flow between distribution channels elements, besides to represents a high percentage of participation on the total logistics costs. In this way, transport service efficiency depends directly of a suitable process of planning in strategic, tactical and operational level. The road transportation, in particular, shows in operational level high complexity problems as routing and loading of vehicles. During the last 50 years, these problems has been object of deep studies and developments, but in a separate manner, leading to results that are difficult to implement in practical situation due to the interdependence between routing and loading of vehicles. The integrated resolution of these two problems is recent in the literature, what opens a quite promising field for new developments. Thus, this thesis has as objective to propose an integrated resolution approach for the vehicle routing and loading where, besides the three-dimensional loading constraints, constraints, the time cicle and the distribution load over de axles are considered. This model adopts an approximated approach that combines the use of heuristics for loading construction with Tabu Search metaheuristics to improve the delivery routes. For computational tests execution is proposed a 12 instances set that tries to simulate practical situation found in delivery operations made by freight firms and thirty party logistics. From this instance set, it is built scenarios that evaluate the use of different vehicle types and the respectives operational costs. Complementary tests made with a 27 instances set available in literature show the capacity of proposed model to get good solutions in an acceptable computational time.

Este trabalho apresenta uma variação do problema de roteamento de veículos que permite o uso de veículos com múltiplos compartimentos. A necessidade de veículos com múltiplos compartimentos surge com frequência em aplicações práticas quando uma série de produtos, que possuem diferentes qualidades ou tipo, precisam ser transportados mas não podem ser misturados. Este problema é chamado na literatura de roteamento de veículos com múltiplos compartimentos (PRVMC). Nós propomos uma heurística busca tabu implementada em uma busca local iterada para resolver este problema. Experimentos foram feitos para avaliar a performance da busca tabu iterada e os resultados obtidos foram comparados com os resultados disponíveis na literatura. O algoritimo proposto é capaz de encontrar soluções melhores e em menos tempo de processamento que as heurísticas existentes. / We study a variant of the vehicle routing problem that allows vehicles with multiple compartments. The need for multiple compartments frequently arises in practical applications when there are several products of different quality or type, that must be kept or handled separately. The resulting problem is called the multi-compartment vehicle routing problem (MCVRP). We propose a tabu search heuristic and embed it into an iterated local search to solve the MCVRP. In several experiments we analyze the performance of the iterated tabu search and compare it with results from the literature. We find that it consistently produces solutions that are better than existing heuristic algorithms.

O Roteamento Global é responsável pelo planejamento da distribuição dos meios de interconexão dentro da área do circuito. Dentro da fase do projeto de circuitos conhecida como Síntese Física, essa fase situa-se após a etapa de posicionamento, que define uma posição exata para cada célula do circuito, e antes da etapa de roteamento detalhado que irá definir uma posição para cada meio de interconexão. Os roteadores globais utilizam uma versão abstrata e simplificada do circuito, que agrega uma região e toda a capacidade de fios que esta região comporta, trabalhando com o planejamento dessas capacidades em relação a demanda de interconexão entre as células do circuito. Este trabalho, apresenta um conjunto de técnicas para delimitação e tratamento de áreas que possuem alta demanda por meios de interconexão em circuitos VLSI. As técnicas são aplicadas em duas fases do fluxo de rotamento global: a primeira é executada na fase de pré-roteamento, onde são identificadas as regiões que possuem alta demanda por interconexão, isto é, são destino ou origem de um número elevado fios em relação a sua capacidade de alocar meios de interconexão; a segunda etapa ocorre dentro da fase de roteamento iterativo, identificando e protegendo aquelas que regiões que possuem os níveis mais elevados de congestionamento. Para avaliar os impactos da aplicação das técnicas propostas, foi feita a implementação em um fluxo de roteamento global existente. A avaliação foi partir da extração de quatro métricas de roteamento global comumente utilizadas na literatura de síntese física, para análise de roteamento global: comprimento dos fios, valor total de congestionamento, máximo congestionamento de aresta e tempo de execução. A partir da execução de experimentos utilizando as técnicas, foi possível verificar ganhos de até 11% em redução do congestionamento total no circuito, em benchmarks para os quais ainda não se tem soluções válidas na literatura. Os tempos de execução obtiveram um redução de até 35%, quando comparados com a implementação usada como referência para aplicação das técnicas, o roteador GR-WL. Um dos efeitos colaterais da aplicação de técnicas de calibração de custos é o aumento do comprimento médio dos fios. Os resultados dos experimentos mostram que as técnicas propostas conseguem reduzir este efeito colateral para, no máximo, 1.39% de acordo com os benchmarks executados. / Global routing phase is responsible for the interconnect planning and distribution across the circuit area. During the integrated circuit project flow, the global routing is contained in the Physical Synthesis, after the placement, that is when the position of all circuit cells are defined, and before the detailed routing, when the position of all interonnection wires is realized. A simplified and abstrate version of the circuit routing area is used by the global router, that will agregate in a single vertex, an specific region of the circuit, that represents a bunch of interconnection with their total capacity. This work presents a set of techniques to delimit and threat areas that have high interconnection demand in VLSI circuits. These techniques are applied in two steps of the global routing flow: the first is executed during the initial routing, where the high interconnection demanding regions are identified. the second step is executed during the iterative routing, where the top offender regions are identified and heva their costs pre-allocated. In order to evaluate the impact of the proposed techniques, they are implemented in an existing global routing flow, and four metrics are collected: total wirelenght, execution time, total overflow and maximum overflow. Tha last two metrics will be different from zero just for the circuits that not have a valid solution. After the execution of the experiments it was possible to verify a reduction up to 11% in wirelenght, in some benchmarks that the literature do no have a valid solution. Furthermore, it was possible to verify a reduction up to 35% in the execution time, when compared to the reference implementation. Once we are including constraints in form of cost pre-allocation, it is possible to verify an wirelength increase in some cases. In this work, it was possible to observe a small presence of these side-effects, up to 1.39%, according to the executed benchmarks.