一种基于复杂网络的多厢车辆配送路径优化算法
|
摘要
寻找复杂配送网络中带有容量约束的多厢车辆优化路径(MCVRP)具有很强的现实意义。将局部搜索方法与果蝇优化算法相结合,提出混合果蝇优化算法(HFOA)来解决这一问题。在该算法中,采用随机方法构造初始可行解,利用路径吸引力概率函数创建果蝇飞行路径方案,选用最优方案更新配送网络的轨迹强度。为了扩大搜索范围、提高算法质量,使用2-OPT、交换和插入3个局部搜索方法优化果蝇群的飞行路径方案。研究发现,HFOA可以有效缩短多厢车辆的最优路径长度,从而使得混合果蝇算法能够产生较好的路径规划方案。并且,在大规模复杂网络上效果更好。基于随机网络、小世界网络或无标度网络的仿真实验发现,网络的平均密度、关键"长程链接"和网络规模对配送路径长度都会产生显著影响。
It is of great practical significance to search capacity constrained optimization multi-compartment vehicle routing problem(MCVRP) in complex distribution networks. In this paper, a hybrid fly optimization algorithm(HFOA) was proposed to solve this problem by combining the local search method with the fly optimization algorithm. In the HFOA proposed, first, the initial feasible solution of MCVRP was constructed by using the stochastic method. Next, from the initial solution, the path probability function was used to create the fruit fly path. Then, three local search methods were used to optimize the path, and the optimal solution was used to update the trajectory of the distribution network. In order to expand the search scope and improve the quality of the algorithm, three local search methods, 2-OPT, switching, and insertion, were used to optimize the path of fly swarm. It is found that the HFOA proposed can effectively shorten the optimal path of multi-compartment vehicles, producing better path planning schemes and achieving better results on large-scale complex networks. The simulation experiments based on stochastic networks, small world networks, or scale-free networks show that the average density of networks, the key "long-distance links" and the size of networks have significant effects on the length of distribution routes.
It is of great practical significance to search capacity constrained optimization multi-compartment vehicle routing problem(MCVRP) in complex distribution networks. In this paper, a hybrid fly optimization algorithm(HFOA) was proposed to solve this problem by combining the local search method with the fly optimization algorithm. In the HFOA proposed, first, the initial feasible solution of MCVRP was constructed by using the stochastic method. Next, from the initial solution, the path probability function was used to create the fruit fly path. Then, three local search methods were used to optimize the path, and the optimal solution was used to update the trajectory of the distribution network. In order to expand the search scope and improve the quality of the algorithm, three local search methods, 2-OPT, switching, and insertion, were used to optimize the path of fly swarm. It is found that the HFOA proposed can effectively shorten the optimal path of multi-compartment vehicles, producing better path planning schemes and achieving better results on large-scale complex networks. The simulation experiments based on stochastic networks, small world networks, or scale-free networks show that the average density of networks, the key "long-distance links" and the size of networks have significant effects on the length of distribution routes.
引文
[1] Pan W T.Mixed modified fruit fly optimization algorithm with general regression neural network to build oil and gold prices forecasting model [J].Kybernetes,2014,43(7):1053-1063.
[2] 宋娟.一种用于PID控制参数优化的混合果蝇算法[J].传感器与微系统,2015(6):137-140.
[3] Longo H,de Arag?o M P,Uchoa E.Solving capacitated arc routing problem using a transformation to the CVRP [J].Computers & Operations Research,2006,33(6):1823-1837.
[4] Ostermeier M,Hübner A.Vehicle selection for a multi-compartment vehicle routing problem[J].European Journal of Operational Research,2018,269(2):682-694.
[5] Silvestrin P V,Ritt M.An iterated tabu search for the multi-compartment vehicle routing problem[J].Computers & Operations Research,2017,81:192-202.
[6] Chajakis E D,Guignard M.Scheduling deliveries in vehicles with multiple compartments[J].Journal of Global Optimization,2003,26(1):43-78.
[7] Avella P,Boccia M,Sforza A.Solving a fuel delivery problem by heuristic and exact approaches[J].European Journal of Operational Research,2004,152(1):170-179.
[8] Axelsson A,Lindvall V C.The opinion leaders of the digital era:A quantitative study of student attitudes towards influencing marketing[J].International Transactions on Electrical Energy Systems,2013,9(1):35-41.
[9] Osaba E,Diaz F.Comparison of a memetic algorithm and a tabu search algorithm for the traveling salesman problem[C]// Computer Science & Information Systems.[s.l.]:[s.n.],2012.
[10] 李锋,魏莹.求解随机旅行时间的C-VRP问题的混合遗传算法[J].系统管理学报,2014,23(6):819-825.
[11] Muyldermans L,Pang G.On the benefits of co-collection:Experiments with a multi-compartment vehicle routing algorithm[J].European Journal of Operational Research,2010,206(1):93-103.
[12] 张涛,张春梅,张玥杰.协同粒子群-模拟退火算法求解VRPSPD问题[J].系统管理学报,2009,18(6):681-685.
[13] 谭巍,文庆.基于蚁群系统和2-opt方法求解同时送取货车辆路径VRPSPD问题[J].数学的实践与认识,2015(24):235-242.
[14] Yahyaoui H,Kaabachi I,Krichen S,et al.Two metaheuristic approaches for solving the multi-compartment vehicle routing problem[J].Operational Research,2018(1):1-24.
[15] Reed M,Yiannakou A,Evering R.An ant colony algorithm for the multi-compartment vehicle routing problem[J].Applied Soft Computing,2014,15:169-176.
[16] Wang C L,Li S W.Hybrid fruit fly optimization algorithm for solving multi-compartment vehicle routing problem in intelligent logistics[J].Advances inProduction Engineering & Management,2018,13(4):466-478.
[17] Jair J,Paternina-Arboleda C D,Cantillo V,et al.A two-pheromone trail ant colony system—tabu search approach for the heterogeneous vehicle routing problem with time windows and multiple products[J].Journal of Heuristics,2013,19(2):233-252.
[18] 张其亮,俞祚明.基于优势种群的离散果蝇优化算法求解无等待流水车间调度问题[J].计算机集成制造系统,2017,23(3):609-615.
[19] Christofides N,Mingozzi A,Toth P.State-space relaxation procedures for the computation of bounds to routing problems[J].Networks,1981,11(2):145-164.
[20] Lin S W,Lee Z J,Ying K C,et al.Applying hybrid meta-heuristics for capacitated vehicle routing problem[J].Expert Systems with Applications,2009,36(2):1505-1512.
[21] Abdulkader M M S,Gajpal Y,ElMekkawy T Y.Hybridized ant colony algorithm for the multi compartment vehicle routing problem[J].Applied Soft Computing,2015,37:196-203.
[22] Erdos P.On the evolution of random graphs[J].Transactions of the American Mathematical Society,2011,286(1):257-274.
[23] Watts D J,Strogatz S H.Collective dynamics of ‘small-world’ networks[J].Nature,1998,393(6684):4440-442.
[24] Barabasi A L,Albert R.Emergence of scaling in random networks[J].Science,1999.DOI:10.1126/Science.286.5439.509.
[2] 宋娟.一种用于PID控制参数优化的混合果蝇算法[J].传感器与微系统,2015(6):137-140.
[3] Longo H,de Arag?o M P,Uchoa E.Solving capacitated arc routing problem using a transformation to the CVRP [J].Computers & Operations Research,2006,33(6):1823-1837.
[4] Ostermeier M,Hübner A.Vehicle selection for a multi-compartment vehicle routing problem[J].European Journal of Operational Research,2018,269(2):682-694.
[5] Silvestrin P V,Ritt M.An iterated tabu search for the multi-compartment vehicle routing problem[J].Computers & Operations Research,2017,81:192-202.
[6] Chajakis E D,Guignard M.Scheduling deliveries in vehicles with multiple compartments[J].Journal of Global Optimization,2003,26(1):43-78.
[7] Avella P,Boccia M,Sforza A.Solving a fuel delivery problem by heuristic and exact approaches[J].European Journal of Operational Research,2004,152(1):170-179.
[8] Axelsson A,Lindvall V C.The opinion leaders of the digital era:A quantitative study of student attitudes towards influencing marketing[J].International Transactions on Electrical Energy Systems,2013,9(1):35-41.
[9] Osaba E,Diaz F.Comparison of a memetic algorithm and a tabu search algorithm for the traveling salesman problem[C]// Computer Science & Information Systems.[s.l.]:[s.n.],2012.
[10] 李锋,魏莹.求解随机旅行时间的C-VRP问题的混合遗传算法[J].系统管理学报,2014,23(6):819-825.
[11] Muyldermans L,Pang G.On the benefits of co-collection:Experiments with a multi-compartment vehicle routing algorithm[J].European Journal of Operational Research,2010,206(1):93-103.
[12] 张涛,张春梅,张玥杰.协同粒子群-模拟退火算法求解VRPSPD问题[J].系统管理学报,2009,18(6):681-685.
[13] 谭巍,文庆.基于蚁群系统和2-opt方法求解同时送取货车辆路径VRPSPD问题[J].数学的实践与认识,2015(24):235-242.
[14] Yahyaoui H,Kaabachi I,Krichen S,et al.Two metaheuristic approaches for solving the multi-compartment vehicle routing problem[J].Operational Research,2018(1):1-24.
[15] Reed M,Yiannakou A,Evering R.An ant colony algorithm for the multi-compartment vehicle routing problem[J].Applied Soft Computing,2014,15:169-176.
[16] Wang C L,Li S W.Hybrid fruit fly optimization algorithm for solving multi-compartment vehicle routing problem in intelligent logistics[J].Advances inProduction Engineering & Management,2018,13(4):466-478.
[17] Jair J,Paternina-Arboleda C D,Cantillo V,et al.A two-pheromone trail ant colony system—tabu search approach for the heterogeneous vehicle routing problem with time windows and multiple products[J].Journal of Heuristics,2013,19(2):233-252.
[18] 张其亮,俞祚明.基于优势种群的离散果蝇优化算法求解无等待流水车间调度问题[J].计算机集成制造系统,2017,23(3):609-615.
[19] Christofides N,Mingozzi A,Toth P.State-space relaxation procedures for the computation of bounds to routing problems[J].Networks,1981,11(2):145-164.
[20] Lin S W,Lee Z J,Ying K C,et al.Applying hybrid meta-heuristics for capacitated vehicle routing problem[J].Expert Systems with Applications,2009,36(2):1505-1512.
[21] Abdulkader M M S,Gajpal Y,ElMekkawy T Y.Hybridized ant colony algorithm for the multi compartment vehicle routing problem[J].Applied Soft Computing,2015,37:196-203.
[22] Erdos P.On the evolution of random graphs[J].Transactions of the American Mathematical Society,2011,286(1):257-274.
[23] Watts D J,Strogatz S H.Collective dynamics of ‘small-world’ networks[J].Nature,1998,393(6684):4440-442.
[24] Barabasi A L,Albert R.Emergence of scaling in random networks[J].Science,1999.DOI:10.1126/Science.286.5439.509.