Robust adaptive routing under uncertainty
From MaRDI portal
Publication:4969320
Abstract: We consider the problem of finding an optimal history-dependent routing strategy on a directed graph weighted by stochastic arc costs when the objective is to minimize the risk of spending more than a prescribed budget. To help mitigate the impact of the lack of information on the arc cost probability distributions, we introduce a robust counterpart where the distributions are only known through confidence intervals on some statistics such as the mean, the mean absolute deviation, and any quantile. Leveraging recent results in distributionally robust optimization, we develop a general-purpose algorithm to compute an approximate optimal strategy. To illustrate the benefits of the robust approach, we run numerical experiments with field data from the Singapore road network.
Recommendations
- An approach to the distributionally robust shortest path problem
- The resource constrained shortest path problem with uncertain data: a robust formulation and optimal solution approach
- Robust routing, its price, and the tradeoff between routing robustness and travel time reliability in road networks
- Robust path choice in networks with failures
- Routing optimization under uncertainty
Cites work
- An Analysis of Stochastic Shortest Path Problems
- Another efficient algorithm for convex hulls in two dimensions
- Arriving on time
- Distributionally Robust Convex Optimization
- Distributionally robust optimization under moment uncertainty with application to data-driven problems
- Generalized Chebyshev Bounds via Semidefinite Programming
- Least expected time paths in stochastic, time-varying transportation networks
- Markov Decision Processes with Imprecise Transition Probabilities
- On distributionally robust chance-constrained linear programs
- On duality theory of conic linear problems.
- Optimal Inequalities in Probability Theory: A Convex Optimization Approach
- Optimal paths in graphs with stochastic or multidimensional weights
- Optimization under probabilistic envelope constraints
- Robust Control of Markov Decision Processes with Uncertain Transition Matrices
- Robust Dynamic Programming
- Robust Markov Decision Processes
- Routing optimization under uncertainty
- Shortest Paths in Probabilistic Graphs
- Speeding up stochastic dynamic programming with zero-delay convolution
- Speedup techniques for the stochastic on-time arrival problem
- Stochastic Shortest Paths Via Quasi-convex Maximization
- The discrete moment problem and linear programming
Cited in
(13)- Adaptive routing with stale information
- The constrained reliable shortest path problem in stochastic time-dependent networks
- Algorithms for non-linear and stochastic resource constrained shortest path
- Adapting to a reliable network path
- Ambiguous joint chance constraints under mean and dispersion information
- The distributionally robust chance-constrained vehicle routing problem
- Anonymous Stochastic Routing
- The Repetitive Turn Model for Adaptive Routing
- Robust routing in deterministic delay-tolerant networks
- Adaptive routing with stale information
- scientific article; zbMATH DE number 934440 (Why is no real title available?)
- Consistency and robustness in location-routing
- Robust routing, its price, and the tradeoff between routing robustness and travel time reliability in road networks
This page was built for publication: Robust adaptive routing under uncertainty
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4969320)
