Le transport de marchandises dans les zones urbaines est un sujet important de nos jours. Le transport est une activité vitale pour les villes, mais implique pollution, congestion, accidents. La logistique urbaine vise à optimiser les processus logistiques et de transports urbains en tenant compte des aspects environnementaux et sociaux. Cette thèse traite de cette thématique et fait partie du projet MODUM.MODUM vise à étudier un système de livraison basé sur des centres de distribution urbains. Nous présentons une classification et une analyse des mouvements de marchandises et des problèmes de tournées de véhicules (VRP) associés.La deuxième partie propose une revue complète des travaux de recherche traitant des problème VRP avec excursions multiples (MTVRP). Le MTVRP est une extension du VRP où les véhicules sont autorisés à effectuer plusieurs tournées. Nous proposons une heuristique pour le MTVRP qui est par la suite adaptée pour un problème plus riche, le MTVRP avec fenêtres de temps et dates de disponibilité. Il s'agit d'une variante du MTVRP où à chaque client est associée une fenêtre de temps et à chaque marchandise une date de disponibilité qui représente l'instant où elle devient disponible au dépôt.Par la suite, nous étudions une variante du MTVRP où les marchandises sont classées par types de produits qui ne peuvent pas être transportés dans le même véhicule. Une analyse est effectuée pour montrer l’avantage des tournées multiples pour le problème de dimensionnement des flottes.Enfin, nous décrivons le problème de tournées qui se pose dans MODUM et le simulateur qui est développé pour évaluation du système. / Transportation of merchandise in urban areas has become an important nowadays topic. In fact, transportation is a vital activity for each city, but entail pollution, congestion, accidents.City logistics aims at optimizing the whole urban logistics and transportation process, taking into account environmental and social aspects. This thesis, that is part of the MODUM project, finds its location in this area of research. In particular, MODUM aims at studying a delivery system based on City Distribution Centers.We first present a classification and an analysis of urban good movements and routing problems peculiar to metropolitan areas. A second survey proposes a complete collection of articles that has been done on the Multi Trip Vehicle Routing Problem (MTVRP). The MTVRP is an extension of the Vehicle Routing Problem (VRP) where vehicles are allowed to perform several trips.We propose an efficient heuristic for the MTVRP that is, in a subsequent step, adapted to a new routing problem, the MTVRP with Time Windows and Release Dates (MTVRPTWR). It is a variant of the MTVRP where each customer is associated with a time window and each merchandise is associated with a release date that represents the instant it becomes available at the depot.We, then, study a variant of the MTVRP where goods belong to different commodities that cannot be transported at the same time by the same vehicle. An analysis is conducted on the benefits of the multi-trip aspect in fleet dimensioning problems.Finally we describe the complex routing problem that arises in MODUM and the simulator that is developed to evaluate the performances of the system.

Orientador: Prof. Dr. Cláudio Nogueira de Meneses / Dissertação (mestrado) - Universidade Federal do ABC, Programa de Pós-Graduação em Ciência da Computação, 2016. / Beyond a complex real world system composed by a set of sophisticated machines and qualied human resources distributed around manufacturing environment, the Auto In- dustry needs a little more to allow their products to reach the nal costumers. Loading vehicles like cars, trucks and vans into auto-carriers and designing routes to delivery sub- sets of vehicles to auto dealers according to their orders are relevant tasks in automotive value chain performed by transportation companies. Given the set of complex constraints related to diferent vehicle models (with diferent dimensions) to be feasibly loaded into dierent auto-carrier models plus the auto-carrier eet routing task, transportation com- panies must explore strong computational alternatives to address this optimization prob- lem. In fact, we explore in this dissertation a real world complex problem composed by two sub-problems, both belonging to NP-hard class: routing and loading. After formally dening the tackled problem, we adopt, in this dissertation, a previously studied procedure based on enumeration techniques for loading task and we propose an alternative approach employing Asynchronous Teams concept, which combines local search algorithms in order to cooperate to each other to try to resolve the routing sub-problem. Setting the results provided by our implementation of Iterated Local Search (ILS) approach (already proposed in literature for solving the routing sub-problem) as benchmark, we propose computational experiments considering real-world instances, to compare performance of ILS to ve vari- ants of our Asynchronous Teams implementations. Final results evidence the power of this proposed alternative approach for founding quality solutions and its exibility to easily assume diferent configurations.

