基于合作博弈论的多配送中心协作VRP问题利益分配

周奇才，方 华，熊肖磊，赵 炯，周雨晴

（同济大学 机械与能源工程学院，上海 201800）

基于合作博弈论的多配送中心协作VRP问题利益分配

周奇才，方 华，熊肖磊，赵 炯，周雨晴

（同济大学 机械与能源工程学院，上海 201800）

提出了一种协同配送的车辆路径问题CoMDVRP(cooperative mutiple depots vehicle routing problem)，通过对传统配送与协同配送的成本进行比较分析，显示协同配送成本实现了有效降低；然后对其合作联盟稳定性进行分析，采用合作博弈的Shapley值、Core center、τ值对每位成员的边界贡献值进行量化，以公平分配合作带来的收益；最后基于SMP原则，计算得到四种合作序列，保证了在这些合作顺序中，每一位成员的收益都是递增的。

CoMDVRP；合作博弈论；利益分配；多配送中心

1 引言

目前VRP的研究多集中在实现单个厂家（Player）单个配送中心或者单个厂家多个配送中心运输成本最小化的算法优化，协作配送研究较少，且实现协同配送后需考虑另一个问题：怎么通过合理的利益分配来保证合作联盟的稳定性。基于此，提出一种协作配送的CoMDVRP问题，并采用TUG（Transferable Utility Game）支付可转移联盟博弈的方法，研究合作联盟的利益分配问题。

MDVRP中配送中心只负责配送各自顾客，不论远近。CoMDVRP中各配送中心之间可以组成联盟进行协

以4个配送中心、50位顾客为例，用遗传算法计算15种合作联盟的最短配送路径，其中4人合作总联盟带来的收益最高，以总联盟为对象，分析不同厂家之间的利益分配公平与否，是本文的研究重点，一旦分配不合理，联盟将面临破裂。博弈论的应用旨在通过合理的分配原则维持联盟的稳定性（Stable）。

2 CoMDVRP路径优化

同配送，协作配送带来的路径优化结果，显然优于各自独立配送，如图1所示。但对于如何选择性加入联盟，加入联盟之后如何尽可能获得相对以前各自为营更多的收入，以及后期利益如何分配都是厂家需要考虑的。以配送中心坐标A（20km,20km）、B（30km,40km）、C（50km,30km）、D（60km,50km）以及其拥有的50位顾客为例，研究多配送中心协作配送带来的成本降低问题。

图1 合作前与合作后的路径优化示例

A配送中心有10个客户，B配送中心有15个客户，C配送中心有15个客户，D配送中心有10个客户。已知每个客户的位置坐标见表1，四个配送中心的位置坐标见上文；每个客户需求见表2。一个4人联盟，除去空集一共有15种联盟，对每一种联盟采用遗传算法多次迭代后进行求解，迭代次数为100次，种群大小为联盟成员的个数。

利用Matlab求得各配送中心之间的距离，表3是第一个配送中心A(20km,20km)的10个顾客之间的距离(其余略)。

表1 各配送中心拥有的客户位置坐标(单位：km)

表2 各客户的产品需求

表3 Player1的10个顾客之间的距离

采用遗传算法对各配送中心个体先进行优化，种群大小为100，交叉比率Pc=0.8，变异比率Pm=0.3。得到路线见表4。一个4成员博弈，除去空集共有15种联盟，对每一种联盟采用遗传算法多次迭代后求最优。表5是四人协作总联盟的最优路径，配送路径有效缩短23%，由原来的1 355km降低到1 044km。

3 合作博弈与利益分配

合作博弈是指参与者能够联合达成一个具有约束力且可强制执行协议的博弈类型，是一个研究合作联盟里参与者如何动作以达到利益最大化的理论，并且合理分配保证联盟稳定性[2]。

表4 单独配送最优路径

表5 所有成员协作配送最优路径

