Search

A family of algorithms for assigning trips onto a road network is developed based on “stochastic” models of route choice which explicitly allow non minimum cost routes to be used. Several alternative formulations are identified and compared both from a theoretical point of view and by a series of tests on a representative London network. As a result of these a “best” choice is given. Although the methods described are most appropriate to networks where congestion effects are unimportant their convergence behaviour with congestion included has also been tested; for the particular network and cost-volume relationships considered a satisfactory degree of convergence could not be obtained.

The three most appropriate algorithms for calculating shortest paths in transport road networks—those due to Moore, D'Esopo and Dijkstra—are examined using CPU times on five realistic networks as criteria. Their relative efficiencies are shown to depend on certain characteristics of the network. In approximate order of importance these are: the network size (in terms of the number of nodes, Nnodes, and/or links, Nlinks), the mean link length d (in terms of the number of integer units), the coefficient of variation of the link lengths, the shape of the network and the ratio of links to nodes. Quantitative rules covering the first two factors have been derived indicating that the fastest algorithm will be: (1) Dijkstra for networks where d/Nnodes