Research by Dr. Zhouchun Huang that studies a stochastic traveling salesman problem with random arc costs was publicized in Journal of Global Optimization in September 2018.  Since 1991, the Journal of Global Optimization has been dedicated to publish significant papers that encompass theoretical, computational, and applied aspects of global optimization. It focus primarily on original research contributions dealing with the search for global optima of non-convex, multi-extremal problems. “It is extremely challenging to solve the proposed NP-hard combinatorial optimization problem with nonlinear risk constraint,”  the authors noted. Abstract is copied below.

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.

Figure 1. left: the probability distributions of optimal total cost in deterministic vs. stochastic models;      right: the changes in VaR/CVaR through the cutting plane algorithm.

Read the paper “A cutting plane method for risk-constrained traveling salesman problem with random arc costs” published in Journal of Global Optimization.