An Improved Hybrid Ant Colony Algorithm for Bi-objective VRPTW
[1]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]
Copy
Journal of Zhengzhou University (Engineering Science)[ISSN
1671-6833/CN
41-1339/T] Volume:
41
Number of periods:
2020 04
Page number:
52-58
Column:
Public date:
2020-08-12
- Title:
- An Improved Hybrid Ant Colony Algorithm for Bi-objective VRPTW
- CLC:
- -
- DOI:
- 10.13705/j.issn.1671-6833.2020.04.004
- 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.
- Similar References:
Memo
-
Last Update:
2020-10-06