姜 婷



基于改进离散蜂群算法的车辆路径问题求解

姜 婷1,2

(1.安徽经济管理学院 信息工程系，安徽 合肥 230059；2.合肥工业大学 管理学院，安徽 合肥 230009)

采用一种改进的人工蜂群算法(IABC)求解标准车辆路径问题. 针对基本人工蜂群算法易陷入局部极小、收敛较慢等缺陷，提出了6种邻域生成策略，并基于此设计了新的局部搜索算法. 引领蜂和跟随蜂根据该算法在邻域空间内更新当前解. 通过小规模和大规模算例的仿真实验，将本文算法与其它智能算法以及基本人工蜂群算法进行了比较，验证了本文提出的算法无论在有效性还是稳定性上都具有良好的效果.

车辆路径问题；离散蜂群算法；邻域生成策略；局部搜索算法

随着我国经济进入新常态，电子商务和物流业迎来了新一轮的发展机遇，物流配送是其中的重要环节. 车辆路径问题(Vehicle Routing Problem, VRP)是这一环节中非常关键的研究内容，属于组合优化领域和运筹学研究的热点和重点. 该问题是一个NP难题，问题规模较大时只能求得近似解，可以采用群智能优化算法进行求解. 很多学者在这方面取得一定的研究成果，如文献[1][2]采用粒子群算法，文献[3][4][5]采用遗传算法，文献[6][7][8]采用蚁群算法分别研究了物流配送中的车辆路径问题.

人工蜂群算法(Artificial Bee Colony Algorithm, ABC)由Karboga等模拟工蜂的采蜜行为提出[9]. 该算法参数较少、鲁棒性强、编码较简单，适用于绝大多数的目标优化问题[10-12]. 已有的研究表明，基本人工蜂群算法存在一些不足，如容易陷入局部极小、收敛较慢等[13]. 近几年，有学者将人工蜂群算法应用于车辆路径问题的求解中. 比如文献[14]采用改进了迭代策略和邻域构成的人工蜂群算法来求解最优路径选择；……