The Research Of Modeling And Algorithms On Traffic Assignment Problem With Side Constraints

Traffic assignment is the basic theory for transportation planning,traffic network design and congestion charging problems,and has an important research value.The traffic assignment theory has further developed a series of theoretical models that have a stronger ability to describe the actual traffic system.The traffic assignment problem with side constraints is a typical representative of them.However,the theoretical developments cannot be applied to engineering practice due to the lack of algorithms that can solve these models with high efficiency and accuracy in large-scale networks.The goal of this paper is to design algorithms for traffic assignment problems with side constraints.The design of efficient algorithms is important to help engineering practice using the results of theoretical developments.The main contents of this thesis have four parts as follows:(1)Chapter 2 of the thesis summarizes the model and mathematical properties of the traffic assignment problem and the traffic assignment problem with side constraints.The focus is on summarizing the physical significance,mathematical form,existence and uniqueness of the optimal solution for the two case models of the capacitied traffic assignment problem and the maximum entropy user equilibrium.For the capacitied traffic assignment problem,if the multiplier of capacity constraints are considered as queuing delay and the sum of travel time and delay is defined as generalized cost,the KKT conditions follow the user equilibrium based on the generalized cost.For the maximum entropy user equilibrium,an equivalent set of proportionality conditions can be derived from the KKT conditions,where the second-order proportionality conditions have good physical meaning.But the solution satisfying only the second-order proportionality conditions is not the optimal solution for MEUE.(2)In the third chapter of the thesis,the principles,formulas and calculation steps of the augmented Lagrangian multiplier method under both equation constraints and inequality constraints are summarized.An algorithmic framework for the traffic assignment problem with side constraints is proposed.By solving the approximate problem and updating the multipliers to obtain the next approximate problem,the optimal solution of the original problem is obtained after several iterations while the multipliers converge to the optimal multipliers.The mathematical form of the approximate problem is similar to that of the traffic assignment problem,so the algorithm of the traffic assignment problem can be used to solve the approximate problem.(3)In Chapter 4 of the thesis,an algorithm for the capacitied traffic assignment problem is designed.Firstly,the approximate problem is constructed according to the principle of ALM,and the parameter updating strategy and convergence evaluation index are proposed according to the algorithm framework.Then the design process of the algorithm for solving the approximate problem is elaborated.The approximation problem is decomposed into a series of single OD subproblems.The subproblems are reduced to quadratic programming and the first and second order derivatives and KKT conditions are derived,and then solved using the Greedy algorithm.Pseudocode for the subproblems and the general procedure of the algorithm is then given.Finally,numerical experiments are performed in three networks of different sizes.The experiments in the Hearn network show that the results of this algorithm outperform the results of several existing studies.Experiments in two large-scale networks show that that too large accuracy limit for approximate problem can lead to overall convergence failure,and the adaptive accuracy limit designed in this paper can better balance the accuracy requirement and computation time.(4)In Chapter 5 of the paper,the algorithm of the maximum entropy user equilibrium is designed.Again,firstly,the approximate problem is constructed according to the principle of ALM,and the parameter updating strategy and convergence evaluation index are proposed according to the algorithm framework.Then the design process of the algorithm for solving the approximate problem is elaborated.The approximate problem is decomposed into a series of single-origin subproblems.The first and second order derivatives of the subproblems and the iterative formulas of the Newton method are derived.In order to solve the subproblems efficiently,e PAS is defined and a method for constructing and storing e PAS is given.The overall procedure and convergence proof of the algorithm are then given.Since the algorithm is suitable for multi-threaded operation,a version of the algorithm adapted to multi-threaded execution is also given.Finally numerical experiments are carried out by performing them in four networks of different sizes.The experiments in two small-sized networks show that the results of this algorithm satisfy all proportionality conditions under certain accuracy limit.Experiments in two other large-scale networks verify the efficiency and applicability of the present algorithm to multiple threads.In summary,this paper studies a class of algorithm design methods for the traffic assignment problem with side constraints,and designs algorithms that can be efficiently solved in large-scale networks for two case models.This research has a driving effect on the algorithm design of other problems of this kind and the application of this kind of problems in engineering practice.