Roteamento de veículos de carga com restrições de empacotamento

• Processo: 09/01129-1
• Modalidade de apoio: Bolsas no Brasil - Doutorado
• Data de Início da vigência: 01 de junho de 2009
• Data de Término da vigência: 31 de janeiro de 2010
• Área de conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
• Pesquisador responsável: Flávio Keidi Miyazawa
• Beneficiário: Thiago Alves de Queiroz
• Instituição Sede: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brasil
• Assunto(s): Meta-heurística Problemas de roteamento de veículos Otimização combinatória Métodos de geração de colunas Algoritmos Veículos de carga
• Palavra(s)-Chave do Pesquisador: Algoritmos Exatos | Empacotamento Tridimensional | Geração de Coluna | Metaheurísticas | Roteamento de Veículos de Carga | Otimização Combinatória

Resumo

Nos dias atuais, existe a necessidade de suprir uma cadeia de clientes espalhada sobre diversas localidades de maneira rápida e barata. Em linhas gerais, este processo envolve o carregamento de itens dentro de um veículo de carga, o qual segue uma rota e realiza a entrega para os respectivos clientes com o objetivo de minimizar os custos envolvidos no transporte. O objetivo deste projeto é investigar o problema de roteamento de veículos de carga considerando diversas restrições reais. Mesmo com restrições simples, este problema se encaixa na classe de problemas NP - Difícil. Com isso, propõe-se investigar novos algoritmos exatos, baseados na técnica branch and cut e branch and price e aproximados, metaheurísticas como busca tabu e GRASP, visando obter soluções ótimas ou próximas da ótima. Os testes computacionais são realizados tanto em instâncias do mundo real como instâncias sintéticas. Para comprovar a eficiência dos algoritmos propostos, comparam-se os resultados obtidos com os de algoritmos descritos na literatura, avaliando o esforço computacional e o tempo gasto para resolver cada instância. Por fim, ao propor novas metodologias e estratégias para resolver este problema, espera-se reduzir de maneira significativa o custo efetivo associado a cada etapa, desde a determinação da rota, a entrega dos itens. (AU)

Publicações acadêmicas

(Referências obtidas automaticamente das Instituições de Ensino e Pesquisa do Estado de São Paulo)

QUEIROZ, Thiago Alves de. Algoritmos para problemas de corte e empacotamento. 2010. Tese de Doutorado - Universidade Estadual de Campinas (UNICAMP). Instituto de Computação Campinas, SP.