An efficient iterative link transmission model

- A novel iterative algorithm for the link transmission model is formulated.
- The method is efficient for a cold started solution with a Gauss-Seidel type of fast sweeping over the nodes in a network.
- The largest compution gains are found for repeated evaluations of the dynamic network loading, which is often needed in practice.
- The method allows for simulations with a large time step discretization, only limited by the accuracy level of the intended application.
- The methodology is numerically evaluated on real world networks of different size and morphology.

In this paper a novel iterative algorithm is presented for the link transmission model, a fast macroscopic dynamic network loading scheme. The algorithm's solutions are defined on a space-time discretized grid. Unlike previous numerical schemes there is no hard upper limit on the time step size for the algorithm to be numerically stable, leaving only the trade-off between accuracy and interpolation errors. This is a major benefit because mandatory small time steps in existing algorithm (required for numerical tractability) are undesirable in most strategic analyses. They lead to highly increased memory costs on larger network instances and unnecessary complex behaviour. In practice results are often aggregated for storage or analysis, which leads to the loss of computationally expensive detailed information and to the introduction of inconsistencies. The novel iterative scheme is consistent with the modelling assumptions independent of the numerical time step. A second contribution of the iterative procedure is the smart handling of repeated runs, which can be initialized (or warm started) by an earlier solution. For applications, repeatedly loading a network is often needed when evaluating traffic states under changing variables or adjusted parameter settings, or in optimization and equilibration procedures. In these cases the iterative algorithm is initialized with the solution of a previous run and iterations are performed to find a new consistent solution. Pseudo-code is provided for both a basic upwind iterative scheme and an extended algorithm that significantly accelerates convergence. The most important computational gains are achieved by ordering and reducing calculations to that part of the network which has changed (most). The properties of the algorithm are demonstrated on a theoretical network as well as on some real-world networks.