Network routing problems are often modeled with the assumption that the network structure is deterministic, though they are often subject to uncertainty in many real-life scenarios. In this paper, we… Click to show full abstract
Network routing problems are often modeled with the assumption that the network structure is deterministic, though they are often subject to uncertainty in many real-life scenarios. In this paper, we study the traveling salesman and the shortest path problems with uncertain topologies modeled by arc failures. We present the formulations that incorporate chance constraints to ensure reliability of the selected route considering all arc failure scenarios. Due to the computational complexity and large scales of these stochastic network optimization problems, we consider two cutting plane methods and a Benders decomposition algorithm to respectively solve them. We also consider to solve the reformulations of the problems obtained by taking the logarithm transformation of the chance constraints. Numerical experiments are performed to obtain results for comparisons among these proposed methods.
               
Click one of the above tabs to view related content.