Research On Chinese Postman Problem In Stochastic Networks

Compared with the static network, Chinese Postman Problem (CPP) research in stochastic dynamic network is more applicable, especially for many complicated applications including Intelligent Transportation System (ITS), computer network and communication, etc. Though traditional network model and associated Chinese Postman Problem algorithms already have efficient algorithms, the traditional algorithm is impractical when the network is stochastic. Due to the efficient algorithm for the stochastic shortest path problem, we can bring in the theory to solve the problem. Therefore, the research of new network model and associated high efficient algorithm for Chinese Postman Problem in stochastic networks become an important problem to be solved urgently, which is also the goal of this paper.First, the stochastic network model and the definition of undirected Chinese Postman Problem in stochastic networks are proposed in the paper. Next, when the edges associated with the optimal solution are in congested states, the theory foundation of the substitutive solution and substitutive algorithm are presented. In addition, SNCPP algorithm and the theory which justifies the correctness of SNCPP algorithm are provided. The paper also analyses the complexity which proves the efficiency of the algorithm. Then, the description and theory foundation of directed Chinese Postman Problem in stochastic networks are proposed. By using the incremental algorithms, the efficiency of the former substitutive algorithm has been improved, and an example is attached to illustrate how the algorithm can be implemented. Finally, the further research of the heuristic algorithms is attached.The stochastic network model and the Chinese Postman Problem provide a wholly new method to effectively implement the Chinese Postman Problem for dynamic network. The advantages of Chinese Postman Problem in stochastic network algorithm express not only on the wide use in many practical areas, but also on the great efficiency to solve the problem, which is very important for many applications.