An approximate iterative algorithm for generating cost sharing nucleolus of collaborative vehicle routing problem.

The collaborative distribution problem is a typical combined optimization cooperative game problem, and is named the collaborative vehicle routing problem. One of its core problems is to determine a fair and reasonable cost sharing plan. Among them, the nucleolus solution is a recognized scientific allocation plan in the field of cost sharing because of its uniqueness and fairness. This paper proposes a method to approximate the nucleolus solution of collaborative distribution problem. Firstly, the paper proves the cost allocation of collaborative vehicle routing problem will theoretically be a convex game problem when the location of the customer is evenly distributed. Based on the theory that the nucleolus solution will be equivalent to the prekernel solution in convex game problems, an approximate iterative algorithm (AIA) is proposed to get the nucleolus solution of convex game problems. The complexity of AIA is O(n42n), and then the paper proposes two effective speed-up strategies of AIA, which reduce the complexity of AIA to polynomial level. Finally, by solving the cooperative distribution examples, it is verified that the AIA algorithm in this paper can accurately solve the nucleolus solution of the collaborative distribution cost allocation problem. The proposed solution can effectively reduce the time-consuming of calculation. And the average deviation between the final result of AIA and the actual nucleolus solution is less than 0.02%. More importantly, AIA can be used to get the nucleolus solution in all convex games. [ABSTRACT FROM AUTHOR]