分支定价割平面法求解带时间窗和人力分配的车辆路径问题

Branch-and-Price-and-Cut Algorithm for the Manpower Allocation and Vehicle Routing Problem with Time Windows

本文研究了带时间窗和人力分配的车辆路径问题,并提出用分支定价割平面法来求其最优解。分支定价割平面法首先根据Dantzig-Wolfe分解技术将问题的数学模型分解为基于路径的主问题模型和求最短路径的子问题模型,然后利用列生成和标签算法在主问题和子问题之间进行迭代,并使用割平面法调整可行区域来求得主问题的最优松弛解,最后采用基于车辆数目和弧的分支策略获取原问题的整数解。算法中加入了两种加速策略:双向标签算法和递减搜索空间法。通过对多组算例进行测试,验证了模型和算法的准确性,并分析了患者数目和车辆数目对结果的影响,也说明了割平面法具有提高算法效率的作用。最后,对大规模算例进行测试的结果也为实际应用提供了理论依据。

This paper studies the manpower allocation and vehicle routing problem with time windows(MAVRPTW)and proposes a branch-and-price-and-cut algorithm to obtain its optimal solution.The algorithm first decomposes the mathematical model of the original problem into a master model based on routes and a subproblem model for the shortest path problem according to the Dantzig-Wolfe decomposition.It then employs a column generation method and a label-setting algorithm to calculate between the master problem and the subproblems iteratively.Moreover,subset-row cuts are generated to adjust the feasible region during these processes.Finally,by obtaining the optimal solution to the linear relaxation of the main problem,the algorithm adopts branching strategies based on the vehicle number and arc for the integer solutions of the problem.In order to improve the efficiency of the algorithm,we use two accelerating strategies:a bidirectional label-setting algorithm and a decremental state-space relaxation.Comparisons with CPLEX show that the algorithm performs well in terms of stability and efficiency.By carrying out extensive computational experiments,we not only analyze the influence of the number of patients and vehicles on the results,but also find that the cutting plane method is capable of improving the efficiency of the algorithm.Finally,test results of large-scale instances provide a theoretical basis for practical application.