三阶段拉格朗日启发式算法求解带同时取送货的绿色车辆路径问题  

Three-stage Lagrangian heuristic algorithm for solving green vehicle routing problem with simultaneous pickup and delivery

作　　者：李熠胥 胡蓉[1] 吴绍云 于乃康 钱斌[1] LI Yi-xu;HU Rong;WU Shao-yun;YU Nai-kang;QIAN Bin(Faculty of Information Engineering and Automation,Kunming University of Science and Technology,Kunming 650504,China;Yuxi Sirun Printing Co.,Ltd,Yuxi 653100,China;Faculty of Mechanical and Electrical Engineering,Kunming University of Science and Technology,Kunming 650504,China)

机构地区：[1]昆明理工大学信息工程与自动化学院,昆明650504 [2]玉溪思润印刷有限公司,云南玉溪653100 [3]昆明理工大学机电工程学院,昆明650504

出　　处：《控制与决策》2023年第12期3525-3533,共9页Control and Decision

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

摘　　要：针对带同时取送货的绿色车辆路径问题,以最小化带碳排放费用的配送成本为优化目标,建立混合整数规划模型,并提出一种结合数学规划方法与启发式算法的三阶段拉格朗日启发式算法进行求解.第1阶段,利用拉格朗日松弛技术得到该问题的拉格朗日对偶模型;第2阶段,设计一种改进的次梯度算法迭代求解该对偶模型,同时引入修复机制,将每次迭代所得下界对应的解修复为原问题较高质量的可行解,并在下次迭代中利用该可行解更新次梯度方向和步长;第3阶段,设计一种启发式局部搜索算法,对第2阶段得到的可行解进行优化,进一步改进解的质量,以得到原问题的近似最优解.实验表明,所提出算法能够获得问题的一个优质解,同时提供一个紧致下界,用以定量评估解的质量.For the green vehicle routing problem with simultaneous pickup and delivery,a mixed integer programming model is developed with the optimization objective of minimizing the distribution cost with carbon emission cost,and a three-stage Lagrangian heuristic algorithm combining mathematical programming methods and heuristics is proposed for solving the problem.In the first stage,the Lagrangian dual model of the problem is obtained using Lagrangian relaxation technique.In the second stage,an improved sub-gradient algorithm is designed to solve the dual model iteratively,and a repair mechanism is introduced to repair the solution corresponding to the lower bound obtained in each iteration to a high-quality feasible solution of the original problem.The feasible solution is then used to update the sub-gradient direction and step size in the next iteration.In the third stage,a heuristic local search algorithm is designed to optimize the feasible solution obtained in the second stage and further improve the quality of the solution to obtain the approximate optimal solution of the original problem.Experiments show that the proposed algorithm can obtain a high-quality solution to the problem and provide a compact lower bound to evaluate the quality of the solution.

关 键 词：绿色车辆路径问题 同时取送货 拉格朗日启发式 可行解修复 松弛技术 问题下界 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]