Abstract: The paper describes the mathematics model of the vehicle scheduling problem with soft time windows. A hybrid differential evolution algorithm combining differential evolution algorithm and simulated annealing algorithm is proposed to solve the vehicle scheduling problem.It maks full of preventing into local minimization in simulated annealing and differential evolution algorithm’s advantages and avoids effectively the common defects of early convergence.The computational results demonstrates that the high quality solutions to the vehicle scheduling problem can be obtained by using the hybrid differential evolution algorithm，and the algorithm is also efficient and robust.So，it is an efficient method for vehicle scheduling problem.