Network Modeling

Historical Background

Network theory is an area of applied mathematics that represents a domain of graph theory. A network model implies an abstraction of reality that helps simplify a problem. Applied mathematics, computer science, engineering, management, and operational research are scientific domains that use network theory.

The beginning of network theory can be traced back to the well-known problem of the seven bridges of Konigsberg in Germany. The stated problem was to find a walk through the city that crosses each bridge once and only once. In 1735, Leonhard Euler proved that this was not possible. He reformulated the problem and constructed a network by replacing each landmass with a node and each bridge with an arc. The study of the network led to the identification of valuable properties of the problem and then to its solution, presenting the first steps of network theory.

Because “network modeling” is a general term, developed in many scientific domains, the focus is to analyze the most significant network modeling methods with applications in transportation. In transportation networks, the main objective is to model the objects' movement through the networks. Thus, the most significant work refers to network flow modeling.

This field traces its roots back to 1845, to the work of Gustav Kirchhoff and scientists who first systematically analyzed electrical circuits. However, research on transportation network flow modeling is much more recent. It can be traced to the late 1940s, when the research and practitioner communities simultaneously developed optimization as an independent field of research. Several important network optimization problems related to transportation include the “shortest path” [Page 985]problem, the “traveling salesman” problem, the “vehicle routing” problem, the “multi-commodity flow” problem, the “network design” problem, the “assignment” problem, the “transportation” problem, and the “minimum spanning tree” problem.

Transportation Flow Modeling Problems

In 1939, Leonid Kantorovich introduced the idea of linear programming. Some years later, in 1951, George Dantzig reinvented and further developed this field. Both researchers' motivation came from fundamental transportation problems.

The minimum cost flow model is the most general network modeling problem. The problem aims to determine the least costly shipment of goods, in order to satisfy demand at central nodes from available suppliers from other central nodes. The most significant special cases of minimum cost flow problems are the shortest path, the transportation, the transshipment, the assignment, and the maximum flow.

Minimum Cost Flow Problem

First, assume that the problem can be presented by a directed graph G(N,A) where N is the set of n nodes and A is the set of m-directed arcs. Each arc (i,j)∈A has an associated cost ci,j, the cost per unit flow on that arc. It is also assumed that the cost varies linearly with the amount of flow. Associating each arc i,j∈A with its upper and lower bounds denotes capacity and minimum amount of flow on the arc.

...