00821020

Component

https://doi.org/10.3141/1771-27

http://scholar.google.com...pati&publication_year=2001

The problem of computing shortest paths in time-dependent networks is considered. This computational problem is at the heart of solution methods to a variety of dynamic network models that arise in the context of intelligent transportation systems applications. The design, implementation, and computational testing are reported for parallel algorithms that exploit possibilities offered by low-cost, commonly available, parallel, and distributed computing platforms to solve many-to-many shortest path problems in time-dependent networks. Five shared-memory implementations and five message-passing implementations are developed. The parallel implementations adopt three decomposition strategies based on the sets of destination nodes, origin nodes, and departure times at origin nodes. The algorithms are coded with two types of parallel computing environments: a message-passing environment based on the parallel virtual machine library and a multithreading environment based on the Sun Microsystems Multi-Threads library. Numerical results are obtained with large-sized dynamic networks and two types of parallel computing platforms: a distributed network of Unix workstations and a Sun shared-memory machine containing eight processors. Satisfactory speedups of sequential algorithms are achieved. Numerical results obtained indicate that, overall, shared-memory platforms appear to be the most appropriate type of parallel computing platforms to solve dynamic shortest path problems that arise in the context of intelligent transportation systems applications.

This paper appears in Transportation Research Record No. 1771, Transportation Network Modeling 2001.

English

p. 219-228

2001

Transportation Research Record

0309072298

Figures (7) ; References (14)

Departure time; Intelligent transportation systems; Network nodes; Networks; Origin and destination; Parallel processing; Shortest path algorithms; Time dependence

Shared memory platforms

Highways; Operations and Traffic Management; Planning and Forecasting; I72: Traffic and Transport Planning

TRIS, TRB, ATRI

Dec 13 2001 12:00AM

• ACCELERATING STRATEGIES AND COMPUTATIONAL STUDIES OF THE FRANK-WOLFE ALGORITHM FOR THE TRAFFIC ASSIGNMENT PROBLEM
• ADVANCES IN DISCRETE-TIME DYNAMIC DATA REPRESENTATION WITH APPLICATIONS TO INTELLIGENT TRANSPORTATION SYSTEMS
• ANALYTICAL DYNAMIC NETWORK LOADING PROBLEM: FORMULATION, SOLUTION ALGORITHMS, AND COMPUTER IMPLEMENTATIONS
• ASSESSING FINANCIAL FEASIBILITY OF A BUILD-OPERATE-TRANSFER PROJECT UNDER UNCERTAIN DEMAND
• ASSESSING PERFORMANCE RELIABILITY OF ROAD NETWORKS UNDER NONRECURRENT CONGESTION
• ASSIGNMENT MODELS FOR LOCAL TRUCKLOAD TRUCKING PROBLEMS WITH STOCHASTIC SERVICE TIMES AND TIME WINDOW CONSTRAINTS
• BITWISE ALGORITHM FOR FASTEST PATHS IN TIME-DEPENDENT NETWORKS
• CALIBRATION AND PATH DYNAMICS ISSUES IN MICROSCOPIC SIMULATION FOR ADVANCED TRAFFIC MANAGEMENT AND INFORMATION SYSTEMS
• COMBINED REVEALED AND STATED PREFERENCE NESTED LOGIT ACCESS AND MODE CHOICE MODEL FOR MULTIPLE MASS TRANSIT TECHNOLOGIES
• COMPARISON OF THREE METHODS FOR DYNAMIC NETWORK LOADING
• COMPUTER VISION DETECTION SYSTEM FOR NETWORK MODEL VALIDATION
• COMPUTING FASTEST PATHS IN CONTINUOUS-TIME DYNAMIC NETWORKS WITH PIECEWISE LINEAR LINK TRAVEL-TIME FUNCTIONS
• DECISION SUPPORT SYSTEM FOR SNOW EMERGENCY VEHICLE ROUTING: ALGORITHMS AND APPLICATION
• DEMAND MATRIX ADJUSTMENT FOR MULTIMODAL FREIGHT NETWORKS
• DYNAMIC TRIP ASSIGNMENT-SIMULATION MODEL FOR INTERMODAL TRANSPORTATION NETWORKS
• EFFECTS OF FLOW UPDATE STRATEGIES ON IMPLEMENTATION OF THE FRANK-WOLFE ALGORITHM FOR THE TRAFFIC ASSIGNMENT PROBLEM
• ESTIMATION OF ORIGIN-DESTINATION DEMAND FOR DYNAMIC ASSIGNMENT WITH SIMULTANEOUS ROUTE AND DEPARTURE TIME CHOICE
• EVALUATION WITH TRAFFIC ASSIGNMENT UNDER DEMAND UNCERTAINTY
• GENETIC ALGORITHM FOR THE TIME-DEPENDENT VEHICLE ROUTING PROBLEM
• LEAST EXPECTED TIME HYPERPATHS IN STOCHASTIC, TIME-VARYING MULTIMODAL NETWORKS
• MODELING OF NONLINEAR STOCHASTIC DYNAMIC TRAFFIC FLOW
• ORIGIN-DESTINATION MATRICES ESTIMATED WITH A GENETIC ALGORITHM FROM LINK TRAFFIC COUNTS
• PARAMETRIC EVALUATION FOR ROUTE GUIDANCE SYSTEMS WITH ANALYSIS OF SUSTAINABLE DRIVER COMPLIANCE
• SOLUTION ALGORITHM FOR COMBINED INTERREGIONAL COMMODITY FLOW AND TRANSPORTATION NETWORK MODEL WITH LINK CAPACITY CONSTRAINTS
• STOCHASTIC DYNAMIC NETWORK DESIGN PROBLEM
• TRANSIT VEHICLE ARRIVAL PREDICTION: ALGORITHM AND LARGE-SCALE IMPLEMENTATION