Exploring the Vehicle Routing Problem with the Simulated Annealing Algorithm

Vehicle routing problem has been widely concerned because of the development of transportation industry, and simulated annealing algorithm as a tool to solve it has also been deeply studied. This work introduces the background information of simulated annealing algorithm and the process of annealing in physics. In order to confirm the effectiveness of simulated annealing algorithm in solving the maximum or minimum value of a function, the author proves that the objective function simulated annealing algorithm almost surely escapes from the local optimal solution and converges to the global optimal solution by using the properties of discrete time Markov chain. Further, traveling salesman problem and two kinds of capacitated vehicle routing problem, which are special cases of vehicle routing problem, are solved by using the simulated annealing algorithm. It proves that simulated annealing algorithm, as a heuristic algorithm, has unique advantages in solving complex optimization problems. Finally, the author analyzes the strengths, disadvantages, and limitations of simulated annealing algorithm and then puts forward an improved measure combining simulated annealing algorithm and genetic algorithm to solve more complex vehicle routing problem, such as heterogeneous vehicle routing problems.