Algoritmos para Problemas de Roteamento com Restrições de Carregamento


Otimização Combinatória é uma das linhas de pesquisa da Ciência da Computação onde se concentram grandes desafios em termos de algoritmos para solucionar problemas clássicos de elevada complexidade computacional. Neste projeto propomos estudar problemas de otimização em transporte que considerem explicitamente em sua formulação a existência de restrições de carga/descarga. Este tipo de problemas aparece em aplicações reais e a sua formulação particular depende da natureza dos bens a serem transportados e do tipo de veículos a serem utilizados. Devido a relevância destes problemas em sistemas de distribuição, nos quais os custos associados com a operação dos veículos e com a mão-de-obra formam uma importante componente dos custos totais, pequenos ganhos percentuais podem resultar em economias consideráveis ao longo da cadeia logística. Consideramos dois tipos de restrições de carga/descarga. O primeiro tipo lida com a política de carga e descarga de objetos nos veículos. Em problemas com este tipo de restrições a ordem em que as mercadorias são entregues está restringida pela ordem em que elas foram coletadas. O segundo tipo de restrição considera o empacotamento dos itens a serem transportados no container do veículo. Neste caso, o tamanho e forma dos itens transportados assim como o tamanho e forma do container devem ser considerados. Uma vez que todos estes problemas são NP-difíceis, propomos o desenvolvimento de heurísticas, algoritmos exatos baseados em técnicas de programação matemática e o uso de programação paralela.

Alunos envolvidos: Graduação: (1) / Mestrado acadêmico: (1) .

Integrantes: Sebastián Alberto Urrutia – Coordenador.