Constrained Newton Methods for Transport Network Equilibrium Analysis  

作　　者：程琳 许项东 邱松林 

机构地区：[1]School of Transportation,Southeast University

出　　处：《Tsinghua Science and Technology》2009年第6期765-775,共11页清华大学学报（自然科学版（英文版）

基　　金：Supported by the National Natural Science Foundation of China (No.50678037);the National Key Basic Research and Development (973) Program of China (No.2006CB705500);the National High-Tech Research and Development (863) Program of China (No.2007AA11Z205)

摘　　要：A set of constrained Newton methods were developed for static traffic assignment problems. The Newton formula uses the gradient of the objective function to determine an improved feasible direction scaled by the second-order derivatives of the objective function. The column generation produces the active paths necessary for each origin-destination pair. These methods then select an optimal step size or make an orthogonal projection to achieve fast, accurate convergence. These Newton methods based on the constrained Newton formula utilize path information to explicitly implement Wardrop＇s principle in the transport network modelling and complement the traffic assignment algorithms. Numerical examples are presented to compare the performance with all possible Newton methods. The computational results show that the optimal-step Newton methods have much better convergence than the fixed-step ones, while the Newton method with the unit step size is not always efficient for traffic assignment problems. Furthermore, the optimal-step Newton methods are relatively robust for all three of the tested benchmark networks of traffic assignment problems.A set of constrained Newton methods were developed for static traffic assignment problems. The Newton formula uses the gradient of the objective function to determine an improved feasible direction scaled by the second-order derivatives of the objective function. The column generation produces the active paths necessary for each origin-destination pair. These methods then select an optimal step size or make an orthogonal projection to achieve fast, accurate convergence. These Newton methods based on the constrained Newton formula utilize path information to explicitly implement Wardrop＇s principle in the transport network modelling and complement the traffic assignment algorithms. Numerical examples are presented to compare the performance with all possible Newton methods. The computational results show that the optimal-step Newton methods have much better convergence than the fixed-step ones, while the Newton method with the unit step size is not always efficient for traffic assignment problems. Furthermore, the optimal-step Newton methods are relatively robust for all three of the tested benchmark networks of traffic assignment problems.

关 键 词：traffic assignment network flow Newton method column generation line search 

分 类 号：O157.5[理学—数学]