• TUCS Publication Series
• How to Publish in TUCS Series
• Publication Search
• Publication Graph
• Publication Input
• Publication Input Guide
• JuFo Browser

A Note on Different Modelling Approaches for the Robust Shortest Path Problem

Yury Nikulin, Zuhair Iftikhar, A Note on Different Modelling Approaches for the Robust Shortest Path Problem. International Journal of Mathematical Modelling and Numerical Optimisation 3(3), 141–157, 2012.

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.

BibTeX entry:

@ARTICLE{jNiIf12a,
  title = {A Note on Different Modelling Approaches for the Robust Shortest Path Problem},
  author = {Nikulin, Yury and Iftikhar, Zuhair},
  journal = {International Journal of Mathematical Modelling and Numerical Optimisation},
  volume = {3},
  number = {3},
  pages = {141–157},
  year = {2012},
}

Belongs to TUCS Research Unit(s): Turku Optimization Group (TOpGroup)

Edit publication