Finding the nucleolus of the vehicle routing game with time windows

摘要

Computing the nucleolus is recognized as an equitable solution to cooperative n person cost games, such as a vehicle routing game (VRG). Computing the nucleolus of a VRG, however, has been limited to small-sized benchmark instances with no more than 25 players, because of the computation time required to solve the NP-hard separation problem. To reduce computation time, we develop an enumerative algorithm that computes the nucleolus of the VRG with time windows (VRGTW) in the case of the non-empty core. Numerical simulations demonstrate the ability of the proposed algorithm to compute the nucleolus of benchmark instances with up to 100 players.