RISK-AVERSE STOCHASTIC ORIENTEERING PROBLEMS

Year 2019, Volume: 20 Issue: 3, 346 - 364, 26.09.2019

Özlem Çavuş

https://doi.org/10.18038/estubtda.540384

Abstract

In
this study, we consider risk-averse orienteering problems with stochastic travel
times or stochastic rewards. In risk-neutral orienteering problems, the objective
is generally to maximize the expected total reward of visited notes. However, due
to uncertain travel times or uncertain rewards, the dispersion in total reward
collected may be large, which necessitates an approach that minimizes the
dispersion (risk) in addition to maximizing the expected total reward. To
handle this, for the orienteering problems with stochastic travel times or
stochastic rewards, we suggest two different formulations with an objective of
coherent measures of risk. For both problems, we conduct an experimental study
using two different coherent measures of risk, which have been extensively used
in the literature, and compare the results. The computational results show that,
in both models suggested and under both risk measures used, the decision maker is
able to obtain a tour with expected total reward being close to the expected
total reward of risk-neutral solution, however with a significant decrease in
the standard deviation of total reward.

Keywords

Stochastic orienteering problem, risk-averse optimization, coherent measures of risk, mean conditional value-at-risk, mean semi-deviation

References

• Tsiligirides T. Heuristic Methods Applied to Orienteering. The Journal of the Operational Research Society 1984; 35(9): 797-809.
• Golden BL, Levy L, Vohra R. The orienteering problem. Naval Research Logistics 1987; 34(3): 307-318.
• Vansteenwegen P, Souffriau W, Van Oudheusden D. The orienteering problem: A survey. European Journal of Operational Research 2011; 209 (1): 1–10.
• Gunawan A, Lau HC, Vansteenwegen P. Orienteering problem: A survey of recent variants, solution approaches and applications. European Journal of Operational Research 2016; 255(2): 315-332.
• Teng SY, Ong HL, Huang HC. An integer L-shaped algorithm for the time-constrained traveling salesman problem with stochastic travel times and service times. Asia-Pacific Journal of Operational Research 2004; 21: 241–257.
• Campbell AM, Gendreau M, Thomas BW. The orienteering problem with stochastic travel and service times. Annals of Operations Research 2011; 186: 61–81.
• Tang H, Miller-Hooks E. Algorithms for a stochastic selective travelling salesperson problem. Journal of the Operational Research Society 2005; 56(4): 439–452.
• Ilhan T, Iravani SM, Daskin MS. The orienteering problem with stochastic profits. IIE Transactions 2008; 40: 406–421.
• Evers L, Glorie K, Van Der Ster S, Barros AI, Monsuur H. A two-stage approach to the orienteering problem with stochastic weights. Computers & Operations Research 2014; 43: 248-260.
• Shang K, Chan FT, Karungaru S, Terada K, Feng Z, Ke L. Two-stage robust optimization for orienteering problem with stochastic weights. 2016; arXiv preprint arXiv:1701.00090.
• Varakantham P, Kumar A. Optimization approaches for solving chance constrained stochastic orienteering problems. In: International Conference on Algorithmic Decision Theory (ADT); 13-15 November 2013; Bruxelles, Belgium. Springer, Berlin, Heidelberg. pp. 387-398.
• Dolinskaya I, Shi ZE, Smilowitz K. Adaptive orienteering problem with stochastic travel times. Transportation Research Part E: Logistics and Transportation Review 2018; 109: 1-19.
• Hoong CL, William Y, Pradeep V, Duc TN, Huaxing C. Dynamic stochastic orienteering problems for risk-aware applications. In: Proceedings of the Conference on Uncertainty in Artificial Intelligence (UAI); 15-17 August 2012; Catalina Island, United States. Oregon, USA: AUAI. pp. 448–458.
• Varakantham P, Kumar A, Lau HC, Yeoh W. Risk-sensitive stochastic orienteering problems for trip optimization in urban environments. ACM Transactions on Intelligent Systems and Technology (TIST) 2018; 9(3): 24.
• Verbeeck C, Vansteenwegen P, Aghezzaf EH. Solving the stochastic time-dependent orienteering problem with time windows. European Journal of Operational Research 2016; 255(3): 699-718.
• Zhang S, Ohlmann JW, Thomas BW. A priori orienteering with time windows and stochastic wait times at customers. European Journal of Operational Research 2014; 239(1): 70-79.
• Zhang S, Ohlmann JW, Thomas BW. Dynamic orienteering on a network of queues. Transportation Science 2018; 52(3): 691-706.
• Shapiro A, Dentcheva D, Ruszczyński A. Lectures on stochastic programming: modeling and theory. Society for Industrial and Applied Mathematics, 2009.
• Artzner P, Delbaen F, Eber JM, Heath D. Coherent measures of risk. Mathematical finance 1999; 9(3): 203-228.
• Ruszczynski A, Shapiro A. Optimization of convex risk functions. Mathematics of operations research 2006; 31(3): 433–452
.
• Ruszczynski A, Shapiro A. Optimization of Risk Measures. In: Calafiore G, Dabbene F, editors. Probabilistic and Randomized Methods for Design under Uncertainty. Springer, London, 2006. pp. 119-157.
• Rockafellar RT, Uryasev SP. Optimization of conditional value-at-risk. Journal of Risk 2000; 2: 21-42.
• Rockafellar RT, Uryasev SP. Conditional value-at-risk for general loss distributions. Journal of Banking and Finance 2002; 26: 1443-1471.
• Rockafellar RT. Coherent approaches to risk in optimization under uncertainty. INFORMS Tutorials in Operations Research. Institute for Operations Research and the Management Sciences, Hanover, MD, 2007. pp. 38–61.
• Chao I, Golden B, Wasil E. Theory and Methodology - A fast and effective heuristic for the Orienteering Problem. European Journal of Operational Research 1996; 88: 475-489.
• Noyan N. Risk-averse two-stage stochastic programming with an application to disaster management. Computers and Operations Research 2012; 39(3): 541 – 559.