Title: A note on different modelling approaches for the robust shortest path problem

Authors: Yury Nikulin; Zuhair Iftikhar

Addresses: Department of Mathematics, University of Turku, FI-20014 Turku, Finland. ' Department of Mathematics, University of Turku, FI-20014 Turku, Finland

Abstract: This paper addresses the robust shortest path problem with interval data, i.e., a case of the classical shortest path problem with given source and sink when arc weights are not fixed but take their values from some intervals associated with arcs. The problem consists in finding a shortest path that minimises some robustness measure. Two different approaches developed recently are considered and compared. While the first approach, relative robustness, plays against the worst-case scenario and leads to NP-hard robust counterpart problem, the second approach, flexible robustness, is more adaptable (it allows to control the degree of conservatism of the given solution by using some integer parameter that restricts uncertainty) and leads to the polynomially solvable robust counterpart model. We empirically analyse these two approaches and compare their robust solutions with respect to closeness to the nominal shortest path cost. Based on the results of this empirical test, we deduce some practical recommendation to the decision maker on appropriate usage of both models and possible tuning of model parameters.

Keywords: shortest path; robust optimisation; interval uncertainty; modelling; parameter tuning.

DOI: 10.1504/IJMMNO.2012.047703

International Journal of Mathematical Modelling and Numerical Optimisation, 2012 Vol.3 No.3, pp.141 - 157

Received: 27 Aug 2010
Accepted: 06 Jun 2011
Published online: 30 Aug 2014 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article