O presente trabalho trata da solução para o problema da elaboração de programações de transporte do sistema de distribuição de materiais da Força Aérea Brasileira (FAB). Essas programações de transporte consistem em definir os roteiros de entrega e coleta de materiais a serem realizadas simultaneamente em cada local de entrega/coleta a partir de um centro de distribuição, considerando-se a frota de veículos homogênea. Isto é característico de um Problema de Roteirização de Veículos com Coletas e Entregas Simultâneas (PRVCES). A gestão do sistema de distribuição física da FAB considera a complexidade desse sistema e os dados relativos às demandas de transporte de carga em cada um desses locais para elaborar as programações de transporte. Essas programações são elaboradas tendo em vista os limites de capacidade dos veículos, as características físicas das cargas e as prioridades de embarque. O gestor desse sistema possui boa visibilidade das demandas de transporte, porém, devido à grande quantidade de informações disponíveis e à elevada complexidade desse sistema, é impossível elaborarem-se manualmente programações de transporte que resultem em viagens de distribuição eficientes. O PRVCES foi resolvido por meio da meta-heurística Busca Dispersa (do inglês Scatter Search) integrada com a meta-heurística Descida em Vizinhança Variável (do inglês Variable Neighborhood Descent) utilizada como método de melhoria das soluções. Os resultados superaram ou se igualaram a alguns dos obtidos por outros autores para os mesmos problemas de teste com as mesmas restrições, o que demonstra que a Busca Dispersa implementada é competitiva para solucionar o PRVCES. Quanto à aplicação na FAB, os resultados mostraram que a utilização do método de solução desenvolvido resultará em programações de transporte elaboradas em curto tempo de processamento e que estas incidirão positivamente sobre a eficiência do sistema de distribuição de materiais da FAB. / This work deals with the solution to the problem of drawing up transport schedules in the material distribution system of the Brazilian Air Force (BAF). These transport schedules consist in defining the routes for material pickup and delivery to be accomplished simultaneously in each delivery/pickup location from a distribution center, considering a homogeneous fleet of vehicles. This is characteristic of a Vehicle Routing Problem with Simultaneous Delivery and Pick-up (VRPSDP). The management of the physical distribution of BAF considers the complexity of this system and the data regarding the cargo transport demands in each one of those locations to draw up transport schedules. These schedules are drawn up regarding the capacity limits of the vehicles, the physical characteristics of the cargoes and the shipping priorities. A good visibility of transport demands in each location is available to the manager of this system, but due to the great quantity of data to deal with and the high complexity of the physical distribution system of BAF, it is impossible to draw up transport schedules that result in efficient distribution trips. The VRPSDP was solved by means of the Scatter Search meta-heuristic integrated with the Variable Neighborhood Descent meta-heuristic as the solution improvement method. The results exceeded or equaled some of those obtained by other authors using the same test problems with the same restrictions, what indicates that the implemented Scatter Search is competitive to solve the VRPSDP. As for the application in the BAF, the results showed that using the solution method developed will result in schedules drawn up in short processing time and focused on the efficiency of the material distribution system of the BAF.

Esta dissertação trata do problema do agrupamento de cargas fracionadas na distribuição de cimento ensacado partindo de um depósito central. O problema consiste em definir quais entregas de cimento serão carregadas juntas em um determinado veículo, de modo a aproveitar ao máximo sua capacidade e ao mesmo tempo reduzir o custo com o frete pago aos transportadores que farão sua distribuição. Em especial, o método de resolução proposto pode ser dividido em três fases. Na primeira fase, as entregas pertencentes a um mesmo cliente são agrupadas prioritariamente. Na segunda fase, são agrupadas as entregas de clientes dentro de uma mesma cidade. Neste caso, uma simplificação necessária é considerar que todas as entregas de uma mesma cidade estão localizadas em um único ponto. Com isso, a distância entre os clientes se torna irrelevante e é proposto um método baseado em um algoritmo genético para resolução de problemas de bin-packing (BPP). Para a terceira fase, é considerado o agrupamento para pontos de entrega pertencentes a cidades diferentes, onde as distâncias rodoviárias são consideradas. Nesta etapa, é proposta uma variação do método anterior, incorporando ao modelo algumas heurísticas para resolução de problemas de roteirização de veículos, como o algoritmo de Clarke & Wright e o algoritmo do Vizinho Mais Próximo. / This thesis deals with the problem of merging less-than-truckload deliveries in bagged cement distribution from a central depot. The problem consists in defining which cement deliveries shall be loaded in each given vehicle, in order to maximize the vehicle full capacity as well as reduce carriers freights. Particularly, the solution method can be divided hierarchically in three stages. In the first stage, the deliveries from the same client are merged with priority. In the second stage, the deliveries from the same city are merged. In this case, a necessary assumption is to consider the deliveries from the same city as located in a single destination point. Consequently, the distances among deliveries can be assumed as irrelevant and a heuristic method is proposed, which relies on a genetic algorithm for the bin-packing problem (BPP). In the third stage, merging of different delivery points that are apart from each other is considered. For this step, a variation of the previous method is proposed, incorporating some heuristics to solve the vehicle routing problem, like the Clarke & Wrights savings algorithm and the Nearest Neighbor algorithm.

