Solving Capacitated Vehicle Routing Problem Model Based On Heuristic Algorithm

The vehicle routing problem(VRP)is a traditional combinatorial optimization problem.It is widely used in logistics,traffic control and other fields.With the development of science and technology,as well as the increasingly rich means of transportation and communication,VRP has once again become a research hotspot,and radiated new vitality.On the one hand,the researchers constantly try to enrich all kinds of constraints and simulate the influence of various factors on the model in reality,so that it can better describe the actual situation.On the other hand,the researchers constantly improve the algorithm,in order to plan the best path with higher efficiency.The solution of vehicle routing problem is proved to be NP-hard problem because it involves complex combinatorial optimization.With the increasing of the number of customers,the exact algorithm can not solve the problem because of the large increase of calculation.Therefore,the heuristic algorithm formed by the problem knowledge or search results has become the mainstream method to solve VRP.In this thesis,the two issues are mainly studied as follows:One is to propose an effective algorithm for solving large scale capacitated vehicle routing problem(LSCVRP).It is a hot practical issue formed by VRP when the number of the customers rises to a certain degree.For LSCVRP,the difficulty lies in how to search effectively in a large solution space.This thesis introduces the hierarchical decomposition strategy to solve LSCVRP,and applies variable neighborhood search to the incumbent solution to further improve the quality of it.In order to verify the effectiveness of the designed algorithm,two benchmark test sets(i.e.,Golden and Li)are calculated and several state-of-the-art algorithms are chose for the comparison.The results show that the algorithm designed in this thesis can outperform the compared algorithms in many examples,especially in large-scale test set Li.The second is to modify the basic CVRP model by simulating the actual road conditions.By taking into account the periodic changes of traffic flow and the impact of emergencies on road conditions,we put forward the CVRP problem under uncertain road conditions.Then,the path is planned under the condition of determined and uncertain road conditions respectively.Ten groups of examples with different sizes,different customer needs and different maximum load constraints in the revised VRP international standard data set are used to test the route planning scheme under the two conditions.Moreover,three groups of examples are statistically analyzed to prove the uncertain road conditions.The results show that the proposed route planning scheme performs better in the actual road test.