Bilevel transportation modeling and optimization

In this dissertation, we focus on the bilevel transportation problem with a network equilibrium constraint that describes the behavior of network users' route choice. From the mathematical viewpoints, the bilevel transportation problem with the network equilibrium constraint can be characterized by the bilevel programming model in which the lower level problem is a nonlinear programming problem that represents the network equilibrium problem. It is well known that the bilevel programming problem is one of the hardest problems to solve in nonlinear programming. Therefore, it is a significant and challenging issue to study the relevant models and algorithms for the bilevel transportation problem by exploring its inherent nature.; First of all, the current state of research is reviewed on models and algorithms in bilevel transportation problem with the network user equilibrium constraint. In general, these existing models and algorithms are classified into seven and four categories, respectively. Secondly, we study the travel demand sensitivity analysis for the deterministic user equilibrium problem that is useful for development of algorithms for solving the bilevel programming problems. We conclude that the deterministic user equilibrium link flows generally are directionally differentiable with respect to the perturbed parameters even if only travel demands are perturbed. This implies that the algorithm based on the sensitivity analysis for the bilevel transportation problem may not be defined well. Thirdly, by identifying the natures of some existing bilevel transportation problems with the network equilibrium constraint, we can design more efficient algorithms for these problems. For the standard continuous network design problem, a single level continuously differentiable optimization model in terms of link flows is proposed. This model results from the proof of the continuously differentiability of the marginal function defined for this special problem. Furthermore, the derivative information of this marginal function can be obtained by implementing a deterministic user equilibrium traffic assignment. Based on the derivative information, a convergent augmented Lagrangian method under certain conditions is designed to find a KKT (Karush-Kuhn-Tucker) point of the equivalent model and it is also available for the large-scale problem. (Abstract shortened by UMI.)...