Solving the robust shortest path problem with interval data using a probabilistic metaheuristic approach

Yury Nikulin

No 597, Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel from Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre

Abstract: This paper addresses the robust shortest path problem with interval data, i.e. the case of 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 minimizes so called robust deviation, i.e. deviation from an optimal solution under the worst case realization of interval weights. As it was proven in [9], the problem is NP-hard, therefore it is of great interest to tackle it with some metaheuristic approach, namely simulated annealing, in order to calculate an approximate solution for the large scale instances efficiently. We describe theoretical aspects and present the results of computational experiments. To the best of our knowledge, this is the first attempt to develop metaheuristic approach for solving the robust shortest path problem.

Keywords: shortest path problem; simulated annealing; uncertainty; robustness (search for similar items in EconPapers)
Date: 2005
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.econstor.eu/bitstream/10419/147655/1/manuskript_597.pdf (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:zbw:cauman:597

Access Statistics for this paper

More papers in Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel from Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre Contact information at EDIRC.
Bibliographic data for series maintained by ZBW - Leibniz Information Centre for Economics ().