Scientific Program > Talks by Speaker > Bianchessi Nicola

The Split Delivery Vehicle Routing Problem with Time Windows (SDVRPTW) is a notoriously hard combinatorial optimization problem. First, it is hard to find 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. 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 work, 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 off such infeasible solutions. However, some integer solutions to the new compact formulation remain to be tested for feasibility. For a given 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 weakly connected components. Computational experiments show that the new approach is able to prove optimality for several previously unsolved instances from the literature.