HEURÍSTICAS PARA O PROBLEMA DO CAIXEIRO VIAJANTE COM REGRA DE PRIORIDADE d-RELAXADA

• Processo: 25/09548-6
• Modalidade de apoio: Bolsas no Brasil - Iniciação Científica
• Data de Início da vigência: 01 de outubro de 2025
• Data de Término da vigência: 30 de setembro de 2026
• Área de conhecimento: Engenharias - Engenharia de Produção - Pesquisa Operacional
• Pesquisador responsável: Silvio Alexandre de Araujo
• Beneficiário: Bruna Gonçalves Assumpção
• Instituição Sede: Instituto de Biociências, Letras e Ciências Exatas (IBILCE). Universidade Estadual Paulista (UNESP). Campus de São José do Rio Preto. São José do Rio Preto , SP, Brasil
• Vinculado ao auxílio: 22/05803-3 - Problemas de corte, empacotamento, dimensionamento de lotes, programação da produção, roteamento e localização e suas integrações em contextos industriais e logísticos, AP.TEM
• Assunto(s): Heurística Modelos matemáticos
• Palavra(s)-Chave do Pesquisador: heuristicas | modelagem matematica | problema do caixeiro viajante | Regra de Prioridade d-Relaxada | Otimização Linear Inteira-Mista

Resumo

Em sua versão clássica, o Problema do Caixeiro Viajante (PCV) pode ser descrito da seguinte forma: dado um conjunto de cidades e conhecendo-se a distância entre cada uma dessas cidades, é necessário encontrar a rota mais curta possível de modo que cada cidade seja visitada apenas uma vez, incluindo a cidade de origem, onde a rota também termina. Em outras palavras, o objetivo é encontrar o circuito com o menor comprimento possível.No clássico PCV, a ordem em que os vértices são visitados não tem restrições. A única condição imposta é que cada vértice seja visitado apenas uma vez. Em algumas situações reais, essa condição pode não ser suficiente para representar o problema, pois há casos em que a ordem de visita dos vértices se torna extremamente importante. Em outras palavras, também é necessário considerar uma prioridade entre os vértices. Para lidar com essas situações, alguns trabalhos foram propostos na literatura e são baseados em uma regra chamada regra de prioridade d-relaxada, que captura o equilíbrio entre a distância total e as prioridades dos vértices. Neste projeto, pretendemos adaptar heurísticas clássicas do PCV para o caso em que se considera a regra de prioridade d-relaxada.