Robust Adaptive Routing Under Uncertainty
© 2017 INFORMS. 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 ar...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Institute for Operations Research and the Management Sciences (INFORMS)
2021
|
| Online Access: | https://hdl.handle.net/1721.1/134852 |
| _version_ | 1811080409293783040 |
|---|---|
| author | Flajolet, Arthur Blandin, Sébastien Jaillet, Patrick |
| author2 | Massachusetts Institute of Technology. Operations Research Center |
| author_facet | Massachusetts Institute of Technology. Operations Research Center Flajolet, Arthur Blandin, Sébastien Jaillet, Patrick |
| author_sort | Flajolet, Arthur |
| collection | MIT |
| description | © 2017 INFORMS. 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. |
| first_indexed | 2024-09-23T11:31:11Z |
| format | Article |
| id | mit-1721.1/134852 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T11:31:11Z |
| publishDate | 2021 |
| publisher | Institute for Operations Research and the Management Sciences (INFORMS) |
| record_format | dspace |
| spelling | mit-1721.1/1348522024-01-02T16:00:16Z Robust Adaptive Routing Under Uncertainty Flajolet, Arthur Blandin, Sébastien Jaillet, Patrick Massachusetts Institute of Technology. Operations Research Center Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology. Laboratory for Information and Decision Systems © 2017 INFORMS. 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. 2021-10-27T20:09:29Z 2021-10-27T20:09:29Z 2018 2019-05-31T18:27:16Z Article http://purl.org/eprint/type/JournalArticle https://hdl.handle.net/1721.1/134852 en 10.1287/OPRE.2017.1662 Operations Research Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Institute for Operations Research and the Management Sciences (INFORMS) MIT web domain |
| spellingShingle | Flajolet, Arthur Blandin, Sébastien Jaillet, Patrick Robust Adaptive Routing Under Uncertainty |
| title | Robust Adaptive Routing Under Uncertainty |
| title_full | Robust Adaptive Routing Under Uncertainty |
| title_fullStr | Robust Adaptive Routing Under Uncertainty |
| title_full_unstemmed | Robust Adaptive Routing Under Uncertainty |
| title_short | Robust Adaptive Routing Under Uncertainty |
| title_sort | robust adaptive routing under uncertainty |
| url | https://hdl.handle.net/1721.1/134852 |
| work_keys_str_mv | AT flajoletarthur robustadaptiveroutingunderuncertainty AT blandinsebastien robustadaptiveroutingunderuncertainty AT jailletpatrick robustadaptiveroutingunderuncertainty |