GENERALIZED DYNAMIC FLOWS PROBLEM

被引：12

作者：

HALPERN, J

机构：

[1] The University of Calgary, Calgary, Alberta

[2] Technion, Haifa

来源：

NETWORKS | 1979年 / 9卷 / 02期

关键词：

D O I：

10.1002/net.3230090204

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

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. Copyright © 1979 Wiley Periodicals, Inc., A Wiley Company

引用

页码：133 / 167

页数：35

共 9 条

[1]

Ford L.R., Fulkerson D.R., Maximal Flow through a Network, Canadian Journal of Mathematics, 8, pp. 399-404, (1956)

[2]

Ford L.R., Fulkerson D.R., A Primal Dual Algorithm for the Capacitated Hitchcock Problem, Naval Research Logistics Quarterly, 4, pp. 47-54, (1957)

[3]

Ford L.R., Fulkerson D.R., Constructing Maximal Dynamic Flows from Static Flows, Operations Research, 6, pp. 419-433, (1958)

[4]

Ford L.R., Fulkerson D.R., Flows in Network, (1962)

[5]

Halpern J., Shortest Route with Time Dependent Length of Edges and Limited Delay Possibilities in Nodes, Zeitschrift fur Operations Research, 21, pp. 117-124, (1977)

[6]

Halpern J., Outerbridge R.A.M., (1977)

[7]

Halpern J., Priess I., Shortest Path with Time Constraints on Movement and Parking, Networks, 4, pp. 241-253, (1974)

[8]

Minieka E., Dynamic Network Flows with Arc Changes, Networks, 4, pp. 255-265, (1974)

[9]

Yen J.Y., Shortest Path Network Problems, (1975)

← 1 →