On the nucleolus of the basic vehicle routing game

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. The authors 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 nonempty. 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 the authors study is such that the values of the characteristic function are obtained from the solution of a set of mathematical programming problems. They do not require an explicit description of the characteristic function for all coalitions. Instead, by applying a constraint generation approach, the authors evaluate information about the function only when it is needed for computation of the nucleolus.