Clique inequalities applied to the vehicle routing problem with time windows

This work presents an exact branch-cut-and-price algorithm for the vehicle routing problem with time windows (VRPTW) where the well-known clique inequalities are used as cutting planes defined on the set partitioning master problem variables. It shows how these cutting planes affect the dominance criterion applied in the pricing algorithm, which is a labeling algorithm for solving resource-constrained elementary shortest path problems.

The idea of using cutting planes defined on the master problem variables for the VRPTW has been recently developed: Chva´tal-Gomory rank-1 cuts were applied. However, to our knowledge, this is a first attempt at incorporating for the VRPTW a set of valid inequalities specialized for the set partitioning polytope.

Computational results show that the use of clique inequalities improves the lower bound at the root node of the search tree and reduces the number of nodes in this tree.