Robust adaptive routing under uncertainty
From MaRDI portal
Publication:4969320
DOI10.1287/OPRE.2017.1662zbMATH Open1455.90142arXiv1408.3374OpenAlexW2963283205MaRDI QIDQ4969320FDOQ4969320
Authors: Arthur Flajolet, Sebastien Blandin, Patrick Jaillet 
Publication date: 5 October 2020
Published in: Operations Research (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1408.3374
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
Programming involving graphs or networks (90C35) Markov and semi-Markov decision processes (90C40) Robustness in mathematical programming (90C17)
Cites Work
- On distributionally robust chance-constrained linear programs
- On duality theory of conic linear problems.
- Least expected time paths in stochastic, time-varying transportation networks
- Optimal paths in graphs with stochastic or multidimensional weights
- Distributionally robust optimization under moment uncertainty with application to data-driven problems
- Generalized Chebyshev Bounds via Semidefinite Programming
- Optimization under probabilistic envelope constraints
- Optimal Inequalities in Probability Theory: A Convex Optimization Approach
- Stochastic Shortest Paths Via Quasi-convex Maximization
- Shortest Paths in Probabilistic Graphs
- Robust Control of Markov Decision Processes with Uncertain Transition Matrices
- Robust Dynamic Programming
- The discrete moment problem and linear programming
- Another efficient algorithm for convex hulls in two dimensions
- An Analysis of Stochastic Shortest Path Problems
- Arriving on time
- Robust Markov Decision Processes
- Markov Decision Processes with Imprecise Transition Probabilities
- Routing optimization under uncertainty
- Distributionally Robust Convex Optimization
- Speedup techniques for the stochastic on-time arrival problem
- Speeding up stochastic dynamic programming with zero-delay convolution
Cited In (13)
- Anonymous Stochastic Routing
- Robust routing in deterministic delay-tolerant networks
- Adapting to a reliable network path
- Adaptive routing with stale information
- Algorithms for non-linear and stochastic resource constrained shortest path
- The Repetitive Turn Model for Adaptive Routing
- Title not available (Why is that?)
- The distributionally robust chance-constrained vehicle routing problem
- Robust routing, its price, and the tradeoff between routing robustness and travel time reliability in road networks
- Adaptive routing with stale information
- The constrained reliable shortest path problem in stochastic time-dependent networks
- Consistency and robustness in location-routing
- Ambiguous joint chance constraints under mean and dispersion information
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)
