Robust Adaptive Routing Under Uncertainty

• 成果类型: Article
• 署名作者: Flajolet, Arthur; Blandin, Sebastien; Jaillet, Patrick
• 署名单位: Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT)
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2017.1662
• 发表日期: 2018
• 页码: 210-229
• 关键词: markov decision-processes; shortest paths; optimization; algorithm

摘要

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.