Robust Approach to Discrete Network Designs with Demand Uncertainty

A discrete network design problem under demand uncertainty is considered. It is assumed that the future travel demand for each origin-destination (O-D) pair can take on nominal or one of several other values, where the probabilities of occurrence of these values are unknown. However, the vector of O-D demands realized for the network must belong to an uncertainty set, a set that allows demands for a group of O-D pairs to deviate from their nominal values simultaneously. A robust counterpart of deterministic discrete network design is formulated as a mathematical program with complementarity constraints under the Wardropian user equilibrium conditions. The algorithm proposed for the problem terminates in a finite number of iterations and converges to a global optimum solution under certain conditions. Numerical results that use two networks from the literature empirically demonstrate that the algorithm is effective and has the potential to solve realistic problems.