Improved bush-based methods for network contraction

• The contracted model is extended to include the interactions between different OD pairs.
• A symmetry result is found in the sensitivity of travel times and demands across different OD pairs: the impact of increased OD flow on another OD pair’s cost is the same as the impact of increased flow of the second OD pair on the first OD pair’s cost.
• A heuristic is proposed to approximate the most prominent interactions.
• A formulation similar to the network equilibrium problem is developed to carry out the sensitivity analysis and compute the derivatives.

Calculating equilibrium sensitivity on a bush can be done very efficiently, and serve as the basis for a network contraction procedure. The contracted network (a simplified network with a few nodes and links) approximates the behavior of the full network but with less complexity. The network contraction method can be advantageous in network design applications where many equilibrium problems must be solved for different design scenarios. The network contraction procedure can also be used to increase the accuracy of subnetwork analysis. This method requires calculating travel time derivatives between two nodes, with respect to the demand between them, assuming that the flow distributes in a way that equilibrium is maintained. Previous research describes two methods for calculating these derivatives. This paper presents a third method, which is simpler, faster, and just as accurate. The method presented in this paper reformulates the linear system of equations defining these sensitivities as the solution to a convex programming problem, which can be solved by making minor modifications to static user equilibrium algorithms. In addition, the model is extended to capture the interactions between the path travel times and network flows, and a heuristic is proposed to compute these interactions. The accuracy and complexity of the proposed methodology are evaluated using the network of Barcelona, Spain. Further, numerical experiments on the Austin, Texas regional network validate its performance for subnetwork analysis applications.