Studies On The Power Penalty Method And Its Application In The Asymmetric Traffic Assignment Problem

Traffic assignment problem(TAP) is a fundamental problem in the transportation planning and management, the resulting traffic flow provides theoretical basis for the design and evaluation of the transportation planning project. Currently, traffic adminis-trative department tries to alleviate traffic congestion by the strategies such as network design, signal timing and congestion pricing, in which TAP serves as a lower model to provide the real distributions of traffic flow under different schemes. Hence, the TAP have to exactly descirbe the distributions of traffic flow, and also it must be efficiently solved. The classical TAP assumes that the Jacobi matrix of the travel cost function is diagonal. However, in many cases of the real transport systems, the Jacobi of the travel cost function is an asymmetric matrix, which leads to the asymmetric TAP(ATAP). In such situations, it might cause upper decision-making error if the classical TAP is applied to obtain the traffic flow. The ATAP can be reformulated as a variational in-equality (VI) or a nonlinear complementarity problem(NCP). Since the solving of VIs and NCPs is difficult, the efficient methods for the ATAP are scarce, which limits its application.Based on the above-mentioned background, this dissertation mainly works on de-veloping new efficient algorithms for the ATAP. The power penalty method has been proposed recently for the complementarity problems. The method is simple and ef-ficient. We establish new convergence results for the power penalty method for the complementarity problems and extend the method to solve the linearly constrained VI. Then, new efficient algorithms for the ATAP are developed based on the power penalty method.The power penalty method approximates a complementarity problem by a nonlin-ear equation with a penalty term. In the case that the nonlinear mapping involved is continuous and ζ monotone, the solution to the penalty equation converges to that of original problem at the rate of O(1/λk/ζ), where λ>1is the penalty parameter and k>1is the power parameter in the penalty term. Based on these original works, some new convergence results are established for the power penalty method. They are listed as follows:1. When the nonlinear mapping is continuous and ζ monotone, a new upper bound for the constant related to the O(1/λk/ζ) is established for the NCP and mixed complementarity problem(MiCP). The new bound is completely independent of the penalty parameter and is closely related to the solution of the NCP. We also proof that the power penalty method can handle the general monotone NCPs and MiCPs. A sufficient condition that ensures the existence of a solution to the original problem and the penalty equation is presented, which is weaker than the ζ monotonicity.2. The KKT system of a class of linearly constrained VI reformulates the VI as an MiCP, then we develop the power penalty method for this MiCP. Although the function defining this MiCP does not ζ monotone even if the VI is ζ monotone, we also proof the method has the advantage of exponential convergence rates. We also state a sufficient condition for the involved problems to have a solution. Then, we develop the power penalty method for the general linearly constrained VI and prove the convergence of the method. The MiCP associated with the monotone linearly constrained VI is still monotone, hence, the power penalty method has the ability to solve the monotone VI.3. Since the strong monotonicity makes the power penalty method and the solution procedure to the penalty equation have nice convergence properties, the proximal point method is combined with the power penalty method to establish new method for the monotone NCPs and VIs, respectively. In this dissertation, the power penalty method is applied to solve four types ofTAPs:the fixed demand ATAP, the elastic demand ATAP, the non-additive TAP and the TAP under uncertainty in demand. Three basic algorithm frames for the solution of these TAPs are investigated in detail, that is, simplicial decomposition (SD) method, col-umn generation(CG) method and disaggregate simplicial decomposition (DSD) method. The main results are as follows:1. For the fixed demand ATAP, the SD algorithm is proposed to solve the arc-based VI model and the CG method is proposed to solve the path-based VI model, in which the restricted master problems of these two methods are solved by the power penalty method. Numerical experiments show that the two new methods are efficient and the performance of methods are insensitive to the penalty parameter and power parameter.2. Through applying the proximal point method to the restricted master problems of SD and DSD methods, respectively, two new algorithm frames for the fixed demand ATAP are established. The proximal point method solves a monotone problem by solving a sequence of uniformly strong monotone problems which can be efficiently solved by the power penalty method. Numerical results show that the new schemes can improve the efficiency of the original methods.3. For the NCP model of the elastic demand ATAP, within the framework of CG method, a new method based on he power penalty method is presented. The method is effective and not sensitive to the power and penalty parameters, which is confirmed by the computational results.4. For the VI model and NCP model of the non-additive TAP, the CG method based on K shortest path and the power penalty method is developed. The computational experiments consider both the fixed demand and elastic demand problems, and the results confirm the efficiency of the method.5. A reliability-based TAP model under uncertainty in demand is established, in which the vehicle’s stochastic turning delay at the intersections is also considered explic-itly. For this non-additive TAP, the solution of the model presented before is used to compute the numerical example.