Study On Models And Algorithms Of Some Problems In Stochastic Flow Network

Network flow theory is an important branch of Graph Theory, and it is the theory of studying optimization problems upon network. In 1956, L.R. Ford and D.R. Fulkerson propound the algorithm to solve the problem of seeking maximal transportation quantity between two nodes on the network. From then on, network flow theory was founded and developed. Network flow theory now has been widely applied to communication, transportation, power transmission, engineering programming and other fields. In order to solve the practical problem better, some new network flow theory were propounded, such as assignment and matching, LaGrange relaxation of network optimization, multi-commodity flow, network flow's decomposition and combination and so on. But above research were all based on network whose parameters and topology structure were determinate. Network system in practical circumstance often presents randomicity because of influence of some factors. So it often causes some errors when apply traditional network flow theory to practical problems. It is significant for improving network flow theory's practicability to optimize network flow in stochastic circumstance. This question has drawn attention.Presently, stochastic factor has been introduced into network flow theory from three aspects: 1. suppose arcs'weights in network are stochastic variables; 2. suppose network's topology structure is stochastic; 3. suppose arcs'capacities are stochastic variables, and propound the conception of stochastic flow network. Previous research on network flow theory upon stochastic flow network focused on designing algorithms to seek network's critical capacity states (d-MCS or d-MPs) and computing network's reliability according to these states. But when stochastic flow network's capacity is not critical state, research on network flow optimization is few. So author selected different objectives according to different circumstance and studied optimization problems under the condition that network flow was not maximal flow V(X). The article mainly contains four contents as follows:1. Basing two frequently used stochastic flow network models (network model with reliable nodes, single-commodity flow, multi-source nodes, multi-sink nodes and network model with unreliable nodes, multi-commodity flow, multi-source nodes, and multi-sink nodes), author studied how to optimize network flow when network flow was not maximal flow V(X).Author selected network flow's reliability as objective, and constructed integer stochastic programming model. According to model's characteristics, genetic algorithm was designed to solve constructed model. Author compared genetic algorithm's result with that obtained by Lingo, and analyzed advantage and disadvantage of these two methods.2. Author transformed network flow transportation time and transportation cost from constraints to objectives, and studied multi-objective optimization problem upon stochastic flow network. In order to solve constructed model, author improved NSGA-II's tournament selection operator, simulated binary crossover operator and elitist strategy. Tested by examples, improved algorithm was better than former NSGA-II.3. Existed algorithms on computing stochastic flow network's reliability contained maximal flow minimal cut theory, Ford-Fulkerson algorithm and other traditional theory, so the variables in stochastic flow network was restricted to be discrete variables. Because of using genetic algorithm to optimize network flow in paper, above restriction was invalid and variables in model could be continuous. In order to deal with equation constraints containing continuous variables, author added a parameter and decomposed an equation constraint to two inequation constraints. Author solved decomposed model by improved NSGA-II. Tested by an example, algorithm can figure out the Pareto frontier of continuous optimization model.4. Network flow optimization problem was studied upon network which nodes'demand was stochastic. Author constructed chance constrained programming model and transformed confidence level constraints to corresponding determinate constraints and dealt with other constraints by stochastic simulation method. A multi-objective genetic algorithm based on stochastic simulation was propounded to solve constructed model. Tested by examples, the algorithm can figure out model's Pareto solutions.