基于碳排放的开放选址-路径问题及算法

蒋海青, 赵燕伟, 张景玲, 冷龙龙

系统工程理论与实践 ›› 2020, Vol. 40 ›› Issue (1) : 182-194.

PDF(767 KB)
中国科学院数学与系统科学研究院期刊网
PDF(767 KB)
系统工程理论与实践 ›› 2020, Vol. 40 ›› Issue (1) : 182-194. DOI: 10.12011/1000-6788-2017-1375-13
论文

基于碳排放的开放选址-路径问题及算法

    蒋海青1,2, 赵燕伟1, 张景玲1, 冷龙龙1
作者信息 +

Minimizing the carbon emission for the open location-routing problem and algorithm

    JIANG Haiqing1,2, ZHAO Yanwei1, ZHANG Jingling1, LENG Longlong1
Author information +
文章历史 +

摘要

基于物流对节能减排的重大影响及第三方物流的广泛应用，本文建立了与配送中心规模、配送路径相关的低碳开放选址-路径（OLRP）问题模型，并设计量子进化算法（QEA）进行求解.算法采用先确定车辆及其顾客集，再选择配送中心的策略，并运用局部优化算子进行解的改善.通过目标值与CPU的综合分析，确定重要参数旋转角变化值Δθ，最大迭代次数itermax，种群Popsize的取值范围，并应用Barreto、Prins及Tuzun案例进行实验验证，结果显示碳排放目标的OLRP一定程度上会增大成本，量子进化算法在Barreto案例中的解均值优于LB、CPLEX及SA算法，在Prins案例中的求解效果与CPLEX相近，在Tuzun案例中绝大多数问题的求解结果优于CPLEX，在小规模问题中，优于SA算法，因此QEA是求解OLRP问题的一种有效算法.

Abstract

It is important to study the carbon emissions of location-routing problems for reducing the carbon emission of logistics. This paper establishes an open location-routing problem model (OLRP), the goal of OLRP is to minimize the carbon emission, considering of facility construction carbon emission and distribution carbon emission. We propose a quantum-inspired evolutionary algorithm (QEA) for solving the model. The algorithm adopts the strategy of determining the vehicles and their paths first, and then selecting the distribution center. Two routing local searches and two distribution local searches are used to improve the solution. Three important parameters (Δθ、itermax、Popsize) are determined by considering the carbon emission and CPU in Prins problem. The algorithm is tested on the benchmark of Barreto、Prins and Tuzun problems, the results show that the low carbon emission target of OLRP will increase the cost. The quantum-inspired evolutionary algorithm can obtain better average results than LB、CPLEX and SA in the Barreto problem, similar results to CPLEX in the Prins problem, and better than CPLEX in most Tuzun problem, which mean that QEA is an effective algorithm to the problem of OLRP.

关键词

开放选址-路径 / 路径问题 / 量子进化算法 / 碳排放

Key words

open location-routing / routing problem / quantum-inspired evolutionary algorithm / carbon emission

引用本文

EndNote

Ris (Procite)

Bibtex

导出引用
蒋海青 , 赵燕伟 , 张景玲 , 冷龙龙. 基于碳排放的开放选址-路径问题及算法. 系统工程理论与实践, 2020, 40(1): 182-194 https://doi.org/10.12011/1000-6788-2017-1375-13
JIANG Haiqing , ZHAO Yanwei , ZHANG Jingling , LENG Longlong. Minimizing the carbon emission for the open location-routing problem and algorithm. Systems Engineering - Theory & Practice, 2020, 40(1): 182-194 https://doi.org/10.12011/1000-6788-2017-1375-13
中图分类号： F224   

参考文献

