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 that unifies arc-based and path-based formulations while also providing new formulations. We show that the LP bound of the p-step formulation has an increasing trend but does not increase monotonically. In particular, the LP bound increases when multiplying p by an integer, whereas an increase, decrease, or no change may be observed otherwise. Furthermore, we prove that computing the set partitioning bound is NP-hard, enabling us in combination with the p-step formulation to show that there does not exist a strongest compact formulation for the CVRP, if $P\ne 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.

Supplemental Material: The online appendices are available at https://doi.org/10.1287/trsc.2024.0936.