Improving convergence of quasi dynamic assignment models

Abstract

For decades congestion levels around the world are rising. To properly incorporate the effects of congestion into strategic transport models, a shift from static capacity restrained towards capacity constrained and dynamic traffic assignment models has occurred. In this paper we focus on quasi dynamic assignment models (more specific: static-capacity and storage constrained models by the definitions in Bliemer et al (2015)). These models explicitly capture the flow metering and spillback effects of congestion, but assume stationary demand during a single time period (e.g. a whole peak hour) and are therefore more scalable and mathematically tractable, both important properties for strategic transport models.
Although computational capabilities of current hardware allow for large scale application of such models, the incorporation of capacity constraints causes route cost functions to be much more sensitive and to be inseparable over space (the latter occurs when routes share bottleneck nodes). Furthermore, the incorporation of storage constraints further increases inseparability (which occurs when queues spill back onto upstream links) and causes cost functions to become implicit. As such quasi dynamic models do not fully contain the favorable mathematical properties that are exploited in many algorithms to solve their capacity restrained counterparts and in fact do not necessarily comply with the requirements for existence and/or uniqueness of the user equilibrium (theorems 1.4 and 1.8 in Nagurney (1993)).
Although in reality these unfavorable properties exist, a substantial body of research suggests that their (spatial) occurrence is limited and as such “…have minimal practical temporal and spatial consequences…” (Peeta and Zilliaskopoulos (2001)). However, several large scale applications using the quasi dynamic assignment model STAQ (first described in Brederode et al (2010)) have shown that especially the addition of storage constraints causes poor or non-convergence in real world applications. Further investigations in this paper will show that also the capacity constraints on their own can cause serious convergence issues.
Contributions in this paper are (i) to give an overview of methods in literature and logical extensions to those methods that could improve convergence of quasi dynamic assignment models, (ii) to reveal and illustrate mechanisms that cause the convergence issues using examples on theoretical networks and (iii) to investigate to what extent enhancements to existing algorithms can be used to (partly) get around the convergence issues encountered. Ultimately, this research should lead to a method that generically solves quasi dynamic assignment models.