Orientador: Jose Raimundo de Oliveira / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Elétrica e Computação / Made available in DSpace on 2018-08-08T12:33:26Z (GMT). No. of bitstreams: 1 Nascimento_JurandyAntoniodo_M.pdf: 1298680 bytes, checksum: eebec168aaccc2455ed7b9dad7ca1ab7 (MD5) Previous issue date: 2007 / Resumo: Devido ao crescente interesse em automação de rodovias e ao desenvolvimento e a viabilidade econômica de tecnologias de comunicação sem fio, surgiram nos últimos anos projetos para a comunicação entre veículos que possibilitam que dados de sensores locais, indicando situação de risco, sejam transmitidos para outros veículos de sua vizinhança para sinalizar a situação, ou mesmo para uma possível atuação no fluxo do tráfico local. É apresentada aqui uma infra-estrutura de comunicação sem fio que faz uso da especificação IEEE 802.15.4 para a comunicação entre veículos e que tem aplicações também em controle de sistemas, devido à sua característica versátil / Abstract: Due to the increasing interest on roads automation and to the development and the economic viability of wireless communication technologies, it has appeared in the last years projects to implement inter-vehicle communication links which makes possible that local sensors data, indicating risk situation, to be transmitted to others vehicles on its neighborhoods to signalize the situation or even to a possible actuation on the local traffic flow. It is presented here a wireless communication infrastructure that makes use of IEEE 802.15.4 specification for inter-vehicle communication and also for control systems applications due to its versatile characteristics / Mestrado / Engenharia de Computação / Mestre em Engenharia Elétrica

