A Skew Gradient-Based Newton Method for Traffic Assignment with Side Constraints

In this paper we describe how the capacitated user equilibrium can be approximated by sequential uncapacitated models by the use of a penalty function. The efficiency of the method is governed by the algorithmic performance of the uncapacitated model. A skew gradient-based Newton method is used to solve the capacitated user equilibrium within the feasible region of path flows. In the path-flow region, the straight gradient is defined as the derivative of the objective function with respect to the flow of the corresponding path, while the skew gradient is defined for each particular origin destination pair and is characterized by the average cost of all the paths for that pair. Instead of movement of flow toward the shortest path, in the equilibration procedure path flows below the average decrease and path flows above the average increase. The characteristics of the Newton method with the column generation procedure are combined to achieve the efficient determination of the equilibrium point. Numerical experiments demonstrate the excellent performance of the proposed method and highlight its potential applications.