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

• Processo: 20/06105-2
• Modalidade de apoio: Bolsas no Brasil - Iniciação Científica
• Data de Início da vigência: 01 de agosto de 2020
• Data de Término da vigência: 31 de julho de 2021
• Área de conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
• Pesquisador responsável: Mário César San Felice
• Beneficiário: Guilherme Gomes Arcencio
• Instituição Sede: Centro de Ciências Exatas e de Tecnologia (CCET). Universidade Federal de São Carlos (UFSCAR). São Carlos , SP, Brasil
• Assunto(s): Otimização combinatória Programação linear inteira Empacotamento e cobertura Problemas de roteamento de estoques
• Palavra(s)-Chave do Pesquisador: Algoritmos Exatos | Otimização Combinatória | Problema do Roteamento de Veículos | programação linear inteira | Otimização Combinatória

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.