On the applicability and solution of bilevel optimization models in transportation science: A study on the existence, stability and computation of optimal solutions to stochastic mathematical programs with equilibrium constraints

Bilevel optimization models, and more generally MPEC (mathematical programwith equilibrium constraints) models, constitute important modelling tools intransportation science and network games, as they place the classic``what-if\u27\u27 analysis in a proper mathematical framework. The MPEC model isalso becoming a standard for the computation of optimal design solutions,where ``design\u27\u27 may include either or both of network infrastructureinvestments and various types of tolls. At the same time, it does normally notsufficiently well take into account possible uncertainties and/orperturbations in problem data (travel costs and demands), and thus may not apriori guarantee robust designs under varying conditions. We consider naturalstochastic extensions to a class of MPEC traffic models which explicitlyincorporate data uncertainty. In stochastic programming terminology, weconsider ``here-and-now\u27\u27 models where decisions on the design must be madebefore observing the uncertain parameter values and the responses of thenetwork users, and the design is chosen to minimize the expectation of theupper-level objective function. Such a model could, for example, be used toderive a fixed link pricing scheme that provides the best revenue for a givennetwork over a given time period, where the varying traffic conditions aredescribed by distributions of parameters in the link travel time and OD demandfunctions.For a general such SMPEC network model we establish not only the existence ofoptimal solutions, but in particular their stability to perturbations in theprobability distribution. We also provide convergence results for generalalgorithmic schemes based on the penalization of the equilibrium conditions orpossible joint upper-level constraints, as well as for algorithms based on thediscretization of the probability distribution, the latter enabling theutilization of standard MPEC algorithms. Especially the latter part utilizesrelations between the traffic application of SMPEC and stochastic structuraltopology optimization problems