The Vehicle Scheduling Problem (VSP) is a critical topic in the field of route planning and routing, with the Vehicle Scheduling Problem with Time Windows (VSPTW) being particularly valuable due to its complex constraints. To address the limitations of the Tabu Search algorithm (TS), such as parameter sensitivity, lack of robustness, susceptibility to local optima, and slow convergence, this paper proposes an Improved Tabu Search algorithm (ITS). By introducing a Cluster First Route Second (CFRS) method and an enhanced savings algorithm to generate high-quality initial solutions, combined with an optimized tabu search strategy, the proposed approach significantly improves efficiency and effectiveness. Experimental comparisons show that, compared with Particle Swarm Optimization (PSO) and Genetic Algorithm (GA), the proposed method achieves superior performance in terms of optimization accuracy and stability, demonstrating its potential in solving complex vehicle scheduling problems.