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

摘要：

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

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

所属期刊栏目：41

分类号：O22;TP31(运筹学)

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

在线出版日期：2014-04-16（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：218-222