摘要
针对绿色带容量的车辆路径问题(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的高质量解。
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.
作者
徐林浩
钱斌
胡蓉
于乃康
Xu Lin-hao;Qian Bin;Hu Rong;Yu Nai-kang(School of Information Engineering and Automation,Kunming University of Science and Technology,Kunming 650500,China;School of Mechanical and Electrical Engineering,Kunming University of Science and Technology,Kunming 650500,China)
出处
《广东工业大学学报》
CAS
2022年第5期61-67,共7页
Journal of Guangdong University of Technology
基金
国家自然科学基金资助项目(62173169,61963022)
云南省基础研究重点资助项目(202201AS070030)。
关键词
绿色带容量的车辆路径问题
混合整数规划
改进拉格朗日松弛
下界
green capacitated vehicle routing problem
mixed integer programming
improved Lagrange relaxation
lower bound
