A p-step formulation for the capacitated vehicle routing problem

We introduce a p-step formulation for the capacitated vehicle routing problem (CVRP). The parameter p indicates the length of partial paths corresponding to the used variables. This provides a family of formulations including both the traditional arc-based and path-based formulations. Hence, it is a generalization which unifies arc-based and path-based formulations, while also providing new formulations. We show that the LP bound of the p-step formulation is increasing in p, although not monotonically. Furthermore, we prove that computing the set partitioning bound is NP-hard. This is a meaningful result in itself, but combined with the p-step formulation this also allows us to show that there does not exist a strongest compact formulation for the CVRP, if P ≠ NP. While ending the search for a strongest compact formulation, we propose the search for the strongest formulation of the CVRP with a number of variables and constraints limited by a polynomial of fixed degree. We provide new strongest such formulations of degree three and higher by using a corresponding p-step formulation. Furthermore, the results of our experiments suggest that there are computational advantages from using the p-step formulation, instead of traditional arc-based and path-based formulations.