K-Trees

Given a graph with n + 1 nodes, a K-tree is defined to be a set of n + K edges that span the graph. The VRP can be modeled as the problem of finding a minimum K-tree with degree 2K on the depot, together with side constraints that impose vehicle capacity and the requirement that the degree at each customer must be 2.