Research On Vehicle Routing Problem Based On Improved Genetic Algorithm

Vehicle Routing Problem which was proposed by Dantzig and Ramser in 1959 is a classical combinatorial optimization problem. Because of the tight relationship between the theoretical research and real-world application, this problem was paid great attention by the experts on computer science, operational research, combinatorics and management since its birth. As so far, the methods used to solve VRP could be classified into three classes, they are precise optimization method, traditional heuristic method, modern heuristic algorithm also called intelligent optimization algorithm. Most of the researchers are all focusing on the research of intelligent optimization algorithm.Genetic algorithm is an intelligent search algorithm that simulates the biological evolutionary process of the nature, as an effective global optimization tool, it has some good features including simplicity, universal, stability and easy used by parallel distribution process, and also including the intelligent features of self-organization and self-learning. This method can be used to solve the intelligent problems as combinational optimization, machine study, adaptive control. In this thesis, we used genetic algorithm to solve VRP, its chief work and creative ideas are listed as follow.1)According to the analysis, deduction and extraction from many related references, this thesis generally described the origin and development, research and application value, current research situation of VRP. It also clarified the background and meaning, proposal reason and chief work of this thesis. And it indicated the existing shortage in current research of VRP, gave preparation for the research of this paper.2)This thesis discussed basic optimization principles, algorithm structure and design procedure of genetic algorithm, analyzed the features of GA, its shortcomings and optimization strategies. Given the defects of premature convergence caused by the decrease of population diversity, in the process of evolution of genetic algorithm, we designed a doubly improved genetic algorithm (DIGA): referring the advantages of immune algorithm which uses antibody concentration restriction to keep population diversity, we add individual concentration operation to genetic algorithm. At the same time, it also refers the individual choice approach of Simulated Annealing Algorithm to improve the choice strategy of genetic algorithm. This improvement could make algorithm jump out of some local optimization point with a certain probability, and adds'Elite Remain'strategy to assure the global convergence of DIGA. 3)We analyzed various restriction conditions of it and concluded the certain classes of methods and features of solution of VRP. We mainly researched multi-objective optimization VRP which is restricted by the vehicle number and capacity, built a related mathematical model for it. We used DIGA to solve VRP and illustrated the structure of DIGA and detailed the design procedure of the algorithm.4)This thesis analyzed the performance of DIGA to solve VRP from the experimental view:â‘ chose several test instances from universal, classical test library used by domestic and foreign researchers, proved the effectiveness of algorithm and good performance by experimental test and analysis;â‘¡chose some experiment data provided by authoritative journals and references to validate our test, compared and analyzed our test results with other references'results, and authenticated the search efficiency and solution quality of DIGA.In conclusion section, we summarized our chief work and creative ideas, analyzed defects in our research and expected the future work.