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

作     者：徐林浩 胡蓉 钱斌 于乃康 Xu Linhao;Hu Rong;Qian Bin;Yu Naikang

作者机构：昆明理工大学信息工程与自动化学院昆明650500 昆明理工大学机电工程学院昆明650500 

出 版 物：《电子测量技术》 (Electronic Measurement Technology)

年 卷 期：2023年第46卷第19期

页      面：96-103页

学科分类：08[工学] 080203[工学-机械设计及理论] 0802[工学-机械工程] 

基　　金：国家自然科学基金(61963022,62173169) 云南省基础研究重点项目(202201AS070030)资助 

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

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