Trees, cycles and sensitivity of the traffic assignment problem

The authors consider the sensitivity of the solution of the traffic assignment problem in a network to changes in link costs or demand, and relate the results to properties of the network such as the cycle space and set of spanning trees. The underlying algebra is already known, but a graph-theoretical formulation is easier to apprehend. The authors show that the theory of electrical networks due to Maxwell and others does not necessarily carry over in the case of many-destination networks, and investigate the changes necessary. It is found that generalizing the concepts of ‘path’ and ‘cycle’ enables a modified verison of the electrical theory to be used to compute the changes in flow on each link and in cost between each origin-destination pair. This generalization also allows the possibility of modelling driver ignorance by restricting the number of routes that can be used between certain origin-destination pairs.