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

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

针对带同时取送货的绿色车辆路径问题,以最小化带碳排放费用的配送成本为优化目标,建立混合整数规划模型,并提出一种结合数学规划方法与启发式算法的三阶段拉格朗日启发式算法进行求解.第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.