Advertisement
Published in:
2015 | OriginalPaper | Chapter
Reducing the Minmax Regret Robust Shortest Path Problem with Finite Multi-scenarios
Authors : Marta M. B. Pascoal, Marisa Resende
Published in: Mathematics of Energy and Climate Change
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
The minmax regret robust shortest path problem is a combinatorial optimization problem that can be defined over networks where costs are assigned to arcs under a given scenario. This model can be continuous or discrete, depending on whether costs vary within intervals or within discrete sets of values. The problem consists in finding a path that minimizes the maximum deviation from the shortest paths over all scenarios. This work focuses on designing tools to reduce the network, in order to make easier the search for an optimum solution. With this purpose, methods to identify useless nodes to be removed and to detect arcs that surely belong to the optimum solution are developed. Two known algorithms for the robust shortest path problem are tested on random networks with and without these preprocessing rules.