绿色VRP的增强拉格朗日松弛启发式算法

来源：电子测量技术杂志2023年第19期北京时间：

作者：徐林浩，胡蓉，钱斌，于乃康

单位：1.昆明理工大学信息工程与自动化学院 昆明 650500; 2.昆明理工大学机电工程学院 昆明 650500

摘要：针对绿色多车型车辆路径问题(GHFVRP)，建立了以最小化车辆固定成本、行驶成本及碳排放成本之和为优化目标的混合整数规划模型(MIP)，并提出一种增强拉格朗日松弛启发式算法(ELRHA)进行求解。首先，通过松弛难约束构造对偶问题，并分解为两个子问题，再采用次梯度法更新拉格朗日乘子，求解两个子问题获得原问题的下界；其次，设计一种两阶段启发式算法对下界进行修复及优化，以获得较好可行解并更新问题上界；最后进行仿真实验，实验结果表明：在相同实验环境下对17个算例进行20次测试，ELRHA平均求解间隙为4.49%，相较Gurobi提升3.28%，同时与其它算法对比进一步验证了ELRHA能求解问题高质量上界。可见，ELRHA能有效求解GHFVRP。

关键词：绿色多车型车辆路径问题;混合整数规划;拉格朗日松弛;次梯度;下界

基金资助：国家自然科学基金（61963022，62173169）、云南省基础研究重点项目（202201AS070030）资助