×

Two-stage robust optimization for the orienteering problem with stochastic weights. (English) Zbl 1454.90079

Summary: In this paper, the two-stage orienteering problem with stochastic weights is studied, where the first-stage problem is to plan a path under the uncertain environment and the second-stage problem is a recourse action to make sure that the length constraint is satisfied after the uncertainty is realized. First, we explain the recourse model proposed by L. Evers et al. [Comput. Oper. Res. 43, 248–260 (2014; Zbl 1348.90085)] and point out that this model is very complex. Then, we introduce a new recourse model which is much simpler with less variables and less constraints. Based on these two recourse models, we introduce two different two-stage robust models for the orienteering problem with stochastic weights. We theoretically prove that the two-stage robust models are equivalent to their corresponding static robust models under the box uncertainty set, which indicates that the two-stage robust models can be solved by using common mathematical programming solvers (e.g., IBM CPLEX optimizer). Furthermore, we prove that the two two-stage robust models are equivalent to each other even though they are based on different recourse models, which indicates that we can use a much simpler model instead of a complex model for practical use. A case study is presented by comparing the two-stage robust models with a one-stage robust model for the orienteering problem with stochastic weights. The numerical results of the comparative studies show the effectiveness and superiority of the proposed two-stage robust models for dealing with the two-stage orienteering problem with stochastic weights.

MSC:

90C27 Combinatorial optimization
90B06 Transportation, logistics and supply chain management
90C15 Stochastic programming

Citations:

Zbl 1348.90085

Software:

CPLEX

References:

