An exact method for a class of robust shortest path problems with scenarios. Issue 4 (12th October 2019)

• Record Type: Journal Article
• Authors: Duque, Daniel; Medaglia, Andrés L.
• Is Part Of: Networks. Volume 74:Issue 4(2019)
• Page Start: 360
• Page End: 373
• Publication Date: 2019-10-12
• Subjects: bw‐robustness -- data‐driven robust optimization -- robustness -- routing -- shortest path -- pulse algorithm; Network analysis (Planning) -- Periodicals; 658.4032
• DOI: 10.1002/net.21909
• Languages: English
• ISSNs: 0028-3045

Abstract

Abstract: In this variant of the robust shortest path problem, the cost of traversing an arc is given by a discrete set of scenarios. The problem is then to find a (robust) path that takes into account the information arising from the multiple cost realizations of the possible scenarios. To account for a robust path, we adopt the bw ‐robustness criterion, which ameliorates the dramatic role played by worst‐case approaches. Under this criterion, the parameter b represents a desirable upper bound for the cost that the decision maker wants for most of the scenarios; while parameter w strictly bounds the cost and represents a value that the decision maker is not willing to exceed in any scenario. To solve the problem, we extend the pulse algorithm, a general‐purpose solution strategy that has been used on shortest path problems with side constraints. The proposed algorithm compares favorably against an integer programming approach both in terms of speed and scalability on networks with up to 39 377 nodes and 192 094 arcs.