An approach to the distributionally robust shortest path problem. (June 2021)

• Record Type: Journal Article
• Authors: Ketkov, Sergey S.; Prokopyev, Oleg A.; Burashnikov, Evgenii P.
• Is Part Of: Computers & operations research. Volume 130(2021)
• Publication Date: 2021-06
• Subjects: Shortest path problem -- Distributionally robust optimization -- Mixed-integer programming -- Polyhedral uncertainty; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2021.105212
• Languages: English
• ISSNs: 0305-0548

Abstract

Highlights: We study a class of distributionally robust shortest path problems. The distributional constraints are constructed from partially observable data. Robust and MIP reformulations are described. A comparison with other robust models is performed. Abstract: In this study we consider the shortest path problem, where the arc costs are subject to distributional uncertainty. Basically, the decision-maker attempts to minimize her worst-case expected loss over an ambiguity set (or a family) of candidate distributions that are consistent with the decision-maker's initial information. The ambiguity set is formed by all distributions that satisfy prescribed linear first-order moment constraints with respect to subsets of arcs and individual probability constraints with respect to particular arcs. Under some additional assumptions the resulting distributionally robust shortest path problem (DRSPP) admits equivalent robust and mixed-integer programming (MIP) reformulations. The robust reformulation is shown to be NP -hard, whereas the problem without the first-order moment constraints is proved to be polynomially solvable. We perform numerical experiments to illustrate the advantages of the considered approach; we also demonstrate that the MIP reformulation of DRSPP can be solved effectively using off-the-shelf solvers.