Authors
Amadeu Almeida Coco, Thiago Ferreira de Noronha, Andréa Cynthia Santos,
Title
Heurística de Refinamento para o Problema de Caminho Mais Curto Robusto
In
Proceedings of the XLVI Simpósio Brasileiro de Pesquisa Operacional (SBPO), Salvador, Brésil
Pages
1913–1923
Year
2014
Indexed by
Abstract
O Problema de Caminho Mais Curto (SP, do inglês Shortest Path) consiste em encontrar um caminho a partir de um vértice de origem s ∈ V para um vértice de destino t ∈ V , onde o custo total é mínimo. SP modela problemas práticos e teóricos. Porém, diversas aplicações para o SP dependem de dados não conhecidos à priori. O Problema do Caminho Mais Curto Robusto (RSP, do inglês Robust Shortest Path) é uma generalização do SP. No RSP, o custo de cada arco é definido por um intervalo de possíveis valores para o custo do arco. O objetivo do RSP é encontrar o caminho entre origem e destino que possui o menor custo robusto relativo. Este problema é conhecido como minmax relative regret RSP e é NP-Difícil. Este trabalho propõe uma heurística de refinamento para o minmax relative regret RSP. Os resultados dos experimentos computacionais mostram que a heurística de refinamento proposta neste trabalho obteve resultados melhores do que as heurísticas da literatura.
Affiliations
Offprint