The work aims to optimize the performance of traditional genetic algorithm (GA) used to solve the vehicle routing problem (VRP) in packaging waste recycling. An improved genetic algorithm (IGA) was put forward. Firstly, in order to improve the quality of initial population, the initial population generation operator based on greedy algorithm was designed; secondly, the crossover and mutation probabilities adaptively adjusted based on fitness values and evolutionary algebras were designed; then, the maximum preserved crossover operator was designed to ensure population diversity. Finally, simulation tests were carried out on an enterprise instance and standard examples. IGA and ant colony algorithm (ACO) were used to get the optimal solution of the example, and IGA ran faster than ACO. The branch and bound algorithm (BBM) and traditional GA could not find the optimal solution of the example. Compared with the BBM, traditional GA and ACO, IGA has better overall performance in solving the VRP problem of packaging waste recycling.