Efficient Dynamic Network Loading Modeling: The Fixed Point Link Transmission Model
Himpe Willem, KU Leuven, CIB Traffic And Infrastructure, Tampère Chris M.J., KU Leuven, CIB Traffic And Infrastructure
For standard numerical schemes that solve the dynamic network loading problem sequentially through the time domain, update time steps are typically kept small. This directly affects efficiency of these implementations, as computational resources depend quasi-linearly on time update frequency. In this paper, we describe a dynamic network loading algorithm that avoids these small calculation steps. The method searches for consistency between the forward propagation of traffic flows and the constraints imposed by roads or intersections by inflicting delays in the network, where both are described separately. Our algorithm is based on the link transmission model that is reformulated as a fixed point algorithm. The numerical scheme also automatically discretizes time intervals and detects nodes that need updating, herewith minimizing numerical errors and optimizing computational resources. We show that the fixed point LTM calculates small adaptations of an existing solution efficiently, which allows for fast sensitivity analyses, efficient calibration of parameters, or calculation of optimization directions.
At the core of dynamic traffic assignment (DTA) we find the Dynamic Network Loading (DNL). The goal of the DNL is to find consistency between the propagation of traffic flows on the network and the constraints imposed by roads (e.g. maximum throughput, speed limits,…) or intersections (e.g. turning restrictions, obstructions by crossing traffic,…) by inflicting delays in the network.
All practical DTA problems are solved as a numerical program. This process involves a careful tessellation (discretization and interpolation) of the variable grid (traffic, space, time). In our context, this involves:
-Traffic: Individual vehicles are aggregated into a continuous vehicle flow represented by cumulative vehicle numbers (CVN) from which the fundamental traffic characteristics (speed, flow and density) can be derived.
-Space: The link transmission model (LTM, Yperman 2007) allows one to have discrete space intervals the size of homogeneous stretches of roads (links).
-Time: The time discretization is depended on the level of the problem: for standard LTM and most other DNL’s typically short (smaller then 1 min), for route choice models and origin destination flows a lot larger (typically around 15 min).
Without going into detail here we note that the time steps of DNLs are typically small because they are bounded by what is referred to as CFL-conditions (Courant Fraichant Lewy condition), meaning that for each link in the network the update interval of the corresponding CVN cannot be larger than the minimum propagation time of information over that specific link. This is of major importance for the efficiency of LTM (and other DNL) implementations, as computational resources are almost linearly dependent on the time update frequency.
In this paper, we describe a DNL algorithm that avoids the CFL-conditions, which as a result allows for inherently faster numerical evaluation. We adopt the fixed point solution algorithm introduced by Gentile et al. (2007) to the LTM formulation resulting in a model that finds consistent network loadings with much larger update time intervals (up to 15 minutes). Rather than solving the DNL sequentially through the time domain, fixed point LTM iterates over the entire time domain until traffic flow complies with simplified (first order) kinematic wave theory. Each iteration step is composed of a forward phase and a backward phase. In the forward phase, flow is propagated downstream with given time depended link travel time profiles, resulting in CVN’s for each link entering or exiting a node. In the backward phase the travel time profiles are updated by recalculating the CVN at each node that is constrained by a downstream restriction, resulting in an upstream movement of restrictions and congestion.
In the full version of our paper we will describe in detail each of the two phases and propose a numerical algorithm which performs an automatic descretization of the algorithms time intervals that minimize numerical errors and optimizes computational resources. The evaluated time steps are carefully chosen to reduce redundant calculations. This means that only the regions where changes in traffic occur are densely sampled in time. A simple rule is used to update the time mesh. If flow is changing rapidly points are added to the mesh to decrease interpolation errors and if flow is almost constant points are removed from the mesh to decrease calculation time. Next these rules are combined with a smart node activation system that only recalculates those nodes that need updating in the forward or backward phase.
We elaborate on a case study to present our findings. The test bed is the highly congested E40 highway between Leuven and Brussels during the morning peak. It covers a distance of around 30km. The fixed point LTM is compared to the basic LTM to illustrate interpolation errors and calculation gains of using a DNL with larger interval times.
Finally the proposed methodology can also be easily exploited to efficiently update an existing solution to small adaptations. The fixed point LTM scheme is designed to find a consistent network loading from any starting solution. If adaptations only influence constrains locally, the forward and backward phase will run only for these local changes. This results in very efficient system for performing sensitivity analysis, calibrating parameters or calculating optimization directions.
Gentile G., Meschini L., Papola N. (2007) Spillback congestion in dynamic traffic assignment:
a macroscopic flow model with time-varying bottlenecks, Transportation Research B 41, 1114-1138.
Yperman I. (2007) The Link Transmission Model for dynamic network loading, PhD Thesis,
Katholieke Universiteit Leuven, Belgium.
Association for European Transport