Wasserstein distributionally robust shortest path problem

DOI10.1016/J.EJOR.2020.01.009zbMATH Open1441.90113arXiv1902.09128OpenAlexW2999214372WikidataQ126379874 ScholiaQ126379874MaRDI QIDQ2301929FDOQ2301929

Authors: Zhuolin Wang, Keyou You, Yuli Zhang, Shiji Song 

Publication date: 25 February 2020

Published in: European Journal of Operational Research (Search for Journal in Brave)

Abstract: This paper proposes a data-driven distributionally robust shortest path (DRSP) model where the distribution of the travel time in the transportation network can only be partially observed through a finite number of samples. Specifically, we aim to find an optimal path to minimize the worst-case $alpha$-reliable mean-excess travel time (METT) over a Wasserstein ball, which is centered at the empirical distribution of the sample dataset and the ball radius quantifies the level of its confidence. In sharp contrast to the existing DRSP models, our model is equivalently reformulated as a tractable mixed 0-1 convex problem, e.g., 0-1 linear program or 0-1 second-order cone program. Moreover, we also explicitly derive the distribution achieving the worst-case METT by simply perturbing each sample. Experiments demonstrate the advantages of our DRSP model in terms of the out-of-sample performance and computational complexity. Finally, our DRSP model is easily extended to solve the DR bi-criteria shortest path problem and the minimum cost flow problem.

Full work available at URL: https://arxiv.org/abs/1902.09128

Recommendations

• An approach to the distributionally robust shortest path problem
• Wasserstein distance and the distributionally robust TSP
• Distributionally robust maximum probability shortest path problem
• New reformulations of distributionally robust shortest path problem
• On distributionally robust chance constrained programs with Wasserstein distance
• Robust shortest path problems
• On the robust shortest path problem.
• Recoverable robust shortest path problems
• Stochastic Shortest Paths Via Quasi-convex Maximization
• Wasserstein distributionally robust chance-constrained program with moment information

zbMATH Keywords

uncertainty modellingWasserstein metricdistributionally robust shortest pathMETTmixed 0-1 convex program

Mathematics Subject Classification ID

Convex programming (90C25) Programming involving graphs or networks (90C35) Stochastic programming (90C15)

Cites Work

• On the robust shortest path problem.
• Ambiguous chance constrained problems and robust optimization
• On duality theory of conic linear problems.
• Distributionally robust optimization under moment uncertainty with application to data-driven problems
• An outer-approximation algorithm for a class of mixed-integer nonlinear programs
• Shortest Paths in Probabilistic Graphs
• Title not available (Why is that?)
• A simulation-based approach to two-stage stochastic programming with recourse
• The sample average approximation method applied to stochastic routing problems: a computational study
• An Analysis of Stochastic Shortest Path Problems
• Data-driven chance constrained stochastic program
• Incremental network design with shortest paths
• Title not available (Why is that?)
• Branch and Bound Experiments in Convex Nonlinear Integer Programming
• Ambiguity in portfolio selection
• Inferring a possibility distribution from empirical data
• Algorithms and uncertainty sets for data-driven robust shortest path problems
• A mean-risk model for the traffic assignment problem with stochastic travel times
• Asymmetry matters: dynamic half-way points in bidirectional labeling for solving shortest path problems with resource constraints faster
• Data-driven distributionally robust optimization using the Wasserstein metric: performance guarantees and tractable reformulations
• A framework for optimization under ambiguity
• Wasserstein distance and the distributionally robust TSP

Cited In (13)

• A study of distributionally robust mixed-integer programming with Wasserstein metric: on the value of incomplete data
• Distributionally robust mean-absolute deviation portfolio optimization using Wasserstein metric
• Distributionally robust bottleneck combinatorial problems: uncertainty quantification and robust decision making
• A distributionally robust approach for the two-machine permutation flow shop scheduling
• Wasserstein distance and the distributionally robust TSP
• An approach to the distributionally robust shortest path problem
• Wasserstein distributionally robust chance-constrained program with moment information
• A fully polynomial time approximation scheme for the probability maximizing shortest path problem
• New reformulations of distributionally robust shortest path problem
• Distributionally robust optimization. A review on theory and applications
• On the multistage shortest path problem under distributional uncertainty
• A data-driven distributionally robust approach for the optimal coupling of interdependent critical infrastructures under random failures
• Distributionally robust front distribution center inventory optimization with uncertain multi-item orders

Uses Software

• GitHub

This page was built for publication: Wasserstein distributionally robust shortest path problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2301929)