The Improved Genetic Algorithm For VRP

With the rapid development of computer science, the Vehicle Routing Problem (VRP for short) is always the researching focus of most computer scholars. It is of great significance for the logistics system and the combination optimization problems that how to design the algorithm with simple operation and excellent capability according to the characteristics of the vehicle routing problem. Thus,the theory in Crop Breeding is applied to two typical algorithms according to the shortage of the common genetic algorithm for VRP. The two typical algorithms are the most widely used single population GA and the efficient double populations GA. The final contrast experiment validates the capability and efficiency of the improved GA. The main research of this paper includes such aspects as below:First, an improved strategy which based on the theory of otherness in Crop Breeding is proposed according to the shortage of early convergence and easy falling in the local minimization in the traditional single population genetic algorithm for VRP. Then, we apply this theory to the process of the father chromosome selection before the chromosome crossover in single population GA and the process of the population crossover in double populations GA. Thus, we can simulate the evolution rule of nature in order to improve the optimization capability.Second, an improved single population GA is designed based on the improved strategy in this paper. This improved algorithm can ensure the chromosomes with some difference to crossover in order to enlarge the difference between the child and father chromosomes by using the new father chromosome selection strategy and new crossover operator. Thus,the diversity of the population is increased, the searching space is enlarged ,the local minimization is avoid and the optimize capability is improved.Third, an improved double populations GA is also designed based on the improved strategy in this paper. This algorithm adopts the new population crossover strategy which makes some improvement on the traditional double populations GA according to the process of exchanging the chromosomes between populations. In addition, we design a new scheme that the two populations use the different crossover operator and mutation operator,and the two populations also use the different crossover and mutation probability. Thus, the improved GA can simulate the process of species evolution more effectively in order to ensure the diversity of the population,and conducive to the evolution of the population.Finally, the improved genetic algorithms based on single population and double populations are applied to the vehicle routing problem which has been widely used as benchmarks in order to contrast to the traditional genetic algorithm. Results of the experimental tests and comparative analysis demonstrate the algorithm proposed by this paper can find the optimal or near optimal solution to the vehicle routing problem more effectively and avoid the early convergence and easy falling in the local minimization in common genetic algorithm for VRP.The research above has good academic reference value in the domain of genetic algorithm for the VRP and good applied value to the development of the logistic system.