IDEAS home Printed from https://ideas.repec.org/p/ems/eureir/37193.html
   My bibliography  Save this paper

The Orienteering Problem under Uncertainty Stochastic Programming and Robust Optimization compared

Author

Listed:
  • Evers, L.
  • Glorie, K.M.
  • van der Ster, S.
  • Barros, A.I.
  • Monsuur, H.

Abstract

The Orienteering Problem (OP) is a generalization of the well-known traveling salesman problem and has many interesting applications in logistics, tourism and defense. To reflect real-life situations, we focus on an uncertain variant of the OP. Two main approaches that deal with optimization under uncertainty are stochastic programming and robust optimization. We will explore the potentialities and bottlenecks of these two approaches applied to the uncertain OP. We will compare the known robust approach for the uncertain OP (the robust orienteering problem) to the new stochastic programming counterpart (the two-stage orienteering problem). The application of both approaches will be explored in terms of their suitability in practice.

Suggested Citation

  • Evers, L. & Glorie, K.M. & van der Ster, S. & Barros, A.I. & Monsuur, H., 2012. "The Orienteering Problem under Uncertainty Stochastic Programming and Robust Optimization compared," Econometric Institute Research Papers EI 2012-21, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    • Handle: RePEc:ems:eureir:37193
    as

    Download full text from publisher

    File URL: https://repub.eur.nl/pub/37193/EI2012-21.pdf
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Xin Chen & Melvyn Sim & Peng Sun & Jiawei Zhang, 2008. "A Linear Decision-Based Approximation Approach to Stochastic Programming," Operations Research, INFORMS, vol. 56(2), pages 344-357, April.
    2. H Tang & E Miller-Hooks, 2005. "Algorithms for a stochastic selective travelling salesperson problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 56(4), pages 439-452, April.
    3. ,, 2000. "Problems And Solutions," Econometric Theory, Cambridge University Press, vol. 16(2), pages 287-299, April.
    4. Vansteenwegen, Pieter & Souffriau, Wouter & Oudheusden, Dirk Van, 2011. "The orienteering problem: A survey," European Journal of Operational Research, Elsevier, vol. 209(1), pages 1-10, February.
    5. A. Ben-Tal & A. Nemirovski, 1998. "Robust Convex Optimization," Mathematics of Operations Research, INFORMS, vol. 23(4), pages 769-805, November.
    6. Evers, L. & Dollevoet, T.A.B. & Barros, A.I. & Monsuur, H., 2011. "Robust UAV Mission Planning," Econometric Institute Research Papers EI 2011-07, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    7. Ann Campbell & Michel Gendreau & Barrett Thomas, 2011. "The orienteering problem with stochastic travel and service times," Annals of Operations Research, Springer, vol. 186(1), pages 61-81, June.
    8. Dimitris Bertsimas & Melvyn Sim, 2004. "The Price of Robustness," Operations Research, INFORMS, vol. 52(1), pages 35-53, February.
    9. Xin Chen & Melvyn Sim & Peng Sun, 2007. "A Robust Optimization Perspective on Stochastic Programming," Operations Research, INFORMS, vol. 55(6), pages 1058-1071, December.
    10. S. Y. Teng & H. L. Ong & H. C. Huang, 2004. "An Integer L-Shaped Algorithm For Time-Constrained Traveling Salesman Problem With Stochastic Travel And Service Times," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 21(02), pages 241-257.
    11. Bruce L. Golden & Larry Levy & Rakesh Vohra, 1987. "The orienteering problem," Naval Research Logistics (NRL), John Wiley & Sons, vol. 34(3), pages 307-318, June.
    12. A. Charnes & W. W. Cooper, 1959. "Chance-Constrained Programming," Management Science, INFORMS, vol. 6(1), pages 73-79, October.
    13. Gilbert Laporte & FranÇois V. Louveaux & Luc van Hamme, 2002. "An Integer L -Shaped Algorithm for the Capacitated Vehicle Routing Problem with Stochastic Demands," Operations Research, INFORMS, vol. 50(3), pages 415-423, June.
    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. Cédric Verbeeck & Pieter Vansteenwegen & El-Houssaine Aghezzaf, 2017. "The time-dependent orienteering problem with time windows: a fast ant colony system," Annals of Operations Research, Springer, vol. 254(1), pages 481-505, July.
    2. Verbeeck, C. & Vansteenwegen, P. & Aghezzaf, E.-H., 2016. "Solving the stochastic time-dependent orienteering problem with time windows," European Journal of Operational Research, Elsevier, vol. 255(3), pages 699-718.

    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. Hamed Mamani & Shima Nassiri & Michael R. Wagner, 2017. "Closed-Form Solutions for Robust Inventory Management," Management Science, INFORMS, vol. 63(5), pages 1625-1643, May.
    2. Dimitris Bertsimas & Melvyn Sim & Meilin Zhang, 2019. "Adaptive Distributionally Robust Optimization," Management Science, INFORMS, vol. 65(2), pages 604-618, February.
    3. Huan Xu & Constantine Caramanis & Shie Mannor, 2012. "Optimization Under Probabilistic Envelope Constraints," Operations Research, INFORMS, vol. 60(3), pages 682-699, June.
    4. Jia Shu & Miao Song, 2014. "Dynamic Container Deployment: Two-Stage Robust Model, Complexity, and Computational Results," INFORMS Journal on Computing, INFORMS, vol. 26(1), pages 135-149, February.
    5. Verbeeck, C. & Vansteenwegen, P. & Aghezzaf, E.-H., 2016. "Solving the stochastic time-dependent orienteering problem with time windows," European Journal of Operational Research, Elsevier, vol. 255(3), pages 699-718.
    6. Joel Goh & Melvyn Sim, 2010. "Distributionally Robust Optimization and Its Tractable Approximations," Operations Research, INFORMS, vol. 58(4-part-1), pages 902-917, August.
    7. Chuen-Teck See & Melvyn Sim, 2010. "Robust Approximation to Multiperiod Inventory Management," Operations Research, INFORMS, vol. 58(3), pages 583-594, June.
    8. Han, Biao & Shang, Chao & Huang, Dexian, 2021. "Multiple kernel learning-aided robust optimization: Learning algorithm, computational tractability, and usage in multi-stage decision-making," European Journal of Operational Research, Elsevier, vol. 292(3), pages 1004-1018.
    9. Wenqing Chen & Melvyn Sim & Jie Sun & Chung-Piaw Teo, 2010. "From CVaR to Uncertainty Set: Implications in Joint Chance-Constrained Optimization," Operations Research, INFORMS, vol. 58(2), pages 470-485, April.
    10. L. Jeff Hong & Zhiyuan Huang & Henry Lam, 2021. "Learning-Based Robust Optimization: Procedures and Statistical Guarantees," Management Science, INFORMS, vol. 67(6), pages 3447-3467, June.
    11. Wenqing Chen & Melvyn Sim, 2009. "Goal-Driven Optimization," Operations Research, INFORMS, vol. 57(2), pages 342-357, April.
    12. Joel Goh & Melvyn Sim, 2011. "Robust Optimization Made Easy with ROME," Operations Research, INFORMS, vol. 59(4), pages 973-985, August.
    13. Shipra Agrawal & Yichuan Ding & Amin Saberi & Yinyu Ye, 2012. "Price of Correlations in Stochastic Optimization," Operations Research, INFORMS, vol. 60(1), pages 150-162, February.
    14. 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.
    15. Shahabi, Mehrdad & Unnikrishnan, Avinash, 2014. "Robust hub network design problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 70(C), pages 356-373.
    16. Yu, Qinxiao & Fang, Kan & Zhu, Ning & Ma, Shoufeng, 2019. "A matheuristic approach to the orienteering problem with service time dependent profits," European Journal of Operational Research, Elsevier, vol. 273(2), pages 488-503.
    17. Wolfram Wiesemann & Daniel Kuhn & Berc Rustem, 2009. "Robust Resource Allocations in Temporal Networks," Working Papers 020, COMISEF.
    18. Hatami-Marbini, Adel & Arabmaldar, Aliasghar, 2021. "Robustness of Farrell cost efficiency measurement under data perturbations: Evidence from a US manufacturing application," European Journal of Operational Research, Elsevier, vol. 295(2), pages 604-620.
    19. Bian, Zheyong & Liu, Xiang, 2018. "A real-time adjustment strategy for the operational level stochastic orienteering problem: A simulation-aided optimization approach," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 115(C), pages 246-266.
    20. Zhi Chen & Melvyn Sim & Huan Xu, 2019. "Distributionally Robust Optimization with Infinitely Constrained Ambiguity Sets," Operations Research, INFORMS, vol. 67(5), pages 1328-1344, September.

    More about this item

    Keywords

    robust optimization; stochastic programming; uncertain orienteering problem;
    All these keywords.

    NEP fields

    This paper has been announced in the following NEP Reports:

    Statistics

    Access and download statistics

    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:ems:eureir:37193. 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: RePub (email available below). General contact details of provider: https://edirc.repec.org/data/feeurnl.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.