[pt] O problema de Roteamento de Veículos com restrição de capacidade (CVRP) é um dos problemas mais estudados em Otimização Combinatória. Sendo uma generalização imediata do conhecido problema do Caixeiro Viajante, o CVRP tem atraído a atenção dos pesquisadores mais proeminentes da área desde os anos 60. Um dos algoritmos mais importantes para a sua resolução foi proposto no início dos anos 80 quando um algoritmo utilizando uma relaxação Lagrangeana particularmente adequada provou ser bastante superior aos algoritmos contemporâneos. Este algoritmo sugeriu a utilização de técnicas de geração de colunas que, nos anos seguintes até o início dos anos 90, assumiram o rótulo de melhor algoritmo para o CVRP. Finalmente, em meados dos anos 90, algoritmos de planos de corte apresentaram resultados que convenceram a comunidade de que esta deveria ser a abordagem para resolver os problemas mais difíceis de CVRP. Esta dissertação apresenta uma revisão deste algoritmos anteriores e propõe um formulação que permite reunir o melhor deles. O algortimo resultante, que pode ser rotulado como de branch-and-cut-and-price, trabalha com um número exponencial de variáveis e restrições que definem um espaço relaxado de soluções que corresponde à interseção dos espaços de solução relaxados utilizados pelos algoritmos anteriores. Esta dissertação também descreve um implementação especial do algoritmo de programação dinâmica para resolução do problema de geração de colunas. Estratégias para fazer um branching robusto também são discutidas. Tudo isso permite construir um algoritmo que é capaz de ter uma boa performance quando aplicado a diferentes classes de instâncias. A experiência computacional mostrou que a abordagem proposta obtém limites inferiores consistentemente melhores que os dos algoritmos anteriores. Mais ainda, permite resolver em tempo hábil diferentes tipos de instâncias de até 135 vértices, incluindo 18 que foram resolvidas pela primeira vez. / [en] The Capacitated Vehicle Routing problem (CVRP) has been one of the most studied problems in the field of Combinatorial Optimization. A straight forward generalization of the popular Travelling Salesperson problem, the CVRP has drawn attention of the most prominent researchers since the early 60`s. One of the most important algorithms appeared in the early 80`s when a suitable Lagrangean relaxation algorithm has demonstrated to be far better than the contemporary ones. This algorithm suggested the use of column generation algorithms that succeeded to become the best ones in the late 80`s and early 90`s. Finally, in the mid 90`s, cutting plane methods presented results that convinced the community that this should be the approach for solving the hardest CVRP problems. This dissertation presents an overview of those early algorithms and proposes a formulation that allows uniting the best contributions of them. The resulting algorithm, labeled as a branch-and-cut-and-price algorithm, deals with exponentially many variables and constraints that define a relaxed solution space that is the intersection of the relaxed solution spaces considered in the previous algorithms. The dissertation also describes a specially devised dynamic programming algorithm to solve the column generation subproblem and discusses robust branching strategies that altogether allowed to build an algorithm that perfoms well on several different classes of instances. The computational experience has shown that the approach here proposed leads to lower bounds superior than the previous ones. Moreover, it allowed to consistently solve instances with up to 135 vertices, including 18 that were solved for the first time.

[pt] A busca pelo desenvolvimento sustentável tem como importante fator diferencial as fontes de energia renováveis. O biodiesel desponta como uma das alternativas mais relevantes, mas suas formas de obtenção no Rio de Janeiro não foram suficientemente investigadas. Este trabalho identifica a oportunidade da produção de biodiesel a partir de óleos residuais de fritura neste cenário, enfatizando os custos de transporte do óleo desde os principais produtores comerciais até a obtenção do biocombustível. O objetivo é avaliar os custos de forma a verificar a viabilidade do emprego desta alternativa. Para tanto, foram estudadas as diversas ferramentas de resolução do Problema de Roteamento de Veículos e foi proposto um algoritmo que visa à otimização dos custos. A formulação matemática utilizada baseia-se numa extensão de algoritmos clássicos, como o apresentado por Arenales et al. (2007), e nas equações desenvolvidas em Kallehauge (2006). Os resultados do modelo de roteamento, atrelados aos custos de produção, impostos e insumos, foram comparados com informações sobre a comercialização do biodiesel, comprovando sua viabilidade econômica. A consolidação dos dados obtidos aponta a produção de biodiesel a partir de óleo residual de fritura como viável, com custos logísticos equivalentes a R/tmp/aaaUFg8ya,19 por litro e custo final de R,22 por litro. / [en] The search for a sustainable development has in renewable energy sources an important differential factor. Biodiesel is one of the most important alternatives, but its obtainment forms in Rio de Janeiro have not been investigated enough. This work identifies the opportunity of biodiesel production from waste cooking oil in this scenery, emphasizing oil`s transport costs until factories, where it is possible to obtain biodiesel in its final form. The objective is to evaluate costs in order to verify viability of this alternative source of energy. Hence, this research analysed several tools for solving Vehicle Routing Problem and it proposes an algorithm that results in cost optimization. The adapted mathematic formulation is based in an extension of classic algorithms, like those presented by Arenales (2007), and in equations developed by Kallehauge (2006). The routing model results, linked to production, tributes and input costs, have been compared with information about biodiesel commercialization, verifying its economic viability. The data consolidation obtained indicates that the biodiesel production from waste cooking oil is viable, with logistic costs equal to R/tmp/aaaPLIh7a,19 per liter and final cost equal to R,22 per liter.

[pt] O crescimento da população no mundo inteiro tem gerado nos últimos anos o nascimento de novas economias e o aumento nos níveis de demanda dos produtos. Com os novos perfis dos consumidores e as novas tendências das mercadorias, as empresas estão criando produtos com ciclo de vida curto, aumentando a geração de Resíduos Sólidos Domiciliares nos municípios. Devido ao fenômeno anterior, o número de pontos de coleta nos itinerários dos veículos aumenta, gerando custos e distâncias maiores, diminuindo a produtividade e qualidade do Sistema de Transporte das empresas de limpeza. Nesta dissertação apresenta-se o planejamento das rotas de coleta de Resíduos Sólidos Domiciliares do Programa de Remoção Gratuita da Companhia Municipal de Limpeza Urbana – COMLURB na zona sul da cidade do Rio de Janeiro, como método de apoio na logística de transporte do sistema de limpeza da cidade. Para tal objetivo, utilizou-se o Sistema de Informação Geográfica para Transporte (SIG-T) TransCAD versão 5.0 Academic Licence com a aplicação do Problema de Roteirização dos Veículos com Janela de Tempo (PRVJT). Os resultados obtidos nas análises reduziram a distância total executada pelos veículos em 30,34 por cento, demostrando a importância da metodologia em problemas de transporte reais. / [en] Population growth worldwide has generated in recent years the emergence of new economies and the increased levels of demand for products. With the new profiles of consumers and new trends of goods, companies are creating products with short life cycle, increasing the generation of Household Solid Waste in the municipalities. Due to the previous phenomenon, the number of collection points on the routes of vehicles increases, generating costs and greater distances, decreasing the productivity and quality of the transport system of cleaning companies. In this dissertation presents the planning of the waste collection routes of Household Solid Free Removal Program of the Municipal Company of Urban Cleaning - COMLURB in the south of the city of Rio de Janeiro, as a support method in the Transport Logistics of city cleaning system . For this purpose, we used the Geographic Information System for Transportation (GIS-T) TransCAD version 5.0 Academic License to the implementation of the Vehicle Routing Problem with Time Windows (VRPTW). The results obtained in this study reduced the overall distance traveled by vehicles in 30, 34 per cent, showing the importance of the methodology in real transportation problems.

