Wasserstein distributionally robust shortest path problem
From MaRDI portal
Publication:2301929
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 -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.
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
Cites work
- scientific article; zbMATH DE number 3134565 (Why is no real title available?)
- scientific article; zbMATH DE number 734930 (Why is no real title available?)
- A framework for optimization under ambiguity
- A mean-risk model for the traffic assignment problem with stochastic travel times
- A simulation-based approach to two-stage stochastic programming with recourse
- Algorithms and uncertainty sets for data-driven robust shortest path problems
- Ambiguity in portfolio selection
- Ambiguous chance constrained problems and robust optimization
- An Analysis of Stochastic Shortest Path Problems
- An outer-approximation algorithm for a class of mixed-integer nonlinear programs
- Asymmetry matters: dynamic half-way points in bidirectional labeling for solving shortest path problems with resource constraints faster
- Branch and Bound Experiments in Convex Nonlinear Integer Programming
- Data-driven chance constrained stochastic program
- Data-driven distributionally robust optimization using the Wasserstein metric: performance guarantees and tractable reformulations
- Distributionally robust optimization under moment uncertainty with application to data-driven problems
- Incremental network design with shortest paths
- Inferring a possibility distribution from empirical data
- On duality theory of conic linear problems.
- On the robust shortest path problem.
- Shortest Paths in Probabilistic Graphs
- The sample average approximation method applied to stochastic routing problems: a computational study
- Wasserstein distance and the distributionally robust TSP
Cited in
(13)- Distributionally robust bottleneck combinatorial problems: uncertainty quantification and robust decision making
- 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
- 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
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)
