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

摘要：

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

关键词：协作车辆路径问题、核仁解、成本分摊、合作博弈

所属期刊栏目：39

分类号：N945(系统科学)

资助基金：国家社会科学基金16CGL016

在线出版日期：2019-07-22（万方平台首次上网日期，不代表论文的发表时间）

页数：共18页

页码：1517-1534