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.