To solve the problem of vehicle routing with waste packaging time, firstly the mathematical model of the problem was established, the tabu search algorithm and memetic algorithm were proposed to solve the problem, and the hill climbing algorithm and the genetic algorithm were selected for comparison. The memetic algorithm was the combination of the hill climbing algorithm and the genetic algorithm. The experiment showed that: in terms of the quality of the solution, the tabu search algorithm and the memetic algorithm were much better than the other two algorithms, but in terms of running time, the tabu search algorithm, the hill climbing algorithm and the genetic algorithm were far superior to the memetic algorithm.