Este trabalho apresenta a avaliação de diferentes algoritmos de roteamento utilizados na camada lógica ponto a ponto (P2P) adotada por um Metaescalonador que provê Qualidade de Serviços (QoS) na Computação em Nuvem. Experimentos mostram a superioridade de três algoritmos de roteamento P2P (BCR, Chord e Pastry) em relação à utilização de Round Robin, analisando-se o tempo de resposta e a variabilidade entre os resultados obtidos em diferentes testes. Os experimentos consideram, além dos algoritmos de roteamento, a influência do número de usuários e do tipo de serviço requisitado e como esses fatores interagem entre si. É apresentado ainda um estudo sobre a melhor métrica a ser adotada para representar as informações da rede. As métricas consideradas foram latência e número de saltos. Os resultados obtidos permitem determinar, com base nos objetivos especificados, qual o impacto dos sistemas P2P utilizados pelo metaescalonador na busca e descoberta de serviços em relação à forma como a qualidade de serviços é abordada / This work presents an evaluation of different routing algorithms that are employed in a logical layer peer-to-peer (P2P) that are adopted by a Metascheduler that provides quality of services (QoS) in Cloud Computing. The experiments show the superiority of three P2P routing algorithms (BCR, Chord, Pastry) in relation to Round Robin utilization, analysing the response times and the variation between the results obtained results in different tests. The experiments consider, besides the routing algorithms, the influence of the number of the users and the type of requested services and how these factors interact between themselves. Besides of this, it is presented a study about the better metric to be adopted to represent the network information. The considered metrics were the latency and number of hops. The obtained results allow to determine, based on specific objectives, the impact of the utilization of P2P systems by the metascheduler in the search and discovery of services in relation to the way that the QoS is performed

O presente trabalho aborda o sistema logístico usualmente denominado Vendor Managed Inventory (VMI), no qual o fornecedor controla e coordena as decisões de reabastecimento, sendo responsável por manter os estoques de seus clientes dentro de limites fixados de antemão. O modelo proposto incorpora ainda as decisões relativas à produção e manutenção de estoque por parte do fornecedor, além da utilização de frota heterogênea na distribuição, e busca a minimização dos custos totais do sistema. Quatro heurísticas de duas etapas são propostas para a resolução do problema abordado. A primeira etapa, comum a todas as heurísticas, baseia-se em uma heurística recentemente publicada na literatura e fornece uma solução inicial viável, utilizada como ponto de partida para a etapa de melhoria subsequente, na qual é utilizada a metaheurística busca tabu ou busca em vizinhança variável. As heurísticas propostas foram avaliadas em um conjunto de teste, sendo obtidos resultados melhores que os reportados na literatura em todas as instâncias testadas. Dentre as estratégias de solução avaliadas, destaca-se a heurística baseada em busca tabu com diversificação, que demonstrou ser superior às demais heurísticas propostas. Os resultados obtidos indicam ainda que, no caso da frota disponível ser heterogênea, é vantajosa a utilização de uma adaptação do procedimento de obtenção da solução inicial, como forma de privilegiar a utilização de veículos de maior eficiência. / This thesis deals with the logistic system usually called Vendor Managed Inventory (VMI). In this system the supplier controls and coordinates the supply decisions and is responsible for keeping the inventory of each of his clients within predetermined minimum and maximum levels. Heterogeneous fleet and production/stocking decisions at the supplier are considered as well, and the proposed model seeks to minimize the total system cost. Four two-stage heuristics are proposed for this problem. The first stage consists in an adaptation of a heuristic found in the bibliography, which provides an initial viable solution that will be improved in the second stage by means of the metaheuristics tabu search or variable neighborhood search. The proposed heuristics were tested on a set of benchmark instances with improvements found on the best known results in all of the tested instances. The obtained results indicate that the tabu search based heuristic with diversification strategy is clearly superior to the other proposed heuristics and that a better fleet utilization can be obtained in the case of heterogeneous fleet by a simple improvement in the first stage, that favors the selection of more efficient vehicles.

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

