Alternative Quasi-Newton Methods for Capacitated User Equilibrium Assignment

Abstract

Two quasi-Newton methods are proposed to deal with traffic assignment in a capacitated network. The methods combine Newton formula, column generation, and penalty techniques. The first method uses the gradient of the objective function to obtain an improving feasible direction scaled by the second-order derivatives. The second one uses a Rosen gradient to obtain an improving direction scaled by the corresponding origin–destination demand. Both methods make a line search to obtain an optimal step size to guarantee the feasibility of either path or link flow. The proposed methods are of fast convergence and high accuracy at the expense of saving path information. Numerical examples verify their efficiency and stability. The quasi-Newton method with a straight gradient demonstrates more stability than the Rosen gradient for capacitated traffic assignment.