Capacited vehicle routing with loading restrictions

• Grant number: 09/01129-1
• Support Opportunities: Scholarships in Brazil - Doctorate
• Start date: June 01, 2009
• End date: January 31, 2010
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Theory of Computation
• Principal Investigator: Flávio Keidi Miyazawa
• Grantee: Thiago Alves de Queiroz
• Host Institution: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brazil

Abstract

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)

Academic Publications

(References retrieved automatically from State of São Paulo Research Institutions)

QUEIROZ, Thiago Alves de. Algorithms for cutting and packing problems. 2010. Doctoral Thesis - Universidade Estadual de Campinas (UNICAMP). Instituto de Computação Campinas, SP.