To address the multi-objective vehicle routing problem of fresh produce cold chain logistics with the constraints of capacity and soft time windows, a two-objective model which aims at minimizing total cost and maximizing customer satisfaction is established. In order to solve this problem, the epsilon constraint method is used, a Genetic-Ant colony algorithm is designed which based on ant colony algorithm and the crossover and mutation operators is introduced. The combination of deterministic selection and pseudo-random proportion were used for the state transfer and the total amount of pheromone is optimized by piecewise function. An actual calculation example is solved by the proposed algorithm and the genetic algorithm and ant colony algorithm respectively. Comparison results show that the proposed model and algorithm is practical and effective.