Research On Memetic Algorithm Based Dynamic Vehicle Routing Problem

With the development of modern logistics, distribution problems have gradually become a bottleneck restricting the development of enterprises. Therefore, optimizing vehicle routing in logistics distribution has become the focus of the study. Modern logistics, targeted at meeting customer’s demand, is a kind of strategic measure which unified production, transportation, marketing and other market situations, Whose essence equals managers’ rational planning of human, material and financial resources which leads to their high-qualified and high-effective use in valid time. Thus, how to realize the systematization, modernization, and rationalization of logistics is of great importance to social development.Vehicle routing problem(Vehicle Routing Problem, VRP) plays a very important role in the logistics and distribution, which is also a hot issue within the industry. However, due to the development of all walks of life in modern society, frequent exchange of goods, too many varieties of items, the narrow road, traffic chaos, crowed durban and a series of unexpected problems such as traffic accidents or roadside breakdown, some problems appear: the vehicles are driven too long, the article failed to reach customers in time and followed decreasing of customer service satisfaction. In this paper, the author will study on the VRP in uncertain environment, discussing about the relationship between dynamic and static vehicle routings; building the mathematical model, using the shortest vehicle driving period and maximized customer satisfaction as the objective function, and based on issues affecting factors; solving dynamic vehicle routing problem based on designed Memetic Algorithm, and also introducing the major approaches and steps.In this paper, the author conducts detailed analysis on Dynamic vehicle routing problem in uncertain environment and use Memetic Algorithm for the solution. Memetic algorithm is a heuristic algorithm combined global search and local search. Different use of global and local search leads to distinct Memetic Algorithm. The author will combine genetic algorithm and Tabu Search to solve related problems.In this paper, genetic algorithm is used to solve the dynamic vehicle routing problem. According to the problem, the designed genetic algorithm steps are as follows: chromosome encoding, initialization, setting the fitness function, evolution operations, concreting steps of local search, algorithm termination condition setc; in Evolutionary operation, selection, crossover, mutation are based on global search; using Tabu search algorithm as a local search strategy, introducing and analyzing the concrete steps of local search. Genetic algorithms and Tabu search algorithm are combined to reach an optimal solution of dynamic vehicle routing problem: which leads to an effective handling of the increase in new orders and cancelling or modifying in old orders, and using timely and effective way to change the vehicle scheduling scheme.