考虑碳排放的两阶段选址-路径问题及其算法

Two-Echelon Location Routing Problem Considering Carbon Emissions and Its Algorithm

为减少物流车辆的碳排放,基于以排放因子为主要参数的碳排放计算方法,建立以碳排放最小化为目标的两阶段选址-路线问题(2E-LRP)模型,并设计了一种可用于快速求解大规模问题的两阶段混合算法(TSHA).算法第一阶段将2E-LRP转化成不考虑车辆路径的两阶段设施选址问题,调用Cplex直接求解得到配送中心选址和客户分配方案;在此基础上,算法第二阶段中,物流园区到被选用的配送中心以及配送中心到所分配客户的车辆路径问题被进一步转化成若干个独立的VRP(vehicle routing problem)问题,再运用改进的蚁群算法进行求解;最后,对Prodhon标准算例集中全部6个最大规模的算例进行测试.研究结果表明:与TSHA具有相同算法思想的TSHA-Ⅱ算法能够在求解质量下降2.3%的情况下将计算时长大大缩短至25 s左右;TSHA算法在求解考虑碳排放的2E-LRP算例时表现非常稳定,可以作为一种求解考虑碳排放2E-LRP的有效算法.

To reduce the carbon emissions from logistics vehicles,this paper presented a two-echelon location routing problem(2E-LRP)model aiming at minimizing carbon emissions based on a carbon emission calculation method employing emission factors as the key parameter.The paper also designed a two-stage hybrid algorithm(TSHA)capable of rapidly solving a large-scale problem.The algorithm first simplified the 2E-LRP into the twoechelon facility location problem without taking vehicle routes into account and called Cplex to solve it to obtain the location solution of distribution centers and the assignment solution of customers.Based on the above solutions,the 2E-LRP was transformed into independent vehicle route problems,and then an improved ant colony algorithm was employed for a solution.All six largest-sized instances from the standard Prodhon benchmark were tested.The test results show that the TSHA-Ⅱ,with the same algorithm ideas as TSHA,can reduce the computation time to about 25 seconds with a decrease of 2.3%in solution quality.The TSHA is stable in solving 2E-LRP considering carbon emissions and can be used as an effective algorithm to solve the 2E-LRP considering carbon emissions.