INDUSTRIAL ENGINEERING APPLICATIONS AND PRACTICE: USERS ENCYCLOPEDIA®
NETWORK FLOW PROBLEMS
The Origin of Theory of Network Flows
The picture below is an artist's rendering of the city of Köningsberg on the banks of River Pregel, published in a book by M. Zeiller around 1650 in Frankfurt, titled Topographia Prussia et Pomerelliae (Reprinted in Biggs, N.L., et al. Graph Theory 1736-1936, Oxford U. Press, 1976).
A close observation of the picture reveals that there was an island and the river that surrounds it was divided into two branches. These branches were crossed by seven bridges, as shown more distinctly in the following picture.
A local sport was to find a route that starts any place in the city, crosses each bridge once, and only once, and comes back to the starting point. Nobody was able to find one, but people kept on trying. Until, in 1736, the famous Swiss mathematician Leonhard Euler proved conclusively that it cannot be done. His paper, published by Academiae Scientiarum Imperialis Petropolitanae, the Academy of Science in St.Petersburg, was the first paper that defined a network flow problem. What he did was, in his own words, he "... formulated the general problem: whatever be the arrangement and division of the river into branches, however bridges there be, can one find out whether or not it is possible to cross each bridge exactly once?" He represented each region of land, A, B, C, and D, by a "point", called a node in network flow problems, and each bridge, a, b, c, d, e, f, and g, connecting these regions by a "line", referred to as an edge. The network for the problem of Köningsberg bridges is shown below.
Euler's elegant proof concludes that for such a route (which we now call an Euler tour) to exist the network should be "connected" (i.e. each region of land can be reached from every other by means of the bridges) and that every node has even degree (i.e. the number of bridges touching each land region must be even.) Clearly, this was not the case for the bridges of Köningsberg.
Euler's work started a whole new branch of mathematics called graph theory. Application of graph theory, together with concepts from optimization theory, to practical problems is the domain of network flow problems. For example, the network flow problem related with Euler tours is the Chinese Postman Problem (after the Chinese mathematician, Kwan Mei-Ko, who discovered it in early 1960's.) The problem is the following. Suppose the distances of the bridges are known and we have to cross each bridge at least once. We would like to find a route that comes back to the starting point which minimizes the total distance traveled on the bridges. Clearly, Euler tour, if it exists, is the optimal solution to the Chinese Postman Problem. But if the network we have on hand does not satisfy the Euler's conditions, Chinese Postman Problem attempts to find a tour with minimal repetition of the edges. Many problems in trash collection, road sweeping, snow-plows, highway lawnmowers, transmission line inspections, school bus routing, and certain problems related with routing of AGVs in material handling systems can be modeled as Chinese Postman Problem.
Other Network Flow Problems
The Chinese Postman Problem is only one among many network flow problems. Networks for the transmission of information, the transportation of people, and the distribution of goods and energy are part of our everyday life. Think about how all the utilities and the telephone, Internet, and Cable-TV services made available in our homes and offices, how our mobility is made possible by the highway, rail, and airline networks. Without effective distribution and logistics networks, we could not have all the goods and services that are available now at affordable prices.
It has been argued that the three properties are responsible for the widespread use of network flow models in practice:
- Visual Content
- These models allow for a problem to be depicted by means of diagrams and that the pictorial appeal of these network diagrams make the problems easily understood by many users.
- Model Flexibility
- Network models having similar structures can be used to "... analyze group communication phenomena in sociology, to determine ancestral orderings in archaeology, to probe the effect of government fiscal and regulatory policies, and to allocate library budgets to determine what types of publications to acquire," in addition to the application areas mentioned above.
- Solvability
- There exist computationally very efficient algorithms, step-by-step solution procedures, for most network flow problems. These special purpose algorithms achieve these extraordinary efficiencies by exploiting the special structure inherent in the network flow problems.
There are a few "generic" network flow problems and a large number of problem types with variations that are made necessary by the practical applications. In the following we shall briefly discuss three general problem types, namely, the shortest path problems, the maximum flow problems, and the minimum cost flow problems.
The Shortest Path Problems
This network flow problem is one that we all use in our daily lives: what is the fastest route to take between two locations in the city during the rush hour, what is the "most" scenic route to drive, or the cheapest route to fly, between two cities in our vacation. The street intersections or the cities are the nodes, and the street or highway segments in between the intersections, or non-stop flights between the cities are the arcs. There are numbers associated with the arcs. These numbers can be the estimates of how long will it take to drive through a street segment during the rush hour, or a measure of "scenic pleasure" one expects to obtain traveling on a certain highway segment, or the cost of flying between two cities. The objective is to find a series of arcs connected with correct directions such that one can start at the origin and arrive at the destination traversing the arcs and that the sum of the numbers on the arcs are either minimum (in the case of the fastest or the cheapest route) or maximum (in case of the "most scenic" route).
Sometimes we might be interested in the longest, rather than the shortest, path; as the critical path in the CPM/PERT techniques of project management. In project networks, we can represent the "activities" by the arcs, and the nodes represent the "events". The estimated duration of each activity is the "length" of the corresponding arc. The first "event" is the start of the project, and the last "event" is the completion of the project. The configuration of the remaining arcs and nodes represents the precedence relations of the activities. In this "activity-on-arc" representation of a project network, the objective is to find the longest path between the first and the last events on the network. The arcs on this longest path are the critical activities in the project in the sense that any delay in these activities will delay the completion of the project, hence the name critical path.
There are other applications of shortest path formulations that may not appear to be a network flow problem at first sight. One such problem class is the replacement problems. Consider, for example, replacement decisions concerning an industrial equipment. After you paid the initial purchase price, each year there are operations and repair expenses which increase as the equipment ages. On the other hand, the trade-in, or re-sale, value decreases by each addition year of use. Suppose it is possible to estimate those figures for the next five years. Then one may construct the following network to determine the optimal replacement policy for the equipment. Let node, i, denote the beginning of year i, and the arc (i,j) denote the decision of purchasing a new equipment at the beginning if year i and keeping it until the beginning of year j, as in the following graph:
The values associated with each arc represent the total cost of purchasing a new equipment at the beginning if year i and keeping it until the beginning of year j, which is obtained by adding the yearly operating and repair costs and the cost of buying the equipment new minus its resale or trade-in value. The optimal policy is composed of the decisions on the arcs of the shortest route from node 1 to node 6 in the above network.
The Maximal Flow Problems
Now the numbers on the arcs represent the "capacity" of the arc. That is, these numbers are the maximum flow (for example, per unit time) possible between the the node from which the arc is incident out of and the node it is incident into. The network can be an oil pipeline in which nodes are the pumping stations and the objective is to determine the maximum amount that can be pumped between an origin node and a destination node. Or the network can represent the city traffic flow network where the capacities on the arcs are the maximum number of vehicles that can travel (per unit time) on a segment between two intersections. During the rush hours by making certain streets one-way, or changing the lane allocation in multi-lane highways or streets, we can increase some of the arc capacities. The solution of maximal flow problem on these networks will help us estimate how much we can ease the traffic congestion during those periods. Maximal flow problems also play an important role in the design and operation of telecommunication networks and computer networks like Internet and the company intranets.
Minimum Cost Flow Problems
The fundamental basis of maximal flow problems is that there exists a capacitated network and costs are constant regardless of how much flow is flowing in the arcs. But if there is a unit cost associated with flow on each arc, we have a minimum cost flow problem. The scenario of a generic minimum cost flow problem is the following. At some nodes ("supply nodes") there are an excess of some commodity, some other nodes ("demand nodes") require certain amounts of this commodity. The remaining nodes ("transshipment nodes") neither require nor supply this commodity. There are lower (which can be zero) and upper (which can be infinity) bounds on the flow on the arcs, as well as unit cost of transportation on the arcs. The objective is to satisfy the demand at a minimal cost without violating the bound constraints. The classical transportation problem of linear programming is a minimum cost flow problem without any transshipment nodes and no upper or lower bounds on arc capacities.
Interestingly, it is possible to transform many network flow problems into a minimum cost flow problem. Take the shortest path problem, for example. Relax the upper and lower bounds on the arc flows (i.e. set them equal to, respectively, infinity and zero.) Assign a supply amount of one unit at the origin node and a demand of one unit at the destination node. The optimal flow in the resulting minimum cost flow problem is the shortest path of the original problem.
Transforming a maximal flow problem into a minimum cost flow problem is a little bit more involved. Assign zero unit cost to all the arcs. Lower bounds are zero and the upper bounds are the arc capacities. Define a "dummy" arc from the origin to the destination node with a flow cost of one per unit and no upper or lower bounds. We also need an upper bound on the maximal flow quantity. Actually any "large" number will do, but this number is very easy to obtain: take, for example, the sum of the capacities of all arcs that are incident out of the origin node. Assign this quantity as the "supply" available at the origin, and same quantity is "demanded" at the destination node. In trying to find the minimum cost flow, the solution procedure will push the maximum possible flow through the original network since it costs nothing on these arcs. Only the overflow over and above the maximal flow possible in the original network is diverted through the "dummy" arc from the origin to the destination node. The optimal objective function value of the minimum cost flow problem is equal to the optimal flow amount on the "dummy" arc. If this amount flows through the "dummy" arc, the rest of the "supply" available at the origin must have been transported to the destination node over the the original network. Thus the difference between the estimated upper bound (i.e. the supply amount at the origin) and the optimal objective function value is the maximum flow possible from the origin to the destination node in the network.
Solving Network Flow Problems
Most network flow problems can be formulated as linear programs, and more complicated one with certain side conditions can be formulated as mixed integer programs. Furthermore, as shown in the previous section, many network flow problems can be formulated as minimum cost flow problems. Like for all problems in mathematical programming, an algorithm that is specifically designed to solve that particular class of problems is more efficient on that class than a general purpose algorithm. For example, shortest path problem can be solved as a minimum cost flow problem which can be solved as a linear program using the Simplex Method. But it is more efficient to use the network simplex algorithm for this network flow problem. Finally, there are special purpose algorithms to solve just shortest path problems, which are the most efficient way of solving these specific type of problems.Why are we, then, discussing these transformations of one problem into a more general class, and why people write general purpose algorithms for a broader class of problems? A simple answer is that if you need to solve a specific class of problems often, then it may be more cost effective to install a special purpose algorithm in your system. But if speed is not a major concern and the size of the problems you solve are of "manageable" size, you may be better off having a general purpose algorithm that is capable of solving various types of problems.
It is the beyond the scope of this short discussion to get into the solution algorithms for network flow problems. There are excellent books by Murty, Evans & Minieka, Glover, Klingman, & Phillips and Ahuja, Magnanti, & Orlin, that discuss the solution algorithms as well as numerous real world applications network flow problems. In addition there are a number of informative resources on the Internet. GIDEN, Graphical Implementation Development Environment for Networks, is an interactive software environment designed to facilitate the visualization of network optimization problems, solutions, and solution algorithms. There are two comprehensive surveys of computer software for network flow problems: Jiefeng Xu's list of network optimization software, and The Optimization Software Guide has information on software packages from the book by Moré and Wright, updated for the NEOS Guide. Before choosing a particular software, make sure to read Software for Optimization: A Buyer's Guide by Robert Fourer.
© Copyright 1999 INTERNATIONAL JOURNAL OF INDUSTRIAL ENGINEERING