Applications Of The Blocking Flow Theory To Optimization Design, Reconstruction And Operation Of Stochastic Flow Networks

This dissertation is composed of six parts.Part 1. Based on the stochastic flow of the network, the new concept of the stochastic flow network is given. The saturated flow model of the stochastic flow network is set up.Part 2. On the basis of the blocking flow theory, new algorithms are presented to solve the minimum saturated flow. The differences between the not-circuit minimum saturated flow and the minimum saturated flow with circular flows are put forward. Firstly, the branch-and-bound algorithm is improved. Secondly, based on blocking cutsets, the conditional longest augmenting directed path is searched. The flow is added along this path until the network flow reaches saturation. The corresponding algorithm is studied. The complexity of this algorithm is analyzed. Finally, the influence on the network blockage by changing arc capacities is studied. When added some arcs capacities in the network, the blockage of the network is aggravated. Searching on these arcs is much more important. Examples show the existence of these arcs and their effect on the minimum saturated flow.Part 3. Optimization design and reconstruction to improve the blockage of networks are discussed. Firstly, a commonly model lessening the blockage of networks is introduced. Using as little as possible cost, restricted with the lower and upper capacity, arcs capacities in the original design are changed to eliminate or decrease as much as possible the structural blocking points. Examples show the rationality and feasibility of the solution procedure. Secondly, aimed at existed transport networks, a model is set up to reconstruct blocking networks. The scenario is compared with the minimum-cost reconstructing method. Results show the rationality and universality of this reconstructing model.Part 4. Indices are presented to evaluate the flow capability of stochastic flow networks. Firstly, selecting different augmenting directed paths leads to the different distribution of saturated flows. Three different selections to augmenting directed paths are put forward. A Monte-Carlo simulation approach is presented to obtain the distribution of stochastic saturated flows under various selections to augmenting directed paths. Examples are used to show the influence on the distribution of saturated flows in different ways to select augmenting directed paths. Secondly, two reconstructing methods are discussed to improve the expectation of saturated flows. Finally, the problem on improving traffic jam of cities is studied. At present, making streets one-way is often used internationally. The optimal one-way reconstructing scenario is found using the multi-objects evaluating model.Part 5. Two problems about the operation of stochastic flow networks are discussed. Firstly, saturated flows of networks under time constraints are studied. The saturated flow and its needed time passing the network should be considered in the process of dynamic optimization of the network. Considering the needed time per unit flow passing each arc has some relations with the existed flow and its capacity. In emergency networks, if users always choose the path in which the needed time is shortest, the augmenting directed path is not fixed. The algorithm about the shortest time saturated flow of stochastic flow networks is given. This saturated flow can reflect on the purpose of maximizing the requirements of users. Secondly, the minimum saturated flow of stochastic flow networks under fuzzy constraints is studied. Indetermination to constraints or goals is proposed. In case of fuzzy capacities constraints, how to get the optimal minimum saturated flow satisfying with fuzzy conditions is discussed, and a corresponding algorithm is given. The problem on the maximum flow or the minimum saturated flow is changed to the making-decision under fuzzy environment.Part 6. Reliability on stochastic flow networks is studied. Firstly, based on the saturated flow model, flows probability distribution of every arc is obtained by simulation. The reliability of stochastic flow networks is evaluated by the probability of saturated flows are not less than the demand. When the network is saturated, the saturated flow value is decided by arc flow distributions of blocking cutsets. Therefore, the system reliability that saturated flows are not less than the demand is reduced to the probability that the sum of flows of the backward arcs is not bigger than a certain value in the blocking cutset. Examples show the practicability and validity of the reliability algorithm presented above. Finally, reliability evaluation of medical salvation in emergency situation is studied. The threat of emergency security incidents is increasingly extruded to people life security and society economy. Restricted by the territory and the economy, it is impossible to set up an integral medical aid post in each district. The medical rescue network system is put forward. At least an integral medical aid post is set up in the system, and the medical rescue of this aid post can include some other regions which haven't set up an own medical aid post. The rescue reliability depends strongly on the ability to transport quickly a large number of casualties from the calamitous region to the medical aid post. Study on the system reliability of the Medical Rescue Network helps us to estimate the rescue ability when an accident occurred in the medical rescue network.