共同配送中成本分攤問題研究

胡 琪

(北京物資學院，北京101149)

一、 引言

近年來物流行業的發展雖然一定程度上促進了物流設施的完善，但是也帶來了物流資源的浪費。 為了降低物流成本，提高物流資源的利用率，共同配送這種模式逐漸興起，共同配送的本質是將零散的客戶聚集在一起進行共同送貨，但如何將節約的成本進行合理的分配成為學者們的研究熱點。

G?the-Lundgren 等人在車輛路徑成本分配問題中，利用集合覆蓋模型計算出博弈的特征值，并運用約束生成方法求解出了核仁。 Engevall 等人將上述文章從單一車型擴展到多車型情況，同樣運用約束生成求解核仁進行總成本的分攤。?sa Hallefjord 等人研究了隱式給出特征函數值的合作博弈，即使是局中人的數量非常多的時候，也可以有效地算出核仁，為求解大規模情況下的核仁提供了有效的方法。 另一些學者對多配送中心的車輛路徑成本分攤進行了研究，姜彥寧等學者為求解多倉庫路徑優化和成本分攤問題建立了一個雙層的規劃模型，第一層模型優化配送路徑；第二層模型利用Shapley 值進行成本分攤。 王勇等人以總成本最小化為目標，運用最小最大費用收益分配模型求解收益分配方案，該方法可以提高聯盟的穩定性。 Joen Dahlberg 等人研究了政府參與調控的VRP 模型，文中分別用Shapley 值、核仁和改進的EPM 進行了成本分配。 V.V.Zakharov 等人研究了大規模運輸網絡中運營商合作下的車輛路徑問題，通過聯合歸納算法構造了滿足次可加性的博弈特征函數，最后利用Shapley 值和次核對成本進行分配。

以上學者的研究雖然比較廣泛，也運用了合作博弈理論中的不同解方案，但是更多的學者傾向于使用Shapley 值，其原因可能是Shapley 值更容易計算，且突出了各個成員對聯盟的貢獻程度，但是Shapley 值有一個缺點就是可能不符合“個人理性”條件。 “個人理性”指的是局中人在聯盟中的成本要小于局中人單干的成本，一旦Shapley 值給出的解方案不滿足個人理性條件，局中人就有離開聯盟的傾向，導致合作失敗。 文章以極小化運輸成本為目標，利用VRP 模型計算實施共同配送的總成本以及所有可能聯盟的最小運輸成本，以所有子聯盟的運輸成本作為特征值進行多種解方案的計算，如Shapley 值、核仁、τ值，并將多種解方案進行比較，選擇出最合理的一種解方案。

二、 問題描述

文章考慮一個零售商、若干個顧客的情況。 零售商需要根據顧客的需求量向其供貨，每位顧客的需求都是確定的常量。 不考慮零售商的庫存能力，即認為其庫存無限大，并且認為零售商的車輛數量不限且車輛型號相同，即每輛車的容量都相同。 不考慮顧客的訂貨成本及零售商的固定成本，以運輸成本極小化為目標，對顧客進行分區配送，這實際上是一個車輛路徑問題(vehicle routing problem，VRP)。 將每個聯盟的極小化的運輸成本作為博弈的特征值，計算不同解方案中每個顧客分攤到的成本。 為了簡化問題，我們做出如下假定:

(1)顧客需要的商品相同，固定的時間段內需求是確定的。

(2)只有一家零售商，即顧客只能從該零售商訂貨。

(3)每位顧客的需求不超過車容量，所有顧客的需求量之和大于車容量。

(4)零售商和顧客都是理性人。

三、 模型建立

(一)合作博弈特征值構建

合作博弈中最為關鍵的就是構造博弈的特征函數，特征函數會對求解方案的結果產生一定影響，文章為了簡化計算，用特征值替代特征函數。 首先，定義如下符號:

N＝{1，2，…，n}為局中人集合；

S表示N的任意一個非空子集，即?S?N，S≠?；

c({i})表示局中人i單干時的成本，文中簡寫為c(i)；

c({S})表示聯盟S形成后的成本，文中簡寫為c(S)；