[pt] O Problema de Roteirização de Veículos (Vehicle Routing Problem - VRP) é um problema clássico combinatório bem conhecido. Este trabalho apresenta um novo fator no modelo de otimização matemática de otimização do VRP, considerando restrições que abordam a probabilidade de roubo de cargas nas regiões visitadas, além das restrições tradicionais, tais como o número de veículos, janelas de tempo, a capacidade do veículo e tempo de ciclo dos veículos. O modelo desenvolvido é testado em um estudo de caso real, considerando uma empresa de distribuição de produtos farmacêuticos do Rio de Janeiro. As soluções de rota com e sem risco de roubo de carga são comparadas. O modelo é resolvido usando o software AIMMS, para análises com instância pequenas, e resolvidas executando a Metaheurística Simulated Annealing, para o estudo de caso, onde se utiliza de duas instâncias. / [en] The Vehicle Routing Problem (VRP) is a classic well-known combinatorial problem. This paper introduces a new factor in the VRP mathematical optimization model, considering restrictions that address the probability of cargo theft in the regions visited, beyond the traditional constraints such as the number of vehicles, time windows, the capacity of the vehicle and the vehicle s cycle time. The paper proposes a mixed integer linear model that minimizes total transportation costs and cargo theft costs. The model is tested in a real-life case study, a company that distributes pharmaceutical products in Rio de Janeiro. The route solutions with and without cargo theft risk are compared. The model is solved using AIMMS software for analysis with small instance, and resolved by running the Simulated Annealing Metaheuristic, for the case study, which uses two instances.

[pt] Sistemas de Medição de desempenho (SMDs) vem ganhando crescente destaque nos ambientes corporativo e acadêmico, tornando-se uma importante ferramenta para a gestão de operações. Contudo, ainda há uma carência de estudos de SMD contemplando a indústria automotiva, em particular, em elos específicos de sua cadeia de suprimentos como os associados aos terminais de veículos em áreas portuárias. A literatura acadêmica também carece de mais estudos com evidências empíricas sobre a aplicabilidade dos SMDs que, em sua maioria, concentram-se em metodologias de estudo de caso ou surveys. Neste contexto, o objetivo desta dissertação é desenhar um SMD, com foco no conjunto de indicadores de desempenho, para as operações de um terminal de veículos localizado no porto do Rio de Janeiro. A presente dissertação utiliza o método empírico de pesquisa-ação e apresenta as lições aprendidas no desenho do SMD que culminou no desenvolvimento de um Painel de Bordo experimental, abastecido com seis meses de dados reais. O SMD forneceu suporte a alta administração para tomadas de decisão, além de corroborar questões chaves da literatura referentes ao desenvolvimento do SMD, como a importância do apoio da alta administração, mitigação dos efeitos das limitações dos sistemas de informação, clareza e simplicidade no desenho do SMD de maneira que seja evitado o excesso de indicadores de desempenho no sistema. / [en] Performance Measurement Systems (PMSs) have gained increasing prominence in the corporate and academic environments, becoming an essential tool for operations management. However, there is still a lack of PMSs studies contemplating the automotive industry, particularly, in specific links of its supply chain such as those associated with vehicle terminals in port areas. The academic literature also lacks more studies with empirical evidence on the applicability of PMS, which mostly focuses on case study methodologies or surveys. Within this context, the objective of this dissertation is to design a PMS, focusing on the set of performance indicators, for the operations of a vehicle s terminal located in the port of Rio de Janeiro. This dissertation uses the empirical action-research method and presents the lessons learned in the design of the PMS, which culminated in the development of an experimental Maple Panel, supplied with six months of real data. The PMS provided support to top management for decision making, in addition to corroborating key issues in the literature regarding, like highlighting the importance of support from top management, mitigating the effects of the limitations of information systems, clarity and simplicity in the design of SMD in order to avoid excessive performance indicators in the system.

