依托平台协作配送成本分摊的有效方法研究

Fair and effective cost-sharing method for collaborative distribution based on a third-party platform

依托平台的协作配送问题,在合理时间内有效计算公平成本分摊方案至关重要.核仁解是公认的公平分摊方案,但需要通过复杂的优化计算.提出了一个能通过公式近似快速计算核仁解的方法,发现任意满足总体理性分摊方案χ的2^(n)-1(n为大联盟N中成员数)个子联盟S(S为N的子集)的满意度e(S,χ)之和为常数,且不同χ对应的任意子联盟S与互补联盟N\S的满意度之和,即L_(s)=e(S,χ)+e(N\S,χ)为常数.基于子联盟满意度越均衡,分配方案越合理的准则,构造了分配方案χ对应的所有子联盟满意度均衡量化函数f(χ)=∑[e(S,χ)-0.5L_(s)]^(2).显然,f越小表示子联盟满意度越均衡.证明了存在分配方案χ*使f取到极小值,且χ*满足总体理性、唯一性、可加性、策略等价相对不变性、一致性、匿名性和可比性等众多分摊方案合理属性.最后,采用文章所提方法和核仁解求解方法,计算了诸多已有文献中的成本分摊算例,求解结果表明文章提出的方法计算速度比传统核仁解求解方法快数万倍以上,与最新求解核仁解及Shapley值的有效算法相比也具有明显的性能优势,且求解结果与核仁解的结果平均偏差只有5%左右.更重要的是,提出的新方法本身具有科学内涵,可以应用于任何支付可转移的合作博弈成本分摊问题.

It is crucial to develop a fair and effective cost-sharing solution within reasonable time for collaborative distribution based on a third-party platform.The nucleolus solution is recognized as a commonly-accepted fair allocation solution,but it needs complicated optimization calculation.In this paper,an efficient method is proposed to calculate the nucleolus solution approximately and quickly by a formula,which finds that for any sub-coalitions with a cost-sharing solution χ that satisfies the overall rationality,the sum of e(S,χ),or the sum of satisfaction,of all 2^(n)-1(n is the player number of the big coalition N)sub-coalitions S(S is a subset of N)is a constant,and that the sum of satisfaction of any sub-alliance S and complementary alliance N\S with different χ is e(S,χ)plus e(N\S、χ),which is equal to a constant L_(s).Based on the rule that the more balanced the sub-coalitions' satisfaction e(S,χ),the more reasonable the cost-sharing solution χ,this paper constructs a function f(χ)=∑[e(S,χ)-0.5L_(s)]^(2) which quantifies the satisfaction balance of all sub-alliances with the cost-sharing solution x.Apparently,the smaller the value of f(χ),the more balanced the sub-coalitions' satisfaction e(S,χ).It is proved that there exists a cost-sharing solution χ* that minimizes function f(χ),and that χ* satisfies many reasonable attributes of cost-sharing solutions,such as overall rationality,uniqueness,additivity,relative invariance with respect to strategic equivalence,consistency,anonymity,and comparability.Last,many cost-sharing instances from previous publications are calculated by the method proposed in this paper and the traditional methods for finding nucleolus,respectively.The results demonstrate that the calculation speed of the proposed method is tens of thousands of times faster than that of the traditional linear programming for finding the nucleolus solution.The proposed method is also superior to the latest effective algorithm for calculating the nucleolus solution and the Shapley value.In addition,the average deviation is only about 5χbetween the result calculated by the proposed method and the nucleolus solution.More importantly,the proposed method is able to explain its connotation by scientific principles and can be applied to any cost-sharing problems of cooperative games with transferable payment.