基于集合划分的车辆路径优化精确算法研究

Research on Exact Algorithm of Vehicle Routing Problem Based on Set Partition

将VRPTW(Vehicle Routing Problem with Time Window)通过D-W分解划分为主问题为集合划分以及子问题为带资源约束的基本最短路径问题,对子问题以割平面回调形式加入两点加强割集不等式来消除网络流中的子回路,并通过二维车流模型代替分支定界过程求得精确解,对有效的提升算法求解速度提供了一种新思路。

In this paper,we divide the VRPTW(vehicle routing problem with time window),using D-W decomposition,into two parts,namely the main problem of set partition and the subproblem which is a basic shortest route problem with resources constraint.For the subproblem,the two-point enhanced cut inequalities are introduced in the form of cutting plane callback to eliminate the subtours in the network flow,and the exact solution is obtained by replacing the branch and bound process with a two-dimensional vehicle flow model.All in all,this paper provides a new perspective to speed up the solution of the vehicle routing problem.