c({N})表示大聯盟N形成后的成本，文中簡寫為c(N)。

論文博弈的特征值只考慮運輸成本(與距離有關)，通過建立VRP 模型，計算出顧客組成所有可行聯盟的最小總成本即為博弈的特征值。 當局中人個數為N時，共有2N個子聯盟，其中包含1 個空聯盟，空聯盟的特征值定義為c(?)＝0，最終有效的聯盟應為2N-1 個。 為了建立VRP 模型，我們定義如下符號和變量:

V表示點集，包括倉庫和所有顧客；

cij為點i到點j的運輸成本，i＝0，1，…，N，j＝0，1，…，N；

K表示車輛集合，K＝1，2，…，k；

C表示車容量；

qi表示顧客的需求量；

dij表示顧客i到顧客j的距離。

定義如下決策變量:

零售商向顧客供貨的VRP 模型表示如下:

目標函數表示極小化運輸成本，前三個約束保證了每位顧客只由一輛車配送，第四個約束表示使用的車輛數不超過給定的車輛數，第五個約束保證了不超過車輛容量，第六到第八個約束避免形成環路，xij為決策變量。

(二)合作博弈的超可加性

超可加博弈指的是任意兩個不相交的聯盟中的所有局中人組成一個更大的聯盟時，他們所創造的利潤不小于這兩個聯盟各自的利潤之和，即對于局中人所組成的任意兩個聯盟S和T，若S∩T＝?，則必有:

若博弈為超可加的，那么大聯盟就有可能形成，能夠進一步增加利潤。 在計算關于成本分攤博弈時，需要在式子兩邊同時添加負號，驗證博弈是否為次可加的，次可加博弈的實質是形成大聯盟后總成本更少。

(三)合作博弈解方案

大聯盟形成后的成本分配方案可能有無限個，在個體理性的情況下，聯盟中的每位零售商都想得到最有利的分配結果，一旦分配不公平，部分零售商就有可能退出大聯盟，這種合作不一定能長久持續下去。 因此，要使大聯盟穩定，必須保證不存在任何一個子聯盟優于大聯盟。

1. 核解

在合作博弈中，每個局中人i都有一個對應的分配成本xi，每個局中人分配的成本之和應等于大聯盟N的總成本v(N)(即有效性)，同時xi又不能劣于其他分配方案(即個人理性)，這樣博弈的核(Core)就可以定義為:

雖然一般情況下，核的內部有多種解方案，但核也可能為空，因此需要注意博弈是否有非空核。

2. Shapley 值

Shapley 值最早是由羅伊德·夏普利(Lloyd Shapley)在1953 年提出的，該利益分配方法在各個領域都有重要的影響。 Shapley 值是滿足有效性、可加性、策略等價的相對不變性、虛擬局中人性和匿名性的單點解，其根據局中人的貢獻來進行利益(或成本)的分配，它的具體形式如下:

3. 核仁

定義核仁，首先要定義聯盟S關于x的超額θ(x，S)，其中用來衡量聯盟S對于該分配的不滿意程度，可見，θ(x，S)越小，聯盟S的滿意程度越高。 在計算核仁的過程中，需要將θ(x，S)按字典序方式排序，即若k

4.τ值

τ值也是合作博弈中的單點解，我們首先定義上向量M(N，v)和下向量m(v)。M(N，v)是局中人的邊際貢獻，聯盟S中局中人i的邊際貢獻就可以表示為Mi(S，v)＝v(S)-v(S＼{i})。 定義Pσ(i)為在排列σ里排在局中人i之前的局中人集合，Pσ(i)＝ {r∈N｜σ-1(r)<σ-1(i)}，局中人i在排列σ中下向量就可以表示為τ值就可以定義為:

τ(v)＝αm(v)＋(1-α)M(N，v)

四、 算例分析

文章給出的算例中零售商是唯一的，6 個顧客分散在零售商周圍，零售商與顧客坐標、顧客需求如表1 所示，數字0表示零售商，數字1 到6 表示顧客，車容量C＝50 單位，單位運輸成本為1。