Made available in DSpace on 2016-06-02T19:52:00Z (GMT). No. of bitstreams: 1 DissRH.pdf: 983555 bytes, checksum: 2f6efc30e82bc4d5f60bb2893dd0bb3f (MD5) Previous issue date: 2004-12-16 / This research consists of the development of algorithms to solve the Periodic Vehicle Routing Problem (PVRP), wich has not received a great deal of attention in the O.R. literature. The objective of the PVRP is to elaborate a set of routes to attend to customers demand along a planning horizon. Each customer roquests that the visits occur in a combination predefined of days. Two heuristics were developed for the PVRP. In the first heuristic, three types of initial solution construction are used to attribute the customers to days. After that, visiting day combinations are changed in order to improvr the solution. The search process is controlled by an adaptative tabu heuristic from the literature which determines intensification and diversification actions, applied for each day in the period. The second heuristic incorporates a similar approach for the period as a whole. Computacional results show that this approach leads to good solution. / Esta pesquisa consiste no desenvolvimento de algoritmos para resolver o Problema de Roteamento de Veículos Periódico (PRPV), o qual tem sido pouco abordado na literatura de Pesquisa Operacional. O objetivo do PRVP é elaborar um conjunto de rotas para atender à demanda de cliente ao longo de um horizonte de planejamento. Cada cliente requer que as visitas aconteçam em uma combinação predefinida de dias. Foram desenvolvidas duas heurísticas para o PRPV, chamadas de VERSÃO 1 e VERSÃO 2. Na VERSÃO 1 são utilizados três tipos de construções iniciais para atribuir os clientes aos dias. Em seguida, são realizadas mudanças de combinações de dias de visitas na tentativa de melhorar a solução. O processo de busca por soluções é controlado por heurísitca tabu adaptativa da literatura que determina as ações de intensificação e diversificação, aplicado a cada dia do período. A VERSÃO 2 incorpora uma abordagem similar para o período como um todo. Resultados computacionais indicam que esta abordagem leva a soluções de boa qualidade.

Made available in DSpace on 2016-06-02T19:52:05Z (GMT). No. of bitstreams: 1 6045.pdf: 14667118 bytes, checksum: f13a2c0983ea271f2e60ed298b158806 (MD5) Previous issue date: 2014-05-26 / Agência Nacional de Petróleo / This work studies the ship routing and scheduling problem in oil transportation from offshore platforms to inland terminals. It is motivated by a real situation in a Brazilian oil company. Brazil is one of the world's greatest oil producers and has around 80% of its oil explored in offshore mode. Thus, transportation costs play an important role in achieving operational excellence, and the recent growth trends for oil exploration in Brazil has transformed its operations and demanded agile and effective decision support systems for addressing the oil sector dynamism. This work's goal consists in developing and applying an optimization-based approach using a mixed integer linear programming model in real decision-making situations, along with a solution method based on mathematical programming (MIP-heuristics) in order to solve the model, such as relax-and-fix. The proposed model is inspired in a problem formulation for pickup and delivery with time windows (PDPTW) and heterogeneous fleet, where costs incurred for fuel consumption and fleet contracts is the objective function to be minimized. The pickup and delivery pairs are predetermined and the model's main decision refers to ship allocation to these pairs compounding a route. Furthermore, some additional constraints are modeled and proposed, such as terminal access and platform mooring limitation according to ship types, as well as product blend incompatibility. The model was implemented in a modeling language along with an optimizarion software. Computational experiments with the model and the heuristics are presented for different data sets supplied by the case study company. These experiments show the potential benefits of this approach for finding good solutions for the problem as well as the dificulty in finding solutions for realistic instances due to its NP-hard characteristics. / Este trabalho estuda o problema de roteirização e programação de navios que realizam o escoamento de petróleo das plataformas marítimas para terminais terrestres, motivado por uma situação real de uma empresa brasileira da indústria petrolífera. O Brasil é um dos maiores produtores mundiais de petróleo, e cerca de 80% de seu petróleo é explorado no mar. Dentro deste contexto, os custos de transporte desempenham um papel importante na busca pela excelência operacional e as tendências de crescimento da exploração de petróleo no Brasil têm tornado as operações mais complexas e demandantes de sistemas de apoio à decisão ágeis e eficazes que contemplem o dinamismo do setor petrolífero. O objetivo deste trabalho consiste em desenvolver e aplicar uma abordagem de otimização baseada em um modelo de programação linear inteira mista em situações reais de tomada de decisão, em conjunto com métodos de solução baseados em programação matemática (MIP-Heuristics) para resolver o modelo, como relax-and-fix. O modelo proposto é inspirado em uma formulação de problemas de coleta e entrega com janelas de tempo (pickup and delivery with time windows PDPTW) e frota heterogênea, no qual busca-se minimizar os custos decorrentes do consumo de combustível dos navios e contratos de afretamento. O modelo é do tipo origem-destino, no qual os pares coleta/entrega são pré-determinados e a decisão do modelo refere-se à alocação de navios para os diferentes pares, compondo uma rota. Além disso, são propostas restrições adicionais que contemplam limitações de acesso a terminais e de atracação em plataformas de acordo com os tipos de navio, além da incompatibilidade de mistura de produtos, entre outros. O modelo foi implementado utilizando uma linguagem de modelagem em conjunto com um software de otimização. Experimentos computacionais com o modelo e as heurísticas são apresentados para diferentes conjuntos de dados fornecidos pela empresa e comprovam o potencial das abordagens para encontrar boas soluções para o problema, mas também suas dificuldades para encontrar soluções para exemplares de tamanho realista, por tratar-se de um problema NP-difícil do ponto de vista de teoria de complexidade.

