Some Network Optimization Problems In Uncertain Environment

Network optimization is an important branch of operations research and its aim isto study how to plan and control network system effectively. It arises in a wide vari-ety of management science, industrial engineering, transportation and communicationnetwork. In some applications, different kinds of uncertainties are frequently encoun-tered, such as randomness and fuzziness, and must be taken into account. In this paper,we study the fundamental problems of network optimization in uncertain environmentincluding the shortest path problem, maximum ?ow problem and minimum cost ?owproblem.When we model the shortest path problem, it is not practical to consider each arcas a deterministic value for some reasons such as weather condition, time interval andpayload. This paper studies the stochastic shortest path problem by probability theory.We present three types of models, and develop a hybrid intelligent algorithm for thesemodels. However, randomness is not the unique uncertainty in real world. Sometimesthe probability distributions of the weights of arcs are difficult to acquire due to lackof historical data. In this case, the weights of arcs are approximately estimated by theexperts, and fuzzy theory offers a powerful tool to deal with this case. In this paper, wepresent some models for fuzzy shortest path and design a hybrid intelligent algorithmfor these models. The capacity of network and transportation cost on arcs are difficultto be given by deterministic value for some reasons. In order to arrange the network?ow on each arc well and make good use of the capacity of the network, some fuzzymaximum ?ow models and fuzzy minimum cost ?ow models are given. In order tosolve all these fuzzy models, some crisp equivalents of them are given for some cases,and the hybrid intelligent algorithms are designed for general case in this paper. Andwe give some numerical examples to reveal the effectiveness of algorithms.In conclusion, this paper contributes to the research area of network optimizationin uncertain environment in the following aspects: (1) Some single objective and mul-tiple objectives shortest path models are presented. Under different decision criteria,three types of models are given in random and fuzzy environment, and some hybridintelligent algorithms integrating simulation and genetic algorithm are designed. Andsome numerical examples are given for effectiveness of algorithms; (2) The minimumexpected cost ?ow model, maximum chance cost ?ow model andα-minimum cost ?owmodel are presented, and a hybrid intelligent algorithm based on genetic algorithm andfuzzy simulation is developed; (3) A chance-constrained programming model is pre-sented for maximum ?ow problem with fuzzy capacity on each arc, and some crispequivalents of models are given. (4) Apply the theory and algorithm of network opti-mization in uncertain environment to solve supply chain network design problem.