国内已有一些供应链系统中利益分配的研究，少有研究不同配送中心之间协作配送带来的成本降低问题，本文提出减少车辆路径的CoMDVRP模式，是一种协作博弈，需要将利益合理分配才能保证联盟稳定性。采用博弈论的方法对协同配送后带来的利益进行合理分配，并探究怎样的合作顺序能使联盟规模扩大时每一个厂家的利益都相应增多。运用博弈论中的Shapley值、Core center（核心）、τ值的计算，表征每个厂家在不同联盟中的贡献值。并基于SMP计算出利益单调增长合作序列，为第三方供应商合理安排其合作顺序、保证合作的利益单调增长性[3](monotonic)提供依据。

3.1 合作博弈的解

3.1.1 Shapley值。设n为配送中心的个数，则2n-1为除去空集后的非空联盟集的个数。N为四个配送中心一起合作的总联盟，T是合作厂家数小于N的联盟。令φ(T,v)为合作博弈联盟T中v的特征函数，用来表征v对联盟T的边界贡献值。沙普利值[4]为：

此模型有四个性质：高效性，确保了总联盟的所有收益都将分配给联盟所有成员；对称性，确保了一旦有两位联盟成员的边界贡献值一样，则从联盟获利相同；虚假性，确保了如果有成员对所加入的任意联盟边界贡献值均为零，则其所得收益也为零；单调性，确保了联盟成员收益随着边界贡献值的增大而增大。

为了实现协同，需要LSP(物流服务提供商)进行厂家之间的货物调配，LSP需要从协同配送的收益中抽取一部分作为其经营管理费用。在此定义协同需求系数为δ∈[0,1]，用以量化LSP从总联盟收益中获取的利益比例。LSP希望δ值越大越好，而联盟成员希望δ尽量小。

其中C(T)指联盟路径总花费，C(i)指联盟某个成员的路径花费。取δ=0.15，卡车每百公里油耗8l，成品油价格6.5元/l。将v(T)计算出的值代入式(1)得各联盟的沙普利值，见表6。

表6 所有联盟的路径花费与边界贡献值

3.1.2 Core center。合作博弈论另一个重要的概念是Core center，一个支付可转移联盟博弈的核心Core center是一个集合，集合当中所有能满足以下两个条件：既要满足整体理性，又要满足总联盟N中所有小联盟的理性。如果合作博弈的一组可行分配不在核心中，那就存在另一个联盟，该联盟的参与人可通过更好的合作。核心的定义为：

如果一个合作的核心不为空集，则此合作是稳定的，核心是一组使每个联盟都获得收益的联盟解集。用Matlab中TUGlab工具箱对总联盟进行计算得：CC=(20.158 4;42.761 5;36.692 8;31.427 1)。

3.1.3 τ值。τ值是对拟均衡博弈定义[6]，这个值是基于一个博弈v∈GN的上向量(upper vector)M(N,v)和下向量(lower vector)m(v)定义的。对于一个博弈v∈GN，其τ值由式（4）定义：

用Matlab中TUGlab工具箱对总联盟进行计算得：tau=(22.771 9;43.228 1;41.771 9;29.228 1)；alfa=0.543 9。

3.1.4 解集分析。将上面的计算结果汇总得表7，发现各联盟用不同方法计算出的边界贡献值近似。并用TUGlab画出解集空间，如图2所示。

表7 四人总联盟中各配送中心的Shapley、Core center、τ值

图2 解集空间

从图3得到单调递增合作序列为：(2341;3241;4231; 4321)，见表8。

由TUGlab计算出总联盟博弈为超可加的，但是显然从图2看出解空间的某一个角在坐标空间内部，根据凸博弈的性质，解空间的每一个角都代表边界贡献值，必须在坐标空间内部，才是凸博弈。故此总联盟博弈为超可加的非凸博弈，其各成员的边界贡献值参考表7，且总联盟协同带来的收益可以按上述边界贡献值进行分配。

3.2 基于SMP的联盟合作顺序

