A note on different modelling approaches for the robust shortest path problem
by Yury Nikulin; Zuhair Iftikhar
International Journal of Mathematical Modelling and Numerical Optimisation (IJMMNO), Vol. 3, No. 3, 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.

Online publication date: Sat, 30-Aug-2014

The full text of this article is only available to individual subscribers or to users at subscribing institutions.

 
Existing subscribers:
Go to Inderscience Online Journals to access the Full Text of this article.

Pay per view:
If you are not a subscriber and you just want to read the full contents of this article, buy online access here.

Complimentary Subscribers, Editors or Members of the Editorial Board of the International Journal of Mathematical Modelling and Numerical Optimisation (IJMMNO):
Login with your Inderscience username and password:

    Username:        Password:         

Forgotten your password?


Want to subscribe?
A subscription gives you complete access to all articles in the current issue, as well as to all articles in the previous three years (where applicable). See our Orders page to subscribe.

If you still need assistance, please email subs@inderscience.com