Abstract: Based on the background of goods distribution in e-business environment, a model for solving the problems VRPBTW, i.e., the vehicle routing problems with backhauls and time windows, is developed, and it is analyzed to improve the VNS (variable neighborhood search) algorithm so as to solve the problems. Applying the modified sequential cheapest insertion heuristic proposed originally by Braysy to generating an initial solution for improvement, the algorithm introduces four different local search operators in accordance to VNS mechanism. The results of computational tests including 15 examples were compared with that by conventional VNS and showed that the modified VNS algorithm is effective for solving the problems and greatly outperforms the conventional one.