[pt] O estudo da dinâmica lateral é de grande importância para análise do comportamento de um veículo durante manobras e fundamental para a implementação de sistemas de controle de estabilidade e de trajetória em veículos autônomos. Nesse contexto, baseado em medições experimentais de um veículo militar de três eixos durante manobras de mudança dupla de faixa a diferentes velocidades, o presente trabalho apresenta métodos de identificação de sistemas para obtenção de modelos lineares por meio da ferramenta CONTSID (CONTinuous-Time System IDentification), disponível no MATLAB; de modelos não lineares baseados em Redes Neurais; e, por fim, a proposta de emprego de modelos híbridos com o intuito de minimizar o erro associado à primeira abordagem, somando-se ao modelo linear, o valor estimado do resíduo com a aplicação de redes neurais. Por se tratarem de modelos obtidos a partir de dados observados, como parâmetros de entrada e de saída do sistema, foram selecionados o ângulo do volante e a taxa de guinada do veículo, respectivamente. Com a utilização do dados observados, foi realizada a identificação das funções de transferência para cada velocidade, o que possibilitou a análise da influência dessa variável no comportamento dinâmico do sistema. Em seguida, empregou-se uma abordagem via redes neurais ao mesmo conjunto de dados, com a construção de arquiteturas distintas por meio da modificação do número de neurônios, número de camadas e função de ativação. Por fim, um modelo híbrido foi combinado utilizando-se a modelagem linear e não linear para obtenção de melhorias na resposta do modelo final estimado. De acordo com os resultados, as técnicas empregadas apresentaram viabilidade de aplicação e resultados satisfatórios, destacando-se o aprimoramento do modelo linear por meio de sua substituição pelo modelo híbrido baseado em redes neurais. Do exposto, objetiva-se destacar o potencial dos métodos apresentados de forma que, posteriormente, esses estudos possam ser aprofundados para implementação de malhas de controle veicular, com o intuito de contribuir com o aumento da segurança, melhoria do conforto e no desenvolvimento de veículos autônomos. / [en] The study of lateral dynamics is of great importance for the vehicle behavior analysis during turning maneuvers, and it is fundamental to stability or path control systems used in autonomous vehicles. In this context, based on experimental measurements of a three-axle military wheeled vehicle during double lane changes maneuvers at different speed, this work presents methods for the identification of linear models using the CONTSID (CONTinuous-Time System IDentification) toolbox, available in MATLAB; nonlinear models based on artificial neural networks; and, the application of hybrid models to reduce the error associated with the first approach, combining the linear model to the estimated error using neural networks. Since those are data-driven methods, as input and output parameters of the system, the wheel steering angle and the yaw rate of the vehicle were respectively selected. Using the CONTSID toolbox, the identification of the transfer functions for each speed was performed, making it possible to evaluate the influence of this variable in the system s dynamics behavior. Thereafter, a neural network approach was applied to the same data set, changing architecture s parameters, such as number of neurons, layers and the activation function. At last, a hybrid model approach was presented through the combination of previous linear and nonlinear approaches to improve the estimated model response. The proposed methods showed satisfatory results, highlighting the improvement in the linear model through its replacement by the hybrid model based on neural networks. Therefore, this work aims to show the potential of the methods presented, and posteriorly contribute to studies on the implementation of vehicle control systems to increase safety, improve comfort and in the development of autonomous vehicles.

