Linear User Cost Equilibrium: the New Algorithm for Traffic Assignment in VISUM



Linear User Cost Equilibrium: the New Algorithm for Traffic Assignment in VISUM

Authors

G Gentile, DITS - Sapienza Università di Roma, IT; K Noekel, PTV AG, IT

Description

Abstract

In this paper we investigate the new algorithm to solve the static assignment problem to multimodal transport networks with deterministic route choice, called Linear User Cost Equilibrium (LUCE), that has been recently included in the software VISUM. Exploiting the inexpensive information provided by the derivatives of the arc costs with respect to arc flows, LUCE achieves a very high convergence speed, while it loads the demand flow of each o-d couple on several paths at once.
Specularly to Origin-Based methods (Bar-Gera, 2002), the assignment problem is partitioned by destinations. The main idea is to seek at each node a user equilibrium (Wardrop, 1952) for the local route choice of divers directed toward the destination among the arcs of its forward star. The travel alternatives that make up the local choice sets are the arcs that belong to the current bush ? a bush is an acyclic sub-graph that connects each origin to the destination at hand. The cost functions associated to these alternatives express the average impendence to reach the destination linearized at the current flow pattern.
The unique solutions to such local linear equilibria in terms of destination flows, recursively applied for each node of the bush in topological order, provide a descent direction with respect to the classical sum-integral objective function (Beckmann et. al., 1956). The network loading is then performed through the corresponding splitting rates, thus avoiding explicit path enumeration.
Contrary to the classical All or Nothing assignment to shortest paths, the network loading map resulting from the application of the LUCE algorithm a) assigns (implicitly) the demand flow of each o-d couple on several paths at once and b) is a one-to-one function that combined with the link cost function yields a well-defined fixed point operator, thus offering both computational and theoretical advantages. For each iteration, the proposed algorithm requires no shortest path calculations and two visits of the bush links for each destination, that is equal to the complexity of the STOCH single pass procedure (Dial, 1971) for the Logit network loading. LUCE presents a higher convergence speed, both in terms of computing time and iterations, than the most advanced Origin-Based method recently proposed by Dial (2006).
LUCE is applied to several networks (elementary, toy and real) with different levels of congestion, so as to compare the performances of the proposed descent direction to those of the classic AoN. Moreover, we investigate different step methods along the proposed direction and the sensitivity to the parameters of the procedure, in order to specify our ultimate assignment algorithm. Finally, two different implementations are compared, showing a resource trade-off between RAM and CPU.

Keywords: deterministic traffic assignment, linear user equilibrium, destination splitting rates, arc cost derivatives, accurate algorithm convergence, multiple path loading.

Publisher

Association for European Transport