01593640

Component

https://doi.org/10.3141/2567-11

The all-pairs shortest path algorithms compute the shortest paths between all node pairs in a network. This paper presents a parallel algorithm for the all-pairs shortest path problem with a network decomposition approach. The algorithm decomposes the network into a set of independent augmented directed acyclic subnetworks that can be efficiently processed in parallel. The shortest path computation for each subnetwork provides a subset of the all-pairs shortest paths in the original network. The superiority of the new algorithm was verified through comparing its performance against that of the parallel single-origin shortest path algorithm. The execution times were compared for hypothetical and real-world networks with different sizes. A percentage of improvement in the execution time of about 50% was recorded for the transportation network of a large metropolitan area.

01618747

16-5078

English

pp 95–104

2016

Transportation Research Record: Journal of the Transportation Research Board

9780309441261

Print

Figures (6) ; References (37)

Metropolitan areas; Network nodes; Networks; Shortest path algorithms; Transportation planning

Data and Information Technology; Planning and Forecasting; Transportation (General)

TRIS, TRB, ATRI

Jan 12 2016 6:13PM

• Analysis of Advanced Management of Curbside Parking
• Data-Driven Prediction Methodology of Origin–Destination Demand in Large Network for Real-Time Service
• Deployment and Calibration Considerations for Large-Scale Regional Dynamic Traffic Assignment: Case Study for Sydney, Australia
• Dynamic Optimal Vehicle Relocation in Carshare Systems
• Genetic Algorithm–Based Routing Problem Considering the Travel Reliability Under Asymmetrical Travel Time Distributions
• Impact of Autonomous Vehicles on Traffic Management: Case of Dynamic Lane Reversal
• Implications of Cost Equity Consideration in Hazmat Network Design
• Modeling Freeway Work Zones with Mesoscopic Dynamic Traffic Simulator: Validation, Gaps, and Guidance
• Optimal Heterogeneous Sensor Deployment Strategy for Dynamic Origin–Destination Demand Estimation
• Path Finding in Stochastic Time Varying Networks with Spatial and Temporal Correlations for Heterogeneous Travelers
• Planning of Resource Replenishment Location for Service Trucks Under Network Congestion and Routing Constraints
• Pricing and Segmentation of Stochastic Demand in Less-Than-Truckload Combinatorial Bids
• Solving Continuous Network Design Problem with Generalized Geometric Programming Approach
• Use of Concepts of Regret and Disappointment to Model Dynamic Route Choice Behavior Under Uncertainty