Abstract: A route improvement method that considers spatial and temporal features simultaneously was proposed to solve vehicle routing problem with time windows．A spatiotemporal representation of vehicle routes was presented to measure the spatiotemporal distance between two customers．Then,a genetic algorithm was designed to cluster the customers into a few groups according to spatiotemporal distances．The resulting customer groups were then used for route adjustment:if a customer was moved to another route,only the nearby routes were searched and considered．By this means the search space is dramatically reduced．The calculation on 1000-customer examples designed by Gehring and Homberger shows that the proposed algorithm can get better solution in shorter time.

Key words: Vehicle routing problem,Time windows,Spatiotemporal distance,Clustering analysis,Genetic algorithm,Variable neighborhood search