求解车辆路径问题的人工蜂群算法

J4 ›› 2014, Vol. 36 ›› Issue (06): 1088-1094.

求解车辆路径问题的人工蜂群算法

王志刚，夏慧明

（南京师范大学泰州学院数学科学与应用学院，江苏泰州 225300）

收稿日期:2012-10-10 修回日期:2013-01-21 出版日期:2014-06-25 发布日期:2014-06-25
基金资助:
江苏省高等学校大学生实践创新训练计划项目(2012JSSPITP3029)；南京师范大学泰州学院资助项目(Q201232)

An artificial bee colony algorithm for the vehicle routing problem

WANG Zhigang，XIA Huiming

（School of Mathematics,Taizhou College,Nanjing Normal University,Taizhou 225300,China）

Received:2012-10-10 Revised:2013-01-21 Online:2014-06-25 Published:2014-06-25

摘要/Abstract

摘要：

采用人工蜂群算法对车辆路径问题进行求解，给出食物源的自然数编码方法，并采用邻域倒位方法生成候选食物源。应用算法求解了多个车辆路径问题的实例，并将结果与其它一些启发式算法进行了比较和分析。计算结果表明，人工蜂群算法可以有效求解车辆路径问题，同时也为算法求解其它一些组合优化问题提供了有益思路。

关键词: 车辆路径问题, 组合优化, 人工蜂群算法, 邻域倒位

Abstract:

An artificial bee colony algorithm is proposed to solve the vehicle routing problem. The algorithm gives a natural number coding method for the food source and adopts neighborhood inversion to produce a candidate food source. It is applied to solve multiple instances of the vehicle routing problem. It is compared with other heuristic algorithms on a set of benchmark instances, and the results show the effectiveness of the proposed artificial bee colony algorithm, which presents a new vision for other combination optimization problems.

Key words: vehicle routing problem;combination optimization;artificial bee colony algorithm;neighborhood inversion

王志刚，夏慧明. 求解车辆路径问题的人工蜂群算法[J]. J4, 2014, 36(06): 1088-1094.

WANG Zhigang，XIA Huiming. An artificial bee colony algorithm for the vehicle routing problem [J]. J4, 2014, 36(06): 1088-1094.

[1]	王扬, 陈智斌. 一种求解CVRP的动态图转换模型[J]. 计算机工程与科学, 2023, 45(05): 859-868.
[2]	庄鹤林, 杨火根, 夏小云, 廖伟志. 关于矩阵乘法问题的人工蜂群优化算法研究[J]. 计算机工程与科学, 2021, 43(12): 2131-2138.
[3]	张瑾, 洪莉, 戴二壮. 求解带容量和时间窗约束车辆路径问题的改进蝙蝠算法[J]. 计算机工程与科学, 2021, 43(08): 1479-1487.
[4]	包敏泽, 胡秀婷, 谢玉莹, 蒋波. 基于人工蜂群算法的p-center问题求解算法[J]. 计算机工程与科学, 2020, 42(06): 1127-1133.
[5]	衡红军, 戚馨桐. 考虑任务均衡的加油车动态调度问题[J]. 计算机工程与科学, 2020, 42(05): 923-930.
[6]	赵凤1,2，孔令润1,2，马改妮1,2. 多目标粒子群和人工蜂群混合优化的阈值图像分割算法[J]. 计算机工程与科学, 2020, 42(02): 281-290.
[7]	宋强. Beam-PSO优化算法在多行程车辆路径问题的应用[J]. 计算机工程与科学, 2019, 41(10): 1882-1891.
[8]	常小刚1，赵红星2. 动态调节因子的邻域搜索人工蜂群算法[J]. 计算机工程与科学, 2019, 41(04): 673-681.
[9]	李进生，蒙江，童名文. 基于分布式遗传算法的水质传感器布置优化研究[J]. 计算机工程与科学, 2019, 41(03): 545-550.
[10]	覃远年，梁仲华. 蚁群算法研究与应用的新进展[J]. 计算机工程与科学, 2019, 41(01): 173-184.
[11]	周忠宝1,刘悦悦1,2,金倩颖1,肖和录1,程旭曼3. 基于FDH的分区域多目标遗传算法[J]. 计算机工程与科学, 2018, 40(07): 1295-1302.
[12]	高雷阜,王飞. 基于混沌更新策略的蜂群算法在SVM参数优化中的应用[J]. 计算机工程与科学, 2017, 39(01): 199-205.
[13]	李锋刚1,2，骆林1,2，陈亚波1,2,蒋祥飞1,2. 求解均值-CVaR投资组合模型的改进粒子群算法[J]. 计算机工程与科学, 2016, 38(09): 1870-1877.
[14]	徐曼舒，汪继文，邱剑锋，王心灵. 基于改进人工蜂群的模糊C-均值聚类算法[J]. J4, 2016, 38(06): 1238-1243.
[15]	黄文明，徐双双，邓珍荣，雷茜茜. 改进人工蜂群算法优化RBF神经网络的短时交通流预测[J]. J4, 2016, 38(04): 713-719.