表1 零售商與顧客坐標

本文采用MATLAB 軟件進行編程及求解，版本為2015b。由于系統中有6 個顧客，則聯盟總數共有26個，我們定義空聯盟的特征函數為c(?)＝0，即空聯盟的成本為0，根據第三節建立的VRP 模型，通過MATLAB 求解最優路徑以及63 個子聯盟的成本。 計算結果顯示，當零售商單獨向6 位顧客遞送貨物時的總運輸成本為133.8，當使用 VRP 模型進行共同配送時，總成本為89.93，成本降低了43.87，說明共同配送確實能夠有效減少物流成本，具體送貨路徑如圖1 所示，各條路徑的具體線路及成本見表2。

表2 具體路線及成本

圖1 具體遞送路徑

根據圖1，由于顧客2 距離零售商最近，且需求量大，因此由零售商單獨配送；顧客4 和5 距離較近且總需求量沒有超過車容量，因此零售商對其一起送貨，顧客1、3、6 形成了一條配送路線。

在確定了最優配送路徑后，我們計算所有可能的聯盟的運輸成本，并將63 個子聯盟的成本作為博弈的特征值進行成本分攤。 計算結果如表3 所示:

表3 子聯盟成本

通過根據上述博弈的特征值，計算Shapley 值、核仁和τ值，計算結果如表4 所示:

表4 成本分攤結果

圖2 可以更直觀地反映出進行共同配送時的成本下降程度，根據圖2 可以看到每個顧客的成本都有所減少。 由于Shapley 值對成本的分配是根據每個顧客對大聯盟貢獻的多少來確定的，雖然顧客2 自己形成了一條路徑，但是Shapley值認為顧客2 對大聯盟也是有貢獻的，所以顧客2 的成本也有一定減少，而顧客2 成本的減少勢必會帶來其他顧客成本的增加。

圖2 成本分攤結果對比

核仁的計算原則遵循的是最大化最小超額，也就是找到讓最不滿意的聯盟相對滿意的唯一解。 根據核仁的計算結果可以看到，由于顧客2 自己形成了一條線路，它的成本和其單獨配送時的成本相差不大，相比于Shapley 值，顧客1、顧客3 和顧客5 的成本有所下降。

τ值的分配方案與核仁相近，顧客2 的成本同樣是16，顧客3 和顧客6 的成本較核仁分配方案有所下降。

當特征值滿足次可加性時，大聯盟才可能形成；核解是滿足個人理性、集體理性和有效性的解，當分配方案屬于核解時，該聯盟更穩定，因此，接下來利用MatTuGames 工具箱驗證博弈的次可加性以及Shapley 值、核仁和τ值是否在核中。 通過計算，結果顯示該博弈滿足次可加性，說明大聯盟有形成的可能；但是經過計算，Shapley 值與τ值并不在核中，說明這兩種分配方案不滿足集體理性，即Shapley 值與τ值的成本分攤結果不能使聯盟的合作可持續；而核仁的成本分攤結果在核解中，說明核仁解能夠滿足核解的一切性質，能夠使所有參與合作的顧客都滿意。 因此文章的成本分攤結果為顧客1 支付13.5，顧客2 支付16，顧客3 支付17.25，顧客4 支付 12.5，顧客 5 支付 13.5，顧客 6 支付 17.25。

五、 結束語

文章考慮了單零售商多顧客的情況，以極小化運輸成本(與距離有關)為目標，利用VRP 模型計算了實施共同配送時的總成本，相比于單獨配送，合理的共同配送確實可以降低成本，提高貨物的配送效率。 進一步的，文章考慮如何對總成本進行合理分攤，將所有子聯盟的運輸成本作為博弈的特征值，根據特征值進行了多種成本分配方案的計算，并將得出的結果進行了對比，結果顯示進行合作時各個顧客的成本相比于單獨配送時的成本均有所下降，但是Shapley 值與τ值的分配方案不屬于核解，因此若實施這兩種分配方案將會使合作失敗，而核仁的分配方案在核中，因此這種分配方式能夠使聯盟穩定，使合作可持續。