Accelerating TrafficAssignment AlgorithmsOn traffic assignment software, compoundzoning and acyclicity in path sets

The overarching goal of this dissertation is to progress on computational challenges in the domain of traffic assignment models.
These models are used widely today to facilitate both operational and strategic decision-making by policymakers relating to vehicular traffic. A common example is infrastructure planning, where these models are used to assess the societal costs and benefits of proposed changes and also play a major role in predicting air pollution.
The Traffic Assignment Problem is about finding consistency between route choice decisions  of travellers and congestion, which arises because of travellers' choices.
Models differ based on the underlying assumptions behind how both route choice and congestion are being captured.
The argument for finding better algorithms for solving the traffic assignment problem is self-perpetuating. Lowering the computational costs/ technical effort involved in the underlying algorithms allows modellers to either answer the same modelling questions in a shorter amount of time, to deploy a more realistic model, or to evaluate within a given time budget more different scenarios for enhanced decision making.

In this thesis, three distinct contributions are presented.
First, we introduce an open-source python package called dyntapy for solving traffic assignment problems, which provides road network and travel demand data processing capabilities, a series of algorithms used for different variants of the Traffic Assignment Problem and visualisation functionality.
The purpose of this tool is two-fold: it facilitates open science by lowering the barrier to publishing algorithms relating to traffic assignment in open source and provides access to state-of-the-art assignment algorithms, which are commonly proprietary.

The second contribution is an approximation scheme for the static traffic assignment
problem, in which long-distance travellers initially route towards a surrogate destination
and transition to routing towards their actual destination en route when they are closer
to their destination. We formulate the problem as an extension to Wardrop’s equilibrium
and show how the approximation scheme can be used in Dial’s Algorithm B. However,
the concept has generic appeal and is in principle applicable to all other static traffic
assignment algorithms and may also aid in improving the efficiency of dynamic traffic
assignment algorithms.
The resulting model offers better scaling with study area size. It is shown that, for
sufficiently large models, computation times can be reduced by more than one order of
magnitude with negligible impact on solution quality when compared to the standard Traffic Assignment Problem.

Lastly, we discuss a new way of capturing path sets on transport networks: by encoding
them in restricted acyclic subgraphs. The arcs forming a path set are not generally acyclic. Two
Integer Programming models for the problem of finding an acyclic subgraph that maximizes
path coverage are introduced. Coverage rates are explored in large-scale case studies on dual
road network graphs. Neither of the problem formulations are tractable in all cases. We propose
a greedy heuristic to generate solutions quickly and compare the coverage rates between the
exact and heuristic approaches. On average, across all instances, coverage rates of more than 90
percent were observed when using the proposed heuristic. This enables efficient acyclic network
loading in which, arguably, almost all the relevant paths are included.