基于Spark的改进蚁群算法对带时间窗车辆路径问题的求解
|
摘要
为应对大数据时代对带时间窗车辆路径问题(VRPTW)的实时求解要求,提出基于Spark平台的改进蚁群算法.在算法层面,利用改进的状态转移规则和轮盘赌选择机制构建初始解,结合k-opt邻域搜索进行路径构建优化,改进最大最小蚁群算法中的信息素更新策略;在实现层面,利用Spark提供的API对蚁群RDD进行操作,实现蚁群分布式并行求解.在标准算例Solomon benchmark和Gehring&Homberger benchmark的实验结果表明,该算法在大规模问题的求解精度和速度上有明显提升.
In order to cope with the real-time solution requirements of the Vehicle Routing Problem with Time Window(VRPTW) in the era of big data, this study proposed an improved parallel ant colony algorithm based on Spark platform.At the algorithm level, the improved state transition rule and roulette selection mechanism are used to construct the initial solution, and the k-opt local search is used to optimize the path construction. In addition, the improved pheromone update strategy of max-min ant colony algorithm is applied. At the implement level, the ant colony is encapsulated into RDD,which is operated by Spark API to realize distributed construction solution. The experimental results of the Solomon benchmark and Gehring & Homberger benchmark show that the proposed algorithm can improve the accuracy and speed of large-scale problems.
In order to cope with the real-time solution requirements of the Vehicle Routing Problem with Time Window(VRPTW) in the era of big data, this study proposed an improved parallel ant colony algorithm based on Spark platform.At the algorithm level, the improved state transition rule and roulette selection mechanism are used to construct the initial solution, and the k-opt local search is used to optimize the path construction. In addition, the improved pheromone update strategy of max-min ant colony algorithm is applied. At the implement level, the ant colony is encapsulated into RDD,which is operated by Spark API to realize distributed construction solution. The experimental results of the Solomon benchmark and Gehring & Homberger benchmark show that the proposed algorithm can improve the accuracy and speed of large-scale problems.
引文
1郎茂祥.配送车辆优化调度模型与算法.北京:电子工业出版社,2009.
2Solomon MM.Algorithms for the vehicle routing and scheduling problems with time window constraints.Operations Research,1987,35(2):254-265.[doi:10.1287/opre.35.2.254]
3Dorigo M,Maniezzo V,Colorni A.Ant system:Optimization by a colony of cooperating agents.IEEETransactions on Systems,Man,and Cybernetics,Part B,1996,26(1):29-41.
4Jin NB,Rahmat-Samii Y.Particle swarm optimization for antenna designs in engineering electromagnetics.Journal of Artificial Evolution and Applications,2008:9.
5Goldberg DE.Genetic algorithms in search,optimization,and machine learning.Upper Saddle River,New Jersey:Addison-Wesley,1989.
6陈迎欣.基于改进蚁群算法的车辆路径优化问题研究.计算机应用研究,2012,29(6):2031-2034.[doi:10.3969/j.issn.1001-3695.2012.06.007]
7李琳,刘士新,唐加福.改进的蚁群算法求解带时间窗的车辆路径问题.控制与决策,2010,25(9):1379-1383.
8董攀.带时间窗车辆路径问题的蚁群算法改进[硕士学位论文].长沙:长沙理工大学,2014.
9Helsgaun K.An effective implementation of the Lin-Kernighan traveling salesman heuristic.European Journal of Operational Research,2000,126(1):106-130.[doi:10.1016/S0377-2217(99)00284-2]
10崔文.大规模多配送中心车辆路径问题研究[硕士学位论文].济南:山东大学,2012.
11吴越钟.改进的Lin-Kernighan局部搜索算法和杂交算法在旅行商问题中的应用[硕士学位论文].合肥:中国科学技术大学,2016.
12葛斌.求解车辆路径问题的蚁群优化算法研究及应用[博士学位论文].合肥:合肥工业大学,2016.
13丁秋雷.带有时间窗的车辆路径问题的混合蚁群算法研究[硕士学位论文].大连:大连理工大学,2006.
14王颖,谢剑英.一种自适应蚁群算法及其仿真研究.系统仿真学报,2002,14(1):31-33.[doi:10.3969/j.issn.1004-731X.2002.01.010]
15Nalepa J,Czech ZJ.A parallel memetic algorithm to solve the vehicle routing problem with time windows.arXiv:1402.6942,2014.
16郭宝恩.基于Spark的蚁群算法在物流配送路径优化问题中的应用研究.信息与电脑(理论版),2018,(3):50-52.
17王诏远,王宏杰,邢焕来,等.基于Spark的蚁群优化算法.计算机应用,2015,35(10):2777-2780,2797.
18金淳,张雨,王聪.带时间窗车辆路径问题的分布式多agent蚁群算法.计算机应用研究,2018,35(3):666-670.
2Solomon MM.Algorithms for the vehicle routing and scheduling problems with time window constraints.Operations Research,1987,35(2):254-265.[doi:10.1287/opre.35.2.254]
3Dorigo M,Maniezzo V,Colorni A.Ant system:Optimization by a colony of cooperating agents.IEEETransactions on Systems,Man,and Cybernetics,Part B,1996,26(1):29-41.
4Jin NB,Rahmat-Samii Y.Particle swarm optimization for antenna designs in engineering electromagnetics.Journal of Artificial Evolution and Applications,2008:9.
5Goldberg DE.Genetic algorithms in search,optimization,and machine learning.Upper Saddle River,New Jersey:Addison-Wesley,1989.
6陈迎欣.基于改进蚁群算法的车辆路径优化问题研究.计算机应用研究,2012,29(6):2031-2034.[doi:10.3969/j.issn.1001-3695.2012.06.007]
7李琳,刘士新,唐加福.改进的蚁群算法求解带时间窗的车辆路径问题.控制与决策,2010,25(9):1379-1383.
8董攀.带时间窗车辆路径问题的蚁群算法改进[硕士学位论文].长沙:长沙理工大学,2014.
9Helsgaun K.An effective implementation of the Lin-Kernighan traveling salesman heuristic.European Journal of Operational Research,2000,126(1):106-130.[doi:10.1016/S0377-2217(99)00284-2]
10崔文.大规模多配送中心车辆路径问题研究[硕士学位论文].济南:山东大学,2012.
11吴越钟.改进的Lin-Kernighan局部搜索算法和杂交算法在旅行商问题中的应用[硕士学位论文].合肥:中国科学技术大学,2016.
12葛斌.求解车辆路径问题的蚁群优化算法研究及应用[博士学位论文].合肥:合肥工业大学,2016.
13丁秋雷.带有时间窗的车辆路径问题的混合蚁群算法研究[硕士学位论文].大连:大连理工大学,2006.
14王颖,谢剑英.一种自适应蚁群算法及其仿真研究.系统仿真学报,2002,14(1):31-33.[doi:10.3969/j.issn.1004-731X.2002.01.010]
15Nalepa J,Czech ZJ.A parallel memetic algorithm to solve the vehicle routing problem with time windows.arXiv:1402.6942,2014.
16郭宝恩.基于Spark的蚁群算法在物流配送路径优化问题中的应用研究.信息与电脑(理论版),2018,(3):50-52.
17王诏远,王宏杰,邢焕来,等.基于Spark的蚁群优化算法.计算机应用,2015,35(10):2777-2780,2797.
18金淳,张雨,王聪.带时间窗车辆路径问题的分布式多agent蚁群算法.计算机应用研究,2018,35(3):666-670.