Problemas de roteamento em arcos com restrições de escalonamento e cobertura

• Processo: 19/00197-5
• Modalidade de apoio: Bolsas no Exterior - Estágio de Pesquisa - Doutorado
• Data de Início da vigência: 16 de maio de 2019
• Data de Término da vigência: 25 de agosto de 2019
• Área de conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
• Pesquisador responsável: Fábio Luiz Usberti
• Beneficiário: Rafael Kendy Arakaki
• Supervisor: Mutsunori Yagiura
• Instituição Sede: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brasil
• Instituição Anfitriã: Nagoya University, Japão
• Vinculado à bolsa: 16/00315-0 - Formulações e Algoritmos para Problemas de Roteamento em Arcos, BP.DR
• Assunto(s): Scheduling Meta-heurística
• Palavra(s)-Chave do Pesquisador: Arc routing | combinatorial optimization | covering constraints | Metaheuristics | Scheduling | Otimização combinatória, Pesquisa operacional

Resumo

Os problemas de roteamento em arcos visam determinar as rotas de menor custo que visitam um subconjunto de arestas a partir de um grafo, com uma ou mais restrições adicionais. A solução desses problemas leva a menores custos logísticos, melhorando a competitividade das empresas. Este projeto diz respeito ao estudo de dois problemas da classe de roteamento em arcos: (1) o problema de roteamento em arcos com restrições de cobertura; (2) o problema de roteamento em arcos com janelas de tempo (restrições de escalonamento). Ambos são problemas de otimização combinatória NP-hard. O objetivo deste projeto é o desenvolvimento de formulações matemáticas e metaheurísticas eficientes, a fim de obter soluções exatas e aproximadas para esses problemas.