Programação linear inteira e o problema do roteamento de veículos

Resumo

No Problema do Roteamento de Veículos, buscamos um conjunto de rotas para que uma frota de veículos atenda a um conjunto de clientes de forma a minimizar o custo de operação. Esse problema é de grande relevância para o setor industrial, visto que pode modelar problemas logísticos como distribuição de produtos e transporte de passageiros. Este projeto tem como objetivo o estudo e desenvolvimento de algoritmos exatos para esse problema, utilizando a abordagem de Programação Linear Inteira. Outro problema a ser atacado brevemente com essa ferramenta é o Problema do Empacotamento Unidimensional, em que se busca a menor quantidade de recipientes necessários para armazenar um conjunto de itens. Este problema também está relacionado a processos industriais, modelando problemas de armazenamento de produtos e corte de materiais. Por ter uma formulação mais simples, esse problema será usado como intermediário para o estudo das bases de Programação Linear Inteira. Também pretendemos estudar algoritmos para resolver programas lineares, como o Simplex, e para resolver programas lineares inteiros, como o Branch-and-Bound. Enquanto iniciação científica, esse projeto visa a introdução do candidato na área de pesquisa científica e a complementação de sua formação em Engenharia de Computação, bem como a produção de um artigo compilando os resultados alcançados.