Decomposition-based exact algorithms for risk-constrained traveling salesman problems with discrete random arc costs. (English) Zbl 1335.90082
Summary: Recently increasing attentions have been given to uncertainty handling in network optimization research. Along this trend, this paper discusses traveling salesman problem with discrete random arc costs while incorporating risk constraints. Minimizing expected total cost might not be enough because total costs of some realizations of the random arc costs might exceed the resource limit. To this respect, this paper presents a model of the traveling salesman problem that incorporates risk constraints based on Conditional Value at Risk to evaluate those worst-cost scenarios. Exact solution methods are developed and applied on the risk-constrained traveling salesman problem. Numerical experiments are conducted, and the results show the ability of the proposed methods in reducing the computational complexity.
MSC:
| 90C27 | Combinatorial optimization |
Keywords:
reliable routing; traveling salesman problem; conditional value at risk; Benders decompositionReferences:
| [1] | Alexander, G.J., Baptista, A.M.: A comparison of VAR and CVaR constraints on portfolio selection with the mean-variance model. Manag. Sci. 50(9), 1261-1273 (2004) · doi:10.1287/mnsc.1040.0201 |
| [2] | Arulselvan, A., Commander, C.W., Pardalos, P.: A hybrid genetic algorithm for the target visitation problem (2007) · Zbl 1190.93094 |
| [3] | Bertsimas, D.J.: A vehicle routing problem with stochastic demand. Oper. Res. 40, 574-585 (1992) · Zbl 0764.90030 · doi:10.1287/opre.40.3.574 |
| [4] | Boginski, V.L., Commander, C.W., Turko, T.: Polynomial-time identication of robust network flows under uncertain arc failures. Optim. Lett. 3, 461-473 (2009) · Zbl 1169.90323 · doi:10.1007/s11590-009-0125-x |
| [5] | Boyles, S.D., Waller, S.T.: A mean-variance model for the minimum cost flow problem with stochastic arc costs. Networks 56(3), 215-227 (2010) · Zbl 1205.90065 · doi:10.1002/net.20374 |
| [6] | Fan, N., Zheng, Q.P., Pardalos, P.M.: Robust optimization of graph partitioning involving interval uncertainty. Theor. Comput. Sci. 447, 53-61 (2012) · Zbl 1245.05101 · doi:10.1016/j.tcs.2011.10.015 |
| [7] | Glockner, G.D., Nemhauser, G.L., Tovey, C.A.: Dynamic network flow with uncertain arc capacities: decomposition algorithm and computational results. Comput. Optim. Appl. 18(3), 233-250 (2001) · Zbl 1009.90016 · doi:10.1023/A:1011233219223 |
| [8] | Laporte, G.: A concise guide to the traveling salesman problem. J. Oper. Res. Soc. 61, 35-40 (2010) · Zbl 1193.90179 · doi:10.1057/jors.2009.76 |
| [9] | Leipälä, T.: On the solutions of stochastic traveling salesman problems. Eur. J. Oper. Res. 2(4), 291-297 (1978) · Zbl 0378.90072 |
| [10] | Levy, D., Sundar, K., Rathinam, S.: Heuristics for routing heterogeneous unmanned vehicles with fuel constraints. Math. Probl. Eng. 2014, 1-12, Art ID 131450 (2014) · Zbl 1407.90389 |
| [11] | Marlow, D.O., Kilby, P., Mercer, G.N.: The travelling salesman problem in maritime surveillance-techniques, algorithms and analysis. In: Proceedings of the International Congress on Modelling and Simulation, pp. 684-690 (2007) · Zbl 1245.05101 |
| [12] | Mendoza, J.E., Villegas, J.G.: A multi-space sampling heuristic for the vehicle routing problem with stochastic demands. Optim. Lett. 7, 1503-1516 (2013) · Zbl 1280.90012 · doi:10.1007/s11590-012-0555-8 |
| [13] | Oberlin, P., Rathinam, S., Darbha, S.: Today’s traveling salesman problem: heterogeneous, multiple depot, multiple uav routing problem. IEEE Robot. Autom. Mag. 17, 70-77 (2010) · doi:10.1109/MRA.2010.938844 |
| [14] | Rockafellar, R.T., Uryasev, S.: Optimization of conditional value-at-risk. J. Risk 2(3), 21-42 (2000) |
| [15] | Ryan, J.L., Bailey, T.G., Moore, J.T., Carlton, W.B.: Reactive tabu search in unmanned aerial reconnaissance simulations. In: Proceedings of the I998 Winter Simulation Conference, vol. 1, pp. 873-879 (1998) |
| [16] | Sarykalin, S., Serraino, G., Uryasev, S.: Value-at-risk vs. conditional value-at-risk in risk management and optimization. In: INFORMS Tutorial in Operations Research, pp. 270-294 (2008) · Zbl 1009.90016 |
| [17] | Toriello, A., Haskell, W.B., Poremba, M.: A dynamic traveling salesman problem with stochastic arc costs. Oper. Res. (2014). http://dx.doi.org/10.1287/opre.2014.1301 · Zbl 1327.90270 |
| [18] | Verweij, B., Ahmed, S., Kleywegt, A.J., Nemhauser, G., Shapiro, A.: The sample average approximation method applied to stochastic routing problems: a computational study. Comput. Optim. Appl. 24(2), 289-333 (2003) · Zbl 1094.90029 · doi:10.1023/A:1021814225969 |
| [19] | Yadlapalli, S., Rathinam, S., Darbha, S.: 3-approximation algorithm for a two depot, heterogeneous traveling salesman problem. Optim. Lett. 6, 141-152 (2012) · Zbl 1259.90116 · doi:10.1007/s11590-010-0256-0 |
| [20] | Zheng, Q.P., Pardalos, P.M.: Stochastic and risk management models and solution algorithm for natural gas transmission network expansion and lng terminal location planning. J. Optim. Theory Appl. 147, 337-357 (2010) · Zbl 1202.90205 · doi:10.1007/s10957-010-9725-y |
| [21] | Zheng, Q.P., Shen, S., Shi, Y.: Loss-constrained minimum cost flow under arc failure uncertainty with applications in risk-aware kidney exchange (2014, submitted) |
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.
