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

作者：徐林浩; 钱斌^*; 胡蓉; 于乃康

来源：广东工业大学学报, 2022, 39(05): 61-67.

• 绿色带容量的车辆路径问题
• 混合整数规划
• 改进拉格朗日松弛
• 下界

针对绿色带容量的车辆路径问题(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的高质量解。

• 单位
  机电工程学院; 昆明理工大学; 自动化学院