基于GA-ACO的带时间窗车辆路径问题研究
|
摘要
针对传统算法求解带时间窗的车辆路径问题时收敛速度慢、解的质量不高等缺点,借鉴其他改进混合算法的思路,提出了一种性能更优的求解VRPTW的混合算法。算法以改进蚁群算法为主体,插入遗传算法作为局部优化方法,在蚁群算法转移概率的改进中引入时间窗因素、节约距离因子,设置随机变量来优化算法的迭代过程,在信息素更新机制中,定义信息素为标量,构造信息素挥发因子的阶段函数,然后使用遗传算法中的交叉变异算子对蚁群算法得到的较优解进行下一步优化,达到加快算法收敛速度,提高解的质量的目的。仿真实验结果表明:对比相关文献的改进混合算法,该混合算法具有有效性与优越性。
Aiming at the shortcomings of traditional algorithms in solving the vehicle routing problem with time window,such as low convergence speed and subpar solution quality and based on the thinking of other improved hybrid algorithms,we proposed a hybrid algorithm of better performance for solving the VRPTW.The algorithm takes the improved ant colony algorithm as its main body,incorporates the genetic algorithm as the method for local optimization,introduces the time window factor and distance saving factor in the improvement of the transition probability of the ant colony algorithm,and sets random variables to optimize the iterative process of the algorithm.With regard to the pheromone updating mechanism,the pheromone is defined as a scalar,and the phase function of the pheromone volatilization factor is constructed.Then,the cross-mutation operator in the genetic algorithm is used to optimize the better solution obtained through the ant colony algorithm,so as to speed up the convergence of the algorithm and improve the quality of the solution.At the end,a simulation test is used to show the effectiveness and superiority of the hybrid algorithm over the improved hybrid algorithm proposed in relevant related literature.
Aiming at the shortcomings of traditional algorithms in solving the vehicle routing problem with time window,such as low convergence speed and subpar solution quality and based on the thinking of other improved hybrid algorithms,we proposed a hybrid algorithm of better performance for solving the VRPTW.The algorithm takes the improved ant colony algorithm as its main body,incorporates the genetic algorithm as the method for local optimization,introduces the time window factor and distance saving factor in the improvement of the transition probability of the ant colony algorithm,and sets random variables to optimize the iterative process of the algorithm.With regard to the pheromone updating mechanism,the pheromone is defined as a scalar,and the phase function of the pheromone volatilization factor is constructed.Then,the cross-mutation operator in the genetic algorithm is used to optimize the better solution obtained through the ant colony algorithm,so as to speed up the convergence of the algorithm and improve the quality of the solution.At the end,a simulation test is used to show the effectiveness and superiority of the hybrid algorithm over the improved hybrid algorithm proposed in relevant related literature.
引文
[1]饶卫振,金淳,王新华,等.考虑道路坡度因素的低碳VRP问题模型与求解策略[J].系统工程理论与实践,2014,34(8):2 092-2 105.
[2]Hiermann G, Puchinger J, Ropke S, et al. The Electric Fleet Size and Mix Vehicle Routing Problem with Time Windows and Recharging Stations[J]. European Journal of Operational Research,2016,Accepted(3):995-1 018.
[3]郝友文,刘烨.遗传算子在VRP中的应用综述[J].东南大学学报(哲学社会科学版),2015,(S2):85-87.
[4]Yammani C, Maheswarapu S, Matam S K. Optimal placement and sizing of DER's with load models using BAT algorithm[A].International Conference on Circuits, Power and Computing Technologies[C].2013.
[5]刘晓勇,付辉.基于启发式蚁群算法的VRP问题研究[J].计算机工程与应用,2011,47(32):246-248.
[6]方金城,张岐山.粒子群算法在VRP中的应用[J].管理观察,2008,(3):134-135.
[7]朱杰,张培斯,张询影,等.基于改进蚁群算法的多时间窗车辆路径问题[J].计算机技术与发展,2019,(1):1-10.
[8]孙小军,介科伟.求解带时间窗动态车辆路径问题的改进蚁群算法[J].大连理工大学学报,2018,58(5):539-546.
[9]陈成.基于改进遗传算法的带时间窗的多目标配送路径优化[J].信息技术与信息化,2018,(10):48-51.
[10]Sivaramkumar V,Thansekhar M R,Saravanan R,et al.Demonstrating the importance of using total time balance instead of route balance on a multi-objective vehicle routing problem with time windows[J]. International Journal of Advanced Manufacturing Technology,2018,98(5-8):1 287-1 306.
[11]Wenbo Dong,Kang Zhou,Huaqing Qi,et al.A tissue P system based evolutionary algorithm for multi-objective VRPTW[J].Swarm and Evolutionary Computation,2018,39:310-322.
[12]黄震,罗中良,黄时慰.一种带时间窗车辆路径问题的混合蚁群算法[J].中山大学学报(自然科学版),2015,54(1):41-46.
[13]宋强.改进混合遗传算法在MTVRPTW中的建模与优化[J].重庆交通大学学报(自然科学版),2018,37(9):79-86,134.
[14]Keskin M,Bülent catay.A Matheuristic Method for the Electric Vehicle Routing Problem with Time Windows and Fast Chargers[J]. Computers&Operations Research, 2017, 100:172-188.
[15]RaúlBanos,JulioOrtega,Consolación Gil,et al.A hybrid meta-heuristic for multi-objective vehicle routing problems with time windows[J]. Computers&Industrial Engineering,2013,65(2):286-296.
[16]李琳,刘士新,唐加福.改进的蚁群算法求解带时间窗的车辆路径问题[J].控制与决策,2010,25(9):1 379-1 383.
[2]Hiermann G, Puchinger J, Ropke S, et al. The Electric Fleet Size and Mix Vehicle Routing Problem with Time Windows and Recharging Stations[J]. European Journal of Operational Research,2016,Accepted(3):995-1 018.
[3]郝友文,刘烨.遗传算子在VRP中的应用综述[J].东南大学学报(哲学社会科学版),2015,(S2):85-87.
[4]Yammani C, Maheswarapu S, Matam S K. Optimal placement and sizing of DER's with load models using BAT algorithm[A].International Conference on Circuits, Power and Computing Technologies[C].2013.
[5]刘晓勇,付辉.基于启发式蚁群算法的VRP问题研究[J].计算机工程与应用,2011,47(32):246-248.
[6]方金城,张岐山.粒子群算法在VRP中的应用[J].管理观察,2008,(3):134-135.
[7]朱杰,张培斯,张询影,等.基于改进蚁群算法的多时间窗车辆路径问题[J].计算机技术与发展,2019,(1):1-10.
[8]孙小军,介科伟.求解带时间窗动态车辆路径问题的改进蚁群算法[J].大连理工大学学报,2018,58(5):539-546.
[9]陈成.基于改进遗传算法的带时间窗的多目标配送路径优化[J].信息技术与信息化,2018,(10):48-51.
[10]Sivaramkumar V,Thansekhar M R,Saravanan R,et al.Demonstrating the importance of using total time balance instead of route balance on a multi-objective vehicle routing problem with time windows[J]. International Journal of Advanced Manufacturing Technology,2018,98(5-8):1 287-1 306.
[11]Wenbo Dong,Kang Zhou,Huaqing Qi,et al.A tissue P system based evolutionary algorithm for multi-objective VRPTW[J].Swarm and Evolutionary Computation,2018,39:310-322.
[12]黄震,罗中良,黄时慰.一种带时间窗车辆路径问题的混合蚁群算法[J].中山大学学报(自然科学版),2015,54(1):41-46.
[13]宋强.改进混合遗传算法在MTVRPTW中的建模与优化[J].重庆交通大学学报(自然科学版),2018,37(9):79-86,134.
[14]Keskin M,Bülent catay.A Matheuristic Method for the Electric Vehicle Routing Problem with Time Windows and Fast Chargers[J]. Computers&Operations Research, 2017, 100:172-188.
[15]RaúlBanos,JulioOrtega,Consolación Gil,et al.A hybrid meta-heuristic for multi-objective vehicle routing problems with time windows[J]. Computers&Industrial Engineering,2013,65(2):286-296.
[16]李琳,刘士新,唐加福.改进的蚁群算法求解带时间窗的车辆路径问题[J].控制与决策,2010,25(9):1 379-1 383.