一种求解协作配送成本分摊问题核仁解的近似迭代算法

协作配送问题是典型的组合优化合作博弈问题,也可称为协作车辆路径问题,其核心问题之一是确定公平合理的成本分摊方案.其中核仁解由于具有唯一性和公平性等特点,是成本分摊领域中公认的科学分摊方案.本文提出了一种近似求解协作配送问题核仁解的方法.首先分析证明了当顾客位置分布均匀,从理论上协作配送成本分摊问题会是凸博弈问题,然后,基于凸博弈的核仁解会等同于预内核解的理论,提出了一个能够求解凸博弈问题核仁解的迭代逼近算法(approximate iterative algorithm,AIA),分析了AIA算法的复杂度为O(n~42~n),为此又提出了AIA的有效提速策略,可将AIA的复杂度降低至多项式.最后,通过求解协作配送算例和实例,验证了本文AIA算法能够准确求解得到协作配送成本分摊问题的核仁解,提出的求解策略能有效的减少求解耗时,并且得到的最终结果与实际核仁解的平均偏差不到0.02%,更重要的是AIA能够用于求解所有凸博弈问题的核仁解.

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(n⁴2ⁿ), 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.