This paper considers the risk-constrained stochastic traveling salesman problem with random arc costs. In the context of stochastic arc costs, the deterministic traveling salesman problem's optimal solutions would be ineffective because the selected route might be exposed to a greater risk where the actual cost can exceed the resource limit in extreme scenarios. We present a stochastic model of the traveling salesman problem that incorporates risk management. Value at Risk and Conditional Value at Risk are respectively applied to measure and control the risk experiencing overly costly scenarios. We propose a novel cutting plane method to find the minimum-cost route in the stochastic environment while the risk level of the route is controlled by bounding the risk measures. Computational experiments are conducted to demonstrate the properties of the proposed models and the performance of the proposed cutting plan algorithm.
Article
View A Cutting Plane Method for Risk-constrained Traveling Salesman Problem with Random Arc Costs