01660910

Component

https://doi.org/10.1177/0361198118799039

Recent methods in the literature to parallelize the traffic assignment problem consider partitioning a network into subnetworks to reduce the computation time. In this article, a partitioning method is sought that generates subnetworks minimizing the computation time of a decomposition approach for solving the traffic assignment (DSTAP). The aim is to minimize the number of boundary nodes, the interflow between subnetworks, and the computation time when the traffic assignment problem is solved in parallel on the subnetworks. Two different methods for partitioning are tested. The first is an agglomerative clustering heuristic that reduces the subnetwork boundary nodes. The second is a flow weighted spectral partitioning algorithm that uses the normalized graph Laplacian to partition the network. The performance of both algorithms is assessed on different test networks. The results indicate that the agglomerative heuristic generates subnetworks with a lower number of boundary nodes, which reduces the per iteration computation time of DSTAP. However, the partitions generated may be heavily imbalanced leading to a higher computation time when the subnetworks are solved in parallel separately at a particular DSTAP iteration. For the Austin network partitioned into four subnetworks, the agglomerative heuristic requires 3.5 times more computation time to solve the subnetworks in parallel. The results also show that the spectral partitioning method is superior for minimizing the interflow between subnetworks. This leads to a faster convergence rate of the DSTAP algorithm.

18-06570

English

pp 116-126

2018-12

Transportation Research Record: Journal of the Transportation Research Board

Digital/other

Figures (4) ; References (31) ; Tables (1)

Algorithms; Cluster analysis; Networks; Traffic assignment

Highways; Operations and Traffic Management; Planning and Forecasting

TRIS, TRB, ATRI

Jan 8 2018 11:42AM

• A Generalized Single-Level Formulation for Origin–Destination Estimation under Stochastic User Equilibrium
• A Greedy Path-Based Algorithm for Traffic Assignment
• Algorithm to Compute Urban Road Network Resilience
• Balanced Scheduling of School Bus Trips Using a Perfect Matching Heuristic
• Characterization of Taxi Fleet Operational Networks and Vehicle Efficiency: Chicago Case Study
• Impact of Extreme Events on Transportation Infrastructure in Iowa: A Bayesian Network Approach
• Improving Scalability of Generic Online Calibration for Real-Time Dynamic Traffic Assignment Systems
• Level-Change Stackelberg Games Model for the Combined Traffic Assignment–Signal Control Equilibrium on Networks
• Link Transmission Model-Based Linear Programming Formulation for Network Design
• Modeling Day-to-Day Dynamics of Travelers’ Risky Route Choices under the Influence of Predictive Traffic Information
• Multimodal Transportation Network Modeling Based on the Generic Second Order Modeling Approach
• Optimal Information Provision at Bottleneck Equilibrium with Risk-Averse Travelers