[1]朱晓东,王鼎.求解双目标VRPTW的改进混合蚁群算法[J].郑州大学学报(工学版),2020,41(04):52-58.[doi:10.13705/j.issn.1671-6833.2020.04.004]
　ZHU Xiaodong,WANG Ding.An Improved Hybrid Ant Colony Algorithm for Bi-objective VRPTW[J].Journal of Zhengzhou University (Engineering Science),2020,41(04):52-58.[doi:10.13705/j.issn.1671-6833.2020.04.004]
点击复制

求解双目标VRPTW的改进混合蚁群算法()
分享到：

《郑州大学学报(工学版)》[ISSN:1671-6833/CN:41-1339/T]

卷:
41
期数:
2020年04期
页码:
52-58
栏目:
出版日期:
2020-08-12

文章信息/Info

Title:
An Improved Hybrid Ant Colony Algorithm for Bi-objective VRPTW
作者:
朱晓东; 王鼎
郑州大学电气工程学院
Author(s):
ZHU Xiaodong; WANG Ding
School of Electrical Engineering, Zhengzhou University
关键词:
蚁群算法; 车辆路径问题; 时间窗; 双目标
Keywords:
ant colony algorithm; vehicle routing problem; time window; bi-objective
DOI:
10.13705/j.issn.1671-6833.2020.04.004
文献标志码:
A
摘要:
为了解决基本混合蚁群算法在求解大规模带时间窗车辆路径问题（VRPTW）时存在的问题，提出一种改进的双目标混合蚁群算法。首先在节点选择上使用周边选择策略提升选择效率，并提出一种首节点选择策略来加速算法收敛；其次在信息素叠加公式上增加了和车辆数有关的惩罚函数，使算法在优化距离的同时优化车辆数；最后提出一种新的局部优化算，通过将节点数较少的线路中的节点插入到其他线路来提升车辆利用率。算法在Solomon标准数据集上的实验和对比，说明了改进的算法具有搜索能力强，收敛速度快，鲁棒性强等优点。
Abstract:
In order to solve the problems of basic hybrid ant colony algorithm in solving large-scale VRPTW,an improved bi-objective hybrid ant colony algorithm was proposed.Firstly,the peripheral selection strategy was used to improve the selection efficiency,and a first node selection strategy was proposed to accelerate the convergence of the algorithm.Secondly,a penalty function related to the number of vehicles was added to the pheromone superposition formula to optimize the number of vehicles while optimizing the distance.Finally,a new local optimization algorithm was proposed to improve vehicle utilization and expand the neighborhood solution by inserting nodes in routes with fewer nodes into other routes.Experiments and comparisons on Solomon benchmark problems showed that the improved algorithm had the advantages of strong search ability,fast convergence speed and strong robustness.

参考文献/References:

[1] DANTZIG G B,RAMSER J H.The truck dispatching problem[J].Management science,1959,6(1):80-91.

[2] MOHAMMED M A,GANI M K A,HAMED R I,et al.Solving vehicle routing problem by using improved genetic algorithm for optimal solution[J].Journal of computational science,2017,21:255-262.
[3] DE OLIVEIRA DA COSTA P R,MAUCERI S,CARROLL P,et al.A genetic algorithm for a green vehicle routing problem[J].Electronic notes in discrete mathematics,2018,64:65-74.
[4] 汪慎文,杨锋,徐亮,等.离散差分进化算法求解共享单车调度问题[J].郑州大学学报(工学版),2019,40(4):48-53.
[5] 崔岩,张子祥,时新,等.考虑顾客时间紧迫度的生鲜电商配送路径优化问题[J].郑州大学学报(工学版),2017,38(6):59-63.
[6] TEYMOURIAN E,KAYVANFAR V,KOMAKI G M,et al.Enhanced intelligent water drops and cuckoo search algorithms for solving the capacitated vehicle routing problem[J].Information sciences,2016,334:354-378.
[7] DORIGO M,MANIEZZO V,COLORNI A.Ant system:optimization by a colony of cooperating agents[J].IEEE transactions on systems,man and cybernetics,part B (cybernetics),1996,26(1):29-41.
[8] YU B,YANG Z Z,YAO B Z.A hybrid algorithm for vehicle routing problem with time windows[J].Expert systems with applications,2011,38(1):435-441.
[9] DING Q L,HU X P,SUN L J,et al.An improved ant colony optimization and its application to vehicle routing problem with time windows[J].Neurocomputing,2012,98:101-107.
[10] 朱杰,张培斯,张询影,等.基于改进蚁群算法的多时间窗车辆路径问题[J].计算机技术与发展,2019,29(1):102-105.
[11] 刘云,张惠珍.多目标带时间窗的车辆路径问题的单亲遗传混合蚁群算法[J].公路交通科技,2016,33(6):95-100,106.
[12] 柴获,何瑞春,苏江省,等.求解双目标带时间窗车辆路径问题的蚁群算法[J].交通运输系统工程与信息,2018,18(4):156-162.
[13] 孙小军,介科伟.求解带时间窗动态车辆路径问题的改进蚁群算法[J].大连理工大学学报,2018,58(5):539-546.
[14] 葛斌,韩江洪,魏臻,等.求解带时间窗车辆路径问题的动态混合蚁群优化算法[J].模式识别与人工智能,2015,28(7):641-650.
[15] CLARKE G,WRIGHT J W.Scheduling of vehicles from a central depot to a number of delivery points[J].Operations research,1964,12(4):568-581.
[16] SOLOMON M M.Algorithms for the vehicle routing and scheduling problems with time window constraints[J].Operations research,1987,35(2):254-265.
[17] GHOSEIRI K,GHANNADPOUR S F.Multi-objective vehicle routing problem with time windows using goal programming and genetic algorithm[J].Applied soft computing,2010,10(4):1096-1107.

