Pesquisa operacional

Introdução aos Conceitos de Problemas de Transporte e Roteamento de Veículos
Alexandre da Costa1

1

Acadêmico do Curso de Matemática - Centro de Ciências Exatas e Tecnológicas da Universidade Estadual do Oeste do Paraná Caixa Postal 711 - 85819-110 - Cascavel - PR - Brasil [e-mail] Resumo. Este trabalho aborda os problemas de transporte e de roteamento de veículos na perspectiva de levar ao conhecimento, de quem venha a se interessar pelo assunto, as dificuldades que se encontra e as estratégias abordadas para se modelar problema como esses. Problemas de roteamento de veículos pertencem a uma classe particular dos problemas de transporte e a programação linear não é capaz de lhes oferecer, sozinha, resultados eficazes. Utiliza-se, então de métodos heurísticos para se obter uma solução otimizada. Além disso, o tratamento dado a cada tipo de problema, por mais semelhantes que estes possam ser, é bastante diversificado, variando não apenas nos algoritmos utilizados, mas também no tipo de tratamento dado às particularidades próprias de cada um [BODIN, 1983].

Palavras Chaves. Problemas de Transporte, Roteamento de Veículos, Programação
Linear, NP-hard.

1. Problemas de Transporte
Geralmente os problemas de transporte requerem uma otimização de seus processos com objetivo de minimizar os gastos. Procura-se assim encontrar a forma mais econômica de distribuir um bem disponível em certa quantidade, não necessariamente em um mesmo local, para outros locais onde se exige determinada quantidade desse bem. O Problema do Transporte é muito usado em exemplos de Problemas de PL por sua grande aplicação prática e por ser alvo de estudado de vários investigadores, embora tenha sido George Dantzig o primeiro a estabelecer a sua formulação como modelo de PL e a propor um método sistemático de resolução, conhecido como método simplex. [CANAVARRO, 2005] Alguns problemas desse tipo, devido as suas estruturas particulares, podem ser resolvidos com métodos