The Application Of Heuristic Algorithm In VRP Based On The Simulated Annealing Algorithm

VRP is widely used in real life. Many problems can be abstracted into VRP to be solved. The research and application about VRP is always a hot spot.First, this paper introduces the VRP’s classification, common constraints, basic research techniques and methods, then gives the introduction and the mathematical model of a several basic VRP.Comparing with other intelligent algorithms, the simulated annealing algorithm (SA) has fast convergence speed and can find the global optimization solution when solving the VRP, So this paper elaborately introduces the model of its mathematic and the optimization method of the simulated annealing algorithm,proves that the simulated annealing algorithm can find the global optimal solution, gives the advantage and disadvantage of the simulated annealing algorithm, gives the MATLAB language algorithm basing on the simulated annealing algorithm about VRP with a fixed number of vehicles and single objective.This paper researches in a central warehouse, uncertain vehicle number, with time window and closed VRP combined with the case, and gives two methods. The first method simplifies the VRP with taking precedence of processing strategy about time window. It gives all the VRP routes combined with the graph. The shortest path is we want; The second method is to translate the VRP into the language of graph theory and structure the graph Gestating the graph G with the graph algorithm by processing time window and get the maximum independent set the of graph G.The largest number of the set of the independent set the of graph G is k. In particular,k is the minimum number of vehicles of the VRP, then fixing the minimum number of vehicles and giving the greedy algorithm of the VRP with the fixed vehicle and single objective.This paper researches in multiple central warehouses, certain vehicle number and closed VRP combined with the case. This paper solves the VRP by two stages. The first stage the multiple objective problems into single objective problem by circular domain expansion algorithm. The second stage solves a central warehouse, uncertain vehicle number and closed VRP.The solving process is divided into four steps. The first step researches the shortest TSP route algorithm basing on the simulated annealing algorithm. The second step solves the shortest TSP route of the central warehouse3by the algorithm of the first step, gives the heuristic algorithm basing on simulated annealing algorithm of the VRP that the client set is uniform distribution being relative to the central warehouse, gives the optimum route of the VRP of the central warehouse3by the above algorithm. The third step solves the the shortest TSP route of the central warehouse1by the algorithm of the first step, gives the scanning method of the VRP that the client set is one side of distribution being relative to the central warehouse, gives the optimum route of the VRP of the central warehouse1by the above algorithm. The fourth step solves the shortest TSP route of the central warehouse2by the algorithm of the first step, then transforms the above answer, solves the solution using the algorithm of the second and third step and get two solutions. the smaller is the optimum route of the VRP of the central warehouse2.