[1] Cooper L. The transportation-location problem[J]. Operation Research, 1972, 20:94-108.
[2] Chan Y, Carter W B, Michael B. A multiple-depot, multi-vehicle, location routing problem with stochastically processed demands[J]. Computers and Operational Research, 1998, 37:39-42.
[3] Salhi S, Nagy G. Consistency and robustness in location-routing[J]. Studies in Locational Analysis, 1999, 13:3-19.
[4] Chan Y, Carter W B, Burnes M D. A multiple-depot, multiple-vehicle, location-routing problem with stochastically processed demands[J]. Computers and Operations Research, 2001, 28(8):803-826.
[5] Puerto J, Fernndez F. Multiple-objectives solution of the uncapacitated plant location problem[J]. European Journal of Operational Research, 2003, 145:509-529.
[6] Rafael C. Solving a multi-objective location-routing problem with a metaheuristic based on TS[J]. European Journal of Operational Research, 2007, 177:1751-1763.
[7] Wu T H. Heuristic solutions to multi-depot location-routing chinyao low problems[J]. Computers & Operations Research, 2008, 29(1):1393-1415.
[8] 石兆. 物流配送选址-运输路径优化问题研究[D].长沙:中南大学, 2015.Shi Z. Location-routing problem of logistics distribution[D]. Changsha:Central South University, 2015.
[9] ZareMehrjerdi Y, Nadizadeh A. Using greedy clustering method to solve capacitated location-routing problem with fuzzy demands[J]. European Journal of Operational Research, 2013, 229:75-84.
[10] 张晓楠, 范厚明, 李剑锋.变动补偿的多模糊选址-路径机会约束模型及算法[J].系统工程理论与实践, 2016, 36(2):442-453. Zhang X N, Fan H M, Li J F. Chance-constrainted model and algorithm for LRP with multiple fuzzy variables under change-reward[J]. Systems Engineering——Theory & Practice, 2016, 36(2):442-453.
[11] Vincent F Y, Lin S Y. A simulated annealing heuristic for the open location-routing problem[J]. Computer & Operations Research, 2015, 62:184-196.
[12] Emrah D, Tolga B, Gilbert L. The bi-objective pollution-routing problem[J]. European Journal of Operational Research, 2014, 232:464-478.
[13] Liu W Y, Lin C C, Chi C R, et al. Minimizing the carbon footprint for the time-dependent heterogeneous-fleet vehicle routing problem with alternative paths[J]. Sustainability, 2014, 6:4658-4684.
[14] Kuo Y Y. Using simulated annealing to minimize fuel consumption for the time-dependent vehicle routing problem[J]. Computers & Industrial Engineering, 2010, 59(1):157-165.
[15] Sevgi E, Elise M H. A green vehicle routing problem[J]. Transportation Research, 2012, 48:100-114.
[16] Ehmke J F, Campbell A M, Thomas B W. Vehicle routing to minimize time-dependent emissions in urban areas[J]. European Journal of Operational Research, 2016, 251(2):478-494.
[17] Alinaghian M, Naderipour M. A novel comprehensive macroscopic model for time-dependent vehicle routing problem with multi-alternative graph to reduce fuel consumption:A case study[J]. Computers & Industrial Engineering, 2016, 99:210-222.
[18] Koç Ç, Bektaş T, Jabali O, et al. The fleet size and mix location-routing problem with time windows:Formulations and a heuristic algorithm[J]. European Journal of Operational Research, 2016, 248(1):33-51.
[19] Eliana M T, John F F, Mauricio G E, et al. A multi-objective model for the green capacitated location-routing problem considering environmental impact[J]. Computers & Industrial Engineering, 2017, 110:114-125.
[20] 饶卫振,金淳, 王新华,等.考虑道路坡度因素的低碳问题模型与求解策略[J]. 系统工程理论与实践, 2014, 34(8):2092-2103. Rao W Z, Jin C, Wang X H, et al. A model of low-carbon vehicle routing problem considering roud gradient and its solving strategy[J]. Systems Engineering——Theory & Practice, 2014, 34(8):2092-2103.
[21] 李进,傅培华.具有固定车辆数的多车型低碳路径问题及算法[J]. 计算机集成制造系统, 2013, 19(6):1351-1362. Li J, Fu P H. Heterogeneous fixed fleet low-carbon routing problem and algorithm[J]. Computer Integrated Manufacturing Systems, 2013, 19(6):1351-1362.
[22] Kazakov T H, Batouche M D. A quantum-inspired evolutionary algorithm for multiobjective image segmentation[C]//Proceedings of World Academy of Science Engineering and Technology, 2007, 25:205-210.
[23] 赵燕伟, 彭典军, 张景玲,等. 有能力约束车辆路径问题的量子进化算法[J]. 系统工程理论与实践, 2009, 29(2):159-166. Zhao Y W, Peng D J, Zhang J L, et al. Quantum evolutionary algorithm for capacitated vehicle routing problem[J]. Systems Engineering——Theory & Practice, 2009, 29(2):159-166.
[24] 王万良, 黄海鹏, 赵燕伟,等.基于车辆共享的软时间窗动态需求车辆路径问题[J].计算机集成制造系统, 2011, 17(5):1056-1063. Wang W L, Huang H P, Zhao Y W, et al. Dynamic customer demand VRP with soft time windows based on vehicle sharing[J]. Computer Integrated Manufacturing Systems, 2011, 17(5):1056-1063.
[25] Wu X L, Wu S M. An elitist quantum inspired evolutionary algorithm for the flexible job-shop scheduling problem[J]. Journal of Intelligent Manufacturing, 2017, 28(6):1441-1457.
[26] Patvardhan C, Bansal S, Srivastav A. Parallel improved quantum inspired evolutionary algorithm solve large size quadratic knapsack problems[J]. Swarm and Evolutionary Computation, 2016, 26:175-190.
[27] European Commission. Methodology for calculating transport emissions and energy consumption[M]. Luxemburg, 1999.
[28] 唐金环, 戢守峰, 朱宝琳.考虑碳配额差值的选址_路径_库存集成问题优化模型与算法[J].中国管理科学, 2014, 22(9):114-122. Tang J H, Ji S F, Zhu B L. Optimization model and algorithm considers carbon-capped difference in the collaboration of location-routing inventory problem[J]. Chinese Journal of Management Science, 2014, 22(9):114-122.
[29] 李进, 张江华.基于碳排放与速度优化的带时间窗车辆路径问题[J].系统工程理论与实践, 2014, 34(12):3063-3072. Li J, Zhang J H. Vehicle routing problem with time windows based on carbon emissions and speed optimization[J]. Systems Engineering——Theory & Practice, 2014, 34(12):3063-3072.
[30] Barreto S S. Análise e modelização de problemas de localização-distribuição [Analysis and modelling of location-routing problems] [D]. Aveiro, Portugal:University of Aveiro, 2004.
[31] Prins C, Prodhon C, Ruiz A, et al. Solving the capacitated location-routing problem by a cooperative Lagrangean relaxation-granular tabu search heuristic[J]. Transportation Science, 2007, 41(4):470-483.

基金

国家自然科学基金（61572438，61402409）
PDF(767 KB)

Accesses

Citation

Detail
段落导航
相关文章

/

〈 〉