This paper presents an adaptive weighting-based local search (AWLS) algorithm for solving the vehicle routing problem with time windows (VRPTW), focusing on minimizing the number of routes. AWLS improves the ejection pool framework by adopting an adaptive weighting technique to diversify the search. First, it adjusts the penalties on customers when both inserting and ejecting them into and from the routes to prevent frequently moving the same customer. Second, we introduce route weighting in the route repairing procedure to encourage paying more attention to corrupted routes that persist for a long time. Third, we design a new objective function for identifying the best set of customers to eject, along with several acceleration strategies. Experimental results on 300 Gehring and Homberger’s benchmarks show that our AWLS algorithm solves 247 instances to optimality, matches the state-of-the-art route minimization algorithms in significantly less runtime, and improves the best-known results for two instances in the literature.