Heurísticas para o problema de caminho mais curto robusto

Abstract

The well-known Shortest Path problem (SP) consists in nding a shortest path from a source node s ∈ V to a destination node t ∈ V such that the total cost is minimized. However, several SP applications rely on uncertain data. The Robust Shortest Path problem (RSP) generalizes the SP once the uncertain data can be modeled with costs as an interval or else by a set of discrete scenarios. This dissertation focuses on the robust optimization criterion minmax relative regret with uncertain data modeled in an interval. We developed several heuristics with emphasis on providing ecient and scalable methods for solving the minmax relative regret RSP, such as constructive heuristics, pilot method based heuristics, and a random key genetic algorithm.