A modified truncated Newton algorithm for the logit-based stochastic user equilibrium problem

摘要

In this paper, we investigate Newton type algorithms to solve the path-based logit stochastic user equilibrium problem in static traffic assignment. This problem is in essence an equality constrained minimization problem. Traditionally, we can first use the variable reduction method to transform this problem into an unconstrained one, and then apply the truncated Newton method to solve this unconstrained minimization problem. All procedures are performed in the reduced variable space. However, we do not know a priori which variables are appropriate to be chosen as reduced variables. If the reduced variables are poorly chosen, sometimes the computation times may be unacceptably high, due to the ill conditioning of the reduced Newton equation. To overcome this drawback, we propose a modified truncated Newton (MTN) algorithm. Compared to the traditional algorithm above, MTN has three distinct features: (1) The iteration point and search direction are generated in the original variable space. (2) The Newton equation is approximately solved in the reduced variable space. (3) The reduced variables can be changed from one iteration to another. These features make MTN particularly suitable for the path-based SUE problem and exhibits superlinear convergence. In order to efficiently solve the reduced Newton equation in each iteration, we propose a principle on how to select the reduced variables. We compare the MTN algorithm with the Gradient Projection (GP) algorithm on the Sioux Falls and Winnipeg networks. The GP algorithm is one of the most efficient algorithms that currently exists for solving the problem. We show that with suitable settings, our MTN algorithm outperforms the GP algorithm, in particular in network problems with high levels of congestion and where the route choice is more deterministic (i.e., more sensitive to route costs), which are the hardest traffic assignment problems to solve. We therefore conclude that our MTN algorithm is currently the fastest algorithm for solving such complex traffic assignment problems.