Submitted by Fernando Souza (fernandoafsou@gmail.com) on 2017-08-15T11:46:12Z No. of bitstreams: 1 arquivototal.pdf: 884446 bytes, checksum: 92314027dddef8365b4a2e655b65bd78 (MD5) / Made available in DSpace on 2017-08-15T11:46:13Z (GMT). No. of bitstreams: 1 arquivototal.pdf: 884446 bytes, checksum: 92314027dddef8365b4a2e655b65bd78 (MD5) Previous issue date: 2016-05-20 / The Static Bike Rebalancing Problem (SBRP) is a recent problem motivated by the task of repositioning bikes among stations in a self-service bike-sharing systems. This problem can be seen as a variant of the one-commodity pickup and delivery vehicle routing problem, where multiple visits are allowed to be performed at each station, i.e., the demand of a station is allowed to be split. Moreover, a vehicle may temporarily drop its load at a station, leaving it in excess or, alternatively, collect more bikes (even all of them) from a station, thus leaving it in default. Both cases require further visits in order to meet the actual demands of such station. This work deals with a particular case of the SBRP, in which only a single vehicle is available and the objective is to nd a least-cost route that meets the demand of all stations and does not violate the minimum (zero) and maximum (vehicle capacity) load limits along the tour. Therefore, the number of bikes to be collected or delivered at each station should be appropriately determined in order to respect such constraints. This is a NP-Hard problem since it contains other NP-Hard problems as special cases, hence, using exact methods to solve it is intractable for larger instances. Several methods have been proposed by other authors, providing optimal values for small to medium sized instances, however, no work has consistently solved instances with more than 60 stations. The proposed algorithm to solve the problem is an iterated local search (ILS) based heuristic combined with a randomized variable neighborhood descent (RVND) as local search procedure. The algorithm was tested on 980 benchmark instances from the literature and the results obtained are quite competitive when compared to other existing methods. Moreover, the method was capable of nding most of the known optimal solutions and also of improving the results on a number of open instances. / O Problema do Rebalanceamento Est atico de Bicicletas (Static Bike Rebalancing Problem, SBRP) e um recente problema motivado pela tarefa de reposicionar bicicletas entre esta c~oes em um sistema self-service de compartilhamento de bicicletas. Este problema pode ser visto como uma variante do problema de roteamento de ve culos com coleta e entrega de um unico tipo de produto, onde realizar m ultiplas visitas a cada esta c~ao e permitido, isto e, a demanda da esta c~ao pode ser fracionada. Al em disso, um ve culo pode descarregar sua carga temporariamente em uma esta c~ao, deixando-a em excesso, ou, de maneira an aloga, coletar mais bicicletas (at e mesmo todas elas) de uma esta c~ao, deixando-a em falta. Em ambos os casos s~ao necess arias visitas adicionais para satisfazer as demandas reais de cada esta c~ao. Este trabalho lida com um caso particular do SBRP, em que apenas um ve culo est a dispon vel e o objetivo e encontrar uma rota de custo m nimo que satisfa ca as demandas de todas as esta c~oes e n~ao viole os limites de carga m nimo (zero) e m aximo (capacidade do ve culo) durante a rota. Portanto, o n umero de bicicletas a serem coletadas ou entregues em cada esta c~ao deve ser determinado apropriadamente a respeitar tais restri c~oes. Trata-se de um problema NP-Dif cil uma vez que cont em outros problemas NP-Dif cil como casos particulares, logo, o uso de m etodos exatos para resolv^e-lo e intrat avel para inst^ancias maiores. Diversos m etodos foram propostos por outros autores, fornecendo valores otimos para inst^ancias pequenas e m edias, no entanto, nenhum trabalho resolveu de maneira consistente inst^ancias com mais de 60 esta c~oes. O algoritmo proposto para resolver o problema e baseado na metaheur stica Iterated Local Search (ILS) combinada com o procedimento de busca local variable neighborhood descent com ordena c~ao aleat oria (randomized variable neighborhood descent, RVND). O algoritmo foi testado em 980 inst^ancias de refer^encia na literatura e os resultados obtidos s~ao bastante competitivos quando comparados com outros m etodos existentes. Al em disso, o m etodo foi capaz de encontrar a maioria das solu c~oes otimas conhecidas e tamb em melhorar os resultados de inst^ancias abertas.

