This work aimed to overcome the shortcoming of standard intelligent water drop (IWD) algorithm in soil content updating and improve its global search ability to solve the vehicle scheduling problem (VSP). Based on IWD algorithm, an improved intelligent water drop (IIWD) algorithm was designed to solve VSP. Firstly, a concept of sub optimal solution set was introduced, and the soil contents in the optimal solution set and sub optimal solution set were updated after every iteration. Secondly, a chaos disturbance mechanism was designed, and the individuals fallen into the local optimal solution were disturbed by it. At last, the IIWD algorithm was used to solve the vehicle scheduling problem. The optimal scheduling scheme with 8 distribution paths containing a total traveling length of 842.60 km was obtained, which saved 98.75 and 18.16 km comparing with the genetic algorithm (GA) and IWD algorithm. In conclusion, compared with GA and IWD algorithm, the IIWD algorithm converged faster and had stronger global optimization ability when used to solve the vehicle scheduling problem.