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

发布时间：2018-04-02 18:45

本文选题：车辆路径问题　切入点：时间窗　出处：《计算机科学》2014年03期

【摘要】：针对带时间窗车辆路径问题,设计了一种同时考虑顾客的时间和空间邻近性的路径改进方法。首先设计了一种顾客间时空距离的表达方式,然后利用遗传算法对顾客点进行时空聚类,并将聚类结果应用于路径调整中,使得顾客尽可能被加入到时空距离近的顾客所在路径中,这样既能有效减小搜索范围,又能更快到达更好的解。以含1000个点的标准问题集作为算例,计算结果表明,与不采用时空聚类的方法相比,该算法能在更短的时间内取得更好的解,显示了在解决大规模车辆路径问题时具有很好的潜力。
[Abstract]:To solve the vehicle routing problem with time windows, a path improvement method considering both customer time and spatial proximity is proposed.In this paper, we first design a representation of the spatio-temporal distance between customers, and then use genetic algorithm to cluster the customer points in time and space, and apply the clustering results to path adjustment.The customer can be added to the path of the customer who is close to time and space as far as possible, which can not only reduce the search range effectively, but also reach a better solution faster.Taking the standard problem set with 1000 points as an example, the calculation results show that the algorithm can obtain better solution in a shorter time than the method without spatio-temporal clustering.It shows that there is a good potential in solving the large-scale vehicle routing problem.
【作者单位】：清华大学深圳研究生院物流与交通学部;深圳市物流工程与仿真重点实验室;
【基金】：国家自然科学基金面上项目(71272030) 深圳科技计划项目(CXZZ2013032114 5336439) 东莞科技计划项目(201010810107)资助
【分类号】：U492.22;TP18

【共引文献】