Hot-Starting the Traffic Assignment Problem by Zone Aggregation and Disaggregation

Abstract

Given a traffic network subject to congestion and given demand for travel between origins and destinations within the network, a user equilibrium is a pattern of flow that satisfies this demand and where no user can reduce their travel time by taking a different path. This can be framed as a minimisation problem with non-linear objective — the Traffic Assignment Problem (TAP). Several algorithms exist for solving TAP that start with an initial feasible solution. It is standard practice to use for an initial feasible solution the so-called all-or-nothing flow allocation, where all flow simply follows the shortest path ignoring congestion. We develop the approach of solving TAP on a simplified aggregated network and then translating this optimal solution into a feasible solution on the full network. An obvious, and effective, simplification is to group neighbouring origin and destination nodes together ignoring local traffic between them. Projecting the resulting solution onto the full network we start closer to the optimum and so require fewer expensive iterations of the full-network problem to arrive at an acceptable solution. We present our new Centroid Aggregation algorithm in detail and discuss the problem of finding effective partitions of the zone set. We test the algorithm on some mid-sized instances of TAP and find that time savings of up to 70 percent are possible. Key words: Traffic Assignment Problem, Graph Theory, Networks, Network equilibrium, Graph abstraction, Algorithms.