基于超启发式算法的选址-路径问题研究
|
摘要
为了降低物流配送过程中车辆的碳排放,采用具有良好通用性的超启发式算法对低碳选址路径问题进行求解。将蛙跳算法作为超启发式算法的高层选择策略,并在蛙跳算法中提出了基于最长公共子序列的相似度计算方式代替原有的相似度计算,而采用动态规划的方法对个体间的最长公共子序列进行计算。实验结果表明:提出的相似度计算方式能更直观地反映个体之间的相似性,具有良好的通用性,并且在低碳选址-路径问题上获得更优秀的解。
In order to reduce the carbon emission of vehicles, the hyper-heuristic algorithm with good universality is used to solve the low-carbon location-routing problem. This paper uses leapfrog algorithm as the top choice strategy of hyper-heuristic algorithms, and proposes the similarity calculation method based on longest common subsequence instead of the original similarity calculation in leapfrog algorithm, and uses the dynamic programming to calculate the longest common subsequence between individuals. The experimental results show that the new similarity calculation method can more intuitively reflect the similarities between individuals, and it makes hyper-heuristic algorithm get better solutions in location-routing problem.
In order to reduce the carbon emission of vehicles, the hyper-heuristic algorithm with good universality is used to solve the low-carbon location-routing problem. This paper uses leapfrog algorithm as the top choice strategy of hyper-heuristic algorithms, and proposes the similarity calculation method based on longest common subsequence instead of the original similarity calculation in leapfrog algorithm, and uses the dynamic programming to calculate the longest common subsequence between individuals. The experimental results show that the new similarity calculation method can more intuitively reflect the similarities between individuals, and it makes hyper-heuristic algorithm get better solutions in location-routing problem.
引文
[1] 曹剑东,李家文.基于顺路原则及位置预估的动态调度策略[J].浙江工业大学学报,2015,43(2):197-201.
[2] 赵燕伟,李文,张景玲,等.多车型同时取送货问题的低碳路径研究[J].浙江工业大学学报,2015,43(1):18-23.
[3] 江贺.超启发式算法:跨领域的问题求解模式[J].中国计算机学会通讯,2011,7(3):63-70.
[4] BURKE E K,HYDE M,KENDALL G,et al.A genetic programming hyper-heuristic approach for evolving 2-d strip packing heuristics[J].IEEE transactions on evolutionary computation,2010,14(6):942-958.
[5] NAREYEK A,SMITH S F,OHLER C M.Integrating local-search advice into refinement search (or not)[C]//Proceedings of the CP 2003 Third International Workshop on Cooperative Solvers in Constraint Programming.Pittsburgh:Carnegie Mellon University,2003:29-43.
[6] BURKE E K,KENDALL G,SOUBEIGA E.A tabu-search hyperheuristic for timetabling and rostering[J].Journal of heuristics,2003,9(6):451-470.
[7] CHEN P C,KENDALL G,BERGHE G V.An ant based hyper-heuristic for the travelling tournament problem[C]//IEEE Symposium on Computational Intelligence in Scheduling.Hawaii:IEEE,2007:19-26.
[8] MARSHALL R J,JOHNSTON M,ZHANG M.Developing a hyper-heuristic using grammatical evolution and the capacitated vehicle routing problem[C]//Asia-Pacific Conference on Simulated Evolution and Learning.New York:Springer International Publishing,2014:668-679.
[9] 张春苗,赵燕伟,张景玲,等.低碳定位——车辆路径问题[J].计算机集成制造系统,2017,23(12):2768-2777.
[10] WALKER J D.Design of vehicle routing problem domains for a hyper-heuristic framework[D].Nottingham:University of Nottingham,2015.
[11] EUSUFF M M,LANSEY K E.Optimization of water distribution network design using the shuffled frog leaping algorithm[J].Journal of water resources planning & management,2003,129(3):210-225.
[12] 贾凌云,李冬妮,田云娜.基于混合蛙跳和遗传规划的跨单元调度方法[J].自动化学报,2015,41(5):936-948.
[13] EBRAHIMI J,HOSSEINIAN S H,GHAREHPETIAN G B.Unit commitment problem solution using shuffled frog leaping algorithm[J].IEEE transactions on power systems,2011,26(2):573-581.
[14] 陈勇,盛家君,王亚良,等.基于改进蛙跳算法的可重构装配线调度研究[J].浙江工业大学学报,2014,43(3):274-279.
[15] 崔文华,刘晓冰,王伟,等.混合蛙跳算法研究综述[J].控制与决策,2012,27(4):481-486.
[16] 骆剑平,李霞,陈泯融.基于改进混合蛙跳算法的CVRP求解[J].电子与信息学报,2011,33(2):429-434.
[17] GNG.算法导论——最长公共子序列(动态规划)LCS[EB/OL].[2016-12-19].https://blog.csdn.net/so_geili/article/details/53737001.
[18] Institut charles Delaunay.Classical Instances for LRP[EB/OL].[2010-02-04].http://prodhonc.free.fr/Instances/instances_us.htm.
[2] 赵燕伟,李文,张景玲,等.多车型同时取送货问题的低碳路径研究[J].浙江工业大学学报,2015,43(1):18-23.
[3] 江贺.超启发式算法:跨领域的问题求解模式[J].中国计算机学会通讯,2011,7(3):63-70.
[4] BURKE E K,HYDE M,KENDALL G,et al.A genetic programming hyper-heuristic approach for evolving 2-d strip packing heuristics[J].IEEE transactions on evolutionary computation,2010,14(6):942-958.
[5] NAREYEK A,SMITH S F,OHLER C M.Integrating local-search advice into refinement search (or not)[C]//Proceedings of the CP 2003 Third International Workshop on Cooperative Solvers in Constraint Programming.Pittsburgh:Carnegie Mellon University,2003:29-43.
[6] BURKE E K,KENDALL G,SOUBEIGA E.A tabu-search hyperheuristic for timetabling and rostering[J].Journal of heuristics,2003,9(6):451-470.
[7] CHEN P C,KENDALL G,BERGHE G V.An ant based hyper-heuristic for the travelling tournament problem[C]//IEEE Symposium on Computational Intelligence in Scheduling.Hawaii:IEEE,2007:19-26.
[8] MARSHALL R J,JOHNSTON M,ZHANG M.Developing a hyper-heuristic using grammatical evolution and the capacitated vehicle routing problem[C]//Asia-Pacific Conference on Simulated Evolution and Learning.New York:Springer International Publishing,2014:668-679.
[9] 张春苗,赵燕伟,张景玲,等.低碳定位——车辆路径问题[J].计算机集成制造系统,2017,23(12):2768-2777.
[10] WALKER J D.Design of vehicle routing problem domains for a hyper-heuristic framework[D].Nottingham:University of Nottingham,2015.
[11] EUSUFF M M,LANSEY K E.Optimization of water distribution network design using the shuffled frog leaping algorithm[J].Journal of water resources planning & management,2003,129(3):210-225.
[12] 贾凌云,李冬妮,田云娜.基于混合蛙跳和遗传规划的跨单元调度方法[J].自动化学报,2015,41(5):936-948.
[13] EBRAHIMI J,HOSSEINIAN S H,GHAREHPETIAN G B.Unit commitment problem solution using shuffled frog leaping algorithm[J].IEEE transactions on power systems,2011,26(2):573-581.
[14] 陈勇,盛家君,王亚良,等.基于改进蛙跳算法的可重构装配线调度研究[J].浙江工业大学学报,2014,43(3):274-279.
[15] 崔文华,刘晓冰,王伟,等.混合蛙跳算法研究综述[J].控制与决策,2012,27(4):481-486.
[16] 骆剑平,李霞,陈泯融.基于改进混合蛙跳算法的CVRP求解[J].电子与信息学报,2011,33(2):429-434.
[17] GNG.算法导论——最长公共子序列(动态规划)LCS[EB/OL].[2016-12-19].https://blog.csdn.net/so_geili/article/details/53737001.
[18] Institut charles Delaunay.Classical Instances for LRP[EB/OL].[2010-02-04].http://prodhonc.free.fr/Instances/instances_us.htm.