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

Vehicle Routing Algorithm Based on Spatiotemporal Clustering

作　　者：戚铭尧[1,2] 张金金[1] 任丽[1] 

机构地区：[1]清华大学深圳研究生院物流与交通学部,深圳518055 [2]深圳市物流工程与仿真重点实验室,深圳518055

出　　处：《计算机科学》2014年第3期218-222,共5页Computer Science

基　　金：国家自然科学基金面上项目(71272030);深圳科技计划项目(CXZZ2013032114 5336439);东莞科技计划项目(201010810107)资助

摘　　要：针对带时间窗车辆路径问题,设计了一种同时考虑顾客的时间和空间邻近性的路径改进方法。首先设计了一种顾客间时空距离的表达方式,然后利用遗传算法对顾客点进行时空聚类,并将聚类结果应用于路径调整中,使得顾客尽可能被加入到时空距离近的顾客所在路径中,这样既能有效减小搜索范围,又能更快到达更好的解。以含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.

关 键 词：车辆路径问题 时间窗 时空距离 聚类分析 遗传算法 可变邻域搜索 

分 类 号：O22[理学—运筹学与控制论] TP31[理学—数学]