Busca avançada
Ano de início
Entree

Busca em vizinhança para problemas de roteamento de veículos

Processo: 03/04237-3
Linha de fomento:Bolsas no Brasil - Iniciação Científica
Vigência (Início): 01 de agosto de 2003
Vigência (Término): 31 de julho de 2004
Área do conhecimento:Engenharias - Engenharia de Produção - Pesquisa Operacional
Pesquisador responsável:Vinicius Amaral Armentano
Beneficiário:Marcelo Mitsumoto
Instituição-sede: Faculdade de Engenharia Elétrica e de Computação (FEEC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brasil
Assunto(s):Meta-heurística   Problemas de roteamento de veículos

Resumo

O projeto aborda o problema de roteamento de veículos com e sem janelas de tempo. O objetivo é determinar uma rota para cada veículo e a seqüência de visita aos clientes de modo a minimizar o número de rotas, o custo de transporte é satisfazer as seguintes restrições operacionais: período do dia (janela de tempo) estabelecido pelo cliente para entrega do pedido, capacidade do veículo expressa em termos de volume, peso ou número de paletes, e tempo total de duração das rotas. Devido a sua complexidade combinatória utilizam-se metaheurísticas para obter soluções de alta qualidade em tempo computacional razoável. Diversas vizinhanças foram propostas na literatura para utilização nas metaheuristicas mais bem sucedidas para este problema: busca tabu e algoritmos genéticos. O objetivo deste trabalho é implementar as diversas vizinhanças propostas e analisá-las de acordo com os seguintes fatores: complexidade, esforço computacional, grau de dificuldade de implementação, eficiência e adequação a diferentes classes de problemas. Para avaliar as vizinhanças utilizaremos a metaheurística de múltiplos reinícios GRASP onde cada iteração consiste de duas fases: construtiva e busca em vizinhança. Esta metaheurística é simples e foi aplicada com sucesso em diversos problemas de otimização combinatória. (AU)