An integration of Lagrangian split and VNS: The case of the capacitated vehicle routing problem
提出一种新颖的拉格朗日松弛方法（拉格朗日分裂），结合整数线性规划来分割车辆路径问题中的大环，并集成到变邻域搜索中，实验表明该方法在基准实例上效果良好。
In this paper, we propose an efficient and novel Lagrangian relaxation method which incorporates a new integer linear programming (ILP) formulation to optimally partition a giant tour in the context of a capacitated vehicle routing problem (CVRP). This approach, which we call Lagrangian split (Ls), is more versatile than the ILP which, in most cases, can be intractable using a conventional solver. An effective repair mechanism followed by a local search are also embedded into the process. The mathematical validity of the repair mechanism and its time complexity are also provided. An integration of Ls into a powerful variable neighbourhood search (VNS) is also presented. Computational experiments are conducted to demonstrate that Ls provides encouraging results when applied on benchmark instances and that the integration of Ls into a metaheuristic scheme produces good results when compared to those found by state-of-the-art methods.