Esta dissertação trata do planejamento do abastecimento de última milha em centros urbanos, propondo métodos para agrupar pedidos de clientes em programação de entregas. Neste estudo, é considerado que o frete pago ao transportador em uma rota é definido pela distância direta do ponto de entrega mais distante do depósito em contraposição à distância total da rota que é usual na literatura sobre problemas de roteirização de veículos. Além disso, também são consideradas categorias, conjunto de produtos similares, que não podem ser transportadas juntas por não serem compatíveis entre si. O objetivo do problema proposto é determinar o agrupamento e sequenciamento de pedidos em roteiros de veículos de acordo com as características operacionais descritas acima, utilizando uma frota homogênea de veículos capacitados que parte de um depósito, de tal forma que toda a demanda seja atendida com o menor frete possível. Para resolução desse problema são propostas uma formulação matemática para obtenção de soluções exatas e a implementação da heurística \"Multi Start Perturbation Tabu\" (MSPT) que é composta das metaheurísticas \"Greedy Randomized Adaptive Search Procedure\" (GRASP), \"Tabu Search\" (TS) e \"Iterated Local Search\" (ILS) para obtenção de soluções heurísticas. Os resultados experimentais indicam que a MSPT é competitiva com os resultados do método exato com até 5 horas de processamento utilizando os recursos computacionais de alto desempenho do Laboratório de Computação Científica Avançada (LCCA) da Universidade de São Paulo. / This dissertation addresses the planning of the last mile supply in urban centers and proposes methods to group customer orders into shipments. In this study, freight paid to the carrier on a route is defined as the direct distance from the point of delivery that is furthest from the depot as opposed to be defined as the total distance of the route which is commonly found in the literature on vehicle routing problems. In addition, it is also considered categories, a set of similar products, which cannot be transported together because they are not compatible with each other. The objective of the proposed problem is to determine the grouping and sequencing of orders into vehicle shipments according to the operational characteristics described above, using a homogeneous fleet of capacitated vehicles that is located in a depot, in such a way that all the demand is delivered with the lowest freight possible. To solve this problem, it is proposed a mathematical formulation to obtain exact solutions and the implementation of the Multi Start Perturbation Tabu (MSPT) heuristic that is composed of the Greedy Randomized Adaptive Search Procedure (GRASP), Tabu Search (TS) and \"Iterated Local Search\" (ILS) for heuristic solutions. Finally, the experimental results indicate that the MSPT is competitive with the outcomes of the exact method with up to 5 hours of processing using the high performance computational resources of the Advanced Scientific Computation Laboratory (LCCA) of the University of São Paulo (USP).

O problema de roteamento de veículos é um dos problemas de otimização combinatória mais estudados nas últimas décadas. Neste trabalho, é estudada uma variante do problema de roteamento de veículos capacitado em que são considerados custos adicionais em viagens que cruzam fronteiras entre estados. Duas abordagens foram apresentadas para considerar tal característica: adicionar custos fixos às viagens de clientes de estados diferentes e adicionar custos que consideram a carga do veículo ao cruzar a fronteira e, para ambas, foram apresentados modelos matemáticos. Um solver comercial foi utilizado para resolver instâncias conhecidas da literatura e devido à resolução ter atingido o tempo máximo computacional para grande parte dos testes, uma Variable Neighborhood Descent com múltiplos inícios foi desenvolvida para a resolução do problema. Os múltiplos inícios são gerados perturbando a solução inicial gerada para a heurística. Como esperado, tanto para a resolução via modelagem quanto a resolução via heurística, considerar custos de fronteira proporcionais a carga apresentaram soluções de melhor qualidade. Essa nova proposta para abordar custos reais de fronteira abre novas possibilidades para considerar custos de fronteira fixos e proporcionais a carga concomitantemente para melhor representar aplicações reais. / The vehicle routing problem is one of the most studied combinatorial optimization problems in the last decades. In this paper, a variant of vehicle routing problem was studied in which the border costs was added to trips that cross borders. In order to consider such characteristic, two approaches were made: add fixed costs for the trips which clients are from different states and add costs that consider the amount of cargo in the vehicle when it crosses the border. In order to consider such characteristics, models were presented. Instances of literature were solved with a commercial solver and due to high computational time obtained from the exact method, a heuristic with Variable Neighborhood Descent as the local search in a multiple start environment was implemented. The multiple starts were generated making a perturbation in the initial solution obtained for the heuristic. As expected, approaching the problem considering the border cost proportional to the cargo in the vehicle presented better results. This study gives the first results for solving the vehicle routing problem considering real border costs and gives the possibility for solving the problem considering real fixed and proportional costs simultaneously in order to better represent real applications.

