For VRP with time windows (VRPTW) solved by conventional cluster‐first and route‐second approach, temporal information is usually considered with vehicle routing but ignored in the process of clustering. We propose an alternative approach based on spatiotemporal partitioning to solving a large‐scale VRPTW, considering jointly the temporal and spatial information for vehicle routing. A spatiotemporal representation for the VRPTW is presented that measures the spatiotemporal distance between two customers. The resulting formulation is then solved by a genetic algorithm developed for k‐medoid clustering of large‐scale customers based on the spatiotemporal distance. The proposed approach showed promise in handling large scale networks.
