【摘要】 为求解带时间窗的车辆路径问题(VRPTW),提出一种改进的细菌觅食算法。将待配送的客户点依据地理位置进行K-means聚类,使得到的分类结果在满足时间窗的要求下,按顺序插入配送路径的最佳位置中,构造VRPTW问题的初始解,同时通过结合趋化操作与大邻域搜索中的removal算子进行距离寻优,扩大算法搜索范围并提高运行效率。实验结果表明,在规定时间窗内,改进算法能合理安排配送路径并最小化总配送成本。更多还原

【Abstract】 This paper proposes an improved Bacterial Foraging Algorithm(BFA)to solve the Vehicle Routing Problem with Time Windows(VRPTW). The to-be-distributed customer points are clustered by K-means according to the geographical location,and the classification results are inserted into the optimal location of the distribution path in order within the time window,so the initial solution of the problem is constructed.Then the chemotaxis operation is combined with the removal operator in Large Neighborhood Search(LNS)for optimization,which expands the search range and improves the operation efficiency of the algorithm. Experimental results show that the algorithm can shorten the distribution path and minimize the overall distribution cost within the time window.更多还原