除了保证联盟利益分配的公平以外，对于新成员加入联盟给联盟原有的成员带来的影响，则需要另外考虑。若某个成员在原先联盟里的贡献值比新组成的联盟贡献小，则此成员有充分理由离开联盟。因此合作的顺序要严格保证联盟各成员利益呈单调增长性，即SMP (Strictly Monotonic Path)(Cruijssen et al.2010;Wang ea al., 2015b)。成本降低比例可按如下公式计算：

其中π(i)是厂家i在序列π中的顺序，在博弈论中，设S,T,M⊆N，且满足S⊂T⊂NM的这样一个联盟，若v(S⋃M)-V(S)＜v(T⋃M)-u(T)，则称此联盟是严格凸博弈。假设某个联盟为严格凸博弈，那么此联盟序列一定是一个SMP序列[7]。代入式(6)进行计算，得合作成本降低比例，如图3所示。

图3 基于SMP原则的总联盟合作序列

表8 基于SMP原则的收益增长合作序列

4 结论

提出一种协同配送的车辆路径问题CoMDVRP，通过遗传算法对15种联盟配送路径进行优化，将4成员形成的总联盟配送成本与各配送中心配送成本之和进行对比分析，证明成本有效降低了23%。

对其合作联盟稳定性进行分析，采用支付可转移联盟博弈方法对每位成员的边界贡献值进行量化。最后基于SMP原则，计算得到几种合作序列(2341;3241; 4231;4321)，保证了在这种合作顺序中，每一位成员的收益都是递增的。

[1]巩固,胡晓婷,卫开夏,郝国生.物流配送车辆路径问题的优化研究[J].计算机工程与科学,2011,33(5):106-111.

[2]Rodica Branzei,Dinko Dimitrov,Stef Tijs,著,刘小冬,刘九强,译.合作博弈理论模型[M].北京:科学出版社,2011.

[3]Yong W,Xiao M,Zhibin L,Yong L,Maozeng X,Yinhai.Profit distribution in collaborative multiple centers vehicle routing problem[J].Journal of Cleaner Production,2017,(144):203-219.

[4]Shapley L S.A value for n-person Games[J].Ann,Math Stud, 1953,28.

[5]Mirás Calvo M A,Sánchez Rodr i´guez E.TUGlab:A Cooperative Game Theory Toolbox[EB/OL].http://webs.uvigo.es/ mmiras/TUGlab/TUGlabICM06.pdf.

[6]Sedighe Z,Ashkan H,Seyed Sajad G.Cooperative vehicle routing problem:an opportunity for cost saving[J].Journal of Industrial Engineering International,2016,(12):271-286.

[7]Frans Cruijssen,Peter Borm,Hein Fleuren,Herbert Hamers. Supplier-initiated outsourcing:A methodology to exploit synergy in transportation[J].European Journal of Operational Research,2010,(207):763-774.

Benefit Allocation in VRP with Multiple Cooperative Depots Based on Game Theory

Zhou Qicai,Fang Hua,XiongXiaolei,Zhao Jiong,Zhou Yuqing
(School of Mechanical&Energy Engineering,Tongji University,Shanghai 201800,China)

In this paper,we proposed a cooperative multiple depots vehicle routing problem(CoMDVRP)and then through a comparative analysis of the cost of the traditional distribution process and the cooperative distribution process,concluded the latter effectively reduced cost.Next,we analyzed the stability of the cooperative alliance involved and quantified the marginal contribution of each of the members based on the Shapley value and core center value in the cooperative game for the purpose to fairly allocate the benefits from the cooperation.At the end,based on the SMP principle,we worked out four cooperative sequences where the benefit to each member would grow progressively.

CoMDVRP;cooperative game theory;benefit allocation;multiple depots

F224;F252.14

A

1005-152X(2017)08-0067-04

2017-07-08

周奇才（1962-），博士，教授，博士研究生导师，主要研究方向：机电一体化、现代物流技术装备控制及自动化、复杂系统及装备监测与控制；方华（1994-），硕士研究生，主要研究方向：机电一体化、物流技术与装备。

doi∶10.3969/j.issn.1005-152X.2017.08.016