heuristica baseada na partição do espaço de soluções para o problema do caminho mínimo com restrição de recursos em algoritmos multifásicos

Vol 57, 2025 - 340706
Pôster
Favoritar este trabalho
Como citar esse trabalho?
Resumo

O Problema do Caminho Mais Curto com Restrições de Recursos (SPPRC) consiste em determinar, em um grafo orientado com custos e múltiplos consumos de recursos associados aos arcos, um caminho de custo mínimo entre uma origem e um destino cujo consumo acumulado respeite limites pré-estabelecidos para cada recurso ao longo da rota. Apesar da formulação simples, o SPPRC é NP-difícil e ocupa papel central em esquemas de geração de colunas aplicados a problemas de roteamento de veículos, escalonamento de tripulações e diversas outras aplicações em logística e transporte, nas quais ele surge como subproblema de pricing. A eficiência com que é resolvido determina, em grande medida, o desempenho global desses esquemas exatos.

 

As abordagens clássicas para o SPPRC são baseadas em programação dinâmica por rotulagem, em que rótulos representando caminhos parciais são propagados pelos vértices do grafo e descartados por meio de regras de dominância, frequentemente combinadas com relaxações elementares, podas por programação dinâmica reversa e busca bidirecional. Apesar dos avanços, o número de rótulos manipulados cresce rapidamente em instâncias de maior porte, o que motiva a busca por algoritmos mais escaláveis.

 

Recentemente, Himmich, El Hallaoui e Soumis (2024) propuseram um algoritmo de programação dinâmica multifásico que particiona o espaço de soluções, explorando progressivamente subconjuntos de caminhos com características estruturais comuns. O método intercala fases de extensão local de rótulos, em que apenas um subconjunto restrito de rótulos é estendido a partir dos vértices ativos da partição corrente, e fases de busca local sobre o conjunto de rótulos resultantes, em que se aplicam testes de dominância e atualização das melhores soluções parciais. Essa decomposição evita a propagação massiva de rótulos típica das abordagens tradicionais e tem apresentado resultados competitivos em instâncias de referência; ainda assim, as duas fases locais continuam dominando o tempo computacional, pois envolvem testes de dominância exatos e extensões exaustivas.

 

O objetivo deste trabalho é desenvolver uma versão heurística do algoritmo multifásico, atuando especificamente sobre as fases de extensão e de busca local de rótulos. Pretende-se substituir as regras de dominância exatas por critérios relaxados, limitar o número de rótulos mantidos por vértice em cada partição e podar de forma mais agressiva extensões consideradas pouco promissoras, de modo a obter soluções de boa qualidade em tempo computacional substancialmente menor, viabilizando o uso do método em instâncias de grande porte e em iterações de geração de colunas em que apenas soluções dual-factíveis suficientemente boas são necessárias.

Compartilhe suas ideias ou dúvidas com os autores!

Sabia que o maior estímulo no desenvolvimento científico e cultural é a curiosidade? Deixe seus questionamentos ou sugestões para o autor!

Faça login para interagir

Tem uma dúvida ou sugestão? Compartilhe seu feedback com os autores!

Instituições
  • 1 Universidade Federal de Mato Grosso do Sul | (Universidade Federal de Mato Grosso do Sul)
  • 2 Universidade Federal de Mato Grosso do Sul
Eixo Temático
  • OD - Otimização Discreta
Palavras-chave
caminho mínimo com restrições de recursos
programação dinâmica
heurísticas
Geração de Colunas