A Dynamic Network Flow Problem with Uncertain arc Capacities: Formulation and Problem Structure
Authors:
- 1 April 2000
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Operations Research
- Vol. 48 (2) , 233-242
Abstract
We consider a dynamic network flow problem where the arc capacities are random variables. This gives a multistage stochastic linear program. We describe the randomness using a multi-scenario approach. Because of the multilayered structure, there are several ways to decompose the linear program. We classify different decomposition schemes, and we develop a scheme called compath decomposition, which is derived from path decomposition for network flows. We give a polynomial-time algorithm to find a cheapest compath that can solve the subproblems resulting from compath decomposition. Finally, compath decomposition is extended to multicommodity flow problems.Keywords
This publication has 25 references indexed in Scilit:
- Effects of Air Traffic Congestion Delays Under Several Flow-Management PoliciesTransportation Research Record: Journal of the Transportation Research Board, 1996
- A network recourse decomposition method for dynamic networks with random arc capacitiesNetworks, 1994
- Dynamic solution to the ground-holding problem in air traffic controlTransportation Research Part A: Policy and Practice, 1994
- Stochastic programs over trees with random arc capacitiesNetworks, 1994
- The Aggregation Principle in Scenario Analysis and Stochastic Optimization1989
- The equal flow problemEuropean Journal of Operational Research, 1988
- Solving stochastic programs with network recourseNetworks, 1986
- A note on the stochastic shortest‐route problemNaval Research Logistics Quarterly, 1978
- Validation of subgradient optimizationMathematical Programming, 1974
- L-Shaped Linear Programs with Applications to Optimal Control and Stochastic ProgrammingSIAM Journal on Applied Mathematics, 1969