Research On Network Optimization Model And Application Based On Uncertain Graphs

With the continuous development of society,the application of graph theory and network optimization is becoming more and more extensive,and a large number of practical problems may be formulated as the problem of graph and network optimization.In this thesis,the knowledge and methods about graph theory,uncertainty theory,uncertain programming,optimization theory etc.are used to study uncertain graph and network optimization problem based on uncertain graph.After the deeper studying of graph theory and uncertainty theory,the general concept of uncertain graph and the derivation and proof of its related properties and theorems have been improved and an improved Prim algorithm for solving connectivity of uncertain graph has been designed.According to the uncertain programming,six network optimization models based on uncertain graph are established based on three different modeling principles,and their solving simulation algorithms are designed.In the application example,the location selection of the logistics nodes and the network route planning are carried out for the underground logistics system.The main works are as follows:(1)The studies on the definition of an uncertain graph,the representation of its matrix,the related properties and theorems.The random,fuzzy,rough and intersecting uncertain factors are unified by using the uncertainty theory.First,the definition of uncertain graph is proposed by analogy of the definition of the graph with uncertain edge structure and with the help of adjacency matrix.This definition unifies the concepts of the edge structure uncertain graph,the vertex structure uncertain graph and the certain graph.Then,the uncertain measure matrix is presented to identify the uncertain graph.And the uncertain measure matrix,the adjacency matrix and the incidence matrix are compared respectively under the two cases of the certain graph and the uncertain graph.Secondly,the numbers of order and edges about the uncertain graph,and their properties as well as the uncertain distribution are analyzed and proved.Finally,based on the idea of Prim algorithm,an improved Prim algorithm is designed to solve the connectivity of uncertain graph by taking the priority of the order of uncertain graph as the greedy criterion,and the rationality of this algorithm is verified by numerical examples.(2)Research on network optimization model and algorithm based on uncertain graph.First,on the basis of uncertain graph,two types of networks based on uncertain graph are analyzed:uncertainty of graph structure and uncertainty of graph attributes.Next,the network optimization model is built on the premise of "the network with uncertain graph structure but having determined attribute".Then,according to three modeling mechanism of the uncertain programming:expected value programming,related opportunity programming,opportunity constraint programming,the six optimal models of expected shortest path,the maximum possibility shortest path,the alpha shortest path,the expected value logistics location selection,the maximum possibility logistics location selection and the alpha logistics location based on uncertain graph have been established with aiming at the problem of the shortest path and site logistics respectively.Secondly,the network optimization models are compared and analyzed from many angles.Finally,analogizing the methods of stochastic simulation and fuzzy simulation,simulation algorithms to solve those models are designed.That is,the network optimization models of the uncertain graph are first transformed into the certain network optimization models by using these simulation algorithms to simulate the uncertainty functions,and then they are solved with the correspondence to the algorithms.(3)In view of the new system of relieving urban traffic congestion-underground logistics system,a case study of the location selection of logistics nodes and the optimal tunnel network planning is carried out.First of all,based on the research about uncertain graph and the network of uncertain graph,as long as the location of the region center is regarded as the vertex in the uncertain graph,the freight relations in the region corresponding to the two logistics nodes is taken as the side between the two vertices,the problem of underground logistics system planning may be formulated as the problem of network optimization with uncertain graph.Then,based on the uncertainty of logistics nodes,a calculation model for the uncertainty measure of the vertex and edge is established in an uncertain graph.The real-time traffic congestion index in each area is used to characterize the uncertainty measaure of underground logistics nodes built in each area.The freight volume between two places depicts the uncertainty measure of the edge.Finally,the logistics location selection model of maximum possibility is constructed,and this model is solved based on the simulation algorithm designed in this thesis and the method of alternate location selection-allocation.Moreover,the location selection of the logistics nodes and the optimal tunnel network planning of the underground logistics system are solved.