协作车辆路径成本分摊问题的 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 Shapley与Shapley的成本分摊结果之间仅有细微的偏差, 其平均准确度可以达到95%左右.

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

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 (N22N) to O (N2log2N) , but also can lower the number of vehicle routing problems to be solved from 2N-1 to 2 N-1.As a result, the cost allocation of collaborative delivery can be completed within a reasonable time.Calculation results of numerical examples 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 about 95%.