Um estudo computacional para o problema do ciclo dominante com coleta de prêmios

• Processo: 16/05036-1
• Modalidade de apoio: Bolsas no Brasil - Iniciação Científica
• Data de Início da vigência: 01 de setembro de 2016
• Data de Término da vigência: 28 de fevereiro de 2017
• Área de conhecimento: Engenharias - Engenharia de Produção - Pesquisa Operacional
• Pesquisador responsável: Fábio Luiz Usberti
• Beneficiário: Luis Henrique Pauleti Mendes
• Instituição Sede: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brasil
• Assunto(s): Meta-heurística Otimização combinatória Linha de produtos Metodologia e técnicas de computação Teoria dos grafos
• Palavra(s)-Chave do Pesquisador: Caixeiro Viajante | Conjunto Dominante em Grafos | metaheuristica | Otimização Combinatória | Problemas de Roteamento

Resumo

Este projeto de pesquisa propõe metodologias para resolver o Problema do Ciclo Dominante com Coleta de Prêmios (PCDCP). Este problema consiste na composição de dois problemas NP-difíceis: o Problema do Conjunto Dominante e o Problema do Caixeiro Viajante. Brevemente, o objetivo do PCDCP consiste em encontrar um ciclo de custo mínimo em um grafo não-direcionado. O ciclo é trafegado por um viajante que necessita visitar um conjunto de clientes (vértices dominantes). A motivação do PCDCP consiste em sua aplicação prática para empresas de transporte, distribuição e coleta de produtos em particular, no processo de definição de rotas para realização desses serviços. Neste projeto de pesquisa, pretende-se estudar metodologias metaheurísticas para a solução do PCDCP, considerando-se a complexidade da solução exata do PCDCP.