[pt] O transporte escolar é fundamental para garantir o acesso e permanência dos alunos nas escolas públicas, principalmente nas áreas rurais, onde os estudantes estão localizados em uma grande área com baixa densidade e as estradas encontram-se em situações precárias. O presente trabalho tem como objetivo aplicar a metaheurística Iterated Local Search para o roteamento de 13.664 alunos da zona rural do estado do Rio de Janeiro. Para isso, considerouse o problema de roteamento de veículo escolares, do inglês School Bus Routing Problem (SBRP), com frota heterogênea e escola única, com o objetivo de minimizar o custo total considerando as restrições de capacidade dos veículos e distância máxima de percurso. Para aplicação do método, foram considerados os dados fornecidos pela Secretaria de Estado de Educação do Rio de Janeiro (SEEDUC-RJ). Os resultados são apresentados em dois cenários, o primeiro considera os dados de 79 rotas utilizadas pela SEEDUC-RJ para comparação dos resultados obtidos com o ILS. O método mostrou uma redução de 40,5 por cento no custo médio das rotas e 46 or cento na quilometragem média por aluno. O segundo cenário considera o roteamento da totalidade dos alunos, que foram divididos em 506 instâncias considerando escola e turno. A maior instância roteada possui 534 alunos. Os resultados consolidados por município são apresentados e mostram a concentração de municípios com maior custo médio por rota no noroeste fluminense. A implementação das rotas propostas pode trazer economia significativa com as despesas relacionadas ao transporte escolar rural, além de indicar um aumento no nível de serviço para os estudantes, com redução da quilometragem média por aluno. / [en] School transport is essential to ensure access and permanence of students in public schools, especially in rural areas, where students are located in a large area with low density and roads are in precarious conditions. This work aims to apply the Iterated Local Search metaheuristic to route 13.664 rural students in the state of Rio de Janeiro. For this, we considered the School Bus Routing Problem (SBRP), with heterogeneous fleet and single school, in order to minimize the total cost considering the vehicles capacity constraints and maximum travel distance. To apply the method, the data provided by Secretaria de Estado de Educação do Rio de Janeiro (SEEDUCRJ) were considered. The results are presented in two scenarios, the first considers data from 79 routes used by SEEDUC-RJ to compare the results obtained with the ILS. The method showed a reduction of 40.5 percent in the average cost of routes and 46 percent in the average mileage per student. The second scenario considers the routing of all students, who were divided into 506 instances considering school and shift. The largest routed instance has 534 students. The results consolidated by municipality are presented and show the concentration of municipalities with the highest average cost per route in northwestern Rio de Janeiro. The implementation of the proposed routes can bring significant savings with expenses related to rural school transport, in addition to indicating an increase in the level of service for students, with a reduction in the average mileage per student.

[pt] O desempenho de veículos automotivos é um importante atributo a ser avaliado quando motores de combustão interna e novos combustíveis estão sendo desenvolvidos. A previsão desse parâmetro também é de suma importância, uma vez que os testes de desempenho de automóveis em pista requerem prazos de realização e altos custos com equipamentos, aluguel da pista, contratação de pessoas e deslocamento de veículos e combustíveis. Além disso, seus resultados são diretamente afetados por irregularidades na superfície da pista e variações nas condições climáticas, como pressão ambiente, temperatura, umidade do ar e velocidade do vento. Assim, este trabalho tem como objetivo utilizar os dados coletados em testes de bancada com um motor de combustão interna com a finalidade de modelar os testes de retomada de velocidade de um automóvel convencional leve. A metodologia proposta simula a força de tração nas rodas a partir do torque medido no dinamômetro do motor ou a partir das curvas de pressão no interior da câmara de combustão com o auxílio de modelos de atrito para motores de ignição por centelha. Para validar o modelo proposto, foi necessário realizar testes de retomada de velocidade com o carro em um dinamômetro de chassi. Além disso, foram utilizadas sete misturas diferentes de etanol e gasolina, e concluiu-se que o etanol anidro puro promoveu maior capacidade de aceleração na maioria dos experimentos, mas apresentou maior consumo de combustível. Os combustíveis hidratados reduziram o desempenho, mas melhoraram a eficiência global. As simulações demonstraram alta precisão em relação ao experimento, com média da diferença do tempo de recuperação da velocidade de 0,51 segundos e desvio padrão de 0,078. Além disso, as simulações de desempenho de aceleração tiveram erros menores que 5,25 por cento. Além disso, a realização desses testes em laboratório tem a vantagem de um maior controle das condições ambientais da sala e dos parâmetros de operação do motor. / [en] Vehicle performance is an important feature to be evaluated when internal combustion engines and new fuels are being developed. Predicting this parameter is also of great significance, once track testing requires long periods of time to be done and high costs with equipment, rental of the track, hiring people and displacement of vehicles and fuels. In addition, their results are directly affected by track surface irregularities and variations in weather conditions such as ambient pressure, temperature, air humidity and wind speed. Thus, this work aims to use collected data in bench tests with an internal combustion engine in order to modeling an automobile speed recovery time. The proposed methodology simulates the traction force on the wheels based on the measured torque in engine dynamometer or from the pressure curves inside the combustion chamber with the aid of friction models for spark ignition engines. In order to validate the proposed model, it became necessary to perform speed recovery tests with the car on a chassis dynamometer. Also, seven different mixtures of ethanol and gasoline were used, and it was concluded that pure anhydrous ethanol promoted a higher acceleration capacity in most of the experiments but it had higher fuel consumption. Hydrated fuels reduced performance but improved global efficiency. The simulations demonstrated a high precision in relation to the experiment, with a speed recovery time diference average of 0.51 seconds and standard deviation of 0.078. Also, the acceleration performance simulations had errors smaller than 5.25 percent. In addition, doing these tests in laboratory has the advantage of a greater control of the room ambient conditions and the engine operating parameters.

