A P-step Formulation for the Capacitated Vehicle Routing Problem

Abstract:

For vehicle routing problems there are two main types of formulations that are commonly used: arc-flow formulations and set-partitioning formulations. Arc-flow formulations typically include decision variables specifying whether an arc is used or not, while set-partitioning formulations include decision variables specifying whether a route is used or not. The former are known for providing weak LP-bounds that can be computed fast, while the latter provide strong LP-bounds that require more computation time. We provide a new formulation based on partial routes containing exactly p arcs, referred to as p-steps. This provides a family of formulations, one for every choice of p, that has arc-flow and set partitioning formulations at its extremes. We are able to show that the LP-bounds are increasing in p, although non-monotonically. Furthermore, we propose a column generation algorithm to compute these bounds. We investigate whether the computation time also increases in p. The goal is to find a value p that provides a good trade-off between strength of the LP-bound and computation time to speed up the branching algorithms to find integer optimal solutions.