The vehicle routing problem (VRP) is a central problem for many transportation applications. Although it is well known that it is difficult to solve, how much of this difficulty is caused by the formulation of the problem is less understood. This paper experimentally investigates how the solution times to solve a VRP with a general integer programming (IP) solver are affected by the formulation of the VRP used. The different formulations are evaluated by examining solution efficiency as a function of several a priori performance measures based on the data parameters. The experimental results show how the solution run times are sensitive to problem parameters; in particular, the sensitivity of formulations to the coefficient of variation of the cost matrix of travel times is explained by two interacting factors.