A Roteirização de Veículos desempenha papel fundamental nos processos modernos de distribuição de produtos e realização de serviços. A atual disseminação de recursos de tecnologia de informação e comunicação, de forma confiável e economicamente acessível, permite trabalhar com informações em tempo real e melhoram os padrões de nível de serviço associados. O presente trabalho apresenta uma solução para roteirização de veículos cujas equipes de bordo realizam serviços que justificam seu deslocamento, uma vez que as demandas estão geograficamente dispersas. Tais demandas são, em parte, conhecidas antes do despacho (permitem programação antecipada) dos veículos e suas equipes; outra parte surge durante a jornada de trabalho. Como exemplos podem-se citar os casos de serviços de montagem e manutenção de instalações, equipamentos, engenharia e inspeção de tráfego, policiamento etc. Trata-se da aplicação da roteirização parcialmente dinâmica, conforme Larsen (2000), cujas bases foram definidas por Psaraftis (1988,1995), Bertsimas et al (1993) no problema DTRP (Dynamic Travelling Repairman Problem). A função objetivo apresenta uma combinação de minimização dos custos de deslocamento, para os pedidos de serviços conhecidos antes da saída dos veículos e de minimização do tempo de resposta (chegada no local do cliente ou da ocorrência) para os casos de pedidos imediatos ou emergenciais. A solução do problema envolve um modelo computacional de testes e avaliação, heurística de Clarke e Wright (1964) para formação das rotas estáticas, no Método Húngaro (Kuhn, 1955) para designar o veículo que resulta no menor tempo de resposta no atendimento a um pedido emergencial e a heurística de Clarke e Wright modificada na otimização do restante dos pedidos quando o veículo voltar a sua rota original. O modelo computacional foi testado em uma empresa de manutenção de elevadores na cidade de São Paulo, Brasil, onde demonstrou resultados comparativamente melhores em relação ao sistema de roteirização utilizado atualmente pela empresa. / The Vehicle Routing Problem plays a critical role on modern processes related to physical distribution of goods and services. The present expansion of information and communication technology in a reliable, economic and accessible way allows real time information and requires the utilization of appropriate tools for real time decisions resulting in significant improvements in quality and service level related to dynamic vehicle routing. A dynamic routing problem is presented, in which vehicles serve geographic dispersed service demands that justify their movement in a fixed area. Such service demands are partially known before vehicles dispatching (allowing prior programming) whilst others are known during the work journey. As examples, one can mention cases concerning installation and maintenance of utilities, equipment, engineering and surveillance services that refer to applications of Partially Dynamic Routing according to Larsen (2000), the groundings of which were defined by Psaraftis (1988,1995), Bertsimas et al (1993) in the Dynamic Travelling Repairman Problem (DTRP). The objective function is a combination of the minimization of movement costs to serve the prior demands and the minimization of time to reach (time to response) Dynamic-or-emergency-demand sites. The proposed solution involves a computational model for testing and evaluating a set of heuristics and methods comprising the Clarke and Wright (1964) Heuristic to compose the static routes, the Hungarian Method (Kuhn, 1955) to assign vehicles to the dynamic demands that produces the lowest response time and, finally, a Clarke and Wright Modified Heuristic used to optimize the remainder of the route when each diverted vehicle returns to its static route. The Computational Model was applied to a lift maintenance company located in the city of São Paulo (Brazil) demonstrating better results as compared to the present routing system.

