Initializing the Traffic Assignment Problem by Zone Aggregation and Disaggregation

Abstract

The traffic assignment problem (TAP) is a key element of many urban transport models. Given trip demand in the form of a matrix indexed by origin and destination, the TAP assigns flow to the traffic network to achieve a user equilibrium in which no individual traveler may reduce his or her trip cost by changing route. Many iterative algorithms have been developed to solve the TAP; these algorithms are usually initialized by all-or-nothing (AON) assignments in which all flow is assigned to the shortest paths and congestion is disregarded. A new method of initialization based on the solution of a simplified TAP formed by aggregating origin and destination nodes is developed. This simplified problem can be solved in a fraction of the time needed for the original problem. The user equilibrium of this aggregated problem can then be mapped onto the space of path flows of the original TAP. With a suitable choice of aggregation, the time required for an iterative TAP algorithm to converge can be greatly reduced. Including the time taken for initialization, this method gives convergence in some cases more than twice as fast as AON initialization. Methods for the automatic aggregation of origins and destinations are also proposed. The results show that the performance of path-based TAP algorithms is strongly dependent on the choice of initial solution.