Este trabalho apresenta uma nova estrutura matemática para a álgebra de caminhos, que permite analisar a convergência dos algoritmos de roteamento multi-restritivos hop-by-hop e, sob o ponto de vista da engenharia de tráfego e da Qualidade de Serviço (QoS) na arquitetura Generalized Multiprotocol Label Switching (GMPLS), garantir de maneira confiável a incorporação de novas métricas de roteamento aos algoritmos de roteamento baseados em múltiplas restrições. Baseando-se nessa nova álgebra de caminhos, são analisadas as propriedades de monotonicidade, isotonicidade e liberdade, conhecidas por garantir a convergência dos algoritmos de roteamento e, ao contrário do indicado na literatura até o momento, verifica-se que a propriedade de monotonicidade não e condição necessária e nem suficiente para garantir a convergência dos algoritmos de roteamento multi-restritivos hop-by-hop. Sendo assim, este trabalho propõe uma nova propriedade, denominada coerência, para a garantia da convergência do roteamento hop-by-hop e um novo algoritmo de roteamento hop-by-hop com convergência garantida. Para avaliar os resultados teóricos obtidos, s~ao analisados dois estudos de casos de aplicação do roteamento multi-restritivos hop-by-hop com o uso de uma ferramenta de simulação desenvolvida em MATLAB e baseada no algoritmo Eliminação de Loop pelo Nó de Destino (ELND) também proposto. Como resultado das simulações desses estudos de casos, verifica-se que as diferentes estratégias de otimização, necessárias as redes (GMPLS), impõem a necessidade de trabalhar com algoritmos de roteamento que permitam a definição de mais de duas métricas de roteamento com diferentes critérios de otimização para cada uma delas, comprovando, portanto, a necessidade do desenvolvimento e da continuação deste trabalho. / This work presents a new mathematical structure for paths algebra that allows the convergence analysis of hop-by-hop multi-constrained routing algorithms and, under the traffic engineering and quality of service perspectives in the Generalized Multiprotocol Label Switching (GMPLS) architecture, trustily ensures the aggregation of new routing metrics in a constrained-based routing. Based on this new paths algebra, we analyze the monotonicity, isotonicity and freeness properties, known as ensuring routing algorithms convergence, and despite of what has been indicated in the literature, we verified that the monotonicity property is not sufficient to ensure the hop-by-hop routing convergence. Therefore, this work proposes a new property, called coherence, as a necessary and sufficient condition to ensure it, as well as, a new multi-constrained hop-by-hop routing algorithm with ensured convergence. In order to evaluate the theoretical results obtained, two study cases of the hop-by-hop multi-constrained routing applications are analyzed in the present thesis by using the Eliminação de Loop pelo Nó de Destino (ELND) simulation tool, developed in MATLAB and also presented as a product of this work. As result of these study cases simulations, we verified that different optimization strategies, requested by the (GMPLS) networks, compel the use of routing algorithms that allow the specification of more than two routing metrics with different optimization criteria for each one of them, thus proving the necessity of this work and its continuation.

