协作车辆路径成本分摊问题的B-T Shapley方法

摘要：

多个企业协作配送能显著地降低物流配送成本和减少尾气排放,研究协作配送模型与成本分摊方法是亟需解决的关键问题.传统经典成本分摊方法需要计算所有子联盟的协作成本,在本问题中等价于需要求解2N-1个(N为企业数量)复杂的车辆路径问题.本文建立了多方协作车辆路径问题模型,分析了协作配送成本分摊问题的属性.基于经典的Shapley成本分摊方法,提出了B-T(Binary Tree)Shapley近似方法,不仅将成本分摊本身计算复杂度由O(N22N)降为O(N2log2N),而且将需要求解的车辆路径问题数量由2N-1个锐减至2N-1个,从而能够在合理时间内完成协作配送问题的成本分摊.通过求解算例和实际案例,计算结果表明,B-T Shapley的耗时与Shapley方法相比几乎可以忽略不计,更重要的是B-T Shap-ley与Shapley的成本分摊结果之间仅有细微的偏差,其平均准确度可以达到95％左右.

关键词：协作车辆路径问题、夏普利值、成本分摊、合作博弈

所属期刊栏目：22

分类号：TP39;C93(计算技术、计算机技术)

资助基金：国家自然科学基金重点项目71632007;国家社会科学基金资助项目16CGL016;博士后基金资助项目2018T110399;山东省自然基金资助项目ZR2018MG001;教育部人文社科基金资助项目15YJC630103

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

页数：共20页

页码：107-126