Study On Capacity Expansion Problems On Directed Networks

We live in a network world. In our real life there are many kinds of network. All these networks play important roles in our economic life and they are the carriers of the country economic growth, such as urban traffic network, telecommunication network, power generation network and computer network.. During all these years of quick development of Chinese economy, network is going through deep changes. For example, China's transport network, telecommunication network, electricity network are all the largest but two in the world. China's annual expansion capacity and the amount of money spent on these are all huge. According to the forecast:in the next 20 years, China's power development task will be very difficult. From 2000 to 2020, the amount of electricity capacity need to be increased is 630,000,000 kW, with an average annual additional installed capacity of over 30,000,000kw, the scale of construction will be even greater considering of updating the equipments. Therefore, research on network optimization is very critical reference for decision makers in real network constructions.In this dissertation, we mainly study capacity expansion problems. For, in reality, a certain network's capacity could be limited,such as the quantity of vehicles through the urban transportation network and the information flow of telecommunication network. When the capacity need be expanded because of increasing demand, the network capacity expansion comes up. This paper studies capacity expansion problems on different aspects: the largest flow, the spanning tree, the paths. We also study on how to eliminate blocking.At first, this article introduces the application background of the models, research methods and creative ideas in detail. There is an overview of the literature, too. Then, the article presents basic models and basic algorithms in network flow theory and capacity expansion models: the largest flow theory, the minimum cost flow problem and the minimum spanning tree theory. These issues and algorithms are the basis for our further research; meanwhile, the heuristic algorithm is also introduced.Secondly, the article studies paths expansion problems. They are: the path between designated nodes, the path between arbitrary nodes. We solve these problems by network switching. We transform these problems into some types of shortest paths problems. Thirdly, the largest flow expansion problem is discussed. Considering of the three kinds of expansion models: node-expanding model, arc-expanding model, the combination of arc-expanding and node-expanding model, we discuss the problems in detail and build a unified model model. Through an example, we compare the merits of the three models and draw the conclusion.Forthly, a model on multiperiod capacity expansion problems on directed networks is proposed. We solve the problem through dynamic programming. We discuss the algorithm in detail under these two situations: the largest flow and the largest capacity spanning tree.Fifthly, the paper studies on how to eliminate blocking in the capacity expansion process. The algorithm is developed and an example is also shown..Finally, this article concludes the main content, innovated points and a prospect on further studies.