Uma proposta de solução para o problema de roteamento de veículos com frota heterogênea e janelas temporais positivas e negativas esparsas

Abstract

Um dos assuntos mais estudados e desafiadores da Pesquisa Operacional é o problema de roteamento de veículos. Neste problema, um conjunto de veículos é alocado para distribuir produtos em uma região, cada um obedecendo a um problema de caixeiro viajante. De valor teórico e operacional, é uma peça chave para a sobrevivência de várias empresas de transporte, que competem entre si em um ambiente árduo, normalmente próximo de concorrência perfeita. Sob estas circunstâncias todos os métodos que minimizem o custo destas empresas, melhorem o serviço prestado e contribuam para sua continuidade, tendem a somente trazer benefícios para todas as partes. É por meio do transporte que os produtos e insumos alcançam os seus destinos, e diminuir o esforço e o custo necessário para cumprir esta função colabora significativamente para tornar, em última análise, o país mais forte economicamente, eficaz e eficiente em seus processos produtivos.O problema de roteamento de veículos sofreu, desde o seu princípio, várias adaptações para torná-lo mais realista, ajustado e aplicável às necessidades das empresas de transporte. Nesta tese apresenta-se um problema de roteamento de veículos com frota heterogênea e janela de tempo. É um problema habitual e que determina fundamentalmente o lucro de empresas de transporte que se prestam unicamente a este fim. O modus operandi de uma empresa de transporte do sul de Santa Catarina foi estudado e as condições a ela impostas pela cadeia de suprimento a jusantee a montante foram avaliadas. Por fim, uma proposta de resolução do problemade roteamento de veículos com frota heterogênea e janelas de tempo positivas e negativas esparsas é apresentada, utilizando algoritmos genéticos aninhados. A heurística em questão é simples de ser compreendida e implementada, gera resultados de boa qualidade e permite a qualquer empresa de transporte, análoga à estudada, ter suporte computacional em suas operações, permitindo a comparação dos resultados que obtém com os heurísticos calculados.

Abstract : One of the most studied and challenging subjects of Operational Research is the vehicle routing problem. In this problem, a set of vehicles is allocated to distribute products in a region, each obeying a traveling salesman problem. Of theoretical and practical value, it is a key element for the survival of several transportation companies, which compete with each other in an arduousenvironment, usually close to perfect competition. Under these circumstancesall methods that minimize the cost of these companies, improve the serviceprovided and contribute to its continuity, tend to bring profits to all actors.It is through transportation that manufactured and raw products reach theirdestinations, consequently reducing effort and costs required to fulfill thisfunction significantly contributes to make the economy stronger, more efficientand effective in its production processes. The vehicle routing problem has undergone several adaptations from the outset to make it more realistic, adjusted and applicable to the needs of transport companies. This thesis presents a vehicle routing problem with heterogeneous fleet and time window. It is a common problem and fundamentally determines the profitability of transport companies that are uniquely established for this purpose. The modus operandi of a transport company in the south of Santa Catarina, Brazil, was studied and the conditions imposed by the downstream and upstream supply chain were evaluated. Eventually, is proposed a solution model to the vehicle routing problem with sparse time windows and heterogeneous fleet using nested genetic algorithms, which helps to give computational support to operations, and make possible to compare the results the company produces with the threshold conceived by the heuristics.