IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v66y2018i1p210-229.html
   My bibliography  Save this article

Robust Adaptive Routing Under Uncertainty

Author

Listed:
  • Arthur Flajolet

    (Operations Research Center, Laboratory for Information and Decision Systems, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139; Department of Electrical Engineering and Computer Science, Laboratory for Information and Decision Systems, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139)

  • Sébastien Blandin

    (IBM Research, Singapore 018983)

  • Patrick Jaillet

    (Department of Electrical Engineering and Computer Science, Laboratory for Information and Decision Systems, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139)

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. The e-companion is available at https://doi.org/10.1287/opre.2017.1662 .

Suggested Citation

  • Arthur Flajolet & Sébastien Blandin & Patrick Jaillet, 2018. "Robust Adaptive Routing Under Uncertainty," Operations Research, INFORMS, vol. 66(1), pages 210-229, January.
    • Handle: RePEc:inm:oropre:v:66:y:2018:i:1:p:210-229
    DOI: 10.1287/opre.2017.1662
    as

    Download full text from publisher

    File URL: https://doi.org/10.1287/opre.2017.1662
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.2017.1662?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Elise D. Miller-Hooks & Hani S. Mahmassani, 2000. "Least Expected Time Paths in Stochastic, Time-Varying Transportation Networks," Transportation Science, INFORMS, vol. 34(2), pages 198-215, May.
    2. Dimitri P. Bertsekas & John N. Tsitsiklis, 1991. "An Analysis of Stochastic Shortest Path Problems," Mathematics of Operations Research, INFORMS, vol. 16(3), pages 580-595, August.
    3. Y. Y. Fan & R. E. Kalaba & J. E. Moore, 2005. "Arriving on Time," Journal of Optimization Theory and Applications, Springer, vol. 127(3), pages 497-513, December.
    4. Wolfram Wiesemann & Daniel Kuhn & Berç Rustem, 2013. "Robust Markov Decision Processes," Mathematics of Operations Research, INFORMS, vol. 38(1), pages 153-183, February.
    5. Patrick Jaillet & Jin Qi & Melvyn Sim, 2016. "Routing Optimization Under Uncertainty," Operations Research, INFORMS, vol. 64(1), pages 186-200, February.
    6. H. Frank, 1969. "Shortest Paths in Probabilistic Graphs," Operations Research, INFORMS, vol. 17(4), pages 583-599, August.
    7. Erick Delage & Yinyu Ye, 2010. "Distributionally Robust Optimization Under Moment Uncertainty with Application to Data-Driven Problems," Operations Research, INFORMS, vol. 58(3), pages 595-612, June.
    8. Wolfram Wiesemann & Daniel Kuhn & Melvyn Sim, 2014. "Distributionally Robust Convex Optimization," Operations Research, INFORMS, vol. 62(6), pages 1358-1376, December.
    9. Chelsea C. White & Hany K. Eldeib, 1994. "Markov Decision Processes with Imprecise Transition Probabilities," Operations Research, INFORMS, vol. 42(4), pages 739-749, August.
    10. Garud N. Iyengar, 2005. "Robust Dynamic Programming," Mathematics of Operations Research, INFORMS, vol. 30(2), pages 257-280, May.
    11. Nie, Yu (Marco) & Wu, Xing, 2009. "Shortest path problem considering on-time arrival probability," Transportation Research Part B: Methodological, Elsevier, vol. 43(6), pages 597-613, July.
    12. Huan Xu & Constantine Caramanis & Shie Mannor, 2012. "Optimization Under Probabilistic Envelope Constraints," Operations Research, INFORMS, vol. 60(3), pages 682-699, June.
    13. Arnab Nilim & Laurent El Ghaoui, 2005. "Robust Control of Markov Decision Processes with Uncertain Transition Matrices," Operations Research, INFORMS, vol. 53(5), pages 780-798, October.
    14. G. C. Calafiore & L. El Ghaoui, 2006. "On Distributionally Robust Chance-Constrained Linear Programs," Journal of Optimization Theory and Applications, Springer, vol. 130(1), pages 1-22, July.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Shubhechyya Ghosal & Wolfram Wiesemann, 2020. "The Distributionally Robust Chance-Constrained Vehicle Routing Problem," Operations Research, INFORMS, vol. 68(3), pages 716-732, May.
    2. Wang, Xin & Kuo, Yong-Hong & Shen, Houcai & Zhang, Lianmin, 2021. "Target-oriented robust location–transportation problem with service-level measure," Transportation Research Part B: Methodological, Elsevier, vol. 153(C), pages 1-20.
    3. Matthias Ruß & Gunther Gust & Dirk Neumann, 2021. "The Constrained Reliable Shortest Path Problem in Stochastic Time-Dependent Networks," Operations Research, INFORMS, vol. 69(3), pages 709-726, May.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Andrew J. Keith & Darryl K. Ahner, 2021. "A survey of decision making and optimization under uncertainty," Annals of Operations Research, Springer, vol. 300(2), pages 319-353, May.
    2. Bakker, Hannah & Dunke, Fabian & Nickel, Stefan, 2020. "A structuring review on multi-stage optimization under uncertainty: Aligning concepts from theory and practice," Omega, Elsevier, vol. 96(C).
    3. Grani A. Hanasusanto & Vladimir Roitch & Daniel Kuhn & Wolfram Wiesemann, 2017. "Ambiguous Joint Chance Constraints Under Mean and Dispersion Information," Operations Research, INFORMS, vol. 65(3), pages 751-767, June.
    4. Zhu, Zhicheng & Xiang, Yisha & Zhao, Ming & Shi, Yue, 2023. "Data-driven remanufacturing planning with parameter uncertainty," European Journal of Operational Research, Elsevier, vol. 309(1), pages 102-116.
    5. Yongchao Liu & Alois Pichler & Huifu Xu, 2019. "Discrete Approximation and Quantification in Distributionally Robust Optimization," Mathematics of Operations Research, INFORMS, vol. 44(1), pages 19-37, February.
    6. Shahabi, Mehrdad & Unnikrishnan, Avinash & Boyles, Stephen D., 2013. "An outer approximation algorithm for the robust shortest path problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 58(C), pages 52-66.
    7. Manseur, Farida & Farhi, Nadir & Nguyen Van Phu, Cyril & Haj-Salem, Habib & Lebacque, Jean-Patrick, 2020. "Robust routing, its price, and the tradeoff between routing robustness and travel time reliability in road networks," European Journal of Operational Research, Elsevier, vol. 285(1), pages 159-171.
    8. Jose Blanchet & Karthyek Murthy, 2019. "Quantifying Distributional Model Risk via Optimal Transport," Mathematics of Operations Research, INFORMS, vol. 44(2), pages 565-600, May.
    9. Huan Xu & Shie Mannor, 2012. "Distributionally Robust Markov Decision Processes," Mathematics of Operations Research, INFORMS, vol. 37(2), pages 288-300, May.
    10. Zhang, Yu & Tang, Jiafu, 2018. "Itinerary planning with time budget for risk-averse travelers," European Journal of Operational Research, Elsevier, vol. 267(1), pages 288-303.
    11. Maximilian Blesch & Philipp Eisenhauer, 2023. "Robust Decision-Making under Risk and Ambiguity," Rationality and Competition Discussion Paper Series 463, CRC TRR 190 Rationality and Competition.
    12. Leilei Zhang & Tito Homem-de-Mello, 2017. "An Optimal Path Model for the Risk-Averse Traveler," Transportation Science, INFORMS, vol. 51(2), pages 518-535, May.
    13. Soumyadip Ghosh & Henry Lam, 2019. "Robust Analysis in Stochastic Simulation: Computation and Performance Guarantees," Operations Research, INFORMS, vol. 67(1), pages 232-249, January.
    14. V Varagapriya & Vikas Vikram Singh & Abdel Lisser, 2023. "Joint chance-constrained Markov decision processes," Annals of Operations Research, Springer, vol. 322(2), pages 1013-1035, March.
    15. Peter Buchholz & Dimitri Scheftelowitsch, 2019. "Computation of weighted sums of rewards for concurrent MDPs," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 89(1), pages 1-42, February.
    16. Levering, Nikki & Boon, Marko & Mandjes, Michel & Núñez-Queija, Rudesindo, 2022. "A framework for efficient dynamic routing under stochastically varying conditions," Transportation Research Part B: Methodological, Elsevier, vol. 160(C), pages 97-124.
    17. Wu, Xing & (Marco) Nie, Yu, 2011. "Modeling heterogeneous risk-taking behavior in route choice: A stochastic dominance approach," Transportation Research Part A: Policy and Practice, Elsevier, vol. 45(9), pages 896-915, November.
    18. Liu, Yang & Blandin, Sebastien & Samaranayake, Samitha, 2019. "Stochastic on-time arrival problem in transit networks," Transportation Research Part B: Methodological, Elsevier, vol. 119(C), pages 122-138.
    19. Wu, Xing, 2015. "Study on mean-standard deviation shortest path problem in stochastic and time-dependent networks: A stochastic dominance based approach," Transportation Research Part B: Methodological, Elsevier, vol. 80(C), pages 275-290.
    20. Yue Zhao & Zhi Chen & Zhenzhen Zhang, 2023. "Distributionally Robust Chance-Constrained p -Hub Center Problem," INFORMS Journal on Computing, INFORMS, vol. 35(6), pages 1361-1382, November.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:oropre:v:66:y:2018:i:1:p:210-229. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.