As redes de sensores sem fio estão presentes nos mais diversos setores, formando um conjunto de elementos colaborativos que realizam o transporte da informação em cenários urbanos, agricultura de precisão, saúde e automação industrial. Sua utilização enfrenta desafios como necessidade constante de adaptações a alterações de topologia, baixas taxas de comunicação e uso eficiente de energia. Dessa forma, as aplicações dessas redes precisam suportar estas características dinamicamente. Esta tese propõe, então, um novo protocolo de roteamento: o HOFACO (Hybrid Objective Function based on Ant Colony Optimization), com base no funcionamento do padrão RPL (Routing Protocol for Low Power and Lossy Networks) aplicado à eficiência energética. Este protocolo proposto preserva as interfaces já consolidadas de roteamento e faz uso de uma informação heurística baseada em swarm intelligence (inteligência de enxames), por meio do uso de agentes - colônia de formigas -, para a composição híbrida de métricas utilizadas na avaliação do rank durante a construção de topologias. Esta proposta foi validada por meio de implementações em simulações e dispositivos reais em duas plataformas distintas: o Contiki e o OpenWSN. O processo de validação utilizou parâmetros como número de mensagens de controle, alterações de configurações topológicas, latência da rede e taxa de entrega de pacotes comparando-se a proposta a soluções tradicionais. Os resultados obtidos demonstraram um funcionamento compatível com estes parâmetros e uma melhoria em torno de 7,6% no sentido de redução do tempo de estabilização da rede. Adicionalmente, foi feito um teste comparativo de consumo de energia, evidenciando uma melhoria em termos de eficiência enérgica de até 20,9% da proposta com relação a protocolos tradicionais. / The wireless sensor networks are present in the most diverse sectors, forming a set of collaborative elements that perform the transport of information in urban scenarios, precision agriculture, health and industrial automation. Its use faces challenges as a constant need for adaptations to topology changes, low communication rates and efficient energy use. In this way, the applications of these networks must support these characteristics dynamically. This thesis proposes, therefore, a new routing protocol: the HOFACO (Hybrid Objective Function based on Ant Colony Optimization), based on the RPL (Routing Protocol for Low Power and Lossy Networks) applied to energy efficiency. This proposed protocol preserves the already consolidated routing interfaces and makes use of heuristic information based on swarm intelligence, using ant colony agents for the hybrid composition of metrics used in rank evaluation during the construction of topologies. This proposal was validated through implementations in simulations and real devices in two different platforms: Contiki and OpenWSN. The validation process used parameters such as number of control messages, changes of topological configurations, network latency and packet delivery rate, comparing the proposal to traditional solutions. The results showed a functioning compatible with these parameters and an improvement around 7.6% in the sense of reducing the time of stabilization of the network. In addition, a comparative test of energy consumption was made, evidencing an improvement in terms of energetic efficiency up to 20.9% of the proposal with respect to traditional protocols.

Le véhicule électrique est actuellement au coeur des alternatives énergétiques qui permettent de faire face à la croissance du coût du carburant et au réchauffement climatique. En revanche, l’autonomie limitée des batteries des véhicules électriques et l’indisponibilité d’un nombre suffisant de bornes de recharge représentent des enjeux majeurs auxquels se trouvent confrontés les utilisateurs. Le déploiement des véhicules électriques doit alors passer par la conception et l’expérimentation des outils d’aide à la décision pour gestion optimisée et adaptée de l’écosystème du véhicule électrique. C’est dans ce contexte que s’inscrit cette thèse qui vise à fournir des outils d’aide à la décision pour l’optimisation des usages, de la recharge et des tournées des véhicules électriques dans le cadre industriel. Dans un premier temps, nous proposons d’étudier le problème d’optimisation conjointe de l’affectation et de la recharge des véhicules électriques. L’objectif de ce problème est de maximiser l’usage des véhicules électriques et minimiser les coûts de recharge tout en prenant en compte les contraintes d’ordre opérationnel et technique. Pour résoudre ce problème, nous proposons une méthode exacte et deux heuristiques. Nous comparons les performances de ces méthodes sur des instances réelles et d’autres aléatoires. Nous exposons ensuite plusieurs extensions au problème de base en intégrant de nouvelles fonctions objectif et de nouvelles contraintes. Nous étudions par la suite notre problème de point de vue ordonnancement et nous proposons une étude de complexité et des algorithmes d’approximation avec garantie de performance pour le problème d’ordonnancement d’intervalles sous contraintes d’énergie. Finalement, nous nous intéressons à un nouveau problème de construction de tournées pour une flotte mixte de véhicules électriques et thermiques. Pour résoudre ce problème, nous proposons des heuristiques et des méta-heuristiques hybrides et nous comparons les performances des différentes méthodes sur des instances généralisées de la littérature / Electric Vehicles may decrease transportation-related emissions and provide for less dependence on foreign oil. However, electric vehicles are still facing many weaknesses related to the high purchase prices, limited battery range and scarce charging infrastructure. The deployment of electric vehicles must then involve the design and the deployment of charging infrastructures. Within this study, the overall objective is to provide enhanced optimization methods and decision tools for electric vehicles assignment, charging and routing that are relevant to different real-world constraints. Firstly, we propose to study the joint scheduling and optimal charging of electric vehicles problem. This problem consists in assigning a set of already constructed routes to the available electric and conventional vehicles and in, simultaneously, optimizing the electric vehicles charging costs while ensuring that all constraints are satisfied. The objective of this problem is to maximize the use of EVs and to minimize charging costs. Secondly, we propose different extensions to our baseline problem and we vary the objective functions and the considered constraints. Moreover, our problem can be seen as a fixed interval scheduling problem with complementary constraints of energy. We propose then to study the complexity and the approximability of many variants of this new problem. Finally, we consider a new variant of the electric vehicle routing problem with a heterogeneous fleet of vehicles and we propose different heuristics and metaheuristics to solve it. We test the different solving methods on benchmark instances and we evaluate the efficiency of each method