Solve the Discrete Network Design Problem Under Construction cost Uncertainties with the Stochastic Programming Approach

摘要

The discrete network design problem (DNDP) under construction cost uncertainties deals with the selection of the links to be added to the existing road network, so that the given demand can be satisfied. It is assumed that the cost of each potential link construction follows a certain stochastic distribution. In this paper, a bi-level stochastic programming model for DNDP is proposed, in which the upper-level model is a chance constrain model with the objective function of minimizing the total travel costs in the network; the lower-level model is a user equilibrium model. A genetic algorithm is designed to solve the model in an efficient way. A comprehensive computational experiment is conducted to illustrate the correctness and efficiency of the model and the algorithm proposed in this paper. The result shows that the uncertain model is more flexible and practical than the deterministic one.