Annals of Operations Research 20(1989)1 - 66 1

A SURVEY OF DYNAMIC NETWORK FLOWS *,*

Jay E. ARONSON
Department of Management Sciences and Information Technology,
College of Business Administration, The University of Georgia,
Brooks Hail, Athens, Georgia 30602, USA

Abstract

Dynamic network flow models describe network-structured, decision-making

problems over time. They are of interest because of their numerous applications
and intriguing dynamic structure. The dynamic models are specially structured
problems that can be solved with known general methods. However, specialized
techniques have been developed to exploit the underlying dynamic structure. Here,
we present a state-of-the-art survey of the results, applications, algorithms and
implementations for dynamic network flows.

1. Introduction

Dynamic network flow models describe network-structured, decision-making

problems over time. The terms multiperiod, multistage, time-phased, staircase, and
sometimes acyclic are synonymous with dynamic in this context. This important
network optimization model occurs readily in production-distribution systems,
economic planning, energy systems, communication systems, material handling systems,
traffic systems, railway systems, building evacuation systems, as well as in many
others. Dynamic network flow problems are of interest because o f their numerous
applications a n d intriguing dynamic structure. Although existing network solution
techniques are much more efficient than methods that do not exploit the network
structure (Glover, Karney and Klingrnan [ 1 9 7 4 ] , Glover, Karney, Klingman and
Napier [ 1 9 7 4 ] , Kennington and Helgason [ 1 9 8 0 ] ) , there are still limitations to the
size o f problems that can be solved without exploiting the multiperiod structure as
well (Aronson and Chen [ 1 9 8 6 , 1 9 8 9 a ] ).

*Presented at the Xll International Symposium on Mathematical Programming, Cambridge,

Massachusetts, August 1985.
*Prepared under National Science Foundation Grant ECS-8307549. Reproduction in whole or in
part is permitted for any purpose of the United States Government. This document has been
approved for public release and sale; its distribution is unlimited.

9 J.C. Baltzer AG, Scientific Publishing Company

 J.E. Aronson, Survey of dynamic network flows

The purpose of this exposition is to provide a survey of the known results,

model applications, algorithms and implementations for dynamic network flow
models. This problem class includes linear and nonlinear cost models, generalized
network models, multicommodity network models, other near-network models,
mixed-integer network models and stochastic network-based models. The focus of
this paper will be on linear cost, dynamic network models. Multicommodity problems
and concave cost problems will also be discussed to some extent because of their
frequent occurrence in the literature and their importance in production planning
systems. Other important references will be briefly discussed as well.
The dynamic models are all specially structured problems that can be solved
with known general methods, i.e. for linear models, the standard network simplex
method. However, because of the underlying dynamic structure, specialized tech-
niques have been developed. Here, we present the two main model classes and special
approaches developed for solving them. We also present some more general models
and results. This survey should aid researchers in moving quickly beyond the initial
stages of the existing work in this area, and practitioners in identifying appropriate
models and applicable, efficient solution techniques. We also refer the reader to an
excellent survey of dynamic transportation problems by Bookbinder and Sethi [ 1980].
We assume that the reader is familiar with the basic concepts of linear
programming (Chv~tal [1983], Dantzig [1963], Gass [1975], Simmonard [1966]);
the basic results, algorithms and implementation technology for network optimiza-
tion (Ali, Hetgason, Kennington and Lall [1978], Aronson [1988], Barr, Glover and
Klingman [1974, 1979], Bradley [I977], Bradley, Brown and Graves [1977], Ford
and Fulkerson [1962], Fulkerson [1961], Glover, Hultz and Klingman [1978a, 1979],
Glover, Hultz, Klingman and Stutz [1978b], Glover, Karney and Klingman [1973,
1974], Glover, Karney, Klingman and Napier [1974], Glover and Klingman [1975a,
1975b,1976,1977,1978,1981a], Glover, Klingman and Stutz [1973, 1974],
Helgason and Kennington [1977], Hultz [1976], Jensen and Barnes [1980],
Johnson [1979], Kennington and Helgason [ 1980], Phillips and Garcia-Diaz [ 1981 ],
Srinivasan and Thompson [1972,1973]); the basics of multicommodity network
flow problems (All, Barnett et al. [1980], Ali, Helgason, Kennington and Lall [ 1980],
Assad [1978], Kennington [1978], Kennington and Helgason [1980]); and a basic
knowledge of integer programming (Garfinkel and Nemhauser [1972], Lawler [1976],
Nemhauser and Wolsey [1988]).
In the next section, we present the minimum cost, dynamic network flow
model. The general model is divided into two classes of interest: the maximal dynamic
network flow and the minimum cost, dynamic network flow models. The discussion
of the results, models, algorithms and implementations developed for these models
is in sections 3 and 4. We discuss other dynamic network models, results and algorithms
in section 5. These include multicommodity models, generalized network models,
nonlinear models, mixed-integer models, dynamic traffic assignment/equilibrium
models, economic models, marketing models, real-world systems, and others. In
 J.E. Aronson, SuJwey of dynamic network flows

section 6, we discuss important directions of current and future research. Finally

in section 7, we offer a summary and conclusions. The reference section is a fairly
comprehensive guide to the literature on dynamic network flows. For convenience,
we list the references by topic in table 1, and by application area in table 2. If any
references have been omitted, the responsibility lies with the author.

2. The dynamic network flow model

A network is defined as a set N of nodes {1 . . . . . n}, and a set A of ordered

pairs of nodes (i,j) called arcs. Arcs represent an allowable directional flow of a
commodity between nodes. For arc (i,/'), node i is called its origin or from node
and node /" its destination or to node. With each node i C N is associated a require-
ment ri, positive for supply node (source); negative for a demand node (sink); and
zero for a transshipment node. For the network [N, A ] , let N ; C__N denote the
set of nodes j E N for which arc (i,/') E A, i.e. the set of nodes having arcs pointing
away from node i; and Nz7 C N the set of nodes j E N for which arc (j, i) E A,
i.e. the set of nodes having arcs pointing toward node i. With each arc (i, i) E A is
associated a cost per unit flow cii, a flow capacity uij and a lower bound lij, usually
set to zero. In order to ensure that the network flow problem is feasible, we add an
artificial node O, called the root node, with associated artificial and slack arcs to the
network. This node either supplies excess demand through artificial arcs, or demands
excess supply through slack arcs. Artificial arcs have a cost of infinity; slack arcs have
a cost of zero. Both have flow capacities of infinity and lower bounds of zero. Some
network optimization techniques introduce artificial arcs from the root to every
demand and transshipment node and slack arcs from every supply node to the root
to form an initial basis tree. The standard network flow problem, then, is to satisfy
the node requirements r i at a minimum cost. We may state the minimum cost net-
work flow problem (NFP) as:

(1) minimize ~.. ~. ciixij,

i~N jEN;

(NFP) (2) subject to ~ xii - ~ xii = r i ; i E N,

ieN; iEN[

(3) O<~xq~u,. i ; (i,])~A.

Variations and extensions of NFP include problems having nonlinear costs,

multicommodity networks, networks with side constraints and/or side columns (also
called embedded networks, near-networks, and network-related problems), generalized
networks, mixed-integer networks, and fixed-charge networks. In the multicommodity
4 J.E. A ronson, Survey o f dynamic network flows

generalization, several commodities share arcs in a capacitated network. Typically,

there are multiple independent copies of the network, one for each commodity, and
mutual arc capacity (side) constraints having the generalized upper bounded (GUB)
structure (Dantzig and Van Slyke [1964]). If necessary, the arc weighting factors
in the mutual capacity constraints convert units among the commodities. The mutual
capacity constraints link the independent network flow problems together. In the
network with side constraints and/or side columns model, a network flow problem
is embedded in a larger, linear programming problem. In generalized network models,
there is a multiplier associated with each arc. A multipkier greater (less) than one
indicates a gain (loss) of the flow through an arc. The multiplier appears in the model
before the terms in the second summation of eq. (2). Some models and methodologies
use two multipliers, one for each element in the node-arc incidence matrix, mainly
so that solutions to mixed-integer models need not be scaled. In mixed-integer models,
some of the flows are restricted to be integer. In fixed-charge problems, there is a
fixed-cost of allowing positive flow through an arc. Multiperiod concave cost models
are subsummed by the models described by Zangwill [1966, 1968, 1969].
The minimum cost, dynamic (or multiperiod, multistage) network flow prob-
lem is a version of NFP where some of the arcs represent commodity flow over time.
We define the transit tone tii of an arc (i,]) to be the time required for a commodity
flowing through arc (i, ]) to leave its origin node i and arrive at its destination node j.
Usually, transit times are nonnegative, i.e. back flow is not allowed. For models that
describe the flow of actual commodities through a pipeline system, transit times
must be nonnegative. For production planning/distribution models that allow back-
ordering and cash flow models, negative transit times are permitted. A transit time
of zero indicates that a commodity can flow through the arc with no delay, relative
to the level of time discretization in the model. To consider transit times, we define
the node and arc sets below.
Let N ( t ) be the set of nodes in period t, for t = 1 , . . . , T. A node is represented
as the two-tuple (i, t) E N ( t ) , where i is the node number, for i = 1 . . . . . n(t); t is its
time period; and n ( t ) is the number of nodes in period t. Node (i, t) is not defined
for t <~ 0 and t /> T + 1. For models that allow t = O, 1 . . . . . T, N ( t ) is not defined
for t ~< - 1 and t >1 T + 1. Let A ( t ) be the set of arcs that have their origin nodes
(i, t) E N ( t ) . An arc is represented by the two-tuple of nodes ((i, t),(], t')) ~ A ( t ) ,
where t' considers the transit time of the arc. In other words, t' = t + ti]. We call an
arc that has its origin and destination nodes in the same period a local arc; one that
has its destination node in a later time period than its origin node a pass-forward arc;
and one that has its destination node in an earlier time period than its origin node a
pass-back arc. For the latter two cases, an alternate definition is a linking arc. Back-
flow is accommodated through pass-back arcs.
Most researchers restrict the nodes and arcs in each period to be identical for
the ease of data handling by their implementations. Although common, this clearly
need not be the case. Notable exceptions to this restriction are due to Aronson and
Chen [1986, 1989a, 1989b] and Chen [1985].
 J.E. Aronson, Survey of dynamic network flows 5

We may define the entire node set of the problem to be

N = N(1) U N(2) U . . . U N(T),

and the entire arc set of the problem to be

A =A(1) U A ( 2 ) U . . . U A ( T ) .

