The paper is focused on the Min-Max Vehicle Routing Problem. And solve this type of problems utilizing improved tabu search algorithm from the overall situation. According to the features of the problem, the essay centered the longest route to construct neighborhood structure. For the operation, 1-exchange and 2-opt* were applied, it can also fasten the speed of convergence, and boost the search efficiency. Finally, the good performance of this algorithm can be proved by experiment calculation and concrete examples.