Abstract: In order to improve the performance of particle swarm optimization algorithm (PSO), a new multiphases particle swarm optimization algorithm (MPSO) is proposed in this paper, which is further applied to the optimization problem of a vehicle scheduling with soft time windows. By means of the idea of parallel search, the detailed procedure of the MPSO algorithm is given for solving vehicle scheduling problem with soft time windows. The simulation results show that the proposed MPSO is feasible for the problem of vehicle scheduling with soft time windows.