Global optimization method for network design problem with stochastic user equilibrium

• Continuous network design problem with stochastic user equilibrium is explored.
• The problem is reformulated as a nonlinear nonconvex programming.
• A tight mixed-integer linear programming relaxation is derived.
• A global optimization method based on range reduction technique is proposed.

In this paper, we consider the continuous road network design problem with stochastic user equilibrium constraint that aims to optimize the network performance via road capacity expansion. The network flow pattern is subject to stochastic user equilibrium, specifically, the logit route choice model. The resulting formulation, a nonlinear nonconvex programming problem, is firstly transformed into a nonlinear program with only logarithmic functions as nonlinear terms, for which a tight linear programming relaxation is derived by using an outer-approximation technique. The linear programming relaxation is then embedded within a global optimization solution algorithm based on range reduction technique, and the proposed approach is proved to converge to a global optimum.