Extensions of labeling algorithms for multi-objective uncertain shortest path problems

Raith A, Schmidt M, Schoebel A, Thom L (2018)

Publication Type: Journal article

Publication year: 2018

Journal

Networks Wiley-Blackwell

Book Volume: 72

Pages Range: 84-127

Journal Issue: 1

DOI: 10.1002/net.21815

Abstract

We consider multi-objective shortest path problems in which the edge lengths are uncertain. Different concepts for finding so-called robust efficient solutions for multi-objective robust optimization exist. In this article, we consider multi-scenario efficiency, flimsily and highly robust efficiency, and point-based and set-based minmax robust efficiency. Labeling algorithms are an important class of algorithms for multi-objective (deterministic) shortest path problems. We analyze why it is, for most of the considered concepts, not straightforward to use labeling algorithms to find robust efficient solutions. We then show two approaches to extend a generic multi-objective label correcting algorithm for these cases. We finally present extensive numerical results on the performance of the proposed algorithms.

Involved external institutions

University of Auckland NZ New Zealand (NZ) Erasmus University Rotterdam (EUR) / Erasmus Universiteit Rotterdam NL Netherlands (NL) Georg-August-Universität Göttingen DE Germany (DE)

How to cite

APA:

Raith, A., Schmidt, M., Schoebel, A., & Thom, L. (2018). Extensions of labeling algorithms for multi-objective uncertain shortest path problems. Networks, 72(1), 84-127. https://doi.org/10.1002/net.21815

MLA:

Raith, Andrea, et al. "Extensions of labeling algorithms for multi-objective uncertain shortest path problems." Networks 72.1 (2018): 84-127.

BibTeX: Download