In this article we introduce the Quadratic Capacitated Vehicle Routing Problem (QCVRP), a combinatorial optimization problem that arises in practical applications in logistics and transportation. The QCVRP extends two other known problems, the Capacitated Vehicle Routing Problem and the Quadratic Symmetric Traveling Salesman Problem, the former by considering a modified cost matrix in which traveling costs are now associated to pairs of two consecutive edges, and the latter by introducing customer demands and vehicle capacities. We present a three-index vehicle-flow formulation for the problem in which variables represent q-edges (pairs of consecutive edges), and strengthen it with several classes of valid inequalities. We present efficient separation routines for the inequalities used in this paper and derive an exact solver based on the branch-and-cut paradigm. We also present an efficient heuristic for finding feasible solutions of the QCVRP quickly, using some state-of-the-art sub-routines from the vehicle routing literature especially adapted for this problem. Parallel implementations of the two algorithms are proposed that take advantage of state-of-the-art multiple-core architectures. We conduct extensive computational experiments to assess the efficiency of the modeling and solution approaches presented, as well as of their parallel implementations. Small- and medium-size problems can be solved to optimality while tight lower and upper bounds are computed for larger - more difficult - problems.