[pt] Na atualidade, as organizações públicas e privadas buscam otimizar seus processos de modo que, estes garantam a qualidade dos serviços e o retorno sobre o capital investido nas diversas operações que estão envolvidas. Com isso, as organizações que não se preocupam em desenhar seus processos com eficácia e eficiência, estarão sujeitas a falhas, onerando assim os custos de operação. O estudo em questão propõe uma política de atendimento às demandas de manutenção e a utilização de uma ferramenta de roteirização diária no desempenho das operações do setor de manutenção de uma universidade pública do estado de Minas Gerais. O Problema de Roteirização de Veículos (PRV), do inglês Vehicle Routing Problem (VRP), como é conhecido na literatura, é definido como o atendimento a pontos de demanda geograficamente dispersos, por intermédio de uma frota de veículos disponíveis que, em geral, partem e retornam a um depósito central. O PRV tem como objetivo encontrar rotas viáveis com um menor custo que respeite as restrições operacionais, como duração da jornada de trabalho, capacidade dos veículos, duração das rotas, entre diversas outras. No trabalho será proposta uma metodologia que sugere uma nova política de distribuição de profissionais e materiais necessários para realização dos atendimentos às demandas de manutenção das unidades internas e externas da universidade e faz uso de um software de solução do PRV para verificar o desempenho das políticas propostas. Os resultados do estudo para as estratégias propostas apresentaram reduções significativas, variando de 17,86 porcento a 66,27 porcento do custo mensal, além de oportunidades de ganhos operacionais frente ao cenário atual. Espera-se que o software de PRV seja utilizado na programação diária dos roteiros dos veículos do setor. / [en] Currently, public and private organizations seek to optimize their process-es in order to guarantee the quality of services and the return on capital invested in the various operations that are involved. As a result, organizations that are not concerned with designing their processes effectively and efficiently, will be sub-ject to failures, thus increasing operating costs. The study in question proposes a policy to meet maintenance demands and the use of a daily routing tool in the performance of operations in the maintenance sector of a public university in the state of Minas Gerais. The Problema de Roteamento de Veículos (PRV), from the English Vehicle Routing Problem (VRP), as it is known in the literature, is defined as the service to meet geographically dispersed demand points, through a fleet of available vehicles that, in general, depart and return to a central depot. The VRP aims to find viable routes at a lower cost that respects operational re-strictions, such as working hours, vehicle capacity, duration of routes, among others. In the work, a methodology will be proposed that suggests a new policy for the distribution of professionals and materials needed to fulfill the demands of maintenance of the university s internal and external units and makes use of a VRP solution software to verify the performance of the proposed policies. The results of the study for the proposed strategies showed significant reductions, varying from 17.86 percent to 66.27 percent of the monthly cost, in addition to opportunities for operational gains compared to the current scenario. It is expected that the VRP software will be used in the daily programming of the routes for vehicles in the sector.