  This paper develops a fast algorithm for computing the equilibrium assignment
with the perturbed utility route choice (PURC) model. Without compromise, this
allows the significant advantages of the PURC model to be used in large-scale
applications. We formulate the PURC equilibrium assignment problem as a convex
minimization problem and find a closed-form stochastic network loading
expression that allows us to formulate the Lagrangian dual of the assignment
problem as an unconstrained optimization problem. To solve this dual problem,
we formulate a quasi-Newton accelerated gradient descent algorithm (qN-AGD*).
Our numerical evidence shows that qN-AGD* clearly outperforms a conventional
primal algorithm as well as a plain accelerated gradient descent algorithm.
qN-AGD* is fast with a runtime that scales about linearly with the problem
size, indicating that solving the perturbed utility assignment problem is
feasible also with very large networks.
