Analista Sistemas

XXXVIII SIMPÓSIO BRASILEIRO DE PESQUISA OPERACIONAL
Pesquisa Operacional na Sociedade: Educação, Meio Ambiente e Desenvolvimento

12 a 15/09/06 Goiânia, GO

UM ALGORITMO DE BUSCA TABU ADAPTATIVO APLICADO A
PROBLEMAS DE ROTEAMENTO DE VEÍCULOS COM PEDIDOS DE
COLETA E ENTREGA
Fermín Alfredo Tang Montané
Universidade Cândido Mendes - Campos.
Rua Anita Peçanha, 100, Parque São Caetano
CEP 28040320, Campos dos Goytacazes, RJ - Brasil
E-mail: [e-mail]

RESUMO
Variantes do problema de roteamento de veículos clássico consideram clientes que fazem pedidos de coleta e entrega, simultâneos ou não. As entregas são realizadas a partir de um único depósito no inicio de cada rota, enquanto que as coletas são conduzidas até o depósito no fim da rota. Uma característica deste tipo de problemas é que a carga do veículo em uma rota qualquer é composta por pedidos de entrega e coleta.
No presente artigo descreve-se um algoritmo de busca tabu para resolver estes problemas.
O algoritmo é uma extensão de um trabalho anterior que incorpora um mecanismo adaptativo para guiar a busca no espaço de soluções. Este mecanismo consiste em identificar padrões na trajetória de busca e em perturbar os valores dos parâmetros de busca tabu de acordo com o padrão observado. Resultados computacionais são reportados para um conjunto de 640 problemas teste com entre 50 e 100 clientes.
PALAVRAS CHAVE. Roteamento de Veículos. Busca Tabu Adaptativa. Pedidos de Coleta e Entrega. Metaheurísticas.

ABSTRACT
Variations of the classical Vehicle Routing Problem (VRP) consider clients that require pick-up and/or delivery service, simultaneously or not. Deliveries are supplied from a single depot at the beginning of the vehicle’s service, while pick-up loads are taken to the same depot at the conclusion of the service. One important characteristic of this type of problems is that a vehicle’s in any given route is a mix of pick-up and delivery loads.
In this paper we