Algorithms for logit-based stochastic user equilibrium assignment

The paper proposes an efficient algorithm for determining the stochastic us er equilibrium solution for logit-based loading. The commonly used Method o f Successive Averages typically has a very slow convergence rate. The new a lgorithm described here uses Williams' result [ Williams, H. C. W. L. (1977 ) On the formation of travel demand models and economic evaluation measures of user benefit. Environment and Planning 9A(3), 285-344] which enables th e expected value of the perceived travel costs S-rs to be readily calculate d for any flow vector x. This enables the value of the Sheffi and Powell ob jective function [Sheffi, Y. and Powell, W. B. (1982) An algorithm for the equilibrium assignment problem with random link times. Networks 12(2), 191- 207], and its gradient in any specified search direction, to be calculated. It is then shown how, at each iteration, an optimal step length along the search direction can be easily estimated, rather than using the pre-set ste p lengths, thus giving much faster convergence. The basic algorithm uses th e standard search direction (towards the auxiliary solution). In addition t he performance of two further versions of the algorithm are investigated, b oth of which use an optimal step length but alternative search directions,b ased on the Davidon-Fletcher-Powell function minimisation method. The first is an unconstrained and the second a constrained version. Comparisons are made of all three versions of the algorithm, using a number of test network s ranging from a simple three-link network to one with almost 3000 links. I t is found that for all but the smallest network the version using the stan dard search direction gives the fastest rate of convergence. Extensions to allow for multiple user classes and elastic demand are also possible. (C) 1 998 Elsevier Science Ltd. All rights reserved.