基于合作博弈論的多配送中心協作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