In the vehicle routing cost allocation problem the aim is to find a good cost allocation method, i.e. a method that according to specified criteria allocates the cost of an optimal route configuration among the customers. We formulate this problem as a co-operative game in characteristic function form and give conditions for when the core of the vehicle routing game is non-empty. One specific solution concept to the cost allocation problem is the nucleolus, which minimizes maximum discontent among the players in a co-operative game. The class of games we study is such that the values of the characteristic function are obtained from the solution of a set of mathematical programming problems. We do not require an explicit description of the characteristic function for all coalitions. Instead, by applying a constraint generation approach, we evaluate information about the function only when it is needed for the computation of the nucleolus.