Authors
Lucas Assunção, Thiago Ferreira de Noronha, Andréa Cynthia Santos, Rafael Castro de Andrade,
Title
Uma heurística baseada em programação linear para o problema do caminho mínimo robusto restrito
In
Proceedings of the XLVI Simpósio Brasileiro de Pesquisa Operacional (SBPO), Salvador, Brésil
Pages
2133–2144
Year
2014
Indexed by
Abstract
Tratamos o problema do caminho mínimo robusto restrito, uma versão de otimiza- ção robusta do clássico problema do caminho mínimo restrito, sabidamente NP-difícil. Os arcos estão associados a um intervalo de custo e a um valor de comprimento. O objetivo é encontrar um caminho de um vértice de origem a um de destino respeitando um limite máximo de comprimento e minimizando um critério robusto chamado de custo de robustez restrito. Um importante resultado teórico que diminui o espaço de busca em diversos problemas de otimização robusta é generalizado para o novo problema. É apresentada uma heurística baseada em programação matemática, juntamente com experimentos computacionais que atestam sua eficácia na resolução de instâncias adaptadas da literatura.
Affiliations
Offprint