A cutting plane method for risk-constrained traveling salesman problem with random arc costs

摘要

In this manuscript, we consider a stochastic traveling salesman problem with random arc costs and assume that the travel cost of each arc follows a normal distribution. All the other parameters in the problem are considered deterministic. In the presence of uncertainty, the optimal route achieved from solving the deterministic model might be exposed to a high risk that the actual cost exceeds the available resource. In this respect, we present the stochastic model incorporating risk management, and the Value at Risk and Conditional Value at Risk techniques are applied as the risk measures to assess and control the risk associated with the uncertainty. A novel cutting plane algorithm is developed to deal with the difficulty of solving such model, and exhibits superior computational performance in our numerical experiments over other solution approaches.