Comparison between LP bound of the Two-Index and the Three-Index Vehicle Flow Formulation for the Capacitated Vehicle Routing Problem

This paper looks into the Two-Index Vehicle Flow Formulation and the Three-Index Vehicle Flow For- mulation for the Capacitated Vehicle Routing Problem. Aside from comparing the number of variables and constraints, we also compare the strength of the LP bound of each formulation. As a result, we found that the Two-Index Vehicle Flow Formulation produces stronger LP bound than the Three-Index Formulation. Furthermore, we also found that these formulation deals with slightly dierent problems. Thus, we adjusted the two formulations so that they solve the same problem, while also prove that the LP bound of the Two-Index Formulation is at least that of the Three-Index Formulation.