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

• Processo: 03/04237-3
• Modalidade de apoio: Bolsas no Brasil - Iniciação Científica
• Data de Início da vigência: 01 de agosto de 2003
• Data de Término da vigência: 31 de julho de 2004
• Área de 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): Problemas de roteamento de veículos Meta-heurística
• Palavra(s)-Chave do Pesquisador: Busca Em Vizinhanca | Grasp | Metaheuristicas | Roteamento De Veiculos | Vizinhancas

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 sequê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)