Journal of Computer Applications ›› 2021, Vol. 41 ›› Issue (3): 851-859.DOI: 10.11772/j.issn.1001-9081.2020071079

Special Issue: 前沿与综合应用

• Frontier and comprehensive applications • Previous Articles     Next Articles

Algorithms for low-carbon pickup and delivery vehicle routing problem with fuzzy demand

MA Yanfang1, WANG Shan1, HUANG Lingyu2, CHENG Cong1   

  1. 1. School of Economics and Management, Hebei University of Technology, Tianjin 300401, China;
    2. Finance Office, Hebei University of Technology, Tianjin 300401, China
  • Received:2020-07-23 Revised:2020-11-09 Online:2021-03-10 Published:2020-12-23
  • Supported by:
    This work is partially supported by the Hebei Social Science Foundation (HB16GL036).


马艳芳1, 王珊1, 黄岭玉2, 程聪1   

  1. 1. 河北工业大学 经济管理学院, 天津 300401;
    2. 河北工业大学 财务处, 天津 300401
  • 通讯作者: 王珊
  • 作者简介:马艳芳(1986-),女,河北保定人,副教授,博士,主要研究方向:决策理论与方法;王珊(1996-),女,陕西渭南人,硕士研究生,主要研究方向:绿色供应链管理;黄岭玉(1990-),女,河北衡水人,中级经济师,硕士,主要研究方向:管理学;程聪(1987-),女,河南焦作人,讲师,博士,主要研究方向:优化理论与方法。
  • 基金资助:

Abstract: Due to high carbon emissions in the logistics and distribution process, from a low carbon perspective, a Low Carbon Vehicle Routing Problem with Pickup and Delivery (LCVRPPD) considering fuzzy demand was formulated, and a 2-OPT based differential algorithm was proposed to solve the problem. In the algorithm, the natural number encoding method was adopted and three different fitness functions were given. Then, the 2-OPT algorithm was introduced to replace the original mutation mechanism of differential algorithm, and the binomial crossover operators and greedy selection operator were combined, so as to accelerate the convergence of the improved algorithm. In the case study, Taguchi method was used to determine reasonable values of parameters in the improved algorithm, and the SPSS (Statistical Product and Service Solutions) analysis revealed that the solution of the model with the minimum total cost as the objective function is the best compared to those of the other two different objective models of transportation cost minimization and carbon minimization respectively. For examples with different customer scales, compared with the basic differential algorithm, the improved algorithm has the total cost reduced by 1.8% to 3.0% and the carbon emission decreased by 0.7% to 3.5%; compared with genetic algorithm, the improved algorithm has the total cost reduced by 1.9% to 16.47% and the carbon emission decreased by 1.2% to 4.3%; compared with particle swarm optimization algorithm, the optimization effect is more obvious, the improved algorithm has the total cost reduced by 4.0% to 22.5% and the carbon emission decreased by 1.56% to 7.88%, which verify the effectiveness and advancement of the proposed algorithm. In summary, the proposed model and algorithm can provide a reference for the low carbon routing problem of pickup and delivery vehicles.

Key words: pickup and delivery problem, fuzzy demand, differential algorithm, low carbon logistics, Taguchi method

摘要: 针对物流配送过程中的高碳排放问题,从低碳视角出发,构建考虑模糊需求的低碳取送货车辆调度(LCVRPPD)模型,并提出一种基于2-OPT的差分算法对问题进行求解。该算法中,采用自然数编码方式并设置三种不同的适应度函数;随后,引入2-OPT算法取代差分算法原有的变异机制,并结合二项交叉算子和贪婪选择算子,从而提高改进算法的收敛速度。案例分析中,通过田口法确定改进算法参数的合理取值,通过SPSS分析揭示了在运输成本最小、碳排放量最小和总成本最小的三种不同目标模型中,以总成本最小为目标函数的模型的解的效果最好。针对不同顾客规模的算例,改进算法与基本差分算法相比,总成本可以降低1.8%~3.0%,碳排放量可以降低0.7%~3.5%;与遗传算法相比,总成本可以降低1.9%~16.47%,碳排放量可以降低1.2%~4.3%;与粒子群优化算法相比的优化效果更加明显,总成本可以降低4.0%~22.5%,碳排放量可以降低1.56%~7.88%,验证了算法的有效性及先进性。综上,所提出的模型和算法可以为低碳取送货车辆调度问题提供参考。

关键词: 取送货问题, 模糊需求, 差分算法, 低碳物流, 田口法

CLC Number: