Para citar este trabalho use um dos padrões abaixo:
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.
Com ~200 mil publicações revisadas por pesquisadores do mundo todo, o Galoá impulsiona cientistas na descoberta de pesquisas de ponta por meio de nossa plataforma indexada.
Confira nossos produtos e como podemos ajudá-lo a dar mais alcance para sua pesquisa:
Esse proceedings é identificado por um DOI , para usar em citações ou referências bibliográficas. Atenção: este não é um DOI para o jornal e, como tal, não pode ser usado em Lattes para identificar um trabalho específico.
Verifique o link "Como citar" na página do trabalho, para ver como citar corretamente o artigo