A new dynamic vehicle scheduling algorithm with changeable time window is presented. This algorithm can consider both bespoken demand and real-time demand. The initial routings are constructed by insertion algorithm, and improved by tabu search algorithm. The time window adjusting policy is presented to allow assigning other feasible time windows for customers. The simulation results show that the algorithm can reduce the number of rejected customers significantly compared with the algorithm with hard constraints of time window. The algorithm can deal with real-time demand dynamically, and the tabu search can improve the initial solution effectively and save traveling cost.