求解带时间窗车辆路径优化问题的改进细菌觅食算法

作者：李珺; 郝丽艳; 何奕涛; 段钰蓉

来源：计算机工程, 2021, 47(11): 44-53.

DOI：10.19678/j.issn.1000-3428.0059260

• 车辆路径问题
• 时间窗
• 细菌觅食算法
• 大邻域搜索
• 贪婪插入法

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

• 单位
  兰州交通大学