相似文献/References:

[1]马欢张建伟赵进超.求解VRPSDP的变邻域混合遗传算法[J].郑州大学学报(工学版),2015,36(03):120.[doi:10.3969/ j. issn.1671 -6833.2015.03.026]
　MA Huan,ZHANG Jian-wei,ZHAO Jin-chao,et al.A Hybrid Genetic and Variable Neighborhood Descent Algorithm for VehicleRouting Problem with Simultaneous Delivery and Pickup[J].Journal of Zhengzhou University (Engineering Science),2015,36(04):120.[doi:10.3969/ j. issn.1671 -6833.2015.03.026]
[2]常玉林,汪小渟,张鹏.改进蚁群算法在交通分配模型中的应用[J].郑州大学学报(工学版),2017,38(02):41.[doi:10.13705/j.issn.1671-6833.2017.02.010]
　Chang Yulin,Wang Xiaoting,Zhang Peng.Modified Ant Colony Algorithm and its Application on Traffic Assignment Model[J].Journal of Zhengzhou University (Engineering Science),2017,38(04):41.[doi:10.13705/j.issn.1671-6833.2017.02.010]
[3]王俊英,颜芬芬,陈鹏,等.基于概率自适应蚁群算法的云任务调度方法[J].郑州大学学报(工学版),2017,38(04):51.[doi:10.13705/j.issn.1671-6833.2017.01.018]
　Wang Junying,Yan Fenfen,Chen Peng,et al.Task Scheduling Method Based on Probabilistic Adaptive Ant Colony Optimization in Cloud Computing[J].Journal of Zhengzhou University (Engineering Science),2017,38(04):51.[doi:10.13705/j.issn.1671-6833.2017.01.018]
[4]焦留成,邵创创,程志平.一种求解连续空间约束优化问题的蚁群算法[J].郑州大学学报(工学版),2015,36(01):20.[doi:10.3969/j. issn.1671 -6833.2015.01.005]
　JIAO Liu-cheng,SHAO Chuang-chuang,CHENG Zhi-ping.Ant Colony Algorithm for Solving Continuous Space ConstrainedOptimization Problems[J].Journal of Zhengzhou University (Engineering Science),2015,36(04):20.[doi:10.3969/j. issn.1671 -6833.2015.01.005]
[5]崔岩,张子祥,时新,等.考虑顾客时间紧迫度的生鲜电商配送路径优化问题[J].郑州大学学报(工学版),2017,38(06):59.[doi:10.13705/j.issn.1671-6833.2017.06.008]
　Cui Yan,Zhang Zixiang,Shi Xin Wang Xiaoliang,et al.Fresh Agricultural E-commerce Product Routing Problem Considering Equally Desirable of Customer[J].Journal of Zhengzhou University (Engineering Science),2017,38(04):59.[doi:10.13705/j.issn.1671-6833.2017.06.008]
[6]汪慎文,杨锋,徐亮,等.离散差分进化算法求解共享单车调度问题[J].郑州大学学报(工学版),2019,40(04):9.[doi:10.13705/j.issn.1671-6833.2019.04.022]
　Wang Shenwen,Yang Feng,Xu Liang,et al.Discrete differential evolution algorithm for solving shared bicycle scheduling problem[J].Journal of Zhengzhou University (Engineering Science),2019,40(04):9.[doi:10.13705/j.issn.1671-6833.2019.04.022]
[7]靳文舟,邓钦原,郝小妮,等.改进人工蜂群算法的农村DRT路径优化研究[J].郑州大学学报(工学版),2021,42(04):84.
　JIN Wenzhou,DENG Qinyuan,HAO Xiaoni,et al.Research on Route Optimization of Rural DRT Based on Improved ABC Algorithm[J].Journal of Zhengzhou University (Engineering Science),2021,42(04):84.

更新日期/Last Update: 2020-10-06