绿色车辆路径问题的改进拉格朗日松弛算法

针对绿色带容量的车辆路径问题(Green Capacitated Vehicle Routing Problem, GCVRP)，建立了以最小化总运费为优化目标的混合整数规划(Mixed Integer Programming,MIP)模型，并提出一种改进拉格朗日松弛算法(Improved Lagrange Relaxation Algorithm, ILRA)进行求解。首先，通过拉格朗日松弛技术得到原问题的对偶问题，并运用次梯度法求解对偶问题获得原问题的下界；然后针对下界设计修复算法和邻域搜索算法获得原问题的上界，进而更新乘子迭代求解；最后进行仿真实验，实验结果表明：在相同实验环境下对19个不同规模算例进行10次测试，ILRA求取MIP的上下界平均间隙为7.61%，而Gurobi求解器求取的平均间隙为15.47%。可见，相较于Gurobi求解器，ILRA能够高效获得GCVRP的高质量解。

An Improved Lagrange Relaxation Algorithm for Green Vehicle Routing Problem

To address the green capacitated vehicle routing problem (GCVRP), a mixed integer programming (MIP) model is established to minimize the total freight cost, and an improved Lagrange relaxation algorithm (ILRA) is proposed to solve the problem. Firstly, the dual problem of the original problem is obtained by Lagrange relaxation technique, and the lower bound of the original problem is obtained by solving the dual problem by subgradient method; Secondly a repair algorithm and a neighborhood search algorithm are designed to obtain the upper bound of the original problem, and then update the multiplier iterative solution; Finally, a simulation experiment is carried out. The experimental results show that 10 tests are carried out on 19 cases of different scales under the same experimental environment. The average gap between the upper and lower bounds of MIP obtained by ILRA is 7.61%, while the average gap obtained by Gurobi solver is 15.47%. Therefore, compared with Gurobi solver, ILRA can obtain high-quality solutions of GCVRP efficiently.