One of the most successful exact approaches for the CVRP is the K-tree method of [Fisher 1994] that succeeded in solving a problem with 71 customers. However, there are smaller instances that have not been exactly solved yet. To treat larger instances, or to compute solutions faster, heuristic methods must be used. It uses a novel Branch and Bound procedure in which the problem is partitioned by fixing the edge incidence of selected subsets of clustered customers. The side constraints are dualized to obtain a Langrangian relaxation that is a minimum degree-constrained K-tree problem.

The K-tree approach can be extended to accommodate realistic variations , such as asymmetric costs, time windows, and non uniform fleets.

A branch and bound algorithm uses a divide and conquer strategy to partition the solution space into subproblems and then optimizes individually over each subproblem. Using branch and bound, we initially examine the entire solution space ${S}$. In the processing or bounding phase, we relax the problem. In so doing, we admit solutions that are not in the feasible set ${S}$. Solving this relaxation yields a lower bound on the value of an optimal solution. If the solution to this relaxation is a member of ${S}$ or has cost equal to that of ${\widehat{s}}$ (where ${\widehat{s} \in S}$), then we are done – either the new solution or ${\widehat{s}}$, respectively, is optimal.

Otherwise, we identify ${n}$ subsets ${S_{1},…,S_{n}}$ of ${S}$, such that ${\bigcup_{i=1}^{n} S_{i} = S}$. Each of these subsets is called a subproblem; ${S_{1},…,S_{n}}$ are sometimes called the children of ${S}$. We add the children of ${S}$ to the list of candidate subproblems (those which await processing). This is called branching. To continue the algorithm, we select one of the candidate subproblems and process it. There are four possible results:

• If we find a feasible solution better than ${\widehat{s}}$, then we replace ${\widehat{s}}$ with the new solution and continue.
• We may also find that the subproblem has no solutions, in which case we discard (prune) it.
• Otherwise, we compare the lower bound for the subproblem to our global upper bound, given by the value of the best feasible solution encountered thus far. If it is greater than or equal to our current upper bound, then we may again prune the subproblem.
• Finally, if we cannot prune the subproblem, we are forced to branch and add the children of this subproblem to the list of active candidates. We continue in this way until the list of candidate subproblems is empty, at which point our current best solution is, in fact, optimal.