The proposed parallel particle swarm optimization(PSO) algorithm combines the fast optimum search ablity of original PSO with probability jump property of simulated annealing(SA).It can avoid trapping to local minima as compared with original PSO and improve the accuracy in the later evolution period.The proposed algorithm was applied to the vehicle routing problem.The experiment results verify that the new algorithm is effective.