[1] Evers, L.; Glorie, K.; Van Der Ster, S.; Barros, A. I.; Monsuur, H., A two-stage approach to the orienteering problem with stochastic weights, Computers & Operations Research, 43, 248-260 (2014) · Zbl 1348.90085 · doi:10.1016/j.cor.2013.09.011
[2] Golden, B. L.; Levy, L.; Vohra, R., The orienteering problem, Naval Research Logistics, 34, 3, 307-318 (1987) · Zbl 0647.90099 · doi:10.1002/1520-6750(198706)34:3<307::aid-nav3220340302>3.0.co;2-d
[3] Mufalli, F.; Batta, R.; Nagi, R., Simultaneous sensor selection and routing of unmanned aerial vehicles for complex mission plans, Computers & Operations Research, 39, 11, 2787-2799 (2012) · Zbl 1251.90409 · doi:10.1016/j.cor.2012.02.010
[4] Evers, L.; Dollevoet, T.; Barros, A. I.; Monsuur, H., Robust UAV mission planning, Annals of Operations Research, 222, 1, 293-315 (2014) · Zbl 1303.90075 · doi:10.1007/s10479-012-1261-8
[5] Vansteenwegen, P.; Van Oudheusden, D., The mobile tourist guide: an or opportunity, OR Insight, 20, 3, 21-27 (2007) · doi:10.1057/ori.2007.17
[6] Gavalas, D.; Konstantopoulos, C.; Mastakas, K.; Pantziou, G., A survey on algorithmic approaches for solving tourist trip design problems, Journal of Heuristics, 20, 3, 291-328 (2014) · doi:10.1007/s10732-014-9242-5
[7] Howe, J., Crowdsourcing: How the Power of the Crowd Is Driving the Future of Business (2008), New York, NY, USA: Random House, New York, NY, USA
[8] Yuen, M.-C.; King, I.; Leung, K.-S., A survey of crowdsourcing systems, Proceedings of the 2011 IEEE Third International Conference on Privacy, Security, Risk and Trust (PASSAT) and 2011 IEEE Third Inernational Conference on Social Computing (SocialCom), IEEE · doi:10.1109/PASSAT/SocialCom.2011.203
[9] Vansteenwegen, P.; Souffriau, W.; Oudheusden, D. V., The orienteering problem: a survey, European Journal of Operational Research, 209, 1, 1-10 (2011) · Zbl 1205.90253 · doi:10.1016/j.ejor.2010.03.045
[10] Gunawan, A.; Lau, H. C.; Vansteenwegen, P., Orienteering problem: a survey of recent variants, solution approaches and applications, European Journal of Operational Research, 255, 2, 315-332 (2016) · Zbl 1346.90703 · doi:10.1016/j.ejor.2016.04.059
[11] Ilhan, T.; Iravani, S. M.; Daskin, M. S., The orienteering problem with stochastic profits, IIE Transactions, 40, 6, 406-421 (2008) · doi:10.1080/07408170701592481
[12] Campbell, A. M.; Gendreau, M.; Thomas, B. W., The orienteering problem with stochastic travel and service times, Annals of Operations Research, 186, 1, 61-81 (2011) · Zbl 1225.90024 · doi:10.1007/s10479-011-0895-2
[13] Varakantham, P.; Kumar, A., Optimization approaches for solving chance constrained stochastic orienteering problems, Proceedings of the International Conference on Algorithmic Decision Theory, Springer · Zbl 1404.90050 · doi:10.1007/978-3-642-41575-3_30
[14] Zhang, S.; Ohlmann, J. W.; Thomas, B. W., A priori orienteering with time windows and stochastic wait times at customers, European Journal of Operational Research, 239, 1, 70-79 (2014) · Zbl 1339.90073 · doi:10.1016/j.ejor.2014.04.040
[15] Shapiro, A.; Philpott, A., A tutorial on stochastic programming, Manuscript (2007), http://www2.isye.gatech.edu/ashapiro/publications.html
[16] Ben-Tal, A.; Goryashko, A.; Guslitzer, E.; Nemirovski, A., Adjustable robust solutions of uncertain linear programs, Mathematical Programming, 99, 2, 351-376 (2004) · Zbl 1089.90037 · doi:10.1007/s10107-003-0454-y
[17] An, Y.; Zeng, B., Exploring the modeling capacity of two-stage robust optimization: variants of robust unit commitment model, IEEE Transactions on Power Systems, 30, 1, 109-122 (2015) · doi:10.1109/tpwrs.2014.2320880
[18] Wang, B.; Wang, S.; Zhou, X.-z.; Watada, J., Two-stage multi-objective unit commitment optimization under hybrid uncertainties, IEEE Transactions on Power Systems, 31, 3, 2266-2277 (2016) · doi:10.1109/tpwrs.2015.2463725
[19] Atamtürk, A.; Zhang, M., Two-stage robust network flow and design under demand uncertainty, Operations Research, 55, 4, 662-673 (2007) · Zbl 1167.90409 · doi:10.1287/opre.1070.0428
[20] Takeda, A.; Taguchi, S.; Tütüncü, R. H., Adjustable robust optimization models for a nonlinear two-period system, Journal of Optimization Theory and Applications, 136, 2, 275-295 (2008) · Zbl 1146.90075 · doi:10.1007/s10957-007-9288-8
[21] Hanasusanto, G. A.; Kuhn, D.; Wiesemann, W., K-adaptability in two-stage robust binary programming, Operations Research, 63, 4, 877-891 (2015) · Zbl 1329.90164 · doi:10.1287/opre.2015.1392
[22] Feige, U.; Jain, K.; Mahdian, M.; Mirrokni, V., Robust combinatorial optimization with exponential scenarios, Proceedings of the International Conference on Integer Programming and Combinatorial Optimization, Springer · Zbl 1136.90451 · doi:10.1007/978-3-540-72792-7_33
[23] Bertsimas, D.; Goyal, V.; Lu, B. Y., A tight characterization of the performance of static solutions in two-stage adjustable robust linear optimization, Mathematical Programming, 150, 2, 281-319 (2015) · Zbl 1309.90121 · doi:10.1007/s10107-014-0768-y
[24] Mehrjerdi, H., Dynamic and multi-stage capacity expansion planning in microgrid integrated with electric vehicle charging station, Journal of Energy Storage, 29 (2020) · doi:10.1016/j.est.2020.101351
[25] Haghi, M.; Fatemi Ghomi, S. M. T.; Jolai, F., Developing a robust multi-objective model for pre/post disaster times under uncertainty in demand and resource, Journal of Cleaner Production, 154, 188-202 (2017) · doi:10.1016/j.jclepro.2017.03.102
[26] Amjady, N.; Attarha, A.; Dehghan, S.; Conejo, A. J., Adaptive robust expansion planning for a distribution network with ders, IEEE Transactions on Power Systems, 33, 2, 1698-1715 (2017) · doi:10.1109/tpwrs.2017.2741443
[27] Zeng, B.; Dong, H.; Sioshansi, R.; Xu, F.; Zeng, M., Bi-level robust optimization of electric vehicle charging stations with distributed energy resources, IEEE Transactions on Industry Applications, 56, 5, 5836-5847 (2020) · doi:10.1109/tia.2020.2984741
[28] Zeng, B.; Feng, J.; Liu, N.; Liu, Y., Co-optimized public parking lot allocation and incentive design for efficient pev integration considering decision-dependent uncertainties, IEEE Transactions on Industrial Informatics (2020) · doi:10.1109/tii.2020.2993815
[29] Bertsimas, D.; Pachamanova, D.; Sim, M., Robust linear optimization under general norms, Operations Research Letters, 32, 6, 510-516 (2004) · Zbl 1054.90046 · doi:10.1016/j.orl.2003.12.007
[30] Ben-Tal, A.; El Ghaoui, L.; Nemirovski, A., Robust Optimization (2009), Princeton, NJ, USA: Princeton University Press, Princeton, NJ, USA · Zbl 1221.90001
[31] Tsiligirides, T., Heuristic methods applied to orienteering, Journal of the Operational Research Society, 35, 9, 797-809 (1984) · doi:10.2307/2582629
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.