协作车辆路径成本分摊问题的 B-T Shapley 方法
DOI:
作者:
作者单位:

作者简介:

通讯作者:

中图分类号:

TP39;C93

基金项目:

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


A Binary Tree Shapely method for cost sharing of the collaborative vehicle routing problem
Author:
Affiliation:

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

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

    Abstract:

    Cooperation in logistics distribution among enterprises can significantly reduce the cost and emission of logistics delivery. Key research questions are how to model cooperation in logistics distribution and develop a cost sharing method. Traditional cost sharing methods need to calculate the cooperative cost for all sub-coalitions,which is equivalent to solving 2N - 1 complex vehicle routing problems for calculating the cooperative cost of 2N - 1 sub-coalitions ( N is the number of enterprises) . This paper analyzes the properties of the cost sharing problem in collaborative distribution by modeling a multi-cooperation vehicle routing. Based on the classical Shapley cost sharing method,a Binary Tree ( B-T) Shapley method is proposed. The new method can not only reduce the computational complexity of cost sharing from O ( N2 2N ) to O ( N2 log2 N) ,but also can N lower the number of vehicle routing problems to be solved from 2 - 1 to 2N - 1. As a result,the cost alloca- tion of collaborative delivery can be completed within a reasonable time. Calculation results of numerical ex- amples and actual cases show that the time needed for the B-T Shapley method is almost negligible compared with that for the Shapley value method. Moreover,the cost allocation results using the B-T Shapley method only have minor deviations compared with those using the Shapley value method,with an average accuracy of a- bout 95% .

    参考文献
    相似文献
    引证文献
引用本文

饶卫振.协作车辆路径成本分摊问题的 B-T Shapley 方法[J].管理科学学报,2019,22(1):107~126

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:
  • 最后修改日期:
  • 录用日期:
  • 在线发布日期: 2021-10-25
  • 出版日期:
您是第位访问者
管理科学学报 ® 2024 版权所有
通讯地址:天津市南开区卫津路92号天津大学第25教学楼A座908室 邮编:300072
联系电话/传真:022-27403197 电子信箱:jmsc@tju.edu.cn