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....[ Read more ]

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. For the O-D matrix estimation problem, a novel single level optimization formulation for the simultaneous estimation of the O-D (Origin-Destination) matrix and the parameter θ in a congested stochastic network is created. The analytical expressions of the derivatives for the logit-based SUE constraints with respect to the O-D demand and the parameter θ are derived and these derivatives can also be obtained by using a stochastic user equilibrium loading approach. Moreover, a SQP (Successive Quadratic Programming) solution method is presented to solve this problem. It should be pointed out that this method only converges to a KKT point of the problem under mild conditions. Fourth, we use the bilevel programming approach to model three types of transportation problem and also present the corresponding algorithm for these problems. For the combined land-use and transportation model for work trips problem, a new bilevel programming model is established to find the maximum work trip generation and the corresponding heuristic algorithm is proposed. For the highway pricing and capacity choice problem in a road network under the BOT scheme, we propose a general bilevel programming model and then four bilevel programming models are specified for various economic criterions. In particular, a simple example with two-dimensional representation of the highway pricing and capacity choice problem in a road network provides a meaningful economic interpretation of the relevant mathematical models. For the network design problem, a new idea addressing the equity issue in terms of the change of the equilibrium O-D travel cost is proposed and four bilevel programming models for the continuous network design problem regarding this equity issue are developed. In order to find the global optima for these bilevel programming models, a penalty function approach embodying a simulated annealing method is provided. Finally, through studying the sensitivity analysis of the general stochastic user equilibrium problem, we confirm that the SUE link flows are the once continuously differentiable functions with respect to the perturbed parameters. Then, the bilevel programming models for the bilevel transportation problems with the stochastic user equilibrium constraint generally belong to the continuously differentiable optimization problems. Hence, a framework of the SQP algorithm as a unified method to solve this kind of problem is also designed. Finally all of the models and the relevant algorithms proposed in this thesis are tested by corresponding examples.