Decomposition-Based Exact Algorithms For Risk-Constrained Traveling Salesman Problems With Discrete Random Arc Costs

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