基于时空聚类的带时间窗车辆路径规划算法

Vehicle Routing Algorithm Based on Spatiotemporal Clustering

针对带时间窗车辆路径问题,设计了一种同时考虑顾客的时间和空间邻近性的路径改进方法。首先设计了一种顾客间时空距离的表达方式,然后利用遗传算法对顾客点进行时空聚类,并将聚类结果应用于路径调整中,使得顾客尽可能被加入到时空距离近的顾客所在路径中,这样既能有效减小搜索范围,又能更快到达更好的解。以含1000个点的标准问题集作为算例,计算结果表明,与不采用时空聚类的方法相比,该算法能在更短的时间内取得更好的解,显示了在解决大规模车辆路径问题时具有很好的潜力。

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.