考虑碳排放的选址-路径问题研究
|
摘要
针对物流配送中的选址-路径问题,在车辆路径安排时加入了碳排放的考虑,建立了包含碳排放、配送成本和客户满意度的多目标优化模型,提出了一种基于禁忌搜索的超启发式算法.在超启发式算法的框架中,构建了一系列基于问题特征的底层启发式算子,设计了禁忌搜索作为高层启发式策略.以某地区物流配送实例进行仿真实验,通过超启发式算法和NSGA-II算法比较证明,所提算法可以更好地解决选址路径的多目标问题,能较快地找到更优解,达到较高的搜索效率和算法稳定性.与传统的启发式算法相比,该算法具有很好的通用性,可以很容易推广到其他选址-路径变种问题上.
Aiming at the optimization of location routing problem in logistics distribution,a multiobjective optimization model including carbon emission, distribution cost and customer satisfaction is established,a tabu search based hyper heuristic algorithm is proposed.In the framework of hyper heuristic algorithm,a series of low level heuristics based on the problem features are constructed,and tabu search is designed as a high level strategy.Compared with the NSGA-II algorithm,the multi-objective problem of location routing problem can be solved better with the hyper heuristic algorithm,and the better solution can be found quickly,and higher search efficiency and stability of the algorithm can be achieved.Compared with the traditional heuristic algorithms,this algorithm has good versatility,and can be easily extended to other location routing problem variants.
Aiming at the optimization of location routing problem in logistics distribution,a multiobjective optimization model including carbon emission, distribution cost and customer satisfaction is established,a tabu search based hyper heuristic algorithm is proposed.In the framework of hyper heuristic algorithm,a series of low level heuristics based on the problem features are constructed,and tabu search is designed as a high level strategy.Compared with the NSGA-II algorithm,the multi-objective problem of location routing problem can be solved better with the hyper heuristic algorithm,and the better solution can be found quickly,and higher search efficiency and stability of the algorithm can be achieved.Compared with the traditional heuristic algorithms,this algorithm has good versatility,and can be easily extended to other location routing problem variants.
引文
[1]曹剑东,李家文.基于顺路原则及位置预估的动态调度策略[J].浙江工业大学学报,2015,43(2):197-201.
[2]赵燕伟,李文,张景玲,等.多车型同时取送货问题的低碳路径研究[J].浙江工业大学学报,2015,43(1):18-23.
[3]JEMAI J,ZEKRI M,MELLOULI K.An NSGA-II algorithm for the green vehicle routing problem[C]//European Conference on Evolutionary Computation in Combinatorial Optimization.Berlin:Heidelberg,2012:37-48.
[4]SAWIK B,FAULIN J,PEREZ-BEMABEU E,et al.Bi-objective optimization models for green VRP approaches[C]//International Conference on Industrial Logistics.Krakow:AGH University of Science and Technology,2016:247-254.
[5]鲁建厦,洪欢蕾,陈青丰.考虑供给商品价格的多车场车辆路径问题[J].浙江工业大学学报,2016,44(5):553-558.
[6]GOLMOHAMMADI A M,BONAB S A,PARISHANI A.A multi-objective location routing problem using imperialist competitive algorithm[J].International journal of industrial engineering computations,2016,7(3):481-488.
[7]范静.考虑客户满意度的同时收发车辆路径问题[J].运筹与管理,2011,20(1):60-64.
[8]史春阳.同时取送货的车辆路径问题中的低碳研究[D].北京:清华大学,2011.
[9]BURKE E K,GENDREAU M,HYDE M,et al.Hyper-heuristics:a survey of the state of the art[J].Journal of the operational research society,2013,64(12):1695-1724.
[10]MAASHI M,KENDALLl G,ZCAN E.Choice function based hyper-heuristics for multi-objective optimization[J].Applied soft computing,2015,28(C):312-326.
[11]PILLAY N.A review of hyper-heuristics for educational timetabling[J].Annals of operations research,2016,239(1):3-38.
[12]HIBA Y,SAOUSSEN K,BILEL D,et al.A Hybrid ILSVND based hyper-heuristic for permutation flowshop scheduling problem[J].Procedia computer science,2015,60(1):632-641.
[13]GOMEZ J C,TERASHIMA-MARíN H.Evolutionary hyper-heuristics for tackling bi-objective 2Dbin packing problems[J].Genetic programming&evolvable machines,2017(1):1-31.
[14]SIM K,HART E.A combined generative and selective hyper-heuristic for the vehicle routing problem[C]//Genetic and Evolutionary Computation Conference.New York:Association Computing Machinery,2016:1093-1100.
[15]SCHRIMPF G,SCHNEIDER J,STAMM-WILBRANDT H,et al.Record breaking optimization results using the ruin and recreate principle[J].Journal of computational physics,2000,159(2):139-171.
[16]MEHRJERDI Y Z,NADIZADEH A.Using greedy clustering method to solve capacitated location-routing problem with fuzzy demands[J].European journal of operational research,2013,229(1):75-84.
[17]PONBOON S,QURESHI A G,TANIGUCHI E.Evaluation of cost structure and impact of parameters in location-routing problem with time windows[J].Transportation research procedia,2016,12:213-226.
[18]MANDAL S K,PACCIARELLI D,LOKKETANGEN A,et al.A memetic NSGA-II for the bi-objective mixed capacitated general routing problem[J].Journal of heuristics,2015,21(3):359-390.
[19]卫田,范文慧.基于NSGAⅡ的物流配送中车辆路径问题研究[J].计算机集成制造系统,2008,14(4):778-784.
[2]赵燕伟,李文,张景玲,等.多车型同时取送货问题的低碳路径研究[J].浙江工业大学学报,2015,43(1):18-23.
[3]JEMAI J,ZEKRI M,MELLOULI K.An NSGA-II algorithm for the green vehicle routing problem[C]//European Conference on Evolutionary Computation in Combinatorial Optimization.Berlin:Heidelberg,2012:37-48.
[4]SAWIK B,FAULIN J,PEREZ-BEMABEU E,et al.Bi-objective optimization models for green VRP approaches[C]//International Conference on Industrial Logistics.Krakow:AGH University of Science and Technology,2016:247-254.
[5]鲁建厦,洪欢蕾,陈青丰.考虑供给商品价格的多车场车辆路径问题[J].浙江工业大学学报,2016,44(5):553-558.
[6]GOLMOHAMMADI A M,BONAB S A,PARISHANI A.A multi-objective location routing problem using imperialist competitive algorithm[J].International journal of industrial engineering computations,2016,7(3):481-488.
[7]范静.考虑客户满意度的同时收发车辆路径问题[J].运筹与管理,2011,20(1):60-64.
[8]史春阳.同时取送货的车辆路径问题中的低碳研究[D].北京:清华大学,2011.
[9]BURKE E K,GENDREAU M,HYDE M,et al.Hyper-heuristics:a survey of the state of the art[J].Journal of the operational research society,2013,64(12):1695-1724.
[10]MAASHI M,KENDALLl G,ZCAN E.Choice function based hyper-heuristics for multi-objective optimization[J].Applied soft computing,2015,28(C):312-326.
[11]PILLAY N.A review of hyper-heuristics for educational timetabling[J].Annals of operations research,2016,239(1):3-38.
[12]HIBA Y,SAOUSSEN K,BILEL D,et al.A Hybrid ILSVND based hyper-heuristic for permutation flowshop scheduling problem[J].Procedia computer science,2015,60(1):632-641.
[13]GOMEZ J C,TERASHIMA-MARíN H.Evolutionary hyper-heuristics for tackling bi-objective 2Dbin packing problems[J].Genetic programming&evolvable machines,2017(1):1-31.
[14]SIM K,HART E.A combined generative and selective hyper-heuristic for the vehicle routing problem[C]//Genetic and Evolutionary Computation Conference.New York:Association Computing Machinery,2016:1093-1100.
[15]SCHRIMPF G,SCHNEIDER J,STAMM-WILBRANDT H,et al.Record breaking optimization results using the ruin and recreate principle[J].Journal of computational physics,2000,159(2):139-171.
[16]MEHRJERDI Y Z,NADIZADEH A.Using greedy clustering method to solve capacitated location-routing problem with fuzzy demands[J].European journal of operational research,2013,229(1):75-84.
[17]PONBOON S,QURESHI A G,TANIGUCHI E.Evaluation of cost structure and impact of parameters in location-routing problem with time windows[J].Transportation research procedia,2016,12:213-226.
[18]MANDAL S K,PACCIARELLI D,LOKKETANGEN A,et al.A memetic NSGA-II for the bi-objective mixed capacitated general routing problem[J].Journal of heuristics,2015,21(3):359-390.
[19]卫田,范文慧.基于NSGAⅡ的物流配送中车辆路径问题研究[J].计算机集成制造系统,2008,14(4):778-784.