The Mixed Chinese Postman Problem With Capacity Constraints And Its Genetic Algorithm

With the continuous development of information technology, the dependence on online shopping to people become more and more strong. At the same time, the speeding up of urbanization and the city’s motor vehicles increasing, goods dis-tributing efficiency become a strong focus on problems for vendors、logistics compa-nies、customers, it is also one of the subject attracting researchers, so the Chinese postman problem arises at the historic moment.This article embarks from the practical problems and combines with genetic algorithm to study the mixed Chinese postman problem with capacity constraints. Firstly, from the definition、classification、matrix representation of figure, etc con-cepts expound the basic knowledge of network; summarizes the present status of Chinese postman problem research, from chromosome coding、decoding、genetic operation, etc concepts summarize the basic theory of genetic algorithm, the basic steps of genetic algorithm and program flow chart is given. Secondly, the mathemat-ical model of the Chinese postman problem with the maximum working time and the carrier vehicle load constraints is given; discussed limitations with the genetic algorithm to solve the Chinese postman problem, this paper uses a new priority encoding and decoding scheme of "walked and service" overcame limitations with genetic algorithm to solve the mixed Chinese postman problem with capacity con-straints. Thirdly, combine with two properties of network topological structure and edge weight puts forward the new classification of network, at the same time, puts forward the new classification of Chinese postman problem; aiming at the problem of dynamic topology structure network, the network topology dynamic algorithm in probability be designed, aiming at the problem of dynamic edge weight network, network edge weight attribute classification and a penalty factor strategy of net- work edge weight dynamic be given in work time. Fourthly, Due to time-varying attribute of edge weight dynamic network problems, we design a work time decoding algorithm about computation time of routing based on dynamic edge weight mixed network, to overcome computational complexity of the time of arc routing based on dynamic edge weight mixed network. Finally, the instance simulation be given to validate the feasibility and validity of the algorithm.