作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2021, Vol. 47 ›› Issue (11): 44-53. doi: 10.19678/j.issn.1000-3428.0059260

• 人工智能与模式识别 • 上一篇    下一篇

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

李珺, 郝丽艳, 何奕涛, 段钰蓉   

  1. 兰州交通大学 电子与信息工程学院, 兰州 730070
  • 收稿日期:2020-08-14 修回日期:2020-11-08 发布日期:2020-11-19
  • 作者简介:李珺(1974-),女,副教授、博士,主研方向为智能计算、图像处理;郝丽艳、何奕涛、段钰蓉,硕士研究生。
  • 基金资助:
    甘肃省科技厅自然科学基金(1506RJZA084);甘肃省教育厅科研基金(1204-13);兰州市科技局科研基金(2015-2-74)。

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

LI Jun, HAO Liyan, HE Yitao, DUAN Yurong   

  1. School of Electronic and Information Engineering, Lanzhou Jiaotong University, Lanzhou 730070, China
  • Received:2020-08-14 Revised:2020-11-08 Published:2020-11-19

摘要: 为求解带时间窗的车辆路径问题(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.

Key words: Vehicle Routing Problem(VRP), time window, Bacterial Foraging Algorithm(BFA), large neighborhood search, greedy insertion method

中图分类号: