Abstract: Vehicle routing problem is a hot topic in the three-dimensional warehouse. When the traditional Tabu search is used to handle the above problem, the quality of the final solution usually depends on the initial solution, which implies that a randomly generated initial solution may reduce the reliability of the algorithm. This paper proposes an improved Tabu search algorithm for this kind of vehicle routing problem by using the simulated annealing algorithm to generate the initial solution so that the dependence of Tabu search on the initial value can be effectively overcome. Two cases of generating the initial value are considered:the one is that the initial values include all messages from beginning location to end location about simulated annealing in an ideal condition; the other is that the initial values ignore the first position and the last position through simulated annealing in an actual condition. The amnesty criterion of Tabu search is assumed to be simulated annealing, which can improve the searching ability of Tabu search algorithm to find shorter vehicle paths under the constraint of the beginning and ending locations. Especially, the proposed algorithm can also give better searching result for the case without the above constraint. Finally, the comparison experiments between the improved Tabu search algorithm in this work and the standard Tabu search algorithm are made with the examples coming from a well-known test library. It is shown from simulation results that the improved algorithm attains greater improvement on the average shortest path and the stability. In addition, the improved algorithm is also applied in the actual three-dimensional warehouse by taking the second algorithm of getting initial solution, whose result is also feasible and meaningful in practical application.