Preprocessing to Reduce Vehicle Capacity for Routing Problems

We provide a preprocessing method to reduce the vehicle capacity for instances of the capacitated vehicle routing problem. This improves the LP bound of many formulations of the capacitated vehicle routing problem. It also speeds up common algorithms for which the computation time depends on the vehicle capacity. Our simulation experiments suggest that, perhaps surprisingly, often the vehicle capacity is very tight in the sense that it cannot be reduced by much.