Branch-and-Cut for the Split Delivery Vehicle Routing Problem with Time Windows
Branch-and-Cut for the Split Delivery Vehicle Routing Problem with Time Windows
复制标题
DOI：
10.1287/trsc.2018.0825
复制
发表时间：
2019-01
期刊：
影响因子：
--
通讯作者：
Nicola Bianchessi;Stefan Irnich
中科院分区：
文献类型：
--
作者：
Nicola Bianchessi;Stefan Irnich
带时间窗的可拆分配送车辆路径问题（SDVRPTW）是一个非常困难的组合优化问题.首先，很难？最后给出了SDVRPTW的一个实用的混合规划（MIP）公式。标准的建模方法要么受到固有的对称性（MIP与车辆指数），或不能准确地捕捉可行性的所有方面。由于可能不止一次地访问客户，因此沿路由沿着传播负载和时间的标准机制失效。其次，由于缺乏有用的公式，任何直接的基于MIP的方法都是不可能的。到目前为止，最有效的精确算法SDVRPTW的分支和价格和切割的方法，使用基于路径的配方。在本文中，我们提出了一个新的和定制的分支和切割算法来解决SDVRPTW。它是基于一个新的松弛紧模型，其中一些整数解是不可行的SDVRPTW。我们使用已知的，并引入一些新的类有效的不等式，以削减？这些不可行的解决方案。一个新的类是路径匹配约束，它概括了不可行路径约束。然而，即使有效的不等式，一些整数解的新的紧凑的制定仍有待测试的可行性。对于给定的整数解，我们构建了原始实例的一般稀疏子网络。在这个子网络上，所有的时间窗口可行的路线可以枚举和路径为基础的剩余问题，然后解决，以决定选择的路线，交付量，从而整体的可行性。所有不可行的解决方案都需要被切断。出于这个原因，我们得到一些加强可行性削减利用的事实，解决方案往往分解成集群。计算实验表明，新的方法是能够证明几个以前未解决的情况下，从文献的最优性。
The Split Delivery Vehicle Routing Problem with Time Windows (SDVRPTW) is a notoriously hard combinatorial optimization problem. First, it is hard to ?nd a useful compact Mixed-Integer Programming (MIP) formulation for the SDVRPTW. Standard modeling approach either suffer from inherent symmetries (MIPs with a vehicle index) or cannot exactly capture all aspects of feasibility. Due to the possibility to visit customers more than once, the standard mechanisms to propagate load and time along the routes fail. Second, the lack of useful formulations has rendered any direct MIP-based approach impossible. Up to now, the most effective exact algorithms for the SDVRPTW are branch-and-price-and-cut approaches using a path-based formulation. In this paper, we propose a new and tailored branch-and-cut algorithm to solve the SDVRPTW. It is based on a new relaxed compact model, in which some integer solutions are infeasible to the SDVRPTW. We use known and introduce some new classes of valid inequalities in order to cut o? such infeasible solutions. One new class is path-matching constraints that generalize infeasible-path constraints. However, even with the valid inequalities, some integer solutions to the new compact formulation remain to be tested for feasibility. For a given integer solution, we built a generally sparse subnetwork of the original instance. On this subnetwork, all time-window feasible routes can be enumerated and a path-based residual problem is then solved in order to decide on the selection of routes, the delivery quantities, and herewith the overall feasibility. All infeasible solutions need to be cut off. For this reason, we derive some strengthened feasibility cuts exploiting the fact that solutions often decompose into clusters. Computational experiments show that the new approach is able to prove optimality for several previously unsolved instances from the literature.