Research Algorithm Of Vehicle Routing Problem With Time Windows Based On IA And TS

Research the related theory and method of Vehicle Routing Problem (VRP) is to reduce the costs of physical distribution, which is an optimization problem by reasonably scheming driving route to minimize the costs of transportation, and it is a hot research in operational research and combinatorial optimization fields. Through deeply researching this problem, many new research branches have been extended from this problem. This paper first analyzes the research current situation of VRP, and then presents the research problem of this paper-vehicle routing problem with time Windows (VRPTW)-combining the actual situation. By building the mathematical modeling of based on the vehicle routing problem with time windows, this paper clearly defines the target function and the constraints condition of VRP. After considering the influences of the dispatching distance, time and the number of vehicles, this paper finally constructs the goal of shortest dispatching total distance. After analyzing the current variety solving methods, this paper use mixed strategy of immune algorithm and tabu search.Firstly, this paper analyzes the tabu search and immune algorithm respectively, and analyzes the solving thought of tabu search, especially the design of aspiration level. After understanding the feature that the target functions of VRP is the shortest distance, this paper takes the target function as the aspiration level of tabu search. By making a comparison of average, variance and average computing time, tabu search, this paper use tabu algorithm, genetic algorithm and ant colony algorithm to solve TSP. This paper obtains the validity of the algorithm of tabu search and prove the independence of initial solution. Secondly, this paper analyzes the thought of immune algorithm, and knows that the feature of immune algorithm is extraction vaccine. And this paper proves that immune algorithm can get the optimal solution in global scope, and verifies immune algorithm can improve the shortage of genetic algorithm. Finally, this paper introduces the algorithm of mixed strategy of immune algorithm and tabu search, and takes the optimal solution of immune algorithm as the initial solution of tabu search. And this paper design the coding way of building mathematical modeling and the affinity of aspiration level.This paper conducts simulation experiments by using the test data sets of Solomon Benchmark in MATLAB, and calculates the best target function and the best dispatching distance, and proves the reasonability and effectiveness of mathematical model and solution algorithm for class R and class RC of Solomon benchmark test set by analyzing the result of experiments.