Using the network [N, A ] , it is possible to define the dynamic network flow prob-
lem in terms of NFP above. Instead, we define it on a time-expanded (also called
space-time) network, i.e. in terms of the node and arc sets of the time periods.
The sets N[(t) and N[(t) are defined similarly to Ni § and N[, for nodes
(i, t) E N(t). Formally, we define N~(t) = {(j, t')l ((i, t),(/, t')) ~ A(t)}, to be the
set of destination nodes for which there is an arc originating at node (i, t) E N(t);
and N[(t) = {(]', t')l ((j, t'),(i, t)) E A}, to be the set of .origin nodes for which
there is an arc having its destination node (i, t) E N(t) for t = 1 . . . . . T.
Let rit be the requirement of node (i, t). The unit cost and flow capacity
for arc ((i, t),(j, t')) are citjt, and uitjt,, respectively. The minimum cost, dynamic
network flow problem (DNFP) may then be stated as:

T
(4) minimize Z Z ~. cit#, xit#,
t=l (i,t)~N(t) (],t')ENT(t)

(DNFP) (5) subject to Z xit]t'- E Xjt'it = rit; (i, t) E N(t),

(],t') E N;(t) (1, t') ~ N~(t) t = 1 . . . . . T,

(6) 0 ~ xitit, ~ uit/t, ; ((i, t),(j, t')) E A(t), t = l . . . . . T.

Model DNFP is a multiperiod linear programming problem where the node-arc

incidence matrix forms a staircase matrix (Aronson, Morton and Thompson [1985]).
Dynamic network flow problems often occur in the modeling of continuous
processes, such as production/distribution and communication systems. The DNFP
is formed when the problem is discretized over time. This aggregation of the continuous
problem into discrete time intervals introduces a level of error. The smaller the time
intervals are, more accurate solutions are found, but at the expense of solving a larger
network flow problem. Recent work on solving continuous-time network flow prob-
lems directly is due to Anderson, Nash and Philpott [1982], Anderson and
Philpott [1984]. Also, see Langley [1973]. For research on continuous linear
programming, see Anderson [ 1979], Drews [ 1974],Perold [1978] and Premoli [1986].
Minimum cost dynamic network models can be used to describe production
planning and resource distribution problems. In fig. 1, we show a time-expanded
network representation (model DNFP) of a T-period production/distribution problem
 J.E. Aronson, Survey of dynamic network flows

PERIOD: 1 2 3 -. - T-1 T

SUPPLIES:

DEMANDS:

Fig. 1. T-period production planning network model. There are 5 nodes and 14 arcs
per time period, except for period T. There are 2 production sources or factories:
supply nodes (1,2); and 3 warehouses: demand nodes (3,4,5) in each period. For
clarity, the t is omitted in designating node (i, t). Ending inventory is allowed at
both the factories and the warehouses. Backorderingis allowed only at the warehouses.

with two factories (nodes (1, t), (2, t)) as available supplies, to meet the demands at
three warehouses (nodes (3, t), (4, t), (5, t)). The local arcs ((i, t), (], t)) for i = 1, 2;
/' = 3,4, 5; t = 1 , 2 , . . . , T take into consideration the production and transportation
of the commodity. The product may be inventoried at the factories and warehouses at
the end of each time period (arcs ((i, t), (i, t + 1)) for i = I . . . . . 5; t = 1 . . . . . T - 1);
and backordered only at the warehouses at the end of each time period (arcs ((i, t),
(i, t - I)) for i = 3 , 4 , 5 ; t = 2 . . . . ,T).
Model DNFP describes network-structured, decision-making problems
over time. Such problems arise in the areas of production-distribution systems
(Aderohunmu [1986], Aderohunmu and Aronson [1987,1988], Bowman [1956],
Evans [1975], Gaimon [1986], Glover, Jones, Karney, Klingman and Mote [1979],
Klingman and Mote [1982], Klingman, Mote and Phillips [1988], Klingman, Phillips
et al. [1986, 1987a, 1987b], Klingman, Randolph and Fuller [1976], Konno [1988],
Hu and Prager [1959], Klingman and Mote [1982], Posner a n d Szwarc [1983],
Ramsey and Rardin [1983], Rao and McGinnis [1983], Sandbothe [1985], Sandbothe
and Thompson [1988], Steinberg and Napier [1980], Zahorik, Thomas and
Trigeiro [1984], Zangwill [1966, 1968,1969,1985,1987a, 1987b]), economic
planning (Fong and Srinivasan [1981,1986], Nagurney and Aronson [1988, 1989],
Zemanian [1983a, 1983b] ), cash flow (Charnes and Cooper [ 1961 ], Crum [ 1976], Crum,
Klingman and Tavis [1979, 1983a, 1983b], McBride, O'Leary and Widmeyer [1988] ),
communication systems (Masson and Jordan [1972], Monma and Segal [1982],
 J.E. Aronson, Survey of dynamic network flows

Smith [ 1979] ), material handling systems (Kang [1978], Maxwell and Wilson [1981 ] ),
personnel planning (Aronson [1986], Charnes and Cooper [1961], Charnes, Cooper
and Stedry [1969], Elnidani [1986], Elnidani and Aronson [1989a, 1989b, 1989c],
Evans [1981], Gilbert and Hofstra [1988]), traffic systems (BieUi, Calicchio,
Nicoletti and Ricciardelli [1982], Carey [1980,1986,1987,1988], Carey and
Srinivasan [1982,1985], Merchant [1974], Merchant and Nemhauser [1978a, 1978b],
RobiUard [1974], Zawack and Thompson [1987]), trucking systems (Dejax and
Crainic [1987], PoweU [1986,1987], Powell et al. [1984,1988]), railway systems
(Crainic, Ferland and Rousseau [1984], Dejax and Crainic [1987], Cuimet [1972],
Ermol'ev et al. [1976], Halpern [1979], Halpern and Priess [1974], Hein [1975, 1978],
Herren [1973, 1977], Jordan [1982], Jordan and Turnquist [1983],Mendiratta [1981],
Mendiratta and Turnquist [ 1982], Ouimet [ 1972], Potts [ 1970], Prevezentsev [ 1974],
Shan [1985], Turnquist [1986], Tumquist and Jordan [1982], White [1972],
White and Bomberault [1969]), water distributions (Bhaumik [1973]), air freight
and transportation systems (Glover, Glover, Lorenzo and McMillan [1982], Glover,
McMillan and Taylor [1977], Gurel and Winbigler [1967], evacuation systems
(Allen [1985], Chalmet, Francis and Saunders [1982], Choi, Francis, Hamacher and
Tufekci [1984], Choi, Hamacher and Tufekci [1988], Hamacher and Tufekci [1987] ),
energy systems (Rosenthal [1981], Ikura, Gross and Hall [1986]), as well as in
many others (Aronson [1988], Glover and Klingman [1977], Glover, Klingman
and McMillan [1977]). Some models incorporate integer variables; some have non-
linear objective functions; some are generalized networks; some are multicommodity
networks; some are networks with side constraints and/or side columns; some are
stochastic; others combine these features.
Solution techniques are discussed by Aderohunmu [1986], Aderohunmu
and Aronson [1985,1987,1988], Allen [1985], Aronson [t986], Aronson and
Chen [1986, 1989a], Bean, Birge and Smith [1987], Chen [1985], Elnidani [1986],
Elnidani and Aronson [1989a], Erickson, Monma and Veinott [1987], Escudero
[1986], Evans [1981], Ford and Fulkerson [1958, 1962], Halpern [1979], Halpern
and Priess [1974], Jarvis and Ratliff [1982], Klingman and Mote [1982],
Konno [1988], Minieka [1973,1974], Nagurney and Aronson [1988,1989],
Orlin [1983,1984], Rosenthal [1981], White [1972], White and Bomberault [1969],
Wilkinson [1971,1973], Zahorik, Thomas and Trigeiro [1984], Zangwill [1966,
1968, 1969], and others.
For historical reasons, the class of problems defined by DNFP are divided
into two subclasses: (1) the maximal dynamic network flow problem, and (2) the
multiperiod transshipment problem. In the next two sections, we discuss results,
applications, and model variations of the two models. We also discuss relevant
algorithms and their implementations.
 J.E. Aronson, Survey of dynamic network flows

3. M a x i m a l d y n a m i c n e t w o r k flows

3.1. THE MAXIMAL DYNAMIC NETWORK FLOW MODEL

Ford and Fulkerson [1958,1962] introduced the concept of dynamic flows

in networks with the maximal dynamic network flow problem. This problem is to
determine the maximum flow of a commodity from a single source to a single sink
over T discrete time periods starting at time period zero. All flow leaving the source
must arrive at the sink by time period T. Multiple sources and sinks may be accom-
modated by connecting a single super source to all sources, and all sinks to a single
super sink with slack arcs. We define their problem as follows: let a network [N, A]
consist of n nodes, N = {1,2 . . . . . n}, and arcs (i,j) E A. Let node 1 be a source,
node n be a sink, and nodes 2 . . . . . n - 1 be transshipment nodes. With each arc
(i, j) E A is associated an integer capacity uq and an integer transit time ti./. There
are no unit arc costs to be considered. Let yq(t) be the flow originating at node i in
time period t, along arc (i,/). This flow will arive at node ]' in time period t + tq.
Nonpositive transit times are not allowed. Further, assume that hold-overs are
permitted, i.e. tii 1. Hold-over arcs, that explicitly appear only in a time-expanded
=

network representation of the problem, have infinite capacity. Theoretically, there

exists an optimal solution with no positive hold-over flow. Let o(T) be the total
flow that leaves the source node in time periods 0, 1 . . . . . T. The constraints of the
maximal dynamic network flow problem (MDNFP) consist of the conservation of
flow equations for each node. MDNFP may be stated as:

(7) maximize v(T),

n T
(8) subject to ~, 7. (Yti(t) -yj,(t - tix)) - o(T) = O,
1=2 t=o

rl
(MDNFP) (9) (yij(t) - y i i ( t - t l i ) ) = 0; i = 2 , . . . , n - 1,
j=l t = 0 . . . . . T,
n-I T
(10) E ~. (yni(t) - yin(t - tjn))+ u(T) = 0,
i=1 t=0

(11) o <<.y u ( t ) <~ uu; (i,/) E A .

For the standard MDNFP, the structure of the network is assumed not to
change over time. This includes the number of nodes per period, number of arcs per
period, the arc linkages, the arc transit times and arc capacities. This simplifying
assumption limits the range of applicability of this model because it often does not
 J.E. Aronson, Survey of dynamic network flows

hold in real systems. MDNFP explicitly considers arc transit times directly in the
conservation of flow equations ( 8 ) - ( 1 0 ) . That MDNFP is a specialization of DNFP
is easily seen when the problem is stated in a time-expanded network format. Most
of the results and algorithms for MDNFP and its variations are based on the simple
and elegant algorithm of Ford and Fulkerson [1958,1962]. In the next two sub-
sections, we discuss results, algorithms, implementations and applications of MDNFP.

3.2. THEORETICAL RESULTS, ALGORITHMSAND IMPLEMENTATIONS

FOR THE MAXIMAL DYNAMICNETWORK FLOW PROBLEM

In their early work, Ford and Fulkerson [1958, 1962] present the development
of an ingenious, specialized algorithm for solving MDNFP. Their procedure requires
the solution of a linear, minimum cost, network flow problem (NFP) on the under-
lying static network of MDNFP. By a static network, consider MDNFP with all transit
times set to zero. In the static problem, the transit times of the arcs are absorbed
into the objective function, also a function of T.
Let u be the total flow from node 1 to node n through the network [N, A ] .
Then, we may state the static network flow problem (SNFP) as:

(12) maximize ( T + 1)v - tijxi] ,

(i,j) E A
/'1

(13) subject to ~,, (xli - x / t ) - v = 0 ,

/'=2
I'1
(SNFP)
(14) ~" (xq - xii ) = 0; i=2,...,n-1,
/'=1
n-I

(15) ~_, (Xni -Xin) +u = 0 ,

]--1

(16) O<~xii~uij; (i,j) EA.

The first step of their specialized procedure is to find the static flow v from
node 1 to node n in SNFP. One approach is to add an artificial arc from node n to
node 1 with unit cost - ( T + 1) and solve the circular flow problem with an out-of-
kilter method. The flow through the artificial arc is u = xnl. An alternative approach
is to take a random cut of the network. Set the supply at node 1 and demand at
node n equal to this quantity. Add to the network an artificial arc with a large cost,
from node 1 to node n. Also, add a node n + 1 and a single arc from node n to node
n + 1 to the network with infinite capacity and unit cost - ( T + 1). Then, solve the
resulting transshipment problem with the primal network simplex method.
10 J.E. Aronson, Survey of dynamic network flows

The algorithm next develops a set of temporally repeated flows. The optimal
flow from the source to the sink of SNFP is decomposed into a set of chain flows.
The set of chain flows is cast into a time-expanded network framework, an explicit
form of MDNFP, where each node and arc is represented in every time period as
long as the arcs exist as in MDNFP. In the time-expanded network, each flow starts
at time zero and is repeated, starting in each time period, as long as the flow can
arrive at the sink by time period T. The sequence of flows is generated in a forward
manner, though not a true forward algorithm (Aronson and Thompson [1984],
Morton [ 1978, 1981] ). The authors show that there always exists a maximal dynamic
flow that avoids hold-overs at transshipment nodes. They also prove the existence
of a maximal dynamic flow within the class of temporally repeated flows.
Consider the example problem shown in fig. 2. The time-expanded network
is shown in fig. 3. The optimal flows to the static problem SNFP are: x~2 = 3, xla = 4,
x23 = 1, x~4 = 2, Xas = 5, and the total flow o = x41 = 7. There are three chains:
1-2-4, 1-2-3-4, and 1-3-4, with respective capacities of 2, 1, and 4 units. All three
chains start in periods 0 and 1 ; only the chain 1-2-4 starts in period 2. No flow leaves
the source in periods 3, 4 and 5. No flow arrives at the sink until time period 3. The
total flow arriving at the sink is 16, equal to the optimal objective value to the SNFP.
The maximal dynamic flow is shown in a time-expanded network representation in
fig. 4.
Ford and Fulkerson [1958,1962] define a minimal dynamic cut for a T-
period MDNFP. The optimal dual variables of SNFP indicate at which period and for
how many periods tile flow through the network is at its maximum capacity. The cut
indicates how the problems decompose into three parts. First, there is an early transient
solution. This leads up to the second part, a steady-state solution, when the dynamic
cut limits the total flow through the system. In steady state, all of the temporal
chains are repeated. The third part follows the steady-state solution as much as possible
until end-effects cause a condition similar to that of the transient. As the solution is
found for time periods close to T, the temporal chains drop out of the solution.
The period at which the steady-state solution begins is a kind of decision horizon
(Aronson and Thompson [1984], Lundin and Morton [1975], Miller [1979],
Morton [1978,1981]). Regardless of certain changes in the network, there will be
no changes in the flows made up to and including that period. This concept has
important implications for traffic flow (Zawack and Thompson [ 1987] ) and evacuation
models (Allen [1985], Chalmet, Francis and Saunders [1982], Choi, Francis,
Hamacher and Tufekci [1984], Choi, Hamacher and Tufekci [1988], Hamacher and
Tufekci [ 1 9 8 7 ] ) w h e n the network is utilized at its maximum capacity. The effect
of the minimal dynamic cut also indicates why the basis tree of a DNFP naturally
decomposes (Aronson and Chen [1986] ).
Gale [1959] coined the term universal maximal dynamic flow to describe the
case where the optimal solution to a T-period problem, when truncated, provides
 J.E. Aronson, Survey of dynamic network flows 11

(Capacity, Transit Time)

SOURCE SINK

(6.2)

Fig. 2. Tile underlying static network o f t h e maximal d y n a m i c

network flow example problem. The two integers near each
arc axe its fixed capacity and transit time (ui],ti]). Node 1 is
the source, node 4 tile sink. The problem is to determine a
maximal flow from node 1 to node 4 over T = 5 time periods.

PERIOD: 0 1 2 3 4 5

SOURCE:

SINK:

Fig. 3. Five-period, t i m e - e x p a n d e d n e t w o r k representation of

the m a x i m a l d y n a m i c network flow example problem. This
network problem is equivalent to the problem s h o w n on the
static network in fig. 2. The flow is allowed to start at time
zero. The capacity of each arc is the same as s h o w n in fig. 2.
There axe hold-over arcs (not shown) for t r a n s s h i p m e n t nodes
2 and 3. T h e capacities of the hold-over arcs (i, i) are infinity;
their transit times are 1. Note that no flow can reach the sink
until period 3, and no flow can leave t h e source following
period 2.
 12 ,I.E. Aronson, Survey of dynamic net~vork flows

PERIOD: 0 1 2 3 4 5

Fig. 4. Optimal solution to the maximal dynamic network

flow example, shown on the five-period time-expanded
network. This solution is found by the Ford and Fulkerson
[1958, 1962] algorithm, using the static network shown in
fig. 2. The solution to the static problem is:xt2 = 3,xt3 = 4,
x23 = 1, x2, = 2, x3s = 5, and u = x4L = 7. The flows through
the chains are: 2 through 1-2-4; 1 through 1-2-3-4; and
4 through 1-3-4. They are used to generate the temporally
repeated flows shown above. The temporally repeated flows
total 7. The arc flows are shown near their respective arcs.
There is no hold-over of the commodity in the optimal
solution. The maximal dynamic flow ovcr the 5 periods is 16.

an optimal solution to any t-period problem for t < T. The temporally repeated
flows produced by the F o r d and Fulkerson algorithm are not necessarily universal
dynamic network flows. Using the s u p p l y - d e m a n d t h e o r e m ( G a l e [1957] ), Gale [1959]
proves the existence o f universal maximal dynamic flows for a generalization o f the
F o r d and Fulkerson network which includes time-varying capacities and transit times.
Gale also conjectured correctly that a mild modification o f the F o r d and Fulkerson
algorithm would generate universal maximal dynamic flows.
Minieka [1973] proved the following property o f maximal network flows with
multiple sources and sinks:
" I f there exists a maximal network flow with a given departure pattern
at the sources and a maximal flow with a given arrival pattern at the
sinks, then there exists a flow that has b o t h this departure pattern at
the sources and this arrival pattern at the sinks."

The p r o o f o f this p r o p e r t y is based n o t on the s u p p l y - d e m a n d theorem, but on

F o r d and Fulkerson's [196:2] m a x i m u m flow algorithm. This result established the
independence o f the input and o u t p u t for a maximal flow. Using the above p r o p e r t y ,
Minieka goes on to prove that:
 J.E. Aronson, Survey of dynamic network flows 13

"There exists a maximal dynamic network flow that simultaneously

has a latest (earliest) departure schedule at the sources and an earliest
(latest) arrival schedule at the sinks"

Minieka [1973] modified Ford and Fulkerson's maximal dynamic flow algo-
rithm to construct a latest departure schedule and an earliest arrival schedule. In
addition, Minieka's algorithm produces a universal maximal dynamic network flow.
Applications of this solution to the general model include freight car flow problems,
for which it may be reasonable to delay departures as long as possible because empty
cars may not arrive on schedule to be loaded and shipped.
Later, Minieka [1974] describes a modification of the Ford and Fulkerson
maximal dynamic flow algorithm to networks where arcs may be added or removed
in any time period. This is a specific instance of Gale's [1959] time-varying arc
capacities, where all possible arcs are in the network at time zero and their capacities
are either at their value, or zero, as required by the problem. Minieka's modifications
to the algorithm are computationally excessive. He indicates that it is computationally
more efficient to apply the standard maximal flow algorithm to the time-expanded
network when the number of arc changes is excessive.
Wilkinson [1971] independently provided the mild modification conjectured
by Gale [1959] to the Ford and Fulkerson algorithm to calculate universal maximal
dynamic flows. His proof is based on the construction of a minimal cut of the net-
work. Wilkinson [1973] later presented an algorithm to determine upper and lower
bounds for arc flows in a maximal dynamic flow solution. His extension of the Ford
and Fulkerson maximal dynamic flow algorithm also solves a minimum cost, network
flow problem. The bounded flow algorithm first obtains a maximal dynamic flow
solution using the Ford and Fulkerson algorithm. Next, slack arc flow bounds are
computed using conservation of flow arguments. This second step can be omitted,
with a demonstrated loss in efficiency. Finally, the arc flow bounds are tightened
to their true value by an application of the Ford and Fulkerson algorithm to a sub-
network composed of a special set of admissible arcs from the original network. The
bounded optimal arc flows may be used to select a particular solution among a number
of optima by a secondary criteria. A PL/I implementation on an IBM 360/50 solved
a 500 arc problem in approximately one CPU minute.
Halpern and Priess [1974] presented an algorithm for solving a problem
closely related to the MDNFP: to find a shortest path in a multiperiod network in
which some arcs may be closed and hold-overs are permitted in the nodes for certain
time periods. An important application of this model is to determine the shortest
path for a train through a railroad network when simultaneous movements in opposite
directions are prohibited, and a number of trains are moving through the network
on defined paths. This yields a set of time intervals during which certain nodes and
arcs are not available. Their algorithm resembles Dijkstra's [1959] labeling algorithm
for the solution of the shortest path problem. Computationally, Halpern and Priess
14 J.E. Aronson, Survey of dynamic network flows

claim that their procedure requires only three to four times as much execution time
as the Dijkstra [1959] procedure for a simple, unrestricted shortest path on the same
network. They mention that their problem can be transformed to that of finding a
simple shortest path on a time-expanded network, but they estimate that their tech-
nique may be as much as one hundred times more efficient than that. Other work on
finding shortest paths through dynamic networks is due to Cooke and Halsey [1966],
Dreyfus [1969], Kibby and Potts [1969], and Saksena and Kumar [1966].
Dreyfus [1969] and Saksena and Kumar [1966] discuss shortest path problems
where there are requirements for visiting specified nodes. Kibby and Ports [1969]
discuss methods of handling turn penalties and prohibitions. Cooke and Halsey [ 1966]
discuss the model for which the transit times are time dependent.
Halpem [1979] presents an algorithm to solve a generalization of MDNFP
that includes time-dependent arc capacities, as discussed by Gale [1959], and the
prohibition of commodity hold-over in nodes during certain time intervals. For this
generalization, an optimal solution may require the cycling of flows, impossible for
the original Ford and Fulkerson problem. Halpern combines the generalized shortest
path problem of Halpern and Priess [1974] and Minieka's [1974] initial step toward
generalizing MDNFP, to include arc addition and removal, to formulate this more
general, dynamic flow model. The algorithm consists of five separate procedures:
(1) Data truncation: To modify input data and save memory space and
computational effort in subsequent parts of the algorithm.
(2) Breakthrough: To find a flow augmenting path that may include cycles
due to changing arc capacities.
(3) Backtracking: To identify the flow augmenting path. The procedure can
be incorporated into the Breakthrough procedure.
(4) Saturating: To detem~ine the increase in flow along the flow augmenting
path.
(5) Updating: To modify the network data to accommodate the flow increase.

Halpem suggests that whenever the changes in the network are excessive, the
algorithm may require as much computational time and memory as solving the
problem directly on the time-expanded network. Halpern remarks that for one
50 node, 600 arc, 250 time period model, their encoded algorithm (Halpern and
Outerbridge [1977]) required 5% of the CPU time needed to solve the same problem
on the time-expanded network. Bottlenecks due to capacity limitations, so-called
easy cuts, enhance the algorithm so that it rapidly converges to an optimum. These
bottlenecks determine decision horizons (Aronson and Chen [1985,1986, 1989a,
1989b], Chen [1985], see section 4).
Chalmet, Francis and Saunders [1982] present a maximal dynamic network
flow model for building evacuation. They represent the evacuation of a building as
 J.E. Aronson, Survey o f dynamic network flows 15

it evolves over discrete consecutive time intervals. Their model has a single source
and sink in each time period. To model the problem, they consider a super source
with arcs pointing into each original source node, and a super sink with arcs pointing
into it from each original sink node. The solution to their MDNFP determines how a
large building with many occupants can be evacuated in a minimum time and where
bottlenecks are likely to occur during evacuation. In one version of their model, the
cost of an evacuee exiting the building in time period t is t. Thus, an optimal
solution should evacuate the building in minimum time. Jarvis and Ratliff [1982],
using the results of Minieka [1973], prove that under the slightly general cost
assumption, that the cost of an evacuee exiting the building in period t is ct, where
c~ < c2 . . . < c t, the Chalmet, Francis and Saunders [1982] dynamic model triply
optimizes in the sense that it:
(1) minimizes the average number of periods an evacuee needs to exit the
building,
(2) maximizes the total number of people evacuating the building during
periods 1 through t for all values of t, i.e. finds universal maximal dynamic
flows, and
(3) minimizes the time period in which the last evacuee exits the building.

Jarvis and Ratliff [1982] also develop an applicable forward-acting algorithm

that solves a sequence of T maximal flow problems. At the kth stage of the algo-
rithm, the problem is truncated to include only time periods 1 through k. The sinks
for time periods k + 1 through T are omitted from the problem.
Chalmet, Francis and Saunders [1982] discuss how dual variables identify
bottleneck arcs (determining a kind of decision horizon). This is similar to the work
of Berlin [1979], who uses the standard Ford and Fulkerson maximum flow
algorithm to identify building evacuation bottlenecks. Chalmet et al. [1982] con-
jecture that results from the traffic flow equilibrium literature, such as Merchant and
Nemhauser [1978a, 1978b], may suggest ways to incorporate nonlinearities into the
model. In a related work, Choi, Francis, Hamacher and Tufekci [1984] examine some
simple network models of building evacuation that have exit capacities dependent
upon arc flows. Some theoretical results, relating to the triple optimization results
of Chalmet et al. [1982] and Jarvis and Ratliff [1982], are given, Also, see Choi,
Hamacher and Tufekci [1987] and Hamacher and Tufekci [1988].
Orlin [1983] discusses the formulation and solution of the infinite horizon,
dynamic, integer, network problem. He generalizes the Ford and Fulkerson MDNFP
to include lower bounds on the arc flows. Through a dynamic analogue to the F o r d -
Fulkerson [1956] max-flow/min-cut theorem, he proves that the maximum flow in
transit (at a time period sufficiently greater than zero) is the minimum capacity of
an appropriately defined cut. He also shows that if the optimum exists, it consists
of temporally repeating flows.
16 J.E. Aronson, Survey of dynamic network flows

3.3. APPLICATIONSOF THE MAXIMAL DYNAMIC NETWORKFLOWPROBLEM

Some application references have already been discussed, because theo-

retical results and algorithms were also developed. Important applications of the
maximal dynamic network flow model and its variations are in the areas of freight
systems (Gurel and Winbigler [1967], Halpern [1979], Halpern and Priess [1974],
Minieka [1973,1974]); material handling systems (Kang [1978], Maxwell and
Wilson [1981]); building evacuation (Chalmet, Francis and Saunders [1982]); and
scheduling (Orlin [1983]).
The early freight system application of maximal dynamic network flow models
arose in the railroad industry in the scheduling of freight cars. Minieka [1973]
describes an application of his latest departure/earliest arrival algorithm to a model
that includes freight car flow problems, where departures may be delayed because
empty cars may be late for loading and shipping. The Halpern and Priess [1974]
algorithm is applicable in determining the shortest path for a train through a railroad
network having single tracks, with some trains already assigned to travel along certain
paths.
The Halpern [1979] algorithm solves a variation of MDNFP that includes
time-varying arc capacities, and commodity hold-over prevented in nodes during
certain time intervals. Applications of his model include to:
- distribute the maximum number of heavy equipment units from several
sources to several sinks within a fixed number of periods,
- maximize the utilization of freight trains,
- maximize the utilization of a conveyor system in a production plant,
- maximize the quantity of a perishable product distributed, and
- maximize the throughput of a communication system over a fixed number
of periods.
In all cases, the commodity may have to leave a source or arrive at a sink at
a fixed interval, perhaps due to loading or unloading new crew availabilities, and
certain nodes may not be available for hold-over storage due to parking restrictions.
Halpern and Outerbridge [1977] document an implementation of the algorithm.
Material handling applications are discussed by Kang [1978] and Maxwell
and Wilson [1981]. These models focus mainly on conveyor systems in production
environments. Maxwell and Wilson [1981] give a simplified application of dynamic
networks to an automotive parts distribution center. The models can be solved by the
Ford and Fulkerson [1958,1962] algorithm or its variations. To solve material
handling problems, a special code, DYNAFLO, was developed (see Hartman [1978]
and Tsui [1978] ).
The building evacuation model of Chalmet, Francis and Saunders [1982] is
actually not a pure dynamic maximal flow problem because there is a known available
 J.E. Aronson, Survey of dynamic network flows 17

supply of building occupants at the start of period O, and it costs more to exit the
building in later time periods. However, much of their work is based on the original
Ford and Fulkerson [1958, 1962] maximal dynamic network flow concepts. Chalmet
et al. [1982] provide an example of an 11 floor, 323 occupant building with
4 elevators and 2 stairwells. They compare model results, obtained with GNET
(Bradley, Brown and Graves [1977] ), to the results of an observed building evacuation.
Although GNET was used to solve the problem, specialized algorithms such as those
of Jarvis and Ratliff [1982] and the dynamic transshipment algorithms of Aronson
and Chen [1986], Klingman and Mote [1982] and White [1972] are also
applicable. Related work on evacuation models is due to Choi, Francis, Hamacher
and Tufekci [1984], Choi, Hamacher and Tufekci [1988], and Hamacher and
Tufekci [1987].
Federgruen and Groenevelt [1986] present a multiperiod maximum flow
model and a specialized algorithm for the preemptive scheduling of uniform machines.
Orlin [1983] presents an application of his infinite horizon, dynamic network
model to the problem of minimizing the number of transport units to meet a fixed
periodic schedule, an important routing problem for certain transportation industries
as the airlines and railroad industries. Finite horizon versions of this problem have
been considered by Dantzig and Fulkerson [1954], Bartlett [1957], and Levin [1969].
Bartlett [1957] and Levin [1969] solved the problem of minimizing the number of
transport units to meet a fixed periodic schedule in which all routes are required.
Bartlett [1957] applied the problem to airline scheduling and railroad scheduling.
In both paper, simple closed form formulas were presented for the minimum number
of airplanes needed.

4. D y n a m i c t r a n s s h i p m e n t flows

4.1. THE DYNAMICTRANSSHIPMENTMODEL

The DNFP, as stated in section 2, is the mathematical statement of the dynamic

transshipment problem, known also as the minimum cost, multiperiod network
flow problem (Aronson and Chen [1986]). Research on the dynamic transshipment
problem DNFP has centered on three areas: (1) theoretical results and the develop-
ment of solution algorithms for extensions and specializations of DNFP; (2) the
modeling of real-world problems from the areas of production planning, traffic flow,
freight movement, energy production, etc; and (3) the development of special algo-
rithms to exploit its multiperiod structure. In this section, we restrict our attention
to dynamic, linear cost, pure network flow problems. Model variations, theoretical
results, specialized algorithms and their implementations are discussed in section 5.
To date, except for Aronson and Chen [1985, 1986,1989a, 1989b], Chen [1985],
Klingman and Mote [1982], White [1972], and White and Bomberault [1969],
most researchers have not taken the multiperiod strucure into consideration in devising
 18 J.E. Aronson, Survey of dynamic network flows

efficient solution methods for the DNFP. Standard network codes are usually used
because of their availability and perceived efficiency. In the next subsection, we review
these, and other results, algorithms and implementations for specialized DNFPs. In
subsection 4.3, we discuss applications.

4.2. THEORETICAL RESULTS, ALGORITHMSAND IMPLEMENTATIONS

FOR THE DYNAMICTRANSSHIPMENTFLOW PROBLEM

White [1972] discusses an inductive out-of-kilter algorithm that solves a

nested sequence of network subproblems of a dynamic, acyclic network. The acyclic
network restriction is a simple property for empty railroad freight cars, which cannot
be backlogged. White [1972] reports computational results indicating that the
specialized network code is at least ten times faster than the linear programming code
MPS/360 (the predecessor of MPSX/370 (IBM [1979])) on an IBM 360/50, but no
comparison to a pure network optimization code is given. From the data graph, we
estimate that an 1100 node problem was solved using the inductive algorithm in
250 CPU seconds, versus 3100 CPU seconds for MPS/360. In another effort, White
and Bomberault [1969] discuss an inductive primal simplex transshipment algorithm
for solving the same problem. White and Bomberault [1969] report that a PL/1 code,
using bit mapping for efficient storage, was developed, but no computational results
are reported.
Klingman and Mote [1982] present a multiperiod production/distribution and
inventory model which they solve with PNET-MP, a specialized implementation of
the efficient, primal simplex network code PNET (ARC [1974]). Unfortunately,
the structure of the network model and its parameters are fixed over time, that is,
the nodes, arcs, costs, upper bounds, lower bounds, and transit times do not vary
over time. Only the node requirements may change. The major contribution of
Klingman and Mote [1982] is their implementation scheme. Because the structure of
the network is fixed over time, only one period of network data need be explicitly
stored. In their code PNET-MP, bit maps are used to determine the status of an arc
in a solution. The efficiency of the pricing operation is increased because multiple
copies of the same arc are priced over all T periods. If an arc prices favorably, the
best one in that set is selected to enter the basis.
Klingman and Mote [1982] report detailed computational results comparing
the performance of PNET-MP to PNET on solving randomly generated problems
having up to 15 periods, 200 nodes and 2000 arcs per period. The largest of the
problems could not be solved by PNET in 60,000 decimal, 60 bit words of core on a
Control Data CDC 6600. PNET required from about 2 to 4.5 times the computer
memory needed by PNET-MP. For the problems that PNET could solve, the solution
CPU time was from 5% to 70% more than that of the solution CPU time of PNET-MP.
The mean pivot times were about the same. The increase in efficiency was due to
PNET requiring from 25% to 111% more pivots than PNET-MP did. A regression
 J.E. Aronson, Survey of dynamic network flows 19

analysis of the limited computational results indicates that for PNET the solution time
is about quadratic in the number of time periods (T); and the pivot count is on the
order of T 1'48. For PNET-MP, the solution time is on the order of T1"76; and the
pivot count is about linear. These are based on the averages of the regression analysis
of the four models solved by PNET-MP and the two models solved by PNET, all for
T = 5, 10, 15.
New terminology must be introduced to discuss the remaining specialized
results and algorithms. A forward algorithm is a procedure for solving multiperiod
problems by solving successively longer finite subproblems, terminating when a
stopping rule can be invoked, or when the entire T-period problem is solved (Aronson,
Morton and Thompson [1984], Aronson and Thompson [1984], Bhaskaran, Chand
and Sethi [1986], Bhaskaran and Sethi [1987], and Morton [1981] ). Such procedures
are available for the dynamic linear programming problem (Aronson [1980a, 1980b],
Aronson, Morton and Thompson [1985]), some of its specializations (Aronson and
Chen [1985,1986, 1989b], Chen [1985] ) and generalizations (Stanley [1984, 1987]),
and many specially structured models (Aronson and Thompson [1984]). A forward
algorithm solves a problem in stages, by first solving the 1-period subproblem, then
the 2-period subproblem, and so on, until the entire problem is solved. An efficient
forward algorithm augments the ( T - 1)-period optimal solution to obtain an initial
solution to the T-period subproblem.
Forward algorithms are efficient for solving multiperiod problems because
of decision horizons. Formally, the number of periods for which the values of the
decision variables will not change when solving a longer finite horizon subproblem
with a forward algorithm is called a decision horizon. Decision horizons are character-
ized as being exact or empMcal (Aronson and Thompson [1984]). An exact decision
horizon guarantees that the decisions in its time period and all previous periods will
not change. An empMcal or computational decision horizon is one that is observed
to hold with a high probability. If the decisions of the first period are all that is
desired, once a decision horizon is found it is possible to exploit it, or stop a forward
algorithm. Forward methods are important because they work intuitively, i.e. similar
to the way managers make decisions over time (Morton [1978, 1981] ).
The forward network simplex algorithm of Aronson and Chen [1986] exploits
the nmltiperiod structure in addition to the network structure of DNFP. It is a specializa-
tion of the forward simplex algorithm (Aronson, Morton and Thompson [1985]
to DNFP. The forward network simplex algorithm and implementations allow the net-
work structure to change over time. The pricing is retricted to the last few time periods,
over only arcs that are guaranteed to price favorably. For each pivot, only a small
part of the basis tree needs to be updated.
When a forward network simplex algorithm is applied to DNFP, a natural
decomposition (Aronson [1980a], Aronson, Morton and Thompson [1985]) of the
basis tree occurs from empirical decision horizons (Aronson and Chen [1985, 1986,
1989b], Chen [1985]). The decision variables (both flows and duals) of the early
20 J.E. Aronson, Survey of dynamic network flows

period portion of the network become isolated from the pivoting activity in the later
period portion of the network as the subproblem length increases. For some models.
the decomposition is formed by exact decision horizons (Aronson and Chen [1985]).
Although exact decision horizon results are only applicable to specific models, the
forward network simplex implementation is more efficient than standard techniques
for the problems tested by Aronson and Chen [1986, 1989a, 1989b].
Aronson and Chen [1986,1989a, 1989b] hypothesize and confirm that when
solving stationary planning models, the solution CPU time of a forward network
simplex algorithm implementation should be linear in T/q (or T), where q is the
average number of time periods of network data connected in a segment of the
decomposition, even if the worst case bound for each q-period problem segment is
attained. For standard network optimization methods, the solution CPU time is
approximately quadratic in T.
Aronson and Chen [1985] present exact decision horizons in the form of
gaps for a special production/inventory model. Their decision horizons are similar
to the regeneration points and production periods of Wagner and Whitin [1958]
and Lundin and Morton [1975]. Also, see Sandbothe [1985], Sandbothe and
Thompson [1989], and Thompson and Sandbothe [1985]. For the general DNFP,
gaps are not guaranteed, but they can be exploited.
The Forward Network Simplex codes, FORNET and FORNETR, were
developed, implemented and tested on a Control Data CDC 6600. The forward codes
use an advanced start procedure restricted to the local arcs of period T, following
augmentation from period T - 1 to period T. In the computational results, Aronson
and Chen [1986] and Chert [1985] compare the two forward network implementa-
tions to two versions of NETFLO (Kenrdngton and Helgason [1976], Kennington
and Helgason [1980] ):(1) the original NETFLO, utilizing an advanced start procedure,
and (2) a modified version, ARTNET, using an all artificial/slack start. The codes have
the same data structures. The node array consists of a predecessor, thread, depth
(level), flow, dual, and arc identifier. In addition, FORNETR has a reverse thread.
The arc array consists of a from node, cost, capacity, lower bound, and arc name
(optional).
For the five largest problems (700 periods, 3500 nodes, 9,100 arcs) of the first
set of three models, NETFLO priced over sixteen times as many arcs and required
about four times the solution CPU time of ARTNET. NETFLO priced over one
hundred and thirty one times as many arcs and required about ten times the solution
CPU time of FORNET. NETFLO priced an average of about eight million arcs and
performed 8615.2 pivots in 366.4 CPU seconds. ARTNET priced about one-half
million arcs and performed 4513.4 pivots in 95.6 CPU seconds. FORNET and
FORNETR priced only about 61,000 arcs and performed 3924.6 pivots. FORNET
required 37.2 CPU seconds; FORNETR required 24.7 CPU seconds. ARTNET required
about four times the solution CPU time of FORNETR, and. NETFLO required almost
fifteen times that of FORNETR. The improvement factors for the CPU time increases
 J.E. Aronson, Survey of dynamic network flows 21

with the problem size. Similar results were obtained for the other models tested.
The CPU solution time of FORNETR was linear versus T, while the standard network
optimization codes NETFLO and ARTNET required solution CPU times that were
approximately quadratic in T. For all codes tested, the pivot counts were about
linear in T. For FORNET and FORNETR, the number of arcs priced was about
linear in T; however, for NETFLO and ARTNET, it was on the order of approximately
T 2 a n d T T M , respectively.
NETFLO spends a long time correcting its advanced start solution that does
not consider the dynamic model structure and consequently tangles up the initial
basis tree. Typically, the solution CPU time when omitting the advanced start was
about one third of that of when it was included. Even if a standard network optimiza-
tion procedure is to be used for solving a DNFP, the advanced start should be modified
as in FORNET, or omitted entirely for substantial computational savings.
A forward network simplex implementation often obtains empirical decision
horizons. A computational study demonstrating the regular occurrence of empirical
decision horizons is given by Aronson and Chen[ 1989b]. A primary/secondary memory
(Kamey and Klingman [1976]) version of FORNET was implemented as FORNET2
by Aronson and Chen [1989a] to handle larger problems. Similar computational
results were obtained.
Other works on forward algorithms and decision horizon procedures are for
specialized DNFPs. Aronson, Morton and Thompson [1984] discuss a forward
algorithm and decision horizon procedure for solving an infinite horizon version of a
production smoothing problem that has an underlying pure network structure. Their
algorithm solves large problems without a basis inverse. Only four types of non-
degenerate pivots are performed, and exact decision horizons limit the pivoting
activity to the last few time periods. Theoretically, the worst case solution time of
the algorithm is on the order of T 3 . Computational experience on a DEC 2050 indicates
that the solution CPU time and pivot count for the forward algorithm are linear in T.
Other theoretical works are the specialized algorithms for solving network-
based equipment replacement problems by Aronson and Aronofsky [1984,1987],
Bean, Lohmann and Smith [1985], Chand and Sethi [1982], and Sethi and
Chand [1979]. The main results of Bean, Lohmann and Smith [1985], Chand and
Sethi [1982], and Sethi and Chand [1979] are the forward algorithms and decision
horizons for this important class of problems. Aronson and Aronofsky [1984, 1987]
do not include a forward algorithm, but exploit the multiperiod network structure
of the model by an efficient longest path algorithm.
Bean, Birge and Smith [1987] present a new single pass aggregation-
disaggregation algorithm for solving dynamic network flow problems on an acyclic,
connected, directed network. Node aggregation, as discussed by Bean, Birge and
Smith [1987] and in general by Zipkin [1980] and Zipkin and Raimer [1983],
yields major computational benefits in that a smaller problem may be solved,
saving both computational time and memory. Bean, Birge and Smith [1987] indicate
22 ,I.E. Aronson, Survey of dynamic network flows

that nesting the levels of aggregation should be used, and that with a simplifying
assumption it is possible to develop good rules of thumb for determining appropriate
aggregation levels. Error bounds determine how accurate a solution to the original
problem can be obtained using the solution to the aggregated problem. Bean, Birge
and Smith [1987] present such bounds, and indicate that they can be tightened by
using the specific structure of a given problem. They present a useful, tight bound
on the level of error introduced by the time discretizations, and present an example
ofinffnite horizon optimization (see Orlin [1984] ).
Posner and Szwarc [1983] devised an ingenious algorithm for solving a
dynamic production planning problem in the format of a transportation model,
originally presented by Bowman [1956]. Their methodology first distributes the
slack production capacity with an efficient, nontransportation tableau-based procedure.
No basis or basis inverse is required. Once the excess production capacity is assigned,
the remaining problem is solved to optimality directly by a one-pass "northwest
comer" solution. Szwarc and Posner [1984] present a tridiagonal transportation
problem that has only diagonal and off-diagonal cells. The dynamic transshipment
model is applicable to the shipment of goods over a single road or rail facility. They
present an equivalent linear program and a greedy algorithm for its solution.

4.3. APPLICATIONSOF THE DYNAMIC TRANSSHIPMENTFLOWPROBLEM

A number of dynamic, pure network models have been developed, but they
have usually been solved by standard network optimization codes. Gaimon [1986]
presents a multiperiod, production planning network model for a group technology
environment. This problem describes the situation of a single-product family on a
serial production line. Changes in the capacities of the facilities may vary over time.
Example problems are solved with NETFLO (Helgason and Kennington [1976],
Kennington and Helgason [1980] ).
The auto traffic flow model of Zawack and Thompson [1987] incorporates
traffic lights by allowing hold-overs at nodes. Congestion effects are explicitly con-
sidered under the model structure because travel time on a street is a piecewise-
linear convex function of its traffic flow. Example problems are solved with NETFLO.
For the special case of a single source, single destination version of the traffic problem,
a shortest path algorithm is discussed. The space-time network model itself has more
general application than simply traffic flow analysis, for instance, to the job shop
scheduling problem (Thompson and Zawack [1985186]). For related queueing
problems defined on space-time networks, see Bently and Lambe [1980] and D'Ans
and Gazis [1976].
The Chalmet, Francis and Saunders [1982] building evacuation model was
solved using GNET (Bradley, Brown and Graves [1977]), a standard network
optimization code. Bielli et al. [1982] discuss a multicommodity model for air traffic
control. A single commodity model of the Rome Air Traffic Control region is solved
with a standard out-of-kilter (Fulkerson [ 1961 ] ) code.
 J.E. Aronson, Survey of dynamic network flows 23

Klingman, Randolph and Fuller [1976] discuss a cotton ginning distribution

operation modeled as a dynamic network flow problem. Glover, Jones, Kamey,
Klingman and Mote [1979] describe an integrated production, distribution, and
inventory planning system for the Agrico Chemical Company. The system has an
underlying dynamic network flow model, solved by a primal simplex network code.
Problems having 6000 nodes and 35,000 arcs were solved in less than one minute
of CPU time on an AMDAHL V-6 computer. The more complete, long-range planning
system incorporates a linear programming model that contains a large, embedded
network. Problems with some 6250 rows and 23,000 columns were solved in less
than five minutes, including all input and output. In 1978 alone, some U.S.$8 million
in costs were saved.
The problem of distributing empty freight cars in a railroad system over time
is discussed by Potts [1970], White [1972], and White and Bomberault [1969].
Potts [1970] uses the standard out-of-kilter algorithm on the problem, while
White [1972] and White and Bomberault [1969] develop the specialized algorithms
described above. The work of White [1972] and White and Bomberault [1969] has
been extended and applied by Baker [1977], Decision Systems Associates [1978a,
1978b], Ermol'ev et al. [1976], Fernandes Grain and Fogliatti de Sinay [1986],
Florez [1986], Hein [1975,1978], Herren [1973,1977], Ouimet [1972], and
Perevezentsev [1974]. Other extensions have nonlinear costs, a multicommodity
structure, or a network with side constraints structure. See Dejax and Crainic [1987]
for a survey. Gurel and Winbigler [1967] discuss a freight distribution application
in the airline industry.
Versions of DNFP specialized for equipment replacement problems may be
found in Aronson and Aronofsky [1984, 1987], Bean, Lohmann and Smith [1985],
Hillier and Lieberman [1987], Phillips, Ravindran and Solberg [1976], Vemuganti,
Oblak and Aggarwal [1989], Waddell [1983], and Wagner [1975]. These network
models are used only as a conceptual guide in most textbooks (Hillier and Lieber-
man [1987], Phillips, Ravindran and Solberg [1976], and Wagner [1975]) and
research publications (Bean, Lohmann and Smith [1985], and Waddell [1983]). The
problems are usually solved by dynamic programming or other, specialized non-
network algorithms. Notable exceptions are due to Aronson and Aronofsky [1984,
1987], who devised efficient specialized algoritl~ms to exploit the network structure.
Aronson and Aronofsky [1987] describe a longest path, multiperiod network,
equipment replacement model and a specialized longest path algorithm, implemented
directly in a Decision Support System. The optiinization of the network problem
takes place in a financial planning language, rather than in an external network opti-
mization routine. In file companion work, Aronson and Aronofsky [1984] extend
the results to provide a system for modeling and solving equipment replacement
problems with changing technology. This model is similar to that of Sethi and
Chand [1979] ; the model of Aronson and Aronofsky [1984] is similar to that of
Chand and Sethi [1982]. Bean, Lohmann and Smith [1985] consider a similar multi-
period network replacement problem. Vemuganti, Oblak and Aggarwal [1989] address
24 ,I.E. Aronson, Survey of dynamic network flows

similar problems. In addition, they develop a multicommodity model for a fleet

consisting of multiple vekicle types and ages.
The NETGEN-II software (Elam and Klingman [1982]) generates feasible
network flow test problems. It can generate multiperiod networks, given the structure
of a single period, and information about the random distributions of factors that
change over time. NETGEN-II is based on NETGEN (Klingman, Napier and
Stutz [1974]).
The dynamic maximal flow applications discussed in subsection 3.3 may be
solved directly on the time-expanded network by standard network flow optimization
techniques, the forward network simplex algorithm of Aronson and Chen [1986], or,
when the network does not change structure over time, the PNET-MP implementation
of Klingman and Mote [1982]. Other dynamic, network-based models of real systems
are due to Bowman [1956], Glover and Klingman [1976,1977], Glover, Klingman
and McMillan [1977], and Hu and Prager [1959].

5. Other dynamic network models, results, algorithms and applications

Here we discuss model extensions of the pure dynamic network flow problem.
These include models with nonlinear costs, generalized networks, multicommodity
networks, networks with side constraints and/or side columns, mixed-integer networks,
and network-based stochastic problems. Some problems exhibit more than one of the
above properties. Some of the models discussed below are referred to as networks
because the underlying structure of the problem is that of a network. In many cases,
the network-based problems are solved using standard linear, integer or nonlinear
optimization codes. Sometimes, specialized algorittuns are developed. Often, no
attempt is made to exploit the multiperiod structure of complicated models, but the
underlying network is considered. The last subsection covers network-based decision
support systems in practice. As most of the results and algorithms for these models
are applications motivated, we have organized this section mainly by application areas.

5.1. PRODUCTIONPLANNINGMODELS,RESULTS,ALGORITHMSAND APPLICATIONS

Many advanced models and solution techniques come directly from the area
of production planning and scheduling. These include Aderohunmu [1986],
Aderohunmu and Aronson [ 1985,1987,1988], Decision Systems Associates [1978a,
1978b], Evans [1975], Gaimon [1986], Glover, Jones, Karney, Klingman and
Mote [ 1979], Glover and Klingman [ 1976, 1977 ], Klingman, Mote and Phillips [ 1988],
Klingman, Phillips et al. [1986,1987a, 1987b], Klingman, Randolph and Fuller [1976],
Konno [1988], Rao and McGinnis [1983], Rosenthal [1981], Sandbothe [1985],
Sandbothe and Thompson [1989], Steinberg and Napier [1980], Thompson and
Sandbothe [1985], Thompson and Zawack [1985/86], Zahorik, Thomas and
Trigeiro [1984], and Zangwill [1966, 1968,1969, 1985, 1987a, 1987b].
 J.E. Aronson, Survey of dynamic network flows 25

Zangwill [1966,1968,1969] analyzes dynamic, concave cost network flow

problems in his early, ground-breaking works. These production planning models
are useful for when there is a set-up charge, discounting, or efficiencies of scale. With
a set-up cost, these models fit the structure of the dynamic lot size model examined
by many authors including Wagner and Whitin [1958], who developed their well-
known forward algorithm and decision (formerly planning) horizon procedure.
Zan_gwill [1966,1968,1969] identified a finite number of dominant or extreme
flows, and developed and presented dynamic programming algorithms. In the first
of the series, Zangwill [1966] analyzes a backlogging model having concave production
costs and piecewise concave inventory costs. Zangwill [1966] finds the form of the
minimum cost production schedule. He identifies a dominant set of schedules, presents
an efficient dynamic programming algorithm, and provides an example.
In a similar manner, Zangwill [1968] develops theorems that explicitly
characterize the extreme points for certain single-commodity networks. By exploiting
this characterization, dynamic programming algorithms are developed that determine
the minimum concave cost solution for three problems:
(1) networks with a single source and a single sink,
(2) acyclic networks with a single source and multiple sinks, and
(3) acyclic networks with multiple sources and a single sink.
He also presents a theorem that describes how the multicommodity case can be
reduced to the single-commodity case for either single source or single sink networks.
Applications to the concave warehouse problem, a single product and inventory
model, a multiproduct production and inventory model, and a plant location problem
are given.
In the third paper, Zangwill [1969] presents a dynamic network backlogging
model and a multi-echelon model of a dynamic lot size production system. As before,
both models have concave arc costs. He shows that both models can be represented
by dynamic, single source network flow problems, for which he develops efficient
dynamic programming algorithms. For the fixed-charge case, the algorithm for the
first model requires exactly twice the effort of the Wagner-Whitin [1958] forward
algorithm without backlogging. Also, he gives a generalization of the Wagner-
Whitin [1958] decision (planning) horizon theorem. The exact decision horizons
can aid in reducing computational effort. The second, multi-echelon model is a
predecessor to the multi-item, multi-echelon multiperiod models of Steinberg and
Napier [1980] and Zahorik, Thomas and Trigeiro [1984]. Examples of both models
and dynamic programming algorithms are given. Konno [1988] extends the work of
Zangwill [1969]. He proposes an efficient algorithm for when time lag occurs in each
facility of a multi-echelon, minimum concave cost production system.
The results of Zangwill [1966,1968,1969], Wagner and Whitin [1958],
Veinott [1969] and the Steiner tree problem in graphs (Dreyfus and Wagner [1971])
were unified and generalized by Erickson, Monma and Veinott [1987]. They present
a more general dynamic programming network algorithm, for which they conjecture
26 J.E. Aronson, Sun,O; of dynamic nenvork flows

an exponential time bound for fairly general networks. They do, however, identify
the class of acyclic single source networks, for which the algorithm is polynomially
bounded. Their algorithm is more efficient than the algorithm of Zangwill [1968].
Their applications include the dynamic single-facility economic-order-and-sale-
quantity problem, and the dynamic tandem-facilities economic-order-quantity problem.
Evans [1975] discusses the formulation of a multicommodity extension of
the nonlinear cost model of Zangwill [1969]. He converts the model to a multistage,
single-commodity network flow problem that can easily be solved.
Zahorik. Thomas and Trigeiro [1984] discuss a multicommodity network
flow model for a multistage, multi-item capacitated production system. The model
has linear costs, and production and inventory constraints for the single-facility case.
An example is shown in fig. 5. They convert the model into a series of 3-period

PERIOD: 1 2 3 4 5 6

COMMODITY (~ Bundlq
PRODUCTION:

LEVEL 1 :

LEVEL 2:

LEVEL 3:

FINAL
DEMAND: @ 9 @ @ @ @
Fig.5. Network representation of a six period, two commodity, multi-level
production scheduling model of Zahorik, Thomas and Trigeiro [1984]. Each level
represents a different st.age in the finished product. The arcs from left to right
represent work in process inventory at the end of the period. There are GUB
structured bundle contraints (shown only for period 1) on the flow through each
arc of this network. This is a multiperiod, multicommodity network flow model.

network flow problems that are easily solved and used as the basis for n-period
heuristics. They solve a series of problems by using a 3-period rolling horizon
(Morton [1981] ) technique.
The Evans [1975] and Zahorik, Thomas and Trigeiro [1984] models motivated
Aderohunmu [1986] and Aderohunmu and Aronson [1985, 1987, 1988] to develop
solution techniques for a class of production planning models that have a structure
they call network problems with bundle side constraints. Multiple production sources
can meet the demand of any of the commodities. There is a mutual capacity bundle
 J.E. Aronson, Survey of dynamic network flows 27

constraint in every time period on the ending inventory that destroys the pure net-
work structure of the model. The bundle constraints have the generalized upper
bounded (Dantzig and Van Slyke [1964] ) structure (see fig. 6). Aderohunmu [1986]
and Aronson and Aderohunmu [1987] discuss the development of an aggregation/

PERIOD: 1 2 3 99- T-1 T

SUPPLIES:

Bundle
~u~ dl

DEMANDS:

- (

Bundle

Vig. 6. The mLdtiperiod network model with bundle side constraintsof Aderohunmu
and Aronson [1985, 1987]. There are 2 supply nodes, 3 demand nodes, and 9 arcs
originating in each time period except for period T, in which there are 6 arcs
originating. Fnding inventory is allowed at the demand nodes. There are 3 bundle
constraints in each time period. They are identified only in period 1.

disaggregation algorithm that converts the network with side constraints into a pure,
capacitated network flow problem. See Zipkin [1980] for background material on
network aggregation. Also, see Rogers et al. [1988] for a comprehensive survey. By
solving two pure network flow problems, they obtain a feasible solution to the original
problem and error bounds on its accuracy. For their test problems, typically, the
costs of solutions obtained were within 0.75% o f optimality and were found fifty
times faster than MPSX/370 (IBM [1979]) on an IBM 3081-D24. In one case, their
code solved a problem over 460 times faster than MPSX/370. When the forward
network simplex code FORNETR (A,ronson and Chen [1986]) is substituted for
NETFLO (Kennington and Helgason [1980]) for the optimization routine, a further
increase in efficiency occurs (Aderohunmu and Aronson [1988]).
Rao and McGinnis [1983] present constructive network-based proofs for the
Wagner-Whitin [1958] property and a generalized nested schedule property for
optimal production schedules in acyclic hierarchical production systems. The model
is a generalized network with a concave cost function. They also describe algorithms
28 J.E. Aronson, Survey of dynamic network flows

for determining schedules for problems with the properties described above. Their
formulation is similar to that of Steinberg and Napier [1980], who discuss a multi-
stage, fixed-charge, generalized network flow model for optimal multilevel lot sizing
for requirement planning systems. Example problems were solved with a mixed-
integer programming package.
Sandbothe [1985], Sandbothe and Thompson [1989], and Thompson and
Sandbothe [1985] present bounds, decision horizon results and a forward algorithm
for dynamic network capacitated lot size models with inventory bounds and stock-
outs permitted. Transportation relaxations are used as an approximation to the
capacitated lot size model to obtain upper and lower bounds on the optimal solution
to one of the problems. Efficient forward algorithms are described and implemented
for variants of the model. See Sandbothe [1985] for a comprehensive review of
capacitated lot size model research. See Chand and Morton [1986] for another
forward algorithm.
In a second series of papers, Zangwill [1985,1987a, 1987b] discusses an
analysis of series facility production systems. He considers the general framework
of moving from the current industrial practices of maintaining inventory to that of
zero inventory (ZI). He also examines the effect of reducing set-up costs on overall
production system cost. Zangwill [1987b] discusses the relationship between ZI and
EOQ (Economic Order Quantity) for series production facilities in order that the
ZI concept can be utilized more precisely and effectively. Using ZI, it is possible to
obtain a set-up cost reduction that does not always reduce inventories nor lower
total production costs. He presents a dynamic lot size model with concave, stationary
costs. The algorithmic results can be interpreted via an analogous network flow
problem, a shortest route problem having n origins and a single sink, equivalent to
a single source, single sink dynamic network flow problem. Numerous examples are
given. An algorithm is presented for determining how much total cost is saved as a
function of the set-up cost reduction. The major conclusion is that certain widely
held presumptions about the process of moving toward ZI are not always true.
Zangwill [1985] provides sufficient conditions to ensure that lowering the
set-up cost actually does lower inventory levels and reduces total costs. Also, he
shows an unexpected result: that the investment in set-up cost reduction exhibits
increasing marginal returns. A parametric algorithm is also presented. Having ZI in
a series production facility is not necessarily optimal. Zangwill [1985] determines
that there is a trade-off between set-up and inventory cost that must be examined.
Analysis of the resulting parametric problem indicates that ZI must not be enforced
immediately, but there is a trajectory that must be followed over an extended period
of time. In complex situations, set-up cost reduction can actually increase costs, as
was observed by Zangwill [1987b]. The analysis is based on the Zangwill [1968]
dynamic, concave cost network flow model.
In the same type of series facility system, Zangwill [1987a] uses the same
network model (Zangwill [1968]) to locate facilities that will not hold inventory
 J.E. Aronson, Survey of dynamic network flows 29

and reduce the set-up costs to eliminate even more inventory. The techniques aid
the process of inventory reduction, simplify production scheduling, and assist attain-
ment of the zero inventory goal. He first examines facility elimination. A partitioning
algorithm is given for determining which facilities will hold inventory.
Rosenthal [1981 ] presents a nonlinear, multi-stage network flow formulation
of a hydroelectric power system for the Tennessee Valley Authority. The model
has a nonseparable, nonlinear, objective function with pure network flow constraints.
He also discusses a nonlinear network flow algorithm for solving the problem.
See Glover and Klingxnan [1977] for a description of several multiperiod
network flow models for production planning and distribution, and for a description
of the Klingman, Randolph and Fuller [1976] cotton ginning application. Also, see
Glover, Jones, Karney, Klingman and Mote [1979] for another production system.

5.2. RAILAND TRUCKINGMODELS,RESULTS,ALGORITHMSAND APPLICATIONS

Stochastic models with underlying dynamic networks are presented for rail
and trucking systems by Crainic, Ferland and Rousseau [1984], Farvolden [1989],
Frantzeskasis and Powell [1988], Jordan [1982], Jordan and Turnquist [1983],
Turnquist [1986], Turnquist and Jordan [1982], Powell [1986, 1987, 1988], Powell
and Cape [1988], Powell and Sheffi [1989], and Powell, Sheffi et al. [1984, 1988].
Deterministic dynamic network-related models are due to Gorenstein, Poley and
White [1971], Haghani [1986], Haghani and Daskin [1986], Kornhauser and
Adamidou [1986], and Shan [1985]. Also, see Baker [1977], Cuimet [1972],
Decision Systems Associates [1978a, 1978b], Dejax and Crainic [1987], Ermol'ev
et al. [1976], Feeney [1957], Florez [1986], Glickman and Sherali [1985],
Hein [1975,1978], Herren [1973,1977],Kornhauser [1985],Mendiratta [1981],
Mendiratta and Turnquist [1982], Ouimet [1972], and Perevezentsev [1974].
Crainic, Ferland and Rousseau [1984] present a rail freight transportation
model. Queueing-based heuristics were developed to solve this nonlinear, mixed-
integer, multicommodity problem. Gorenstein, Poley and White [1971] propose a
dynamic multicommodity network model of empty rail car distribution embedded
within a real-time control system. Shan [1985] describes a dynamic network for
empty rail car management. Komhauser and Adamidou [1986] model freight car
management as an N person noncooperative game, formulated as a multicommodity
flow problem on space-time networks, which they solve by an iterative heuristic.
Haghani and Daskin [1986] propose a nonlinear mixed-integer, dynamic network
formulation of train routing and empty car allocation. See Haghani [1986] for a
detailed presentation of the model and solution procedure. Hughes and Powell [1989]
discuss the distortions introduced in dynamic network vehicle allocation models by
employing finite planning horizons. These types of end effects have been discussed
by many others (Aronson and Thompson [1985], Miller [1979], and Murphy and
Soyster [1986].
30 J.E. Aronson, Sttrvey of dynamic network flows

Komhauser [1985] discusses the Princeton Transportation Network Model

and Graphic Infonnation System (PTNM/GIS), a system for maintaining data and
solving realistic, large transportation problems. The U.S. and Canadian Rail, Highway
and Waterway network systems, augmented by worldwide shipping lanes, are included
in its cartographic-based network database. As illustrated by example applications,
we suggest that such systems will become increasingly useful and even necessary for
managing network data used in obtaining solutions to very large-scale, real-world
dynamic network, commodity transportation and distribution problems.

5.3. COMMUNICATIONMODELS, RESULTS, ALGORITHMSAND APPLICATIONS

A major area in which dynamic network models have impact is communication

systems. Smith [ 1979] describes such an application to a complex, large-scale, dynamic
mixed-integer programming forlnulation of a national telecommunications system
that requires capacity expansion. To solve the problem, he considers a heuristic
based on defen'al strategies that allow the rerouting of messages through less efficient
channels in order to delay incurring large fixed-charges from capacity expansion. For
small prototype network problems, solutions obtained by the heuristic-based procedure
compare favorable with the exact solutions obtained by solving the corresponding
mixed-integer, linear programming problems. Also, the heuristiobased procedure
solved the test problems over one hundred times faster than MPSX/MIP/370
(IBM [1975]). Other authors who have considered the same application include
Klessig [1974], McCallum [1977], and Yaged [1971,1973, 1975]. See also
Zadeh [1973,1974]. Stochastic dynamic network models are also of use in solving
problems in the communications area (for example, Hajek and Ogier [1984] ).
Momna and Segal [1982] present a primal algorithm for solving minimum
cost network flow problems. Their methodology incorporates anti-cycling procedures
(Cunningham [1976,1979]), and implicitly encompasses piecewise-linear costs
(Fourer [1985, I986,1988], Premoli [I986]) instead of explicitly storing multiple
arcs. They present a dynanaic network application to scheduling the collection of
call records in private communications networks.

5.4. DYNAMICGENERALIZEDNI-TWORKS

Generalized network models for manpower planning are presented by Charnes

and Cooper [1961], Dantzig [1963], and Wagner [1975]. A complete water distri-
bution system with losses was modeled as a dynamic generalized network by
Bhaumik [1973]. Kim [1972] utilizes generalized networks to represent copper
refining processes to analyze the effect of short circuits in the refining process. Charnes
and Cooper [1961] present a generalized network, warehouse funds-flow model.
The arcs represent sales, production, and the inventory holding of both products
and cash. The multipliers facilitate the conversions between cash and products.
 <I.E. Aronson, Survey of dynamic network flows 31

Crum [1976] modeled a cash management problem for a multi-national firm as a

dynamic generalized network. See Crum and Dye [1981], Crum, Klingman and
Tavis [1979,1983a,1983b], Mulvey [1984a], Mulvey and Zenios [1985], and
Srinivasan [ 1974] for other cash flow models. McBride, O'Leary and Widmeyer [ 1988]
describe a generalized-network-based system for supporting cash management decisions.
See Glover, Glover and Martinson [ 1984] and Glover and Martinson [1982] for network-
based, resource planning models. Glover, Hultz, Klingman and Stutz [1978b] discuss
sources for other applications of dynamic generalized networks, including production
and distribution scheduling problems, machine loading problems, crew scheduling,
and aircraft scheduling.
5.5. MIXI-D-INTF.G1-RMULTICOMMODITYMODI-LS. RI~SULTS.ALGOP,ITIIMS
AND APPLICATIONS
In the integer programming area, Aronson [1986] introduced a multi-
commodity network formulation of the multiperiod assignnrent problem. It considers
the case of assigning jobs to persons over T discrete time periods. The model takes
into consideration not only the assignment costs in each time period, but also the
cost of transferring a person from one job to another between consecutive time
periods. The underlying network problem for each person (coimnodity) is a shortest
path problem, for which an efficient, specialized algorithm was developed and imple-
mented. This algorithm was embedded in both an effective heuristic and a specialized
branch and bound procedure for solving the problem to optimality. For randomly
generated problems, the branch and bound algorithm obtained solutions to moderately
sized problems having four persons, four jobs, and up to six time periods, in less than
11 CPU seconds on a Control Data CDC 6600. Larger problems having seven persons,
seven jobs, and four time periods, required about 8.65 CPU minutes. Elnidani [1986]
and Elnidani and Aronson [1989a, 1989b, 1989c] have developed new variations of
the model (Elnidani and Aronson [1989c]), and implemented a branch and bound
procedure (Elnidani and Aronson [1989a] ) that exploits the multicommodity structure
(Elnidani and Aronson [1989b] ) differently.
Evans [1981] discusses an aggregation heuristic for solving a related problem,
in which the number of periods equals the number of jobs and persons. In addition,
each person is assigned each job exactly once over the time horizon. The heuristic
solves a sequence of pure network flow problems. It obtains good solutions to this
large, np-complete problem. The Aronson [1986] model may be modified to consider
the Evans [1981] specialization by adding a set of GUB side constraints. Other works
on multiperiod assignment problems include Charnes, Cooper and Stedry [1969]
and Gunawardane [1982]. Further references on the related multi-index (mostly
three-dimensional) assignment and transportation problems include Balas and
Landweer [1983], Balas and Saltzman [1988,1989], Corban [1964,1966],
Frieze [1974,1983], Frieze and Yadegar [1981], Gotlieb [1962], Haley [1962,
1963, 1965], Leue [1972], Moravek and Vlach [1967], Oblak and Vemuganti [1989],
Pierskalla [1967a,1967b, 1968], Schell [1955], Shamma [1971], Vajda [1961],
32 J.E. Aronson, Survey of dynamic network flows

Vlach [1967], and Williams and Haley [1959]. See Gilbert and Hofstra [1988] for
a recent survey.
Allen [1985] discusses the development of a large-scale integer, dynamic,
multicommodity network flow model for troop evacuation. Allen [1985] presents
an efficient algorithm that solves a sequence of pure network flow problems for
which the objective functions converge to an optimal value. As the algorithm proceeds,
lower and upper bounds on the total cost of the solution obtained are determined.
Extremely large problems, for which the linear programming relaxation could not
be solved using standard linear programming or multicommodity codes, were solved
to within a prespecified cost tolerance of optimality in a reasonable computational
time. Allen's [1985] efficient solution methodology, however, did not consider the
multiperiod structure.
Helgason, Kennington and Wong [1982] present a fixed-charge, dynamic
multicommodity network flow planning model for national forest land management.
They present a specialized branch and bound algorithm with special rounding heuristics,
an efficient, experimental code, and some limited computational results.

5.6. INFINITEHORIZON MODELS, RESULTS.ALGORITHMS AND APPLICATIONS

Orlin [1984] generalizes his previous work on infinite horizon dynamic maxi-
mal flows to present a polynomial time algorithm for the infinite horizon, minimum
convex cost, integer dynamic network flow problem. The objective is to minimize
the average cost per period of sending the flow. His algorithm first relaxes the
integrality condition on the flows to find an optimal temporally repeated continuous
valued flow using the results of Orlin [1983]. This solution is then rounded to obtain
an optimal integral flow that repeats every q periods, where q is the least common
denominator of the fractional parts of the continuous flow. The results ofOrlin [ 1984]
are applicable to integer problems that have deterministic demands repeating periodic-
ally over time. This problem class includes the cyclic capacity scheduling problem
(a generalization to the finite horizon capacity scheduling problem of Veinott and
Wagner [1962]), the cyclic staffing problem (for the one-day cyclic staffing problem
(Baker [ 1974,1976], Bartholdi, Orlin and Ratliff [ 1980], Bartholdi and Ratliff [ 1978],
Odin [1977], and Tibrewala, Philippe and Browne [1972]), the periodic production
and transshipment problem with convex costs (Odin [1983]), the airline scheduling
problem (Orlin [I 983] ), and the minimum cost-to-time ratio circuit problem (Dantzig,
Blattner and Rao [1967]).

5.7. OTHERMODELS, RESULTS,ALGORITHMSAND APPLICATIONS

Escudero [1986] presents results for a class of dynamic network flow

problems that have non-differentiable, nonlinear Objective functions (also, see
Escudero [1985]). He reports on the computational performance of a truncated
Newton method using the new concept of independent superbasic sets to allow for
obtaining independent pieces of the solution in parallel at each iteration. Computa-
 J.E. Aronson, Survey of dynamic network flows 33

tional results indicate that the method is effective for problems with many time
periods and few linking arcs. He has identified the natural decomposition of the non-
linear problems similar to that described by Aronson and Chen [1985, 1986, 1989b]
for linear cost problems.
Mulvey [1984b] presents a dynamic network model for the U.S. air traffic
system. The nonlinear cost, generalized network model allocates aircraft to high-
altitude jet routes. Both risks and transportation costs are considered. He describes
two applications of the model. Also, see Mulvey and Zenios [1987].
Merchant and Nemhauser [1978a,1978b] present a dynamic traffic assign-
ment optimization model for a single destination and single commodity. Travel costs,
route choices and flow rates are interdependent in their nonlinear, nonconvex formula-
tion. A specialized algorithm (Merchant and Nemhauser [1978a]) and optimality
conditions (Merchant and Nemhauser [1978b]) are presented. Here, the problem
is only defined on a network (also, see Merchant [1974]). Related network models
and results are due to Fong and Srinivasan [1981,1986], who discuss a multiregion
economic planning model.
Carey [1987] presents a well-behaved convex programming model for least
cost flows on a general congested network for which arc transit times are flow
dependent. Multiple destinations and multiple commodity extensions are also
presented. It is not an equilibrium model like that of Merchant and Nemhauser [ 1978a].
As part of the solution, the model yields a set of non-negative time-varying optimal
flow controls for each arc (traffic lights, etc.). Sufficient conditions for some of or all
of these flow controls to be zero are determined and confirmed by computational
experience using MINOS (Murtagh and Saunders [1977, 1980] ). Extensions to flexible
departure times and elastic demands are also given. See Carey and Srinivasan [1982]
for more computational results. In a related work, Carey [1986] presents a constraint
qualification for a dynamic traffic assignment model. Carey and Srinivasan [1985]
discuss system marginal costs, user perceived costs, and user externality costs for
arcs and paths in congested networks with time-varying flows. Thus, optimal tolls
and flow controls may be found and imposed on the network. Further models and
results are described by Carey and Srinivasan [1989]. In a recent paper, Carey [1988]
presents a modeling scheme and characterization to describe nonlinear, dynamic
network flow problems for which the transit time is a nonlinear function of the flow
through the arc.
Nagurney and Aronson [1988] present a network-based formulation, algorithm
and computational results for a general dynamic spatial price equilibrium model.
They have extended economic equilibrium models to consider the multiperiod nature
of the problem. Nagurney and Aronson [1989] further extend the work to a
generalized network formulation to consider gains and losses. Nagurney [1988]
describes parallel computer implementations for these and related problems. For
background on these models, see Dafermos [1971,1972, 1980, 1982a, 1982b, 1984],
Dafermos and Nagurney [1984], and Dafermos and Sparrow [1969]. Parallel
computer architecture algorithms are also being developed (Nagurney [1988]).
34 J.E. Aronson, Survey of dynamic network flows

Zemanian [1983a,1983b] discusses dynamic, network-based economic equilibrium

models.
Multiperiod, near-network, resource allocation problems with storable and
substitutable resources are discussed by Klein, Luss and Smith [1987], Luss and
Smith [1988], and Nguyen and Stone [1987]. The last model may be solved by the
specialized network with side variables atgoritlun of Stone [ 1988].
As mentioned in section 2, the continuous dynamic network flow approach
of Anderson, Nash and Philpott [1982], Anderson and Philpott [1984] and
Philpott [1984] considers the dynamic network problem as a continuum, eliminating
the analyst's problem of determining an appropriate level of discretization. Further
developments of these continuous methods should be applicable to solving problems
with pipeline flows, for which the node requirements and network characterization
may change continuously.

5.8. NETWORK-BASEDDECISION SUPPORTSYSTEMS IN PRACTICE

In this subsection, we describe implemented systems that incorporate dynamic

network-based optimization models to aid decision making. Most include generaliza-
tions of DNFP. They have demonstrated their abilities to aid executive planning and
decision making by annual savings in the hundreds of millions of dollars.
Glover, Glover, Lorenzo and McMillan [1982] describe a passenger-mix
determination system implemented for Frontier Airlines. The system performs
reservation monitoring and price/route setting. Although not explicitly mentioned,
a dynamic network-related model was used. The model is also applicable to trucking
companies, steamship companies, etc., that have a set of regularly scheduled routes.
Also, see Glover, McMillan and Taylor [1977].
Ikura, Gross and Hall [1986] describe a Pacific Gas and Electric scheduling
tool having a multiperiod network flow model with a nonlinear objective function.
It maximizes the weighted sum of hydro energy, which is described as a function
of the flows on the arcs. There are side constraints to restrict reservoir releases, storage
amounts and other conditions. Benefits of this system were estimated to be between
U.S.$10 to U.S.$45 million per year.
Powell, Sheffi, Nickerson, Butterbaugh and Atherton [1988] describe an
operational, network-based system for the Truckload Division of North American
Van Lines. It provides a higher level of service while increasing profits by an esti-
mated U.S.$2.5 million annually. Some stochastic data are considered in the real-
time, multiperiod network flow model.
Klingman, Phillips et al. [1986,1987a, 1987b] discuss a dynamic, network-
based integrated products planning system for the Citgo Petroleum Corporation.
The optimization-based decision support system, coupled with a state-of-the-art,
on-line corporate data base, provided management with information that resulted
in benefits estimated to exceed U.S.$100 million per year.
 .I.E. Aronson, Survey of dynamic network flows 35

Klingman, Mote and Phillips [1988] describe a multiperiod, multicommodity,

production/distribution system implemented for the W.R. Grace Company, one of
the U.S.'s largest suppliers of phosphate-based chemical products. A linear program-
ming model was reformulated as a generalized network with side constraints. This
model was transformed into a pure network flow problem that was efficiently solved.
Multimillion dollar decisions were supported by the planning system.
For more real-world systems, see Decision Systems Associates [1978a, 1978b],
Farina and Glover [1980], Glover, Glover and Martinson [1984], Glover, Jones,
Karney, Klingman and Mote [1979], Klingman, Randolph and Fuller [1976] ,McBride,
O'Leary and Widmeyer [1988], Poweli and Sheffi [ 1989], and Tomlin [1988].

6. Current and future research

The directions of current research fall into the same broad categories of
previous research on DNFP. Important advances are being made in the modeling of
real-world problems, the development of special algorithms that exploit multiperiod
structure, and the development of decision support systems that incorporate such
models and algorithms. Specially structured problems, larger than ever before, are
being modeled and solved with reasonable computational effort. These include
multiperiod assignment models (Aronson [1986], Elnidani [1986], Elnidani and
Aronson [1989a,1989b], Evans ]1981]), building evacuation models (Chalmet,
Francis and Saunders [1982], Choi, Francis, Hamacher and Tufekci [1984], Choi,
Hamacher and Tufekci [1988], Hamacher and Tufekci [1987]) and troop evacuation
models (Allen [1985]). Elnidani and Aronson [1989c] have developed variations
of the multiperiod assignment model for personnel planning and facility location.
A great deal of work on algorithms and implementations focuses on
developing forward algorithms and decision horizon procedures (Aronson, Morton
and Thompson [1984], Sandbothe [1985], Sandbothe and Thompson [1989])for
solving specializations and generalizations of DNFP.
The results of Evans [ 1981 ], Bean, Birge and Smith [ 1987 ], Aderohunmu [ 1986],
and Aderohunmu and Aronson [1985,1987,1988] indicate that aggregation
procedures show promise in solving large problems efficiently. These efforts are
directed both toward aggregating segments of a network within time periods, and
toward aggregating the time periods. Error bounds on the solution cost (Bean, Birge
and Smith [1987] )may determine a reasonable level of time discretization.
The forward simplex method of Aronson, Morton and Thompson [1985]
is applicable to the dynamic models having linear costs. The forward-convex simplex
method of Stanley [1984,1987] applies to convex cost problems. These forward
algorithms may be cutomized for specific applications as for DNFP (Aronson and
Chen [1985,1986,1989a, 1989b] ,Chen [1985] ) and, as is outlined in Aronson [ 1980a]
and Aronson, Morton and Thompson [1985], for multicommodity network flow
problems, generalized networks (Adolphson and Aronson [1988]), and networks
36 J.E. A ronson, Survey of dynamic network flows

with side constraints and/or side columns. Some of these extensions are being imple-
mented and tested. Immediate benefits in improved solution CPU times can be gained
in solving the models of Aderohunmu [1986], Aderohunmu and Aronson [1985,
1987, 1988], and Allen [1985] by substituting the forward network code FORNETR
for NETFLO. In addition to the pure linear programming case, the forward methods
offer possibilities for solving very large, dynamic, mixed-integer network programming
problems.
Dynamic linear programming methods (Propoi and Krivonozhko [1977]) are
valid for solving the DNFP and its variations. Based on the limited computational
experience of Propoi and Krivonozhko [1977], we do not expect good results, even
for network flow specializations.
Research on implementation technology has focused on data structures over
the last fifteen years. The forward network algorithm has been implemented in a
primary/secondary mode (Aronson and Chen [198%])to solve larger problems.
Alternatively, data or bit mapping as described by Klingman and Mote [1982] may
be used for storing the networks by a single period for identical arc data over time.
Parallel implementations of specialized algorithms will have impact in terms of the
size of the largest solvable problems. For the Allen [1985] model, independent
processors could solve the several independent network flow problems simultaneously.
Also, the forward network simplex algorithm lends itself to certain parallel imple-
mentations because of the decision horizons.
We expect more development and use of network database systems, as described
by Kornhauser [1985], for data management and retrieval by general and customized
decision support systems for solving large-scale, real-world, dynamic network
production and distribution problems routinely as by Klingman, Phillips et al. [1986,
1987a, 1987b], etc.
Barr [1985] presents computational work on solving network flow problems
on personal computers. His results indicate that some of the earlier personal computers
are capable of solving problems at speeds that are on the order of those of second-
generation mainframe computers. Based on his results and the results of specialized
dynamic network algorithms, personal computers should be able to solve small to
medium sized dynamic network flow problems in reasonable computer time. We
expect the development of personal computer-based systems for solving large prob-
lems routinely.
The Karmarkar algorithm for solving linear programming problems has
seeded new research (Karmarkar [1984a,1984b], Barnes [1986], Gay [1987],
Gill et al. [1986], Shanno [1988], Todd [1988]). Todd [1988], in a discussion on
developing versions of the Karmarkar algorithin that can exploit special structures,
indicates that simple, generalized, and variable upper bounds can be handled efficiently,
but not network constraints. Computational testing is recommended. Also, see Aronson,
Barr, Helgason, Kennington, Loh and Zaki [1985].
New techniques like the Pivot and Probe Algorithm (PAPA) (Sethi [1983],
Sethi and Thompson [1984,1986]) show promise in solving large-scale linear
 J.E. Aronson, Survey of dynamic network flows 37

programming and network flow problems. Sethi, Thompson and Hung [1988] provide
a PAPA implementation within the framework of the XMP system (Marsten [1981]).
New specializations of multiobjective network flow optimization problems are currently
being explored by Aronson and Steuer [1989] and Olson et al. [1989].
Many real-world linear programs are network based. The identification of
embedded networks in linear programs (Brown, McBride and Wood [1985], Brown
and Wright [1984], Bixby and Cunningham [1980], Bixby and Fourer [1988],
Glover [1981], Truemper [1983]) so that the structure can be exploited either
through decomposition approaches (i.e. Barr, Farhangian and Kennington [1986],
Glover and Klingman [1981,1985]), or by Lagrangian relaxation approaches (Glover
and Klingman [1988] ), is directly applicable to dynamic models.
There are exciting new approaches for solving networks, generalized networks
and related problems due to Ali, Kennington and Shetty [1988], Ali, Padman and
Thiagarajan [1989], Aderohunmu [1986], Aderohunmu and Aronson [1985,1987,
1988], Beck, Lasdon and Engquist [1983], Bertsekas [1981,1985, 1986], Bertsekas
and Eckstein [1987], Bertsekas and E1Baz [1987], Bertsekas,Hosein and Tseng [1988],
Chen and Engquist [1986], Glover and Klingman [1988], Rosenthal [1986],
Shetty [1985], Tseng [1986], and Tseng and Bertsekas [1987a,1987b]. Parallel,
network-based implementations on new computer architectures (Bertsekas and
E1 Baz [1987], Bertsekas and Tsitsiklis [1988], Clark and Meyer [1987], Kennington
and Muthukrishnan [1988] ,Meyer [ 1987] ,Meyer and Zenios [1988],Nagurney [1988],
Miller, Pekny and Thompson [1989], Zenios [1986,1989], Zenios and Lasken [1988],
Zenios and Mulvey [1985,1986,1988a,1988b]) offer opportunities to expand
problem sizes dramatically. Anticycling procedures (Barr, Elam, Glover and
Klingman [1980], Cunningham [1976,1979], Elam, Glover and Klingman [1979])
offer stable versions of existing algorittuns. Specialized approaches that incorporate
these concepts may prove very effective for solving dynamic network flow problems.

7. Summary and conclusions

We have presented a state-of-the-art survey of the models, results, algorithms,

implementations, and applications for dynamic network flows. Based on experience
with dynamic network flow algorithm development, and the past and current research,
we make the following observations and conclusions:
The most important factor in modeling dynamic network flow problems is
the level of time discretization. By discretizing a problem, error is introduced for
certain continuous problems. If a continuous model is needed, the solution approaches
pioneered by Philpott [1984], Anderson, Nash and Philpott [1982], and Anderson
and Philpott [1984] should be considered. If it is not possible to apply the continuous
approaches, then the forward methods of Aronson, Morton and Thompson [1985]
as specialized by Aronson and Chen [1986], or the implementation scheme of
Klingman and Mote [1982] should be considered. If the problem is too large, its
38 J.E. Aronson, Survey of dynamic network flows

aggregation can yield near-optimal solutions in reasonable computer CPU time and
memory.
The approaches for solving maximal dynamic network flow problems, based
on Ford and Fulkerson [1958, 1962], are efficient, as long as there are 17o changes
to the network over time. When there are changes, then the problem should be solved
as a time-expanded network (Halpern [1979], Minieka [1974]). As before, we
recommend using algorithms specialized to exploit the dynamic structure.
Customized forward algorithms and decision horizon procedures are effective
and efficient solution methods for specific problems such as the capacitated lot size
problem (Sandbothe [1985], Sandbothe and Thompson [1989] ) and other network-
based models for production (Aronson, Morton and Thompson [1984], Chand and
Sethi [1982], Sethi and Chand [1979]). Large versions of some of these problems,
if stated in their complete linear programming or mixed-integer form, would be
impossible to solve otherwise.
Most researchers, when confronted with a dynamic network flow problem, do
not devise methods for exploiting the multiperiod structure, but use existing methods
and codes, mainly because their interest is the model. If a problem is small and solved
infrequently, and an existing network code is available, then it may be adequate in
terms of code development or acquisition expense and computer time. However, if
the problem is large and frequently solved, then an implementation of a specialized
efficient starting procedure and dynamic algorithm should be considered.
Ho and Loute [1983] indicate that d#'ect methods, i.e. no special decom-
positions or factorizations, provide the best algorithms and implementations for
solving multiperiod linear programming problems. The forward network simplex
algorithm (Aronson and Chen [1986]) and the implementation technology developed
by Klingman and Mote [1982] are direct methods. They are as efficient as the standard,
direct approaches when solving a single period problem. They exploit dynamic structure
when present.
Advances in serial and parallel computer architectures reaching the market-
place, extremely fast and powerful personal computers, and new methodologies for
solving problems with special structures enhances our ability to solve large-scale
problems. Large problem size should no longer be an issue as to why dynamic net-
work models are not used in practice. The procedures surveyed here can accommodate
them. Exploitation of the dynamic structure should yield at least another order of
magnitude in the size of problems solvable with reasonable computational effort.

Acknowledgement

This work was supported in part by National Science Foundation Grant

ECS-8307549.
 Table 1
References arranged by category

Topic Models Theoretical results Algorithms/Implementations

Maximal dynamic Chalmet, Francis and Saunders [ 1982] Chalmet, Francis and Saunders [ 1982 ] Federgruen and Groenevelt [ 1986 ]
network flows: Choi, Francis, Hamacher Choi, Francis, Hamacher Ford and Fulkerson [1958, 1962]
and Tufekci [1984] and Tufekci [ 1984] Halpern [1979]
Federgruen and Groenevelt [1986] Federgruen and Groenevelt [ 1986 ] Halpern and Outerbridge [1977]
Ford and Fulkerson [1958, 1962] Ford and Fulkerson [1958, 1962] Hartman [ 19781
Kang [19781 Gale [1959] Jarvis and Ratliff [ 1982]
Maxwell and Wilson [ 1981 ] Halpern [ 1979] Minieka [1973, 1974]
Minieka [ 1973 ] Jarvis and Ratliff [19821 Orlin [ 19831
Orlin [1983] Minieka [1973, 1974l Tsui [1978]
Orlin [1983] Wilkinson [1971. 1973]
Wilkinson [1971, 1973]

Dynamic shortest Aronson and Aronofsky [ 1984, 1987] Aronson and Aronofsky [ 1984, 1987 ] Aronson and Aronofsky [ 1984, 1987 ]
path problems: Bean, Lohmann and Smith [1983] Bean, Lohmann and Smith [1983] Bean, Lohmann and Smith [19831 ,-a
Chand and Sethi [1982] Chand and Sethi [19821 Chand and Sethi [1982]
Cooke and Halsey [1966] Cooke and Halsey [ 1966 ] Cooke and Halsey [ 1966]
Halpern and Priess [1974] Dreyfus [ 1969] Dreyfus [1969]
HiUier and Lieberman [ 1987 ] Halpern and Priess [1976] Halpern and Priess [ 19741
Kibby and Potts [19691 ~V
Kibby and Potts [1969] Kibby and Potts [ 1969]
Phillips, Ravindran and Solberg [1976] Saksena and Kumar [ 1966 ] Saksena and Kumar [ 1966 ]
Saksena and Kumar [ 1966] Sethi and Chand [ 1979] Sethi and Chand [1979}
Sethi and Chand [1979] ZangwiU [ 1987b] WaddeU [1983]
Vemuganti, Oblak and Aggarwal [1989] Zawack and Thompson [ 1987 ] Zangwill [ 1987b]
Waddell [ 1983] Zawack and Thompson [1987]
Wagner [ 19751
ZangwiU [1987b]
Zawaek and Thompson [ 1987 ]
taO
',D
 Table 1 (continued)

Topic Models Theoretical results Algorithms/Implementations

Dynamic Aronson and Chen[ 1985] Aronson and Chen [1985, 1986, 1989b] Aronson and Chen [1986, 1989a]
transshipment Aronson, Morton and Thompson [1984] Aronson, Morton and Thompson [1984] Aronson, Morton and Thompson [1984]
problems: Aronson and Thompson [ 1984] Aronson and Thompson [ 1984 ] Aronson and Thompson [1984]
Bean, Birge and Smith [1987] Bean, Birge and Smith [1987] Bean, Birge and Smith [1987]
Bielli, Calicchio, Micoletti Bookbinder and Sethi [1980] Bookbinder and Sethi [1980]
RicciardeUi [1982] Chen[ 1985] Chen [1985] ,~-
Bookbinder and Sethi [ 1980] Erickson, Monma and Veinott [ 1987 ] Erickson, Monma and Veinott [1987]
Bowman [1956] Glickman and Sherali [ 1985 ] Florez [1986]
Chen [1985] Posner and Szwarc [ 1983] Glickman and Sherali [ 1985 ] .~
Crainic, Ferland and Rousseau [ 1984 ] Szwarc and Posner [ 1984] Hamacher [1989]
Cuimet [1972] White [1972] Klingman and Mote [1982]
Elam and Klingman [1982] White and Bomberault [ 1969 ] Monma and Segal [1982] ,~
Erickson, Monma and Veinott [1987] Zawack and Thompson [1987] Posner and Szwarc [1983]
Ermol'ev, Krivets and Petukhov [1976] Szwarc and Posner [1984] ~.
Feeney [1957] White [1972]
Fernandes Grain and White and Bomberault [1969]
Figliatti de Sinay [1986] Zawack and Thomoson [ 1987 ] E"
Florez [1986] t~
Gaimon [1986]
Glickman and Sherali [ 1985 ]
Glover, Jones, Karney, Klingman
and Mote [1979]
Glover and Klingman [1977, 1978]
Glover, Klingman and McMillan [ 1977 ]
Gurel and Winbigler [ 1967 ]
Hein [1975, 1978]
Herren [1973, 1977]
Hu and Prager [1959]
Klingman and Mote [1982]
Klingman, Randolph and Fuller [ 1976 ]
Mendiratta [ 1981 ]
 Mendiratta [ 1982]
Monma and Segal [1982]
Quimet [1972]
Perevezentsev [ 1974 ]
Posner and Szwarc [1983]
Potts [1970]
Shan [1985]
Srinivasan [ 1974 ]
Szwarc and Posner [1984]
White [1972]
White and Bomberault [ 1969]
Zawack and Thompson [1987]

Continuous Anderson, Nash and Phflpott[1982] Anderson, Nash and Philpott [1982] Anderson, Nash and Philpott [1982]
network Anderson and Phflpott[1984] Anderson and Philpott [1984] Anderson and Philpott [1984]
programming: Lan~ey [1973] Langley [1973] Langley [1973 ]
Phflpott[1985] Philpott [1985] Philpott [ 1985 ]

Dynamic multi- Aderohunmu [1986] Aderohunmu [1986] Aderohunmu [ 1986] ~-

commodity Aderohunmu and Aderohunmu and Aderohunmu and
models: Aronson [1984, 1985] Aronson [1987, 1988] Aronson [1985, 1987, 1988]
Alien [1985] Allen [1985] Allen [19851
Aronson [1986] Aronson [ 1986] Aronson [1986]
BieUi, Calicehio, Micoletti Elnidani [ 1986 ] Elnidani [1986]
and RicciardeUi [ 1982] Elnidani and Aronson [ 1986b1 Elnidani and Aronson [1986b]
Elnidani [1986] Helgason, Kennington and Wong [1982] Helgason, Kennington and Wong [1982]
Elnidani and Aronson [1986a] Zahorik, Thomas and Trigeiro [1984] Zahorik, Thomas and Trigeiro [1984]
Helgason, Kennington and Wong [1982]
Vemuganti, Oblak and Aggarwal [1989]
Zahorik, Thomas and Trigeiro [ 1984]

4~
 Table 1 (continued)

Topic Models Theoretical results Algorithm s/Implementations

4~
tO
Nonlinear cost, Beckman [1967] Adolphson and Aronson [ 1988 ] Adolphson and Aronson [ 1988]
generalized, Bently and Lambe [1980] Carey [1986, 1987, 1988] Carey [1988]
multicommodity, Bhaumik [1973] Carey and Srinivasan [1985] Choi, Hamacher and Tufekci [1988]
side constraints, Carey [1987, 1988] Choi, Hamacher and Tufekci [1988] D'Ans and Gazis [ 1976]
integer, and/or Carey and Srinivasan [1982,1985, 1989] D'Ans and Gazis [1976] Erickson, Monma and Veinott [ 1987 ]
stochastic Chaxnes and Cooper [ 1961 ] Erickson, Monma and Veinott 11987] Escudero [ 1986]
dynamic network- Choi, Hamacher and Tufekci [1988] Escudero [ 1985, 1986] Farvolden [ 1989] %,
based models: Crum [ 1976 ] Farvolden [ 1989 ] Fong and Srinivasan [1981,1986]
Crum and Dye [19811 Fong and Srinivasan [ 1981,1986 ] Frantzeskasis and PowelJ [1988] ~-
Crum, Klingman and Tavis [1979, 1983a, Frantzeskasis and Powell [ 1988 ] Gorenstein, Poley and White [19711
1983b] Haghani [ 1986] Haghani [1986]
Crum, Klingman and Tavis [1979, 1983] Haghani and Daskin [ 1986] Haghani and Daskin [1986] :~
D'Ans and Gazis [1976] Hamacher and Tufekci [ 1987 ] Hamacher and Tufekci [1987] r.o
Dantzig [1963] Jordan [1982] Klein, Luss and Smith [1987]
Decision Systems Associates [ 1978a,b] Jordan and Turnquist [1983] Konno [1988]
Erickson, Monma and Veinott [ 1987 } Kornhauser and Adamidou [ 1986 ] Kornhauser and Adamidou [1986]
Escudero [1985, 1986] Konno [1988] Luss and Smith [1988]
Evans [1975] Merchant [ 1974] Merchant [ 1974 ] ,~
Farvolden [ 1989] Merchant and Nemhauser [ 1978a,b[ Merchant and Nemhauser [1978a, 1978b]
Fong and Srinivasan [ 1981, 1986 ] Nagurney and Aronson [1988, 1989] Mulvey and Zenios [ 1987 ] ~"
Farina and Glover [ 19801 Powell [ 1986,1987,1988] Nagurney and Aronson [1988, 1989] e~'~
Glover and Martinson [1982] Powell and Cape [1988] Nguyen and Stone [1987] ~'
Glover, Glover, Lorenzo Powell, Sheffi and Thiriez [1984] Powell [1986, 1987,1988] ~-,
and McMillan [ 1982] Rao and McGinnis [ 1983] Powell and Sheffi [ 1989] ~"
Glover, Glover and Martin son [1984] Sandbothe [ 1985 ]
Powell, Sheffi and Thiriez [1984]
Glover, Hultz, Klingman Sandbothe and Thompson [1989] Rao and McGinnis [ 1983 ]
and Stutz [ 1978b] Steinberg and Napier [ 1980] Rosenthal [1981 ]
Glover, McMillan and Taylor [1977] Thompson and Sandbothe [ 1985 ] Sandbothe [ 1985 ]
Gorenstein, Poley and White [ 1971 ] Thompson and Zawack [1985/86] Sandbothe and Thompson [ 1989 ]
Haghani [ 1986] Tomlin [ 1988] Smith [1979]
Haghani and Daskin [ 1966 ] Turnquist [ 19861 Thompson and Sandbothe [ 1985]
Hamacher and Tufekci [ 1987 } Turnquist and Jordan [1982] Tomlin [1988]
Ikura, Gross and Hall [ 1986] Wagner and Whitin [ 1958 ] Wagner and Whitin [1958]
Jordan [1982] ZangwiU [1966, 1968, 1969, 1985, Zangwill [1966, 1968, 1969, 1985, 1987a]
Jordan and Turnquist [19831 1987a, 1987b]
Zemanian [1983a, 1983b]
Kiln [1972]
Klein, Luss and Smith [ 1987]
Klingman, Mote and Phillips [ 19881
Klingman, Phillips et al.
[1986, 1987a, 1987b]
Konno [1988]
Kornhauser and Adamidou [ 1986 ]
Luss and Smith [1987]
McBride, O'Leary and Widmeyer [1988]
Merchant [1974]
Merchant and Nemhauser [1978a, 1978b]
Mulvey [1984a, 1984b]
Mulvey and Zenios [ 1985 ]
Nagurney and Aronson [1987, 1988, 1989]
Orlin [1984]
Powell [1986, 1987,1988]
Powell, Sheffi, Nickerson, Butterbaugh
and Atherton [ 19881
Powell and Sheffi [1989]
Powell, Sheffi and Thiriez [ 1984 ]
Rao and McGinnis [1983] r
Robillard [1974]
Rosenthal [1981]
Smith [1979]
Steinberg and Napier [ 1980]
Thompson and Zawack [1985/86]
Tomlin [ 1988]
Turnquist [1986]
Turnquist and Jordan [ 1982]
Wagner [1975]
Wagner and Whitin [1958]
Zang-will [1966, 1968, 1969, 1985,
1987a, 1987b]
Zemanian [1983a, 1983b] 4~
%0
 4~
4~

Table 1 (continued)

Topic Models Theoretical results Algorithms/Implementations

Multi-index Aronson [1986] Aronson [ 1986] Aronson [1986]

assignment Balas and Landweer [1983] Balas and Landweer [ 1983 ] Balas and Landweer [1983]
problems: Balas and Saltzman [ 1988,1989[ Balas and Saltzman [1988, 1989] Balas and Saltzman [ 1988, 1989 ]
Carey [1980] Carey [1980] Carey [1980]
Charnes, Cooper and Stedry [ 1969] Corban [1964, 1966] Elnidani [1986]
Corban [1964, 1966] Elnidani [ 1986 ] Elnidani and Aronson [ 1989a]
Elnidani [ 1986] Elnidani and Aronson [1989a, 1989b] Evans [1981]
Elnidani and Aronson [ 1989c] Evans [1981] Frieze and Yadegar [ 1981 ]
Evans [1981] Frieze [1974, 1983] Haley [1962, 1963]
Frieze [ 1974] Gilbert and Hofstra {1988] Leue [1972]
Frieze and Yadegar [1981] Haley 11962, 1963, 1965] Oblak and Vemuganti [ 1989 ]
Gilbert and Hofstra [1988] Leue [19721 Pierskalla [1967a, 1967b, 1968]
Gotlieb [1962] Moravek and Vlach [1967] Schell [ 1955 ]
Gunawardane [ 1982] Oblak and Vemuganti [ 1989] Gilbert and Hofstra [1988]
Haley [1962, 1963] Pierskalla [1967b, 1968] Shamma [1971]
Oblak and Vemuganti [ 1989 ] Schell [ 1955 ] Vlach [1967]
Pierskalla [1967b, 19681 Shamma [ 1971 ]
ScheU [1955 ]
Shamma [1971]
Williams and Haley [1959]
 Table 2
References arranged by application areas

Production/distribution systems Railway/freight systems Personnel planning/scheduling

Aderohunmu [ 1986] Baker [19771 Aderohunmu [ 1986 ]

Aderohunmu and Aronson [1985, 1987,1988] Bartlet [1957] Aderohunmu and Aronson [1987]
Aronson [ 1986 ] Cooke and Halsey [1966] Aronson [ 1986]
Aronson and Chen [ 1985 ] Cralnic, Ferland and Rousseau [1984] Balas and Saltzman [1988, 1989]
Aronson, Morton and Thompson [ 1984] Cuimet [ 1972] Charnes and Cooper [ 1961 ]
Bowman [1956] Decision Systems Associates [ 1978a,b] Charnes, Cooper and Stedry [ 1969 ]
Charnes and Cooper [19611 Dejax and Crainic [ 1987 ] Dantzig [ 1963 ]
Chert [1985] Dreyfus [19691 Elnidani [ 1986]
Decision Systems Associates [1978a, 1978b] Ermol'ev et al. [1976] Elnidani and Aronson [ 1989c]
Elnidani [1986] Farvolden [ 1989] Evans [1981]
Elnidani and Aronson [ 1989a,b,c] Frantzeskasis and Powell [ 1988] Frieze and Yadegar [ 1981 ]
Erickson, Monma and Veinott [ 1987 ] Feeney [1957] Gilbert and Hofstra [1988]
Evans [1975] Fernandes Grain and Gotlieb [ 1962]
Federgruen and Groenevelt [ 1986] Figliatti de Sinay [ 1986] Gunawardane [ 1982 ]
Ford and Fulkerson [1958, 1962] Florez [1986] Haley [1962, 1963]
Gaimon [1986] Ford and Fulkerson [1958, 1962] Orlin [1983, 1984]
Gilbert and Hofstra [1988] Glickman and Sherali [ 1985 ] Pierskalla [1967a, 1967b, 1968]
Glover, Jones, Karney, Klingman and Gorenstein, Poley and White [ 1971 ] Schell [1955]
Mote [1979] Gurel and Winbigler [ 1967] Thompson and Zawack [1985/86]
Glover and Klingman [ 1977 ] Haghani [ 1986] Wagner [ 1975 ]
Glover, Klingman and McMillan [1977] Haghani and Daskin [19861 Williams and Haley [1959]
Helgason, Kennington and Wong [1982] Halpern [1979] 5,
Hu and Prager [1959] Halpern and Outerbridge [ 1977 ]
Klingman and Mote [1982] Halpern and Priess [ 1974 ]
Klingman, Mote and Phillips [1988] Hein [1975, 1978]
Klingman, Phillips et al. [1986, 1987a,b] Herren [1973, 1977]
Klingman, Randolph and Fuller [1976] Hughes and Powell [1988]
Konno [1988] Jordan [1982]
Jordan and Turnquist [ 1983 ] .Ix
Kibby and Potts [1969]
 Table 2 (continued)

Production/distribution systems Railway/freight systems Personnel planning/scheduling 4~

G',

Posner and Szwarc [1983] Kornhauser [ 1985, 1989]

Ramsey and Rardin [1983] Kornhauser and Adamidou [ 1986]
Rao and McGinnis [1983] Mendiratta [ 1981]
Rosenthal [1981] Mendiratta and Turnquist [1982]
Sandbothe [ 1985 ] Minieka [1973, 1974]
Sandbothe and Thomspn [1989] Orlin [1983]
Steinberg and Napier [ 1980] Ouimet [1972]
Szwarc and Posner [ 1984 ] Perevezentsev [ 1974] .m
Thompson and Sandbothe [1985] Ports [1970]
Thompson and Zawack [1985/86] Powell [ 1986, 1987, 1988]
Wagner and Whitin [ 1958] PoweU and Cape [ 1988]
Wilkinson [1971, 1973] PoweU and Sheffi [ 1989]
Zahorik, Thomas and Trigeiro [1984] PoweU, Sheffi, Nickerson, Butterbaugh
Zangwill [1966, 1968, 1969, 1985, 1987a,b] and Atherton [ 1988]
Powell, Sheffi and Thiriez [1984]
Saksena and Kumar [ 1966 ]
Shah [1985]
Turnquist [ 1986]
Turnquist and Jordan [ 1982]
White [1972]
White and Bomberault [1969]
Wilkinson [1971, 1973]

Communication systems Material handling systems Equipment replacement

Hajek and Ogler [1984] Ford and Fulkerson [1958, 19621 Aronson and Aronofsky [ 1984, 1987 ]
Halpern [ 1979] Halpern [ 1979] Bean, Lohmann and Smith [1985]
Halpern and Outerbridge [ 1977 ] Halpern and Outerbridge [1977] Chand and Sethi [ 1982]
Klessig [1974] Hartman [ 1978 ] Hillier and Lieberman [1987]
Masson and Jordan [ 1972] Kang [1978] Phillips, Ravindran and Solberg [1976]
McCallum [1977] Maxwell and Wilson [1981] Sethi and Chand [1979]
Monma and Segal [1982] Tsui [1978] Vemuganti, Oblak and Aggarwal [ 1989 ]
Smith [ 1979] Wilkinson [1971, 1973] Waddell [ 1983 ]
Yaged [1971, 1973, 1975] Wagner [ 1975 ]
Zadeh [1973, 1974]
Traffic systems Evacuation systems Economic planning

Beckman [ 1967] Allen [1985] Fong and Srinivasan [1981, 1986]

Bently and Lambe [1980] Chalmet, Francis and Saunders [1982] Merchant [1974]
Bielli, Calicchio, Micoletti Choi, Francis, Hamacher Merchant and Nemhauser [1978a, 1978b]
and Ricciardelli [ 1982 ] and Tufekci [ 1984] Nagurney [ 1988]
Carey [1980, 1986, 1987, 1988] Choi, Hamacher and Tufekci [ 1988] Nagurney and Aronson [1988, 1989]
Carey and Srinivasan [1982, 1985, 1989] Ford and Fulkerson [ 1958, 1962] Zemanian [ 1983a, 1983b]
D'Ans and Gazis [ 1976] Hamacher and Tufekci [ 19871
Ford and Fulkerson [1958, 1962] Jarvis and Ratliff [ 1982 ]
Glover, Glover, Lorenzo and McMillan [ 1982 ] Wilkinson [1971, 1973]
Mulvey [1984b]
Mulvey and Zenios [1987]
Robillard [1974]
Wilkinson [1971, 1973]
Zawack and Thompson [1987]

Cash flow models/systems Hydro systems Miscellaneous

,ez
Crum [1976] Bhaumik [ 1973 ] Kim [1972]
Crum and Dye [1981] Escudero [ 1985, 1986 ] Elam and Klingman [1982]
Crum, Klingman and Tavis [1977, 1983a, 1983b] Ikura, Gross and Hall [1986] Farina and Glover [1980]
Charnes and Cooper [ 1961 ] Rosenthal [ 1981 ] Glover, Glover and Martinson [ 1984]
Glover and Klingrnan [ 1977 ]
McBride, O'Leary and Widmeyer [ 1988]
Mulvey [1984a]
Mulvey and Zenios [ 1985 ]
Srinivasan [ 1974 ]
 -Ix
OO

Table 2 (continued)

Dynamic network-based decision support systems Surveys

Decision Systems Associates [ 1978a,b] Ali, Barnett, Farhangian, Kennington,

Farina and Glover [1980] McCarl, Patty, Shetty and Wong [1984]
Glover, Glover, Lorenzo and McMiUan [ 1982 ] Aronson [1988]
Glover, Glover and Martinson [1984] Aronson and Thompson [1984]
Glover, Jones, Karney, Klingrnan and Mote [1979] Assad [1981, 1987]
Glover, McMillan and Taylor [ 1977 ] Baker [1977]
l-Iein [1975, 1978] Bhaskharan, Chand and Sethi [1986]
Herren [1973, 1977] Bhaskharan and Sethi [ 1987 ]
Ikura, Gross and Hall [1986] Bookbinder and Sethi [ 1980]
Klingman, Phillips et al. [1986, 1987a,b] Bradley [1975]
Klingman, Mote and Phillips [1988] Charnes, Karney, Klingman, Stutz
Klingrnan, Randolph and Fuller [1976] and Glover [ 1975 ]
McBride, O'Leary and Widmeyer [1988] Dejax and Crainic [ 1987]
Powell and Sheffi [ 1989] Gilbert and Hofstra [ 1988]
Powell, Sheffi, Nickerson, Butterbaugh Glover, Hultz and Klingman [1978a, 1979]
and Atherton [1988] Glover, Hultz, Klingrnan and Stutz [1978b]
Tomlin [1988] Glover and Klingman [1975a, 1976, 1977,
1978, 1981a]
Golden and Magnanti [ 1977]
Kennington [ 1978 ]
Kornhauser [ 1989]
Powell [1988]
Rogers, Plante, Wong and Evans [ 1988]
Zenios [ 1989]
 J.E. Aronson, Survey of dynamic network flows 49

References

Aderohunmu, R.S., The solution of multiperiod network models with bundle constraints by
aggregation, Doctoral Dissertation, Department of Operations Reseach and Engineering Manage-
ment, School of Engineering and Applied Sciences, Southern Methodist University, Dallas, TX
(August, 1986).
Aderohunmu, R.S. and J.E. Aronson, Computational results of problems applying aggregation of
multiperiod network models for production planning, presented at the Joint National TIMS/
ORSA Meeting, Atlanta, GA (November 1985).
Aderohunmu, R.S. and J.E. Aronson, The solution of multiperiod network models with bundle
constraints by aggregation, Working Paper No. 87-244, Department of Management Sciences
and Information Technology, College of Business Administration, The University of Georgia,
Athens, GA (December 1987).
Aderohunmu, R.S. and J.E. Aronson, A forward network-based implementation of an algorithm
for solving multiperiod network problems (with bundle constraints by aggregation), Working
Paper (forthcoming), College of Business Adminstration, The University of Georgia, Athens,
GA, presented at TIMS/ORSA, Washington, DC (April 1988).
Adolphson, D. and J.E. Aronson, A forward generalized network algorithm, Private Communica-
tion of Research in Progress, Department of Management Sciences and Information Tech-
nology, College of Business Administration, The University of Georgia, Athens, GA (1988).
Ali, A.I., D. Barnett, K. Farhangian, J.L. Kennington, B. McCarl, B. Patty, B. Shetty and P. Wong,
Multicommodity network problems: Applications and computations, liE Trans. 16(1984)
127-134.
Ali, A.I., R.V. Helgason, J.L. Kennington and H. Lail, Primal simplex network codes: State of the
art implementation technology, Networks 8(1978)315 - 339.
Ali, A.I., R.V. Helgason, J.L. Kennington and H. Lall, Computation comparison among three
multicommodity network flow algorithms, Oper. Res. 28(1980)995 -1000.
Ali, A.I., J.L. Kennington and B. Shetty, The equal flow problem, Eur. J. Oper. Res. 36(1988)
107-115.
Aft, A.I., R. Padman and H. Thiagarajan, Dual algorithms for pure network problems, Oper. Res.
37, 1(1989)159-171.
Allen, E.P., Using two sequences of pure network problems to solve the multicommodity network
flow problem, Doctoral Dissertation, Department of Operations Research and Engineering
Management, Southern Methodist University, Dallas, TX (May 1985).
ARC: Analysis Research and Computation, Inc., PNET User's Guide, Austin, TX 78765 (1974).
Anderson, E.J., Basic solutions and a 'simplex' method for a class of continuous linear programs,
in: Optimization Techniques, Proc. 9th IFIP Conf. on Optimization Techniques, Warsaw,
Poland (Springer-Verlag, Berlin, 1979) pp. 26-35.
Anderson, E.J., P. Nash and A.B. Philpott, A class of continuous network flow problems, Math.
Oper. Res. 7, 4(1982)501 -514.
Anderson, E.J. and A.B. Philpott, Duality and an algorithm for a class of continuous transporta-
tion problems, Math. Oper. Res. 9, 2(1984)222-231.
Aronson, J.E., Forward linear programming, Doctoral Dissertation, Graduate School of Industrial
Administration, Carnegie-MeUon University, Pittsburgh, PA (April 1980a).
Aronson, J.E., The forward simplex method: Computational results, Working Paper No. 62-79-80,
Graduate School of Industrial Administration, Carnegie-MeUon University, Pittsburgh, PA
(April 1980b).
Aronson, J.E., The multiperiod assignment problem: A multicommodity network flow model and
specialized branch and bound algorithm, Eur. J. Oper. Res. 23(1986)367 - 381.
Aronson, J .E., Networks tutorial, in: Proc. 1988 Annual Meeting of the Decision Sciences Institute,
Las Vegas, NV (November 1988).
50 J.E. Aronson, Sulwey of dynamic network flows

Aronson, J.E. and J.S. Aronofsky, Network generating models for equipment replacement with
changing technology, Research in Progress, presented at the Joint National ORSA/TIMS Meeting,
Dallas, TX (November 1984).
Aronson, J.E. and J.S. Aronofsky, The integration of model generation and network optimization
in a decision support environment, Technical Report 83-OR-5, Department of Operations
Research and Engineering Management, Southern Methodist University, Dallas, TX (revised
April 1987).
Aronson, J.E., R.S. Barr, R.V. Helgason, J.L. Kennington, A. Loh and H. Zaki, The projective
transformation algorithm by Karmarkar: A computational experiment with assignment problems,
Technical Report 85-OR-3, Department of Operations Research and Engineering Management,
Southern Methodist University, Dallas, TX (revised August 1985), presented at the TIMS
XXVII International Meeting, Gold Coast City, Queensland, Australia (July 1986).
Aronson, J.E. and B.D. Chen, Decision horizon results for an infinite horizon, production planning
network model, Technical Report 85-OR-11, Department of Operations Research and
Engineering Management, Southern Methodist University, Dallas, TX (September 1985).
Aronson, J.E. and B.D. Chen, A forward network simplex algorithm for solving multiperiod
network flow problems, Naval Research Logistics Quarterly 33, 3(1986)445-467.
Aronson, J.E. and B.D. Chen, A primary/secondary memory implementation of a forward network
simplex algorithm for multiperiod network flow problems, Computers and OR (1989a), forth-
coming.
Aronson,l.E. and B.D. Chen, A computational study of empirical decision horizons in infinite
horizon, multiperiod network flow models, Working Paper No. 89-275, Department of Manage-
ment Sciences and Information Technology, College of Business Administration, The University
of Georgia, Athens, GA (revised January 1989b).
Aronson, J.E., T.E. Morton and G.L. Thompson, A forward algorithm and planning horizon
procedure for the production smoothing problem without inventory, Eur. J. Oper. Res. 15,
3(1984)348- 365.
Aronson, J.E., T.E. Morton and G.L. Thompson, A forward simplex method for staircase linear
programs, Management Science 31, 6(1985)664-679.
Aronson, J.E. and R.E. Steuer, An interactive procedure for solving multicriteria network flow
problems, Working Paper in preparation, Department of Management Sciences and Information
Technology, College of Business Administration, The University of Georgia, Athens, GA,
presented at the CORS/TIMS/ORSA Joint National Meeting, Vancouver, BC, Canada (May
1989).
Aronson, J.E. and G.L. Thompson, A survey on forward methods in mathematical programming,
Large Scale Systems 7(1984)1 - 1 6 .
Aronson, J.E. and G.L. Thompson, The solution of multiperiod personnel planning problems by
the forward simplex method, Large Scale Systems 9(1985)129- 139,
Assad, A.A., Analytical models in rail transportation: An annotated bibliography, INFOR 19,
1(1981)59-80.
Assad, A.A., Multicommodity network flows: A survey, Networks 8, 1(1987)37 - 9 2 .
Baker, K.R., Scheduling a full-time workforce to meet cyclic staffing requirements, Management
Science 20(1974) 1561 - 1568.
Baker, K.R., Workforce allocation in cyclical scheduling problems, Oper. Res. Quart. 27(1976)155.
Baker, K.R., Workforce allocation in cyclical scheduling problems, Oper. Res. Quart. 27(1976)
155 - 167.
Baker, L., Overview of computer based models applicable to freight container utilization, Report
prepared for U.S. Department of Transportation, NTIS, Springfield, VA (1977).
Balas, E. and P. Landweer, Traffic assignment in communication satellites, Oper. Res. Lett. 2(1983)
141-147.
 J.E. Aronson, Survey o f dynamic network flows 51

Balas, E. and M.J. Saltzman, An algorithm for the three-index assignment problem, Management
Science Research Report 550, Graduate School of Industrial Administration, Carnegie-Mellon
University, Pittsburgh, PA (September 1988).
Balas, E . a n d M.J. Saltzman, Facets of the three-index assignment polytope, Discr. Appl. Math.
(1989), forthcoming.
Barnes, E.R., A variation on Karmarkar's algorithm for solving linear programming problems,
Math. Progr. 36, 2(1986)174 - 182.
Barr, R.S., Network optimization on microcomputers, Department of Operations Research and
and Engineering Management, Southern Methodist University, Dallas, TX. Presented at the
ORSA/TIMS Joint National Meeting, Boston, MA (April 1985).
Barr, R.S., J.J. Elam, F. Glover and D. Klingman, A network alternating path basis algorithm for
transshipment problems, in: Extrernal Methods and Systems Analysis (Springcr-Verlag, NY,
1980).
Barr, R.S., K. Farhangian and J.L. Kennington, Networks with side constraints: An LU factoriza-
tion update, Ann. Soc. Logistics Engineers 1, 1(1986),68- 85.
Barr, R.S., F. Glover and D. Klingman, An improved version of the out-of-kilter method and a
comparative study of computer codes, Math. Progr. 7, 1 ( 1 9 7 4 ) 6 0 - 8 6 .
Barr, R.S., F. Glover and D. Klingman, The alternating path basis algorithm for assignment prob-
lems, Math. Progr. 13, 1(1977) 1 - 13.
Barr, R.S., F. Glover and D. Klingman, The generalized alternating path basis algorithm for trans-
portation problems, Eur. J. Oper. Res. 2(1978) 137 - 144.
Barr, R.S., F. Glover and D. Klingman, Enhancements to spanning tree labeling procedures for
network optimization, INFOR 17, 1 ( 1 9 7 9 ) 1 6 - 33.
Bartholdi III, J.J., J.B. Orlin and H.D. Ratliff, Cyclic scheduling via integer programs with ckcular
ones, Oper. Res. 28, 5(1980) 1074 - 1085.
Bartholdi, J.J. and H.D. Ratliff, Unnetworks with applications to idle time scheduling, Manage-
ment Science 2 4 ( 1 9 7 8 ) 8 5 0 - 858.
Bartlett, T.E., An algorithm for the minimum number of transport units to maintain a fixed
schedule, Naval Research Logistics Quarterly 4(1957)207 - 2 2 0 .
Bean, J.C., J.R. Birge and R.L. Smith, Aggregation in dynamic programming, Oper. Res. 35,
2(1987)215 - 2 2 0 .
Bean, J.C., J.R. Lohmann and R.L. Smith, Dynamic infinite horizon replacement economy decision
model, Engin. Econ. 30, 2(1985)99 - 120.
Beck, P, L. Lasdon and M. Engquist, A reduced gradient algorithm for nonlinear network fl0w
problems, ACM Trans. on Mathematical Software 9 ( 1 9 8 3 ) 5 7 - 70.
Beckman, M.J., On the theory of traffic flows in networks, Traffic Quarterly 21 (1967) 109 - 116.
Bently, R.W. and T.A. Lambe, Assignment of traffic to a network of signalized city streets, Trans-
portation Research 14A(1980)57 - 65.
Berlin, G.N., The use of directed routes for assessing escape potential, National Fire Protection
Association, Boston, MA (1979).
Bertsekas, D.P., A new algorithm for the assignment problem, Math. Progr. 2 1 ( 1 9 8 1 ) 1 5 3 - 1 7 1 .
Bertsekas, D.P., A unified framework for primal-dual methods in minimum cost network flow
problems, Math. Progr. 32, 2(1985) 125 - 145.
Bertsekas, D.P., Distributed relaxation methods for linear network flow problems, in: Proe. 25th
IEEE Conf. on Decision and Control, Athen, Greece (1986) pp. 2101 - 2106.
Bertsekas, D.P. and J. Eckstein, Distributed asynchronous relaxation methods for linear network
flow problems, in: Proe. IFAS-87, Munich, West Germany (Pergamon Press, Oxford, UK,
1987).
Bertsekas, D.P. and J. Eckstein, Dual coordinate step methods for linear network flow problems,
Math. Progr. 42, 2 ( 1 9 8 8 ) 2 0 3 - 243.
52 J.E. Aronson, Survey of dynamic network flows

Bertsekas, D.P. and D. E1 Baz, Distributed asynchronous relaxation methods for convex network
flow problems, SIAM Journal on Control and Optimization 2 5 ( 1 9 8 7 ) 7 4 - 8 5 .
Bertsekas, D.P., P. Hosein and P. Tseng, Relaxation methods for network flow problems with
convex arc costs, SIAM Journal on Control and Optimization 25(1987) 1 2 1 9 - 1243.
Bertsekas, D.P. and P. Tseng, Relaxation methods for minimum cost ordinary and generalized
network flow problems, Oper. Res. 36, 1 ( 1 9 8 8 ) 9 3 - 1 1 4 .
Bertsekas, D.P. and J.N. Tsitsiklis, Paralleland Dzst~buted Algorithms (Prentice-Hall, Englewood
Cliffs, N J, 1988).
Bhaskaran, S., S. Chand and S.P. Sethi, Decision and forecast horizon procedures in operations
management, Private Communication of Research in Progress (1986).
Bhaskaran, S. and S.P. Sethi, Decision and forecast horizons in a stochastic environment: A survey,
Optimal Control Applications and Methods 8, 3(1987) 201 - 217
Bhaumik, G., Optimum operating policies of a water distribution system with losses, Unpublished
Dissertation, The University of Texas at Austin, Austin, TX (August 1973).
Bielli, M., G. Callcchio, B. Micoletti and S. RicciardeUi, The air traffic flow control problem as
an application of network theory, Computers and Operations Research 9, 4(1982)265 - 278.
Bixby, R. and W. Cunningham, Converting linear programs to network programs, Math. Oper. Res.
5(1980)321 - 3 5 7 .
Bixby, R.E. and R. Fourer, Finding embedded network rows in linear programs. 1: Extraction
heuristics, Management Science 34, 3(1988)342 - 3 7 6 .
Bookbinder, J.H. and S.P. Sethi, The dynamic transportation problem: A survey, Naval Research
Logistics Quarterly 27, 3(1980)447 - 4 5 2 .
Bowman, E.H., Production scheduling by the transportation method of linear programming,
Oper. Res. 4(1956) 100 - 103.
Bradley, G.H., Survey of determinsitic networks, AIIE Trans. 7, 3 ( 1 9 7 5 ) 2 2 2 - 234.
Bradley, G.H., G.G. Brown and G.W. Graves, Design and implementation of large-scale primal
transshipment algorithms, Management Science 24(1977) 1 - 3 4 .
Brown, G.G., R.D. McBride and R.K. Wood, Extracting embedded generalized networks from
linear programming problems, Math. Progr. 32, 1(1985) 11 - 31
Brown, G.G. and W.G. Wright, Automatic identification of embedded network rows in large-scale
optimization models, Math. Progr. 29, 1(1984)41 - 5 6 .
Carey, M., A convex dynamic assignment model, Working Paper, School of Urban and Public
Affairs, Carnegie-Mellon University, Pittsburgh, PA (1980).
Carey, M., A constraint qualification for a dynamic traffic assignment model, Transportation
Science 20, 1 ( 1 9 8 6 ) 5 5 - 5 8 .
Carey, M., Optimal tim e-varying flows on congested networks, Oper. Res. 35, 1(1987 ) 58 - 69.
Carey, M., An approach to modeling dynamic network flows on congested networks, Working
Paper, School of Urban and Public Affairs, Carnegie-Mellon University, Pittsburgh, PA (1988).
Carey, M. and A. Srinivasan, Modeling network flows with time-varying demand, Report to the
Urban Mass Transportation Administration under Contract No. PA-06-0063, School of Urban
and Public Affairs, Carnegie-Mellon University, Pittsburgh, PA (1982).
Carey, M. and A. Srinivasan, Externalities, optimal tolls and flow controls on congested networks
with time-varying flows, School of Urban and Public Affairs, Carnegie-Mellon University,
Pittsburgh, PA (July 1985).
Carey, M. and A. Srinivasan, Congested network flox~s: Time-varying demands and start-time
policies, Eur. J. Oper. Rcs. (1989), forthcoming.
Chalmet, L.G., R.L. Francis and P.B. Saunders, Network models for building evacuation, Manage-
ment Science 28, 1 ( 1 9 8 2 ) 8 6 - 105.
Chand, S. and T.E. Morton, A perfect planning horizon procedure for a determinstic cash flow
balance, Management Science 28, 6(1982)652 - 6 6 9 .
 J.E. A ronson, Survey of dynamic network flows 53

Chand, S. and T.E. Morton, Minimal forecast horizon procedures for dynamic lot size models,
Naval Research Logistics Quarterly 33, 1(1986) 111 - 122.
Chand, S. and S.P. Sethi, Planning horizon procedures for machine replacement models with
several possiblc replacement alternatives, Naval Research Logistics Quarterly 29, 3(1982)
483-493.
Charnes, A. and W.W. Cooper, ManagementModels and Industrial Applications of Linear Program-
mh~g, Vols. I and II (Wiley, New York, 1961).
Charnes, A., W.W. Cooper and A. Stedry, Multi-dimensional and dynamic assignment models
with some remarks on organization design, Management Science 15, 8(1969)B-365-B-375.
Charnes, A., D. Karncy, D. Klingman, J. Stutz and F. Glover, Past, present, and future of develop-
ment, computational efficiency, and practical use of large scale transportation and trans-
shipment computer codes, Computers and OR 2(1975)71-81.
Chen, B.D., Forward network programming, Doctoral Dissertation, Department of Operations
Research and Engineering Management, Southern Methodist University, Dallas, TX (May 1985).
Chen, C.J. and M. Engquist, A primal simplex approach to pure processing networks, Management
Science 32, 12(1986)1582 - 1598.
Chen, R.J. and R.R. Meyer, Parallel optimization for traffic assignment, Math. Progr. 42, 2(1988)
327 - 3 4 5 .
Choi, W., R.L. Francis, H.W. Hamacher and S. Tufekci, Network models of building evacuation
problems with flow-dependent exit capacities, Operational Research (Proc. lOth Int. Conf.
on Operations Research, Washington, DC, August 1984), ed. J.P. Brans (North-Holland,
Amsterdam, 1984) pp. 1047 - 1059.
Choi, W., H.W. Hamacher and S. Tufekci, Modeling of building evacuation problems by network
flows with side constraints, Eur. J. Oper. Res. 35(1988)98-110.
Chvzltal, V., Linear Programming (Freeman, New York, 1983).
Clark, R.H. and R.R. Meyer, Multiprocessor algorithms for generalized network flows, Computer
Sciences Technical Report No. 739, Computer Sciences Department, University of Wisconsin,
Madison, Wl (1987).
Cooke, K.L. and E. Halsey, The shortest route through a network with time-dependent inter-
nodal transit times, J. Math. Anal. and Appl. 14(1966)493 - 4 9 8 .
Corban, A., A multidimensional transportation problem, Revue Roumaine des Mathematiques
Pures et Appliquees 9(1964)721 - 7 3 5 .
Corban, A., On a three-dimensional transportation problem, Revue Roumaine des Mathematiques
Pures et Appliquees 11(1966)57 - 75.
Cralnic, T., J.A. Ferland and J.M. Rousseau, A tactical planning model for rail freight transporta-
tion, Transportation Science 18, 2(1984) 165 - 184.
Crum, R.L., Cash management in the multinational firm: A constrained generalized network
approach, Working Paper, University of Florida, Gainesville, FL (1976).
Crum, R.L. and D.J. Dye, A network model of insurance company cash flow management, Math.
Progr. Study, Vol. 15 (1981) 8 6 - 101.
Crum, R.L., D. Klingman and L.Tavis, Implementation of large-scale financial planning models:
Solution, efficient transformations, J. Financial and Quantitative Analysis (1979)137 - 152.
Crum, R.L., D. Klingnnan and L. Tavis, An operational approach to integrated working capital
planning, J. Economics and Business 35(1983a)343- 378.
Crum, R.L., D.D. Klingman and L.A. Tavis, Strategic management of multinational companies:
Network-based planning systems, in: Applications of Management Science, ed. R.L. Shultz,
Vol. 3 (JAI Press, Inc., Greenwich, CT, 1983b) pp. 177-201.
Cuimet, G.P., Empty freight car distribution, Master's Thesis, Queen's University, Kingston,
Ontario, Canada (April 1972).
Cunningham, W.H., A network simplex method, Math. Progr. 11(1976)105 - 116.
54 J.E. Aronson, Survey of dynamic network flows

Curminghara, W.H., Theoretical properties of the network simplex method, Math. Oper. Res.
4, 2(1979)196-208.
Dafermos, S., An extended traffic assignment model with application to two-way traffic, Trans-
portation Science 5(1971)366-389.
Dafermos, S., The traffic assignment problem for multiclass-user transportation networks, Trans-
portation Science 6(1972)73-87.
Dafermos, S., Traffic equilibrium and variational inequalities, Transportation Science 14(1980)
42-54.
Dafermos, S., Relaxation algorithms for the general asymmetric traffic equilibrium problem,
Transportation Science 14(1982a)231 - 2 4 0 .
Dafermos, S., The general multimodal network equilibrium problem with elastic demands,
Networks 12(1982b)57 - 72.
Dafermos, S. and A. Nagurney, Sensitivity analysis for the general spatial economic equilibrium
problem, Oper. Res. 32,5(1984a)1069 - 1086.
Dafermos, S. and A. Nagurney, Sensitivity analysis for the asymmetric network equilibrium prob-
lem, Math. Progr. 28, 2(1984b)174 - 184.
Dafermos, S. and F. Sparrow, The traffic assignment problem for a general network, Journal of
Research of the National Bureau of Standards 75B(1969)91 - 117.
D'Ans, G.C. and D.C. Gazis, Optimal control of oversaturated store and forward transportation
networks, Transportation Science 10(1976)1 - 19.
Dantzig, G.B., LinearProgrammingand Extensions (Princeton, N J, 1963).
Dantzig, G.B., W. Blattner and M.R. Rao, Finding a cycle in a graph with minimum cost to times
ratio with application to a ship routing problem, in: Theory of Graphs, ed. P. Rosenthiehl
(Dunod, Paris; Gordon and Breach, New York, 1967) pp. 7 7 - 8 4 .
Dantzig, G.B. and D.R. Fulkerson, Minimizing the number of tankers to meet a fixed schedule,
Naval Research Logistics Quarterly 1(1954)217 - 222.
Dantzig, G.B. and R.M. Van Slyke, Generalized upper bounded techniques for linear program-
ruing- 1, Proc. IBM Scientific Computing Symposium Combination Problems (March 1 6 - 1 8 ,
1964) pp. 2 4 9 - 2 6 1 ; also see: Generalized upper bounded techniques, Journal of Computer
System Science 1(1967)213-226.
Decision Systems Associates, Inc., Implementation studies via simulation of the computer-based
model for freight car distribution, Report prepared for U.S. Department of Transportation,
FRA, DSAI, Rockville, MD (1978a).
Decision Systems Associates, Inc., Computer-based model for optimal freight car distribution,
FRA Contract DPT-FR-65140, U.S. Department of Transportation, DSAI, Rockville, MD
(1978b).
Dejax, P.J. and T.G. Crainic, A review of empty flows and fleet management models in freight
transportation, Transportation Science 21,4(1987)227 - 2 4 7 .
Dijkstra, E.W., A note on two problems in connexion with graphs, Numerische Mathematik 1
(1959)269-271.
Drews, W.P., A simplex-like algorithm for continuous-time linear optimal control problems, in:
Optimization Methods for Resource Allocation (Proc. NATO Conf., Elsinore, Denmark)
(English University Press, London, 1974) pp. 3 0 9 - 322.
Dreyfus, S.E., An appraisal of some shortest-path algorithms, Oper. Res. 17(1969)395 - 4 1 2 .
Dreyfus, S.E. and R.A. Wagner, The Steiner problem in graphs, Networks 1 (1971) 195 - 2 0 7 .
Elam, J.J., F. Glover and D. Klingman, A strongly convergent primal simplex algorithm for general-
ized networks, Math. Oper. Res. 4, i ( 1 9 7 9 ) 3 9 - 5 9 .
Elam, J.J. and D. Klingman, NETGEN-II: A system for generating network-based mathematical
programming test problems, in: EvaluatingMathematical Programming Techniques, Lecture
Notes in Economics and Mathematical Systems 199, ed. J.M. Mulvey (Springer-Verlag, New
York, 1982).
 J.E. Aronson, Survey Of dynamic network flows 55

Elnidani, M.A., The multicommodity, multiperiod assignment problem, Doctoral Dissertation,

Department of Operations Research and Engineering Management, Southern Methodist
University, Dallas, TX (May 1986).
Elnidani, M.A. and J.E. Aronson, The multicommodity, multiperiod assignment problem I: A
specialized branch and bound algorithm, Working Paper 89-276, Department of Management
Sciences and Information Technology, College of Business Administration, The University of
Georgia, Athens, GA (presented at the TIMS XXVII International Meeting, Gold Coast City,
Queensland, Australia, July 1986) (1989a).
Elnidani, M.A. and J.E. Aronson, The multicommodity, multiperiod assignment problem II:
Theoretical results, Working Paper 89-277, Department of Management Sciences and Informa-
tion Technology, College of Business Administration, The University of Georgia, Athens, GA
(presented at the ORSA/TIMS Joint National Meeting, Denver, CO, October 1988) (1989b).
Einidani, M.A. and J.E. Aronson, The multicommodity, multiperiod assignment problem III:
Variations for facility location and personnel planning, Working Paper 89-278, Department
of Management Sciences and Information Technology, College of Business Administration,
The University of Georgia, Athens, GA (presented at the Joint National ORSA/TIMS Meeting,
Los Angeles, CA, April 1986) (1989c).
Erickson, R.E., C.L. Monma and A.F. Veinott, Jr., Send-and-split method for minimum-concave-
cost network flows, Math. Oper. Res. 12, 4(1987)634-664.
Ermol'ev, Y.M., T.A. Krivets and V.S. Petukhov, Planning of shipping empty seaborne containers,
Cybernetics 12(1976)664.
Escudero, L.F., On nonlinear replicated networks, Questiio 9(1985)55- 74.
Escudero, L.F., Performance evaluation of independent superbasic sets on nonlinear replicated
networks, Eur. J. Oper. Res. 23, 3(1986)343- 355.
Evans, J.R., A single-commodity transformation for certain multicommodity networks, Oper. Res.
26,4(1975)673-681.
Evans, J.R., The multicommodity assignment problem: A network aggregation heuristic, Computers
and Mathematics with Applications 7, 2(1981 ) 187 - 194.
Farina, R. and F. Glover, Optimal development and aUocation of Colorado's energy resources
over the coming decade, in: Energy Issues in Colorado's Future (Colorado Energy Research
Institute, 1980) pp. 161 - 199.
Farvolden, J.M., A primal partitioning solution for capacitated multicommodity network flow
problems, Doctoral Dissertation, Department of Civil Engineering and Operations Research,
Princeton University, Princeton, NJ (1989).
Federgruen, A. and H..Groenevelt, Preemptive scheduling of uniform machines by ordinary net-
work flow techniques, Management Science 32, 3(1986)341 -349.
Feeney, G., Controlling the distribution of empty freight cars, in: Proc. lOth National Meeting
(Operations Research Society of America, 1957).
Fernandes Grain, M.T. and M.C. Fogliatti de Sinay, Optimal distribution of empty railroad cars,
in: Proc. 1st Int. Congress in France of Industrial Engineeringand Management, Ecole Centrale
de Paris, Paris, France (1986) pp. 21-26.
Florez, H., Empty-container repositioning and leasing: An optimization model, Doctoral Disserta-
tion, Polytechnic Institute of New York, New York, NY (1986).
Fong, C.O. and V. Srinivasan, The multiregion dynamic capacity expansion problem, Parts I and II,
Oper. Res. 29, 4(1981)787- 816.
Fong, C.O. and V. Srinivasan, The multiregion dynamic capacity expansion problem: An improved
heuristic, Management Science 32, 9(1986)1140 - 1152.
Ford, Jr., L.R. and D.R. Fulkerson, Maximal flow through a network, Can. J. Math. 8(1956)399.
Ford, Jr., L.R. and D.R. Fulkerson, Maximal flow through a network, Can. J. Math. 8(1956)
399 -404.
56 J.E. Aronson, Survey of dynamic network flows

Ford, Jr., L.R. and D.R. Fulkerson, Constructing maximal dynamic flows from static flows, Oper.
Res. 6(1958)419-433.
Ford, Jr., L.R. and D.R. Fulkerson, Flows in Networks (Princeton University Press, Princeton, N J,
1962).
Fourer, R., A simplex algorithm for piecewise-linear programming I: Derivation and proof, Math.
Progr. 33, 2(1985)204-233.
Fourer, R., A simplex algorithm for piecewise-linear programming III: Computational analysis and
applications, Technical Report 86-03, Department of Industrial Engineering and Management
Sciences, Northwestern University, Evanston, IL (1986).
Fourer, R., A simplex algorithm for piecewise-linear programming lI: Finiteness, feasibility and
degeneracy, Math. Progr. 41,3(1988) 281 - 316.
Frantzeskasis, L.F. and W.B. Powell, Development and evaluation of a successive linear approxima-
tion procedure for stochastic dynamic networks, Report SOR-88-13, Department of Civil
Engineering and Operations Research, Princeton University, Princeton, NJ (1988).
Frieze, A.M., A bilinear programming formulation of the 3-dimensional assignment problem,
Math. Progr. 7, 3(1974)376 - 379.
Frieze, A.M., Complexity of a 3-dimensional assignment problem, Eur. J. Oper. Res. 13(1983)
161 - 1 6 4 .
Frieze, A.M. and J. Yadegax, An algorithm for solving 3-dimensional assignment problems with
application to scheduling a teaching practice, 1. Oper. Res. Soc. 32(1981)989 - 9 9 5 .
Fulkerson, D.R., An out-of-kilter method for minimal-cost flow problems, J. Society of Industrial
and Applied Mathematics 9, 1(1961)18-27.
Galmon, C., Optimal inventory, backlogging and machine loading in a serial, multi-stage, multi-
period production environment, Int. J. Prod. Res. 24, 3(1986)647 - 6 6 2 .
Gale, D., A theorem on flows in network, Pacific J. Math. 7(1957) 1073 - 1086.
Gale, D., Transient flows in networks, Michigan Mathematical Journal 6(1959)59- 63.
Garfinkel, R.S. and G.L. Nemhauser, Integer Programming (Wiley, New York, 1972).
Gass, S.l., Linear Programming: Methods and Applications, 4th ed. (McGraw-Hill, New York,
1975).
Gay, D.M., A variant of Karmarkar's linear programming algorithm for problems in the standard
form, Math. Progr. 37, 1(1987)81-90.
Gilbert, K.C. and R.B. Hofstra, Multidimensional assignment problems, Decision Sciences 19,
2(1988)306-321.
Gill, P.E., W. Murray, M.A. Saunders, J.A. Tomlin and M.H. Wright, On projected Newton barrier
methods for linear programming and an equivalence to Karmarkar's projective method, Math.
Progr. 36, 2(1986)183-209.
Glickman, T.S. and H.D. Sherali, Large-scale network distribution of pooled empty freight cars
over time, with limited substitution and equitable benefits, Transportation Research 19(1985)
85 - 9 4 .
Glover, F., Creating network structure in Lp's, in: Computer-Assisted Analysis and Model Simpli-
j~cation, ed. Greenberg and Maybee (Academic Press, New York, 1981) pp. 361 - 3 6 8 .
Glover, F., R. Glover, J. Lorenzo and C. McMillan, The passenger-mix problem in the scheduled
airlines, Interfaces 12, 3(1982)73 - 80.
Glover, F., R. Glover, and F. Martinson, A netform system for resource planning in the U.S.
Bureau of Land Management, J. Oper. Res. Soc. 35(1984)605 - 6 1 6 .
Glover, F., J. Hultz and D. Klingman, Improved computer-based planning techniques, Part I,
Interfaces 8,4(1978a) 16 - 25.
Glover, F., J. Hultz and D. Klingman, Improved computer-based planning techniques, Part II,
Interfaces 9, 4(1979)12 - 2 0 .
 J.E. Aronson, Survey o f dynarnic network flows 57

Glover, F., J. Hultz, D. Klingrnan and J. Stutz, Generalized networks: A fundamental computer-
based planning tool, Management Science 24.12(1978b)1209- 1220.
Glover, F., G. Jones, D. Karney, D. Klingman and J. Mote, An integrated production, distribution,
and inventory planning system, Interfaces 9, 5(1979)21 - 3 5 .
Glover, F., D. Karney and D. Klingman, Double-pricing dual and feasible start algorithms for tl~
capacitated transportation (distribution) problem, CCS Research Report 105, Center for
Cybernetic Studies, The University of Texas at Austin, Austin, TX (1973).
Glover, F., D. Karney and D. Klingman, Implementation and computational comparisons of
primal, dual, and primal-dual computer codes for minimum cost network flow problems,
Networks 4, 3 (1974) 191 - 212.
Glover, F., D. Karney, D. Klingman and A. Napier, A computational study on start procedures,
basis change criteria, and solution algorithms for transportation problems, Management Science
20, 5(1974)793 - 813.
Glover, F. and D. Ktingman, New advances in the solution of large-scale network and network-
related problems, in: Colloquia Matheman'ca Societatis, ed. A. Prekopa (North-Holland,
Amsterdam, 1975a) pp. 2 1 0 - 2 2 3 .
Glover, F. and D. Ktingman, Improved labeling of L.P. bases in networks, Omega 23, 2(1975b)
220-221.
Glover, F. and D. Klingman, A practitioner's guide to the state of large-scale network and network-
related problems, AFIPS-Conference Proceedings, Vol. 45, Montvale, NJ (1976) pp. 945 - 9 5 0 .
Glover, F. and D. Klingman, Network applications in industry and government, AIIE Trans.
9,4(1977)363-376.
Glover, F. and D. Klingman, Modeling and solving network problems, in: Design andIrnplementa-
tion of Optl"mizatT"onSoftware, ed. H. Greenberg (Sijthoff and Noordhoff, Alphen aan den
Rijn, 1978).
Glover, F. and D. Klingman, Mathematical optimization - a successful tool for logistics problems,
in: Operan'on Research '81, ed. J.P. Brans (IFORS - North-Holland, Amsterdam, 1981a)
pp. 453 - 4 6 2 .
Glover, F. and D. Klingrnan, The simplex SON algorithm for LP/embedded network problems,
in: Network Models and Associated Applications, ed. D. Klingman and J.M. Mulvey, Mathe-
matical Programming Study 15 (North-Holland, Amsterdam, 1981b) pp. 1 4 8 - 1 7 6 .
Glover, F. and D. Klingman, Basis exchange characterizations for the simplex SON algorithm for
LP/embedded network problems, Mathematical Programming Study 24(1985)141 - 157.
Glover, F. and D. Klingman, Layering strategies for creating exploitable structure in linear and
integer programs, Math. Progr. 40, 2(1988)165 - 182.
Glover, F., D. Klingman and C. McMillan, The netform concept: A more effective model form
and solution procedure for large-scale nonlinear problems, Proc. ACM '77 (Association for
Computing Machinery Conference, October 1977).
Glover, F., D. Klingman and J. Stutz, Extensions of the augmented predecessor method to
generalized network problems, Transportation Science 7(1973)377- 384.
Glover, F., D. Klingman and J. Stutz, Augmented threaded index method, INFOR 12, 3(1974)
293-298.
Glover, F. and F. Martinson, Linear programming/netform model for vegetation allocation, in:
Ecological Modeling (Elsevier, Amsterdam, 1982).
Glover, F., C. McMillan and P. Taylor, A computer-based decision support system for air terminal
overload management, Proc. lOth Annual Internat~'onal Conference on Systems Sciences,
Honolulu, HI (1977).
Golden, B.L. and T.L. Magnanti, Deterministic network optimization: A bibliography, Networks
7(1977)149- 183.
58 J.E. Aronson, Survey of dynamic network flows

Gorenstein, S., S. Poley and W.W. White, On tile scheduling of the railroad freight operations,
IBM Data Processing Report, Technical Report 320-2999, IBM, Philadelphia Scientific Center,
Philadelphia, PA (1971).
Gotlieb, C.C., The construction of class-teacher timetables, Proc. IFIP Congress (1962) pp. 73 - 77.
Gunawardane, G., A three-dimensional assignment problem, presented at the ORSA/TIMS Joint
National Meeting, San Diego, CA (October 1982).
Gurel, M. and D.M. Winbigler, Container provisioning for an airline network, presented at the 32nd
National Meeting, ORSA, Chicago, IL (November 1967).
Hajek, B. and R.G. Ogler, Optimal dynamic routing in communications networks with continuous
traffic, Networks 14(1984)457-487.
Haghani, A.E., A combined model of train routing, makeup and empty distribution, Doctoral
Dissertation, Northwestern University, Evanston, IL (1986).
Haghani, A.E. and M.S. Daskin, A combined model of train routing, makeup and empty car distri-
bution, Technical Report, Northwestern University, Evanston, IL (t986).
Haley, K.B., The solid transportation problem, Oper. Res. 10(1962)448-463.
Haley, K.B., The multi-index problem, Oper. Res. 11(1963)368- 379.
Haley, K.B., The existence of a solution to the multi-index problem, Oper. Res. Quart. 16(1965)
471-474.
Halpern, J., A generalized dynamic network flows problem, Networks 9, 2(1979) 133 - 167.
Halpern, J. and R.A.M. Outerbridge, PFLOW: A computer program for the generalized P-period
maximal dynamic flows problem, Working paper WP- 11-77, Faculty of Business, University of
Calgary, Alberta, Canada (August 1977).
Halpern, J. and 1. Priess, Shortest path with time constraints on movement and parking, Networks
4(1974)241 - 2 5 3 .
Hamachcr. H.. EJOR software exchange program, Eur. J. Oper. Res. 38(1989)119.
Hamacher, H.W. and S. Tufekci, On the use of lexicographic-minimum cost flows in evacuation
modeling, Naval Research Logistics 34(1987)487-503.
Hartman, D., User's Manual: The interactive DYNAFLO program, A-level, Working Paper No. 6,
Manufacturing Flow Research Project, Department of Industrial and Operations Engineering,
The University of Michigan, Ann Arbor, MI (December 1978).
Hein, O., Naherungsverfahren ffir das @berschuss-Bedarf' Problem, Angewandte Informatik 17
(1975)324-326.
Hein, O., Naherungsverfahren fiir die Leerwagenverteilung, Eisenbahntechnische Rundschau 27
(1978)73-77.
Helgason, R.V. and J.L. Kennington, NETFLO program documentation, Technical Report IEOR
76011, Department of Industrial Engineering and Operations Research, Southern Methodist
University, Dallas, TX (September 1976).
Helgason, R.V. and J.L. Kennington, An efficient procedure for implementing a dual-simplex
network flow algorithm, AIIE Trans. 9, 1(1977)63- 68.
Helgason, R.V., J.L. Kennington and P. Wong, An application of network programming for
National Forest Planning, Technical Report 81006, Department of Operations Research and
Engineering Management, Southern Methodist University, Dallas, TX (February 1982).
Herren, H., The distribution of empty wagons by means of computer: Analytical model of the
Swiss Federal Railways, Rail Int. 4(1973) 1005 - 1010.
Herren, H., Computer-controlled empty wagon distribution on the SBB, Rail Int. 8(1977)25 - 32.
Hillier, F.S. and G.J. Liebcrman, Introduction to Operations Research, 4th ed. (Holden-Day,
San Vrancisco, CA, 1987).
Ho, J.K. and E. Loute, Computational experience with advanced implementation of decomposition
algorithms, Math. Progr. 27, 3(1983)283-290.
Hu, T.C. and W. Prager, Network analysis of production systems, Naval Research Logistics Quarterly
6(1959)17-23.
 J.E. Aronson, Survey of dynamic network flows 59

Hughes, R.E. and W.B. Powell, Mitigating and effects in the dynamic vehicle allocation model,
Management Science 34, 7 ( 1 9 8 8 ) 8 5 9 - 8 7 9 .
Hultz, J., Algorithms and applications for generalized networks, Unpublished Dissertation, The
University of Texas at Austin, Austin, TX (1976).
IBM: International Business Machines Corporation, IBM Mathematical Programming System
Extended/370, Mixed Integer Programming/370 (MIP/370) Program Reference Manual, White
Plains, NY (November 1975).
IBM:International Business Machines Corporation, IBM IVlathematical Programming System
Extended/370 Program Reference Manual, White Plains, NY (December 1979).
Ikura, Y., G. Gross and G.S. Hall, PGandE's state-of-the-art scheduling tool for hydro systems,
Interfaces 16, 1(1986)65 - 82.
Jarvis, J.J. and H.D. Ratliff, Some equivalent objectives for dynamic network flow problems,
Management Science 28, 1 ( 1 9 8 2 ) 1 0 6 - 109.
Jensen, P. and J.W. Barnes, Network Flow Programming (Wiley, New York, 1980).
Johnson, E., Flows in networks, in: Handbook of OperatT"onsResearch, ed. S.J. Moder and S.E.
Ehnaghraby (van Nostrand Rhcinhold, New York, 19791 pp. 1 8 3 - 206.
Jordan, W.C., The impact of uncertain demand and supply on empty rail car distribution, Doctoral
Dissertation, Cornell University, Ithaca, NY (1982).
Jordan, W.C. and M.A. Turnquist, A stochastic dynamic model for railroad car distribution, Trans-
portation Science 17(1983)123-145.
Kang, M.K., Dynamic network flow models of conveyor systems, Working Paper No. 5, Manu-
facturing Flow Research Project, Department of Industrial and Operations Engineering, The
University of Michigan, Ann Arbor, MI (March 1978).
Karmarkar, N., A new polynomial-time algorithm for linear programming, Combinatorics 4(1984a)
373 - 395.
Karmarkar, N., A new polynomial-time algorithm for linear programming, Proc. 16th Annual
ACM Symposium on the Theory of Comt~aT"ng(1984b) pp. 302 - 311.
Karney, D. and D. Klingman, Implementation and computational study on an in-core out-of-core
primal network code, Oper. Res. 24, 6(1976)1056 - 1077.
Kennington, J.L., A survey of linear cost multicommodity network flows, Oper. Res. 26, 2(1978)
209-236.
Kennington, J.L. and R.V. Helgason, Algorithms for Network Programming (Wiley, New York,
1980).
Kennington, J.L. and R. Muthukrishnan, An asynchronous algorithm to solve generalized network
problems, presented at the ORSA/TIMS Joint National Meeting, Denver, CO (November 1988).
Kibby, F.R. and F.B. Potts, The minimum route problem with turn penalties and prohibitions,
Transportation Research 3 ( 1 9 6 9 ) 3 9 7 - 408.
Kim, Y., An optimal computational approach to the analysis of a generalized network of copper
refining process, presented at the Joint National ORSA/TIMS/AIIE Conference, Atlantic
City, NJ (1972).
Klein, R.S., H. Luss and D.R. Smith, Multiperiod resource allocation: A lexicographic minimax
approach, presented at the ORSA/TIMS Joint National Meeting, St. Louis, MO (1987).
Klessig, R.W., An algorithm for nonlinear ,multicommodity flow problems, Networks 4(1974)
343-355.
Klingman, D. and J. Mote, A multi-period production, distribution, and inventory planning model,
Advances in Management Studies 1,2(1982) 56 - 76.
Klingman, D., J. Mote and N.V. Phillips, A logistics planning system at W.R. Grace, Oper. Res.
36,6(1988)811-822.
60 ZE. Aronson, Survey o f dynamic network flows

Klingman, D., A. Napier and J. Stutz, NETGEN: A program for generating large scale capacitated
assignment, transportation, and minimum cost flow network problems, Management Science
20, 5(1974) 814 -821.
Klingman, D., N.V. Phillips, D. Steiger, R. Wixth, R. Padman and R. Krishnan, An optimization-
based integrated short-term refined petroleum product planning system, Management Science
33,7(1987a)813-830.
KlJngman, D., N.V. Phillips, D. Steiger and W. Young, The successful deployment of management
science throughout Citgo Petroleum Corporation, Interfaces 17, 1(1987b)4- 25.
Klingman, D., N.V. Phillips, D. Steiger, R. Wirth and W. Young, The challenges and success factors
in implementing an integrated products planning system for Citgo, Interfaces 16, 3(1986) 1 - 19.
Klingman,D., P. Randolph and S. Fuller, A cotton ginning problem, Oper. Res. 24, 4(1976)700- 718.
Konno, H., Minimum concave cost production systems: A further generalization of multi-echelon
model, Math. Progr. 41,2(1988)185 -194.
Kornhauser, A.L., A very large transportation network interactive computer graphic information
system and problem solver, Working Paper, Department of Civil Engineering, Transportation
Program, Princeton University, Princeton, NJ, presented at the TIMS/ORSA Joint National
Meeting, Boston, MA (May 1985).
Kornhauser, A.L., Modeling for optimal real time railroad plant management, presented at the
CORS/ORSA/TIMS Joint National Meeting, Vancouver, BC, Canada (May 1989).
Kornhauser, A.L. and E.A. Adamidou, User and system optimal formulation and solution to the
shared rail fleet management problem, presented at the TIMS/ORSA Joint National Meeting,
Miami, FL (1986).
Langley, R., Continuous and integer generalized flow problems, Unpublished Dissertation, Georgia
Institute of Technology, Atlanta, GA (1973).
Lawler, E.L., Combinatorial Optimization, Networks and Matroids (Holt, Rinehart and Winston,
New York, 1976).
Leue, O., Methoden zur L6sung dreidimensionaler Zuordnungsprobleme, Angewandte Informatik
(April 1972)154-162.
Levin, A., Some fleet routing and scheduling problems for air transportation systems, Report
FTL-R68-5, Massachusetts Institute of Technology, Cambridge, MA (1969).
Lundin, R.A. and T.E. Morton, Planning horizons for the dynamic lot size model: Zabel vs.
protective procedures and computational results, Oper. Res. 23, 4(1975 )711 - 734.
Luss, H. and D.R. Smith, Multiperiod allocation of limited resources: A minimax approach, Naval
Research Logistics Quarterly 35(1988)493-501.
Mangasarian, O.L. and R.R. Meyer, eds., Parallel Methods in Mathematical Programming, Mathe-
matical Programming 42, 2(1988), special issue.
Marsten, R.E., The design of the XMP linear programming library, Transactions on Mathematical
Software 7,4(1981).
Masson, G.M. and B.W. Jordan, Jr., Generalized multi-stage connection networks, Networks
2(1972)191-209.
Maxwell, W.L. and R.C. Wilson, Dynamic network flow modelling of fixed path material handling
systems, AIIE Trans. 13, 1(1981)12-21.
McBride, R.D., D.E. O'Leary and G.R. Widmeyer, A system for supporting cash management
decisions, Working Paper, Graduate School of Business Administration, University of Southern
California, Los Angeles, CA (1988).
McCaUum, C.J., A generalized upper bounding approach to a communications network planning
problem, Networks 7(1977) 1 - 23.
Mendiratta, V.B., A dynamic optimization model of the empty car distribution process, Doctoral
Dissertation, Department of Civil Engineering, Northwestern University, Evanston, IL (1981).
 J.E. Aronson, Survey of dynamic network flows 61

Mendiratta, V.B. and M.A. Turnquist, A model for the management of empty freight cars, Trans-
portation Research Rec. 838(1982)50-55.
Merchant, D.K., A study of dynamic traffic assignment and control, Doctoral Dissertation, Cornell
University, Ithaca, NY (1974).
Merchant, D.K. and G.L. Nemhauser, A model and an algorithm for the dynamic traffic assignment
problem, Transportation Science 12, 3(1978a)183-199.
Merchant, D.K. and G.L. Nemhauser, Optimality conditions for a dynamic traffic assignment
model, Transportation Science 12, 3(1978b)201 -207.
Meyer, R.R., Parallel algorithms for large-scale nonlinear networks, presented at the SIAM Con-
ference on Optimization, Houston, TX (May 1987).
Meyer, R.R. and S.A. Zenios, eds., Parallel Optt'rnization on Novel Computer Architectures, Ann.
Oper. Res. 14(1988) (J.C. Baltzer, Basel, 1988).
Miller, D., J. Pekny and G.L. Thompson, Solution of large, dense transportation problems using
a parallel primal algorithm, Oper. Res. Lett. (1989), forthcoming.
Miller, L.W., Using linear programming to derive planning horizons for a production smoothing
problem, Management Science 25, 12(1979)1232- 1244.
Minieka, E., Maximal, lexicographic and dynamic network flows, Oper. Res. 12, 2(1973)517 -527.
Minieka, E., Dynamic network flows with arc changes, Networks 4(1974)255 -265.
Monma, C.L. and M. Segal, A primal algorithm for finding minimum-cost flows in capacitated
networks with applications, The Bell System Technical Journal 61,6(1982)949 -968.
Moravek, J. and M. Vlach, On the necessary conditions for the existence of the solution of the
multi-index transportation problem, Oper. Res. 15(1967)542-545.
Morton, T.E., Universal planning horizons for generalized convex production scheduling, Oper.
Res. 26,6(1978)1046 - 1057.
Morton, T.E., Forward algorithms for forward thinking managers, in: Applications of Management
Science, ed. R.L. Schultz, Vol. 1 (JAI Press, Inc., 1981).
Mulvey, J.M., A network portfolio approach for cash flow management, J. Cash Management
(1984a) 4 6 - 4 8 .
Mulvey, J.M., A network planning model for the U.S. Air Traffic System, Working Paper EES-83-8,
Department of Civil Engineering, Princeton University, Princeton, NJ (1984b).
Mulvey,J.M. and S.A. Zenois, Solving large scale generalized networks, J. Information and
Optimization Science 6(1985)95- 112.
Mulvey, J.M. and S.A. Zenios, Real-time operational planning for the U.S. air traffic system,
Applied Numerical Mathematics 3(1987)427-441.
Murphy, F.H. and A.L. Soyster, End effects in capacity expansion models with finite horizons,
Naval Research Logistics Quarterly 33, 3(1986)373 - 383.
Murtagh, B. and M. Saunders, MINOS User's Guide, Technical Report 77-9, Stanford Optimization
Laboratory, Department of Operations Research, Stanford University, Stanford, CA (February
1977).
Murtagh, B. and M. Saunders, MINOS]Augmented User's Manual, Technical Report SOL 80-14,
Stanford Optimization Laboratory, Department of Operations Research, Stanford University,
Stanford, CA (June 1980).
Nagurney, A. and D.S. Kim, Parallel vs. serial algorithms for large-scale multicommodity spatial
price equilibrium problems, International Journal of Supercomputer Applications (Spring
1989).
Nagurney, A. and J.E. Aronson, A general dynamic spatial price equilibrium model: Formulation,
solution and computational results, J. Comput. Appl. Math. 22(1988)339- 352.
Nagurney, A. and J.E. Aronson, A general dynamic spatial price network equilibrium model with
gains and losses, Networks (1989), forthcoming.
62 J.E. Aronson, Swwey o f dynamic network flows

Nemhauser, G.L. and L.A. Wolsey, hTteger and Combinatorial Optimization (Wiley, New York,
1988).
Nguyen, Q.C. and R.E. Stone, A multiperiod resource allocation problem with storable and substi-
tutable resottrccs, presented at the ORSA/TIMS Joint National Meeting, St. Louis, MO (1987).
Oblak, M. and R.R. Vemuganti, The multiperiod assignment problem with changeover constraints,
Working Paper, Merrick School of Business, University of Baltimore, Baltimore, MD, prcsented
at the CORS/TIMS/ORSA Joint National Meeting, Vancouver, BC, Canada (May 1989).
Olson, D.L., B. Shetty, M.A. Venkataramanan and I. Murthy, Network reoptimization procedures
for multiobjective network problems, Ann. Oper. Res. 20(1989), this volume.
Orlin, J.B., Quick optimal weekly scheduling with two consecutive days off, Technical Report
77-1, Department of Operations Research, Stanford University, Stanford, CA (1977).
Orlin, J.B., Maximum-throughput dynamic network flows, Math. Progr. 27, 2(1983)214- 231.
Orlin, J.B., Minimum convex cost dynamic network flows, Math. Oper. Res. 9, 2(1984)190- 207.
Ouimet, G.P., Empty freight car distribution, Masters Thesis, Queen's University, Kingston,
Ontario, Canada (1972).
Perevezentsev, E.N., Scheduling of containers shipments, in: Proc. Central Scientific-Research
Institute of the Maritime lqeet, No. 195 (Transport, Leningrad, USSR, 1974), in Russian.
Perold, A.F. Continuous linear programming, Doctoral Dissertation, Department of Operations
Research, Stanford University, Stanford, CA (1978).
Phillips, D. and A. Garcia-Diaz, Fundamentals of Network Analysis (Prentice-Hall, New York,
1981).
Phillips, D.T., A. Ravindran and J.J. Solberg, Operations Research, Pn'nciplesand Practice (Wiley,
New York, 1976).
Philpott, A.B., Network programming in continuous time with node storage, Engineering Depart-
ment, Cambridge University, Cambridge, UK (1985), Infinite Programming, Proc. of a
Symposium on Infinite Dimensional Linear Programming, ed. E. Anderson and A. Philpott
(1984).
Pierskalla, W.P., The tri-substitution method for the three-dimensional assignment problem, CORS
Journal 5(1967a)71-81.
Pierskalla, W.P., The multi-dimensional assignment and quadratic assignment problems, Technical
Memorandum No. 93, Case Western Reserve University, Operations Research Department,
School of Management, Cleveland, OH (September 1967b).
Pierskalla, W.P., The multi-dimensional assignment problem, Oper. Res. 15, 2(1968)422 -431.
Posner, M.E. and W. Szwarc, A transportation type aggregate production model with backordering,
Management Science 29, 2(1983)188 - 199.
Ports, R.B., Movement of empty containers within Australia, presented to the Operations Research
Society of Victoria, Melbourne, Australia (September 1970).
Powell, W.B., A stochastic model of the dynamic vehicle allocation problem, Transportation
Science 20, 2(1986) 117 - 129.
Powell, W.B., An operational planning model for the dynamic vehicle allocation problem with
uncertain demands, Transportation Research 21 B, 3(1987 )217 - 232.
Powell, W.B., A comparative review of alternative algorithms for the dynamic vehicle allocation
problem, in: Vehicle Routing: Methods and Studies, ed. B. Golden and A.A. Assad (North-
Holland, Amstcrdam, 1988) pp. 249- 291.
Powcll, W.B. and D.J. Cape, Sensitivity analysis of dynamic networks: An application to pricing
and load evaluation for truckload motor carriers, Report SOR-88-8, Department of Civil
Engineering and Operations Rcscarch, Princeton University, Princeton, NJ (1988).
Powell, W.B. and Y. Sheffi, Design and implementation of an interactive optimization system for
network design in the motor carrier industry, Oper. Rcs. 37, 1(1989)12- 29.
 J.E. Aronson, Survey o f dynamic network flows 63

Powell, W.B., Y. Sheffi, K.S. Nickerson, K. Butterbaugh and S. Atherton, Maximizing profits
for North American Van Lines' Truckload Division: A new framework for pricing and opera-
tions, Interfaces 18, 1(1988)21-41.
Powell, W.B., Y. Sheffi and S. Thiriez, The dynamic vehicle allocation problem with uncertain
demands, in: 9th Int. Syrup. on Transportation and Traffic Theory, ed. J. Volmuller and
R. Hamerslag (VNU Science Press, The Netherlands, 1984).
Premoli, A., Piecewise-linear programming: The compact (CPLP) algorithm, Math. Progr. 36,
2(1986)210-227.
Propoi, A.I. and V. Krivonozhko, The dynamic simplex method, RM-77-24, International Institute
for Applied Systems Analysis, Laxenburg, Austria (1977).
Ramsey, Jr., T.E. and R.R. Rardin, Heuristics for multistage production planning problems,
J. Oper. Res. Soc. 34, 1(1983)61-70.
Rao, V.V. and L.F. McGinnis, Optimal lot sizing in acyclic multiperiod production systems, liE
Trans. 15(1983)54-62.
Robillard, P., Multipath traffic assignment with dynamic input flows, Transportation Research
8(1974)567 -583.
Rogers, D.F., R.D. Plante, R.T. Wong and J.R. Evans, Aggregation techniques and methodology
in optimization, Working Paper QA-1988-I0, Department of Quantitative Analysis and
Information Systems, College of Business Administration, University of Cincinnati, Cincinnati,
OH (1988).
Rosenthal, R.E., A nonlinear network flow algorithm for maximization of benefits in a hydro-
electric power system, Oper. Res. 29, 4(1981)763-786.
Rosenthal, R.E., Representing inverses in pure network flow optimization, Eur. J. Oper. Res.
23, 3(1986)356 - 366.
Saksena, J.P. and S. Kumar, The routing problem with 'K' specified nodes, Oper. Res. 14(1966)
909 -913.
Sandbothe, R.A., Solving the capacitated lot size model, Doctoral Dissertation, Graduate School
of Industrial Administration, Carnegie-Mellon University, Pittsburgh, PA (November 1985).
Sandbothe, R.A. and G.L. Thompson, A forward algorithm for the capacitated lot size model
with stockouts, Oper. Res. (1989), forthcoming.
Schell, E., Distribution of a product by several properties, Directorate of Management Analysis,
Proc. 2nd Syrup. in Linear Programming, ed. H. Antosiewicz, 2, DCS/Comptroller H.Q., U.S.
Air Force, Washington, DC, 615-642 (January 1955).
Sethi, A.P., Algorithmic enhancements of the simplex method, Doctoral Dissertation, Graduate
School of Industrial Administration, Carnegie-Mellon University, Pittsburgh, PA (1983).
Sethi, A.P. and G.L. Thompson, The pivot and probe algorithm for solving a linear program,
Math. Progr. 29, 2(1984)219 -233.
Sethi, A.P. and G.L. Thompson, Solution of constrained generalized transportation problems
using the pivot-and-probe algorithm, Computers and OR 13(1986)1-9.
Sethi, A.P., G.L. Thompson and M.S. Hung, The pivot-and-probe algorithm and XMP, presented
at the TIMS/ORSA Joint National Meeting, Washington, DC (April 1988).
Sethi, S.P. and S. Chand, Planning horizon procedures for machine replacement models, Manage-
ment Science 25, 2(1979)140 - 151
Shamma, M.M., A generalized assignment problem, Doctoral Dissertation, Computer Science/
Operations Research Center, Southern Methodist University, Dallas, TX (March 1971).
Shan, Y., A dynamic multicommodity network flow model for real time optimal rail freight car
management, Doctoral Dissertation, Princeton University, Princeton, NJ (1985).
Shanno, D.F., Computing Karmarkar projections quickly, Math. Progr. 41, 1(1988)61 - 7 2 .
Shetty, B., The equal flow problem, Doctoral Dissertation, Department of Operations Research
and Engineering Management, Southern Methodist University, Dallas, TX (May 1985).
64 J.E. Aronson, Survey of dynamic network flows

Simmonard, M., LinearProgramming(Prentice-Hall, Englewood Cliffs, N J, 1966).

Smith, R.L., Deferral strategies for a dynamic communications network, Networks 9(1979)61 - 8 7 .
Srinivasan, V., A transshipment model for cash management decisions, Management Science
20, 10(1974)1350-1363.
Srinivasan, V. and G.L. Thompson, Accelerated algorithms for labeling and relabeling of trees,
with applications to distribution problems, Journal of tile Association for Computing
Machinery 19, 4(1972)712 - 7 2 6 .
Srinivasan, V. and G.L. Thompson, Benefit-cost analysis of coding techniques for the primal
transportation algorithm, Journal of the Association for Computing Machinery 20(1973)
194-213.
Stanley, J.D., A forward convex-simplex method with applications, Doctoral Dissertation, Graduate
School of Industrial administration, Carnegie-Mellon University, Pittsburgh, PA (April 1984).
Stanley, J.D., A forward convex-simplex method, Eur. J. Oper. Res. 29(1987)328 - 335.
Steinberg, E. and H.A. Napier, Optimal multi-level lot sizing for systems requirements planning,
Management Science 26, 12(1980)1258 - 1271.
Stone, R.E., An algorithm for solving network problems with side variables, Working paper, AT&T
Bell Laboratories, Holmdcl, NJ (Nov. 1988).
Szwaxc, W. and M.E. Posner, The tridiagonal transportation problem, Oper. Res. Lett. 3, 1(1984)
25-30.
Thompson, G.L. and R.A. Sandbothe, Bounds for the capacitated lot sized model: A transporta-
tion approach, presented at the Joint National ORSA/TIMS Meeting, Atlanta, GA (November
1985).
Thompson, G.L. and D.J. Zawack, A problem expanding parametric programming method for
solving the job shop scheduling problem, Ann. Oper. Res. 4(1985/1986)327 - 3 4 2 .
Tibrewala, R., D. Philippe and J. Browne, Optimal scheduling of two idle periods, Management
Science 19(1972)71 - 75.
Todd, M.J., Exploiting special structure in Karmarkar's linear programming algorithm, Math.
Progr. 41,1(1988)97 - 113.
Tomlin, J.A., Special ordered sets and an application to gas supply operations planning, Math.
Progr. 42, 1(1988)69-84.
Truemper, K., How to detect hidden networks and totally-unimodular subsections of linear
programs, presented at the TIMS/ORSA Joint National Meeting, Chicago, IL (April 1983).
Tseng, P., Relaxation methods for monotropic programming problems, Doctoral Dissertation,
Department of Electical Engineering and Computer Science, Operations Research Center,
Massachusetts Institute of Technology, Cambridge, MA (1986).
Tseng, P. and D.P. Bertsekas, Relaxation methods for linear programs, Math. Oper. Res. 12, 4
(1987a)569 - 5 9 6 .
Tseng, P. and D.P. Bertsekas, Relaxation methods for problems with strictly convex separable
costs and linear constraints, Math. Progr. 38, 3(1987b)303 - 321.
Tsui, L., DYNAFLO User's Manual, Working paper No. 7, Manufacturing Flow Research Project,
Department of Industrial and Operations Engineering, The University of Michigan, Ann Arbor,
MI 48109 (October 1978).
Turnquist, M.A., MOV-EM: A network optimization model for empty freight car distribution,
School of Civil and Environmental Engineering, CorneU University, Ithaca, NY (1986).
Turnquist, M.A. and W.C. Jordan, A computer-based method for railroad car distribution, Final
Report, DTRS5680-C-00013, U.S. Department of Transportation, Office of University Research
(1982).
Vajda, S., MathematicalProgramming (Addison-Wesley, Reading, MA, 1961) p. 147.
Veinott, Jr., A.F., Minimum concave-cost solution of Leontief substitution models of multi-
facility inventory systems, Oper. Res. 17(1969)262-291.
 J.E. Aronson, Survey of dynamic network flows 65

Veinott, Jr., A.F. and H.M. Wagner, Optimal capacity scheduling, I and II, Oper. Res. 10(1962)
518-546.
Vemuganti, R.R., M. Oblak and A. Aggarwal, Network models for fleet management, Decision
Sciences 20, 1 ( 1 9 8 9 ) 1 8 2 - 197.
Vlach, M., Branch and bound method for the three index assignment problem, Ekonomicko-
Matematicky Obzor (Czechoslovakia) 3(1967)181 - 1 9 1 .
Waddell, R., A model for equipment replacement decisions and policies, Interfaces 13, 4(1983)1.
Wagner, H.M., Principlesof Operatz'onsResearch, 2nd ed. (Prentice-HaU, N J, 1975).
Waddell, R., A model for equipment replacement decisions and policies, Interfaces 13,4(1983)1 - 7.
Wagner, H.M., Principles of Operations Research, 2nd ed. (Prentice-Hall, Englewood Cliffs, N J,
1975).
Wagner, H.M. and T.M. Whitin, Dynamic version of the economic lot size model, Management
Science 5 ( 1 9 5 8 ) 8 9 - 9 6 .
White, W.W., Dynamic transshipment network: An algorithm and its application to the distri-
bution of empty containers, Networks 2 ( 1 9 7 2 ) 2 1 1 - 2 3 6 .
White, W.W. and A.M. Bomberault, A network algorithm for empty freight ear allocations, IBM
Systems Journal 8, 2(1969)147 - 169.
Wilkinson, W.L., An algorithm for universal maximal dynamic flows in a network, Oper. Res. 19,
7(1971)1602-1612.
Wilkinson, W.L., Min/max bounds for dynamic network flows, Naval Research Logistics Quarterly
20, 3(1973)505 - 5 1 6 .
Williams, K.B. and K.B. Haley, A practical application of linear programming in the mining industry,
Oper. Res. Quart. 10, 3(1959)131 - 138.
Yaged, Jr., B., Minimum cost routing for static network models, Networks 1(1971)139 - 172.
Yaged, Jr., B., Minimum cost routing for dynamic network models, Networks 3 ( 1 9 7 3 ) 1 9 3 - 2 2 4 .
Yaged, Jr., B., Economies of scale, networks, and network cost elasticity, IEEE Trans. on Systems,
Man, and Cybernetics 5(1975)30 - 39.
Zadeh, N., On building minimum cost communications networks, Networks 3(1973)315 - 3 3 1 .
Zadeh, N., On building minimum cost communications networks over time, Networks 4(1974)
19-34.
Zahorik, A., L.J. Thomas and W. Trigeiro, Network programming models for production scheduling
in multi-stage, multi-item, capacitated systems, Management Science 30, 3(1984)308 - 325.
Zangwill, W.I., A deterministic multiperiod production scheduling model with backloggings,
Management Science 13(1966) 105 - 119.
Zangwill, W.I., Minimum concave cost flows in certain networks, Management Science 14, 7(1968)
429 - 4 5 0 .
Zangwill, W.I., A backlogging model and a multi-echelon model of a dynamic economic lot size
production system - a network approach, Management Science 15, 9 ( 1 9 6 9 ) 5 0 6 - 5 2 7 .
Zangwill, W.I., Set-up cost reduction in series facility production, Working paper, University of
Chicago, Chicago, IL (January 1985).
ZangwiU, W.I., Eliminating inventory in a series facility production system, Management Science
33, 9(1987a) 1 1 5 0 - 1164.
ZangwiU, W.I., From EOQ toward ZI, Management Science 33, 1 0 ( 1 9 8 7 b ) 1 2 0 9 - 1223.
Zawack, D.J. and G.L. Thompson, A dynamic space-time network flow model for city traffic
congestion, Transportation Science 21, 3 (1987) 153 - 161.
Zemanian, A.H., A dynamic marketing network with monopsonistic acquisition and perfectly
competitive disposition, IEEE Trans. on Circuits and Systems, CAS-30, 6 ( 1 9 8 3 a ) 3 8 2 - 387.
Zemanian, A.H., A dynamic marketing, storage and transportation system with perfect competition
in each of its markets, IMA J. Appl. Math. 31(1983b)51 - 7 8 .
66 J.E. Aronson, Survey of dynamic network flows

Zenios, S.A., Sequential and parallel algorithms for convex generalized network problems and
related applications, Doctoral Dissertation, Civil Engineering Department, Princeton University,
Princeton, NJ (May 1986).
Zenios, S.A., An annotated bibliography on parallel optimization, ORSA Journal on Computing
(1989), forthcoming.
Zenios, S.A. and R.A. Lasken, Nonlinear network optimization on a massively parallel connection
machine, Ann. Oper. Res. 14(1988)147 - 165.
Zenios, S.A. and J.M. Mulvey, Simulating a distributed synchronous relaxation method for convex
network problems, Working Paper, Department of Civil Engineering, Princeton University,
Princeton, NJ (January 1985).
Zenios, S.A. and J.M. Mulvey, Nonlinear network programming on vector supercomputers: A study
on the CRAY-XMP, Oper. Res. 34,5(1986)667 - 682.
Zenios, S.A. and J.M. Mulvey, A distributed algorithm for convex network optimization problems,
ParallelComputing6 (North-Holland, Amsterdam, 1988a) pp. 4 5 - 5 6 .
Zenios, S.A. and J.M. Mulvey, Vectorization and multitasking of nonlinear network programming
algorithms, Math. Progr. 42, 2(1988b)449 - 4 7 0 .
Zipkin, P., Bounds for aggregation nodes in network problems, Math. Prog. 19(1980)155 - 177~
Zipkin, P. and P. Raimer, An improved disaggregation method for transportation problems, Math.
Progr. 26, 2(1983)238 - 2 4 2 .