Genetic Algorithms For Solving The Vehicle Routing Problem

Vehicle Routing Problem gives birth to the transportation in the real life. Since it was put forward in 1959, it has been a hotspot in the area of operational research and combination optimization. There are many traditional methods to solve VRP, but they all need long runtime in solving large number problems. Genetic Algorithm is an evolutionary algorithm, it acts well in both runtime and efficiency. Using GA solving the NP-hard problem VRP is a excellent method, and it has developing future. We have read many literature related overseas and domestic broadly, and in this paper, we first analyze the basic theory and method in GA, then using the GA to solve one-objective VRP and multi-objective VRP. The main content from three parts as follows:1. We introduce related biology knowledge and give a brief review of the development history of GA. Then we conclude the main characters of GA and sum up the present situation of the theories and applications of GA. Through comparing and analyzing several multi-objective GAs now in use, this paper indicates their excellence and deficiency.2. We give a brief review on the origin and development of VRP and sum up the solving methods. Then this paper provides a new GA to solve the one-objective VRP. The new GA is coded in natural number, introduces improving PMX.3. This paper introduces a new multi-objective GA to solve the bi-objective VRP. The two objectives and minimize the transport cost and longest transport time in all vehicles. The new GA introduces NSGA-II and improved PMX to put up genetic operation, and it uses two method—local search andλ-interchange local search method to optimize the value. The examples in our paper show the efficiency of the algorithm.