O trabalho apresenta o desenvolvimento e a aplicação de um modelo de localização de centros intermediários de consolidação e redistribuição de cargas em um ambiente urbano brasileiro. O método integra o TransCAD e o OpenSolver e é aplicado à cidade de Curitiba, uma das dez mais populosas do Brasil. O método proposto é caracterizado como um modelo de localização-roteirização baseado em agrupamento e subsequente roteirização, identificado na literatura por cluster-first routesecond; a adoção deste ordenamento permite tratar o problema para o atendimento de muitos estabelecimentos, como os até 65 mil em alguns dos cenários no estudo de caso de Curitiba. Cada agrupamento representa os pontos a serem visitados em uma única viagem e o processo inicial tenta minimizar as distâncias entre os estabelecimentos de cada grupo; na fase seguinte o melhor roteiro é computado para cada grupo; a terceira etapa consiste em calcular, para cada grupo e candidato, a distância total percorrida na viagem; por fim, a implantação ou não dos candidatos a centros de distribuição é obtida com a minimização em um modelo de programação linear inteira dos custos de aquisição e de operação dos centros de distribuição e dos custos de transportes. A dissertação também aborda a crescente percepção da importância da logística urbana à qualidade de vida nas cidades onde o adensamento populacional acirra a disputa pelo espaço viário e o conceito de City Logistics, que delineia entre outras medidas o ambiente cooperativo no qual implantação de centros de distribuição urbanos deve ocorrer. / This work presents the development and application of a model for the location of intermediary consolidation and redistribution freight centers in Brazilian cities. The method integrates TransCad and OpenSolver, and its use was evaluated with data from the City of Curitiba one of the ten largest in Brazil. The proposed method is characterized as a location-routing model based on clustering and subsequent tour building known as cluster-first route-second. This enables dealing with problem instances containing as many as 65 thousand customers. Each cluster comprehends the points visited on a single trip and the initial process minimizes the distances between customers; the routes are calculated in the next phase and the third step consists in computing the total distance covered in each trip for every cluster and every candidate; finally, the implementation of each distribution center candidate is decided by minimizing the costs of acquisition, operation and distribution, using an integer linear programming model. The dissertation also highlights the growing realization of the importance of urban freight transport to quality of life, especially in cities where increasing population density intensifies the competition for road space, and City Logistics concepts, that outline among other measures the cooperative environment where implementation of urban distribution centers should occur.

A concern of logistics management is the correct and efficient use of the available fleet. The central focus of fleet management is determining the routes that will be used in customer service and the efficient allocation of available resources (vehicles). The correct fleet management can generate a competitive advantage. There is a problem in the Operations Research dedicated to working this type of situation, the Vehicle Routing Problem (VRP). The VRP tries to generate the most economical route to efficient use of the available fleet. The case study discussed in this work was a particular situation VRP where there is a heterogeneous fleet and where the collections and deliveries of passengers are carried at separate times. To solve this problem we designed a Genetic Algorithm. Additionally, three different crossover operators were tested in the search for better results. At the end of the study, the Genetic Algorithm was capable of solving the problem in a short time and finding the most economical way to generate routes, using efficiently the fleet and fulfilling all requests. / Uma das preocupaÃÃes da gestÃo logÃstica à a correta e eficiente utilizaÃÃo da frota disponÃvel. O foco central da gestÃo da frota està em determinar as rotas que serÃo utilizadas no atendimento aos clientes e a alocaÃÃo eficiente dos recursos (veÃculos) disponÃveis. A gestÃo correta da frota pode gerar um diferencial competitivo. Existe na Pesquisa Operacional um problema dedicado a trabalhar este tipo de situaÃÃo, denominado Problema de Roteamento de VeÃculos (PRV). O PRV procura gerar a rota mais econÃmica com utilizaÃÃo eficiente da frota disponÃvel. No estudo de caso, realizado neste trabalho, foi abordada uma situaÃÃo particular do PRV onde hà uma frota heterogÃnea e as coletas e entregas de passageiros sÃo realizadas em momentos separados. Para a resoluÃÃo deste problema foi desenvolvido e implementado um Algoritmo GenÃtico (AG). Adicionalmente, trÃs operadores de cruzamento diferentes foram testados na busca dos melhores resultados encontrados pelo AG. Ao final, o Algoritmo GenÃtico conseguiu se mostrar capaz de resolver o problema em tempo hÃbil e de maneira a gerar rotas mais econÃmicas, utilizando eficientemente a frota e atendendo todas as solicitaÃÃes.

[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.