Network Capacity Expansion

The network capacity expansion problem is a classic problem in operations research. It is closely related to real life and has a strong theory and reality background. The knowledge of network capacity expansion is widely used in Transformation of urban transport network, power network upgrade, and communication network optimization etc.This chapter introduces the basic knowledge of network capacity expansion problem and gives some classic models. These models are based on different network capacity definitions. In Zhang Jian-zhong and Yang Chao's model, the network capacity is defined as the maximum capacity of the network spanning tree, while the capacity of the spanning tree is defined as the smallest edge capacity on the tree. Their model is highly effective, therefore the definition method have been quoted extensively. Stochastic model is a research focus, which related to stochastic cost, stochastic demand, stochastic route choice and other uncertainties. It is a very broad study field.The second chapter gives a network capacity expansion model on demand. In a connected and undirected network, the flow path between two points is defined as the shortest path between them. Every flow path between any two points has a flow demand. In the network, every arc's capacity must no less than the total demands of the entire flow paths which include this arc. Otherwise, this arc's capacity needs to be expanded. Suppose that the cost of every expanding scheme is a linear increasing function of the expanding capacity, a polynomial solution algorithm is given in this article to make the arc's capacity in the network meet the total demands and have the minimum cost. This article considers two cases of the shortest path:(1) there isn't delay on nodes. That is the number of nodes on the path has no effect on the length of the path; (2) there is delay on nodes. That is the nodes have delay effects on flow, thus need to consider the impact on path length. In the second case, we improved the Floyd-Warshall algorithm according to the need, and give a new FWE algorithm.The third chapter considers the randomness of the route choice to determine the flow path. There are a lot of factors to affect the route choice, in which the delay of nodes and uncertain events (such as emergencies) on arcs has important effect. The uncertainty of the events on arcs leads to the randomness of the path chosen. This paper gives the corresponding model of the problem, and improves the algorithm in the second chapter to solve the problem effectively.