Research On Vehicle Routing Problem Based On Multi-objective Evolutionary Algorithm

Vehicle Routing problem is an important reserch direction for combinatorial optimization and operation reserch. Its main purpose is to get the routes that can delivev goods to the custom with the lowest cost, Because of its important application value in the transportation, logistics, courier industry has a wide range of applicationsSince there is no way to solve this problem in determine polynomial time effectively, many heuristic algorithms have been applied to solve the problem, wherein evolutionary algorithms have been proven suitable for solving the problem. Although evolutionary algorithms can provide a more complete solution to the problem in multiple optimization objectives relative balance between the obtained solution, very few specifically for the multi-objective optimization problem in the direction of research, but also less likely to have studied the solution diversity as a specialized research content, which may put the performance of any evolutionary computation techniques are vital good performance.This paper, based on evolutionary algorithms, proposed a new multi-objective evolutionary algorithm-Enhanced coverage-restricted evolutionary algorithm, ECREA,which is used for two classic variants of VRP:VRPTW and CVRP,and the particular optimization goal is for at least two optimization objectives. Related research works are as follows:Proposed a method can be quantified the VRP similarity between two solutions, and this information, is then used to determine an individual solutions and other solutions in the population similarity, on the basis of which effective assessment population diversity. The main advantage of the method are:it does not depend on the specific encoding of solution,and can also be applied to any kind of VRP variants, and it has a linear time complexity.Designed a new process of mutation, the mutation process and evolutionary algorithms that incorporated for VRP can be used to make better use of the search space. The new process involves three basic functions, two of which are random used to choose the route and customer, the other is a deterministic for customer re-inserted into the routed to go. In addition, proposed three new mutation operator, used to adjust the route inter the customer distribution and the route service order.Proposed a new solution that can effectively solve CVRP,VRPTW by means of Enhanced coverage-restricted evolutionary algorithm, ECREA, the algorithm can be optimized simultaneously at least two optimization objectives. The algorithm integrates the above mentioned similarity quantitative methods and mutation process in order to better explore and exploit the search space, so as to maintain a high diversity of population. The results show that the solution obtained algorithm provides a more suitable compromise between the multi-objective optimization results.By the test on CVRP, VRPTW benchmark set, the new algorithm results compared to solutions with the existing optimization goals based on a single study considered showed the new algorithm to obtain a solution, though not on the whole are optimal, but at least, and the latter compared to the results of many studies can be compared, which is mainly manifested in the new solution algorithm can obtain fewer number of routes or shorter travel distance, while the corresponding other optimization objectives and the results of the latter different less than2%. Because obtained through an optimization goal is not necessarily the optimal solution can exhibit multi-objective optimization results, so the algorithm has practical value.Then the three multi-objective optimization performance metric are used in ECREA VRPTW bi-objective optimization problem and three-objective optimization, results were analyzed and compared with the famous multi-objective optimization algorithm NSGA-II solutions obtained were compared the results showed that the former won in many of the test cases better results than the latter. In solving the CVRP problem, because the test case test set goals and there is no conflict, there is no multi-objective optimization performance analysis.Because most existing studies regarding VRP tend to present and analyse the multiple objective optimization results in single objective manner, the paper has put forward through the use of formal methods for multi-objective evaluation of the performance of multi-objective optimization proper comparison and analyzed, and with the final conclusion...