System Convergence in Transport Modelling



System Convergence in Transport Modelling

Authors

J Rich, O Anker Nielsen, DTU Transport, DE, G Cantarella, University of Salerno, IT

Description

The paper considers system stability and convergence performance for transport models. By first exploring stability of the internal assignment equilibrium, the analysis is extended to the external loop between demand and assignment models.

Abstract

A fundamental premise of most applied transport models is the existence and uniqueness of an equilibrium solution that balances demand x(t) and supply t(x). The demand consists of the people that travel in the transport system and on the defined network, whereas the supply consists of the resulting level-of-service attributes (e.g., travel time and cost) offered to travellers. An important source of complexity is the congestion, which causes increasing demand to affect travel time in a non-linear way.
Transport models most often involve separate models for traffic assignment and demand modelling. As a result, two different equilibrium mechanisms are involved, (i) the internal traffic assignment equilibrium, and (ii) the external equilibrium loop between the assignment model and the demand model.
Traditionally, there has been much research focus on the internal assignment equilibrium, which involves iterating between a route-choice (demand) model and a time-flow (supply) model. It is generally recognised that a simple iteration scheme where the level-of-service level is fed directly to the route-choice and vice versa may exhibit an unstable pattern and lead to cyclic unstable solutions. It can be shown that the contractor region, e.g. the region for which {x,t} is stable, depends on the demand and the supply curve. Generally, as the slope (i.e., dx(t)/dt and dt(x)/dx) between the curves increases, the contractor region shrinks. To obtain stable convergence various techniques including the method-of-successive-averages (MSA) have been proposed. Convergence of the MSA under fairly weak regularity conditions was shown in Robbins and Monro (1951).
The iteration between demand and assignment ? the external equilibrium ? are in many models either decoupled or follow a very simple iteration pattern. However, as demand models are often based on logit or probit models, and thus conform to the way demand is represented in stochastic assignment models, there is reason to believe that convergence problems should also be expected in the external equilibrium loop. The intuitive explanation is that, if an iterative solution algorithm may not converge in traffic assignment with fixed demand (base OD-matrix), adding the complexity of variable demand makes the problem even more difficult to solve. At a more practical level there is also the issue of computation time needed to obtain a certain level of precision. As the external equilibrium loop involves running a complete assignment model combined with a complete demand model (which may involve simulation of taste heterogeneity), iterations are much more costly than for the inner loop. This does not justify a simple iteration scheme for the sake of simplicity. As only 3 to 8 iterations may be possible in practice, it is important that these are spent wisely.
In the paper, we first investigate in details the convergence of the inner assignment loop and demonstrate the conditions for stability. On a synthetic network we explore convergence performance of various techniques including MSA, weighted MSA and adaptive averaging. Hereafter, we focus on the convergence of the external loop. To facilitate the analysis, the synthetic model framework is extended to include a demand model for the choice of mode, which is iterated with a stochastic assignment algorithm. A detailed stability analysis based on simulation experiments is presented and conditions for stability are explored. Finally, we investigate techniques for improved speed of convergence. In addition to the techniques tested for the inner-loop, which were all based on the MSA averaging principle, we explore the possibility of using gradient-based algorithms. This includes a simple linear curve fit approach, a spline approximation, and a Newton-based algorithm. In each of these cases, the idea is to utilise knowledge of the curvature of the demand curve to obtain faster convergence. Problems and limitations are discussed.

Publisher

Association for European Transport