A generalized dynamic flows problem
Author:
Abstract
The original maximal dynamic flows problem is to find the maximal flow that may be transferred within a given period of time, from the source to the destination of a network with constant edge capacities and lengths. This paper generalizes the problem in two ways. First, the edge's capacity is time dependent, and secondly, the heldover of flows in the vertices may be prohibited during certain intervals of time. The presence of these two additional features implies that cycling of flows may be necessary in order to generate an optimal solution, an impossible result in the original problem. The generalized maximal dynamic flows problem requires, therefore, a special method of solution, and the paper presents a suitable algorithm which solves the problem.Keywords
This publication has 6 references indexed in Scilit:
- Shortest route with time dependent length of edges and limited delay possibilities in nodesMathematical Methods of Operations Research, 1977
- Shortest path with time constraints on movement and parkingNetworks, 1974
- Dynamic network flows with arc changesNetworks, 1974
- Constructing Maximal Dynamic Flows from Static FlowsOperations Research, 1958
- A primal‐dual algorithm for the capacitated Hitchcock problemNaval Research Logistics Quarterly, 1957
- Maximal Flow Through a NetworkCanadian Journal of Mathematics, 1956