Models and algorithm for stochastic network designs

摘要

The network design problem (NDP) is one of the most difficult and challenging problems in transportation. Traditional NDP models are often posed as a deterministic bilevel program assuming that all relevant inputs are known with certainty. This paper presents three stochastic models for designing transportation networks with demand uncertainty. These three stochastic NDP models were formulated as the expected value model, chance-constrained model, and dependent-chance model in a bilevel programming framework using different criteria to hedge against demand uncertainty. Solution procedures based on the traffic assignment algorithm, genetic algorithm, and Monte-Carlo simulations were developed to solve these stochastic NDP models. The nonlinear and nonconvex nature of the bilevel program was handled by the genetic algorithm and traffic assignment algorithm, whereas the stochastic nature was addressed through simulations. Numerical experiments were conducted to evaluate the applicability of the stochastic NDP models and the solution procedure. Results from the three experiments show that the solution procedures are quite robust to different parameter settings.