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

Improved Bacterial Foraging Algorithm for Solving Vehicle Routing Optimization Problem with Time Windows

作　　者：李珺[1] 郝丽艳 何奕涛 段钰蓉 LI Jun;HAO Liyan;HE Yitao;DUAN Yurong(School of Electronic and Information Engineering,Lanzhou Jiaotong University,Lanzhou 730070,China)

机构地区：[1]兰州交通大学电子与信息工程学院,兰州730070

出　　处：《计算机工程》2021年第11期44-53,共10页Computer Engineering

基　　金：甘肃省科技厅自然科学基金(1506RJZA084);甘肃省教育厅科研基金(1204-13);兰州市科技局科研基金(2015-2-74)。

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

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

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]