基于限制博弈的具有容量限制的易腐品聯(lián)合運輸費用分攤問題

單而芳, 梁莉敏, 張 廣

(上海大學管理學院, 上海 200444)

1 引言

易腐品，尤其是生鮮農(nóng)產(chǎn)品的新鮮度對其銷售價格有極大的影響。因此，保證易腐品的新鮮度對保證零售商的利潤具有重要的意義。易腐品的新鮮度通常會隨著時間的流逝而下降，在其整個生命周期中, 效用呈現(xiàn)遞減趨勢[1]。張琳和龐燕[2]指出，我國蔬果在運輸過程中的損失率高達30%～40%。

目前易腐品運輸問題的研究主要有兩個方面。第一方面是主要研究在新鮮度或易腐品最終質(zhì)量與運輸過程中各種影響因素(運輸設施、運輸時間、保鮮技術等)之間的關系。van Arsdel和Guadagni[3]研究了冷凍食品的最終質(zhì)量與流通階段的溫度、流通時間等的關系，并得到“溫度越低(一定限度內(nèi))，冷凍食品的質(zhì)量下降越慢，保質(zhì)期也相應延長”的基本結論。因此在易腐品存儲與運輸過程中，冷藏或冷凍技術的使用在為易腐品提供安全保障的同時， 也可以有效地延緩易腐品新鮮度降低的速度，進而保證了易腐品零售商的銷售利潤。Sider[4]指出在競爭性市場環(huán)境下，易腐品的零售商可能會以較高的運輸成本來減少運輸時間，從而通過保持易腐品的新鮮度來獲得較高的市場價格，進而得到更高的銷售利潤。張玉潔[5]研究易腐品分類以及特點，并指出易腐品運輸組織應注意的問題、原則、鮮活貨物運輸?shù)奶攸c及組織方法。

第二方面主要研究易腐性產(chǎn)品的運輸協(xié)調(diào)問題。Hsu等[6]研究了易腐性產(chǎn)品的運輸路徑選擇問題，旨在運輸過程中，通過協(xié)調(diào)行駛時間和溫度，進而保證易腐品的新鮮度。朱麗君[7]綜合考慮了在供應商管理庫存的模式下，供應商向需求商配送兩種可以相互替代產(chǎn)品，同時考慮需求商的時間窗要求，以運輸成本和貨損成本最小為目標函數(shù)，建立易腐農(nóng)產(chǎn)品調(diào)度問題模型，利用粒子群算法求解，仿真結果驗證了模型和算法的有效性。張奕和傅少川[8]研究了一個易腐品供應商使用多個運輸設施進行配送的庫存路徑問題，通過建立隨機需求的多周期易腐品庫存路徑問題模型，將庫存控制和路徑選擇整合優(yōu)化。林峰、賈濤和李然[9]同樣研究了一個易腐品供應商給多個客戶進行配送的庫存路徑問題，創(chuàng)新性的考慮了在運輸過程和銷售過程中產(chǎn)品具有不同的腐敗速率，以包括生產(chǎn)、配送、腐敗、庫存成本在內(nèi)的供應鏈總成本為目標函數(shù)，建立了總成本最小化的模型。從文獻綜述看來，易腐性產(chǎn)品庫存路徑問題是研究的熱點，但鮮有論文研究運輸設施選擇問題，且大部分為定性分析，缺乏定量分析。李軍和蔡小強[10-11]討論了易腐品的運輸設施選擇問題，并通過構建線性價值和負指數(shù)價值損失函數(shù)來衡量因易腐品新鮮度下降而造成的損失，他們沒有考慮運輸設施所采用的冷藏或冷凍技術有減緩易腐品新鮮度下降速度的作用。

在零售商需求量不大的情況下不同的零售商通常會考慮聯(lián)合運輸，即選用同一個運輸設施來滿足他們的需求，最后再共同承擔運輸?shù)母黜椯M用。此類問題通常稱作易腐品聯(lián)合運的費用分攤問題。該問題的關鍵在于費用分攤方案的設計。若費用分攤方式不合理，就會導致某些參與聯(lián)合運輸?shù)牧闶凵桃蜇摀讼鄬^多的費用而拒絕合作，最終導致聯(lián)合運輸聯(lián)盟的破裂。因此， 制定一個公平合理的成本分攤規(guī)則是合作能夠持續(xù)進行、提高運輸效率的關鍵。

許多學者從不同的角度研究了收益及費用的分配方法。Yong[12]研究了成本分攤問題的基本方法、原則及相關應用。在各類政治、經(jīng)濟和社會活動中，合作共贏是人們關注的焦點問題， 由于合作博弈能夠給出公平合理的利潤分配方案或成本分攤規(guī)則，因此它被廣泛應用到各個領域。Drechsel[13]研究了物流運輸中的利潤分配和成本分攤問題。對河流沿線城市水資源分配問題，Ambec和Sprumont[14]進行了深入研究。 Gilles[15]對具有等級劃分的組織的利潤分配問題進行了討論，而Guan Xin等[16]則利用合作博弈解決通訊網(wǎng)絡搭建及選址問題。關于運輸費用分攤問題，曾銀蓮等[17]和曾銀蓮[18]研究了兩種合并運輸策略下的成本分攤博弈模型，并設計了具有穩(wěn)定性的分配方案，即支付向量是核中的元素。Su Luan和Hu Dawei[19]利用合作博弈為旅游景點的公共運營車輛與私人營運車輛的合作提供合理的利潤分配方案，使公共運營車輛與私人營運車輛的合作聯(lián)盟更穩(wěn)定，從而增加旅游景點的整體社會效益。馮海榮、李軍和曾銀蓮[20]研究了在各零售商獨立采購時基于兩級信用支付的庫存模型。并應用合作博弈理論，將聯(lián)合采購下的費用分配問題構造成基于兩級信用支付的易腐品聯(lián)合采購博弈。研究表明，與各零售商獨立采購相比，聯(lián)合采購降低了各零售商的總費用，提高了產(chǎn)品的補貨頻率，減少了由產(chǎn)品變質(zhì)帶來的損失。

核心是合作博弈中重要的解概念，作為合作博弈的一個穩(wěn)定解，核對應的分配方案是一個公平的分配方案。不過，對于許多合作博弈，確定其核分配是NP-難問題。人們在研究運輸博弈時[21]，考慮到運輸博弈屬于線性規(guī)劃博弈，因此常把研究的關注點放在核非空與線性規(guī)劃松弛的對偶最優(yōu)解之間的關系上。Goemans和Skutella[22]證明了無約束運輸設施選址問題其核非空當且僅當其線性規(guī)劃松弛無整數(shù)間隙(Integrality gap)。但同時也證明了判定線性規(guī)劃松弛是否無整數(shù)間隙是NP-完全問題。人們注意到凹博弈的核一定非空，因此具有凹性的博弈模型被廣泛研究。李軍和蔡小強[10-11]建立了具有固定運輸費用的易腐性產(chǎn)品聯(lián)合運輸?shù)馁M用分攤博弈模型，證明該博弈為凹博弈，并得到在易腐品線性價值以及負指數(shù)價值損失的情況下，核分配非空的結論。他們也討論了當每個運輸設施只能執(zhí)行兩項任務時的運輸設施選擇問題，并得到結論：當該問題的線性規(guī)劃松弛問題無整數(shù)解時該博弈的核不存在；最后他們指出有約束的運輸設施選擇博弈的核有可能為空。

在經(jīng)典的合作博弈中，通常假定所有的合作聯(lián)盟都可以形成，并且這些聯(lián)盟會影響到各參與者最終的支付[23]。然而，在現(xiàn)實生活中，由于受到某些因素(例如，地域、文化背景、社會地位等)的影響，并非所有的聯(lián)盟都能形成。這促使了具有限制結構的合作博弈(簡稱為限制博弈)的產(chǎn)生。其中，Aumann和Dreze[24]研究了具有聯(lián)盟結構的限制博弈。Myerson[25]則研究了具有圖結構的限制博弈。通常，限制博弈可以被定義為一個三元組(N，c，Ω)，其中N為有限的參與者集合，c為特征函數(shù)，Ω為可行聯(lián)盟(即可以形成的聯(lián)盟)的集合，并且φ，N∈Ω，即空集和大聯(lián)盟均是可行聯(lián)盟[26]。Faigle[27]研究了大聯(lián)盟不是可行聯(lián)盟的情況(即N?Ω)，進而定義了一個四元組(N，c，Ω，c0)，其中c(N)=c0?？尚新?lián)盟集Ω通常有多種表現(xiàn)形式，例如，Owen[28]定義的優(yōu)先聯(lián)盟(即在博弈開始之前參與者約定結盟并統(tǒng)一行動)，Myerson[25]通過圖結構假定只有連通的參與者才能形成聯(lián)盟， 而Gilles和Owen[29]則通過準許結構假設參與者要獲得其上級的同意才可以形成聯(lián)盟等。此外，Bilbao[30]給出了凸幾何結構的特點。

2 問題的模型描述及相關符號

我們考慮某一區(qū)域的易腐品零售商在某個時間段T需要一定量的同種易腐品，且市場上有一些具有不同運輸時間、保鮮技術和運輸費用的運輸設施可以選擇。

對于一個易腐品零售商來說，在選擇運輸設施時，他需要考慮運輸成本、運輸時間和保鮮效果。本文將易腐品新鮮度的變化量價值化，將它看作為費用。因此零售商要承擔包括運輸成本和易腐品新鮮度下降帶來的損失在內(nèi)的總費用。在易腐品需求量不大的情況下，一些零售商可以考慮選擇同一個運輸設施來實現(xiàn)聯(lián)合運輸。這就是找到一個運輸設施使總費用最小的設施選擇問題。

通常，用新鮮度因子來刻畫易腐品的新鮮度。但在不同的情況下新鮮度因子的定義也不一樣。但斌等[31]通過構建具有加速衰減特征的指數(shù)函數(shù)θt=θ0e-ηt來作為生鮮農(nóng)產(chǎn)品新鮮度因子的表達式，并建立了考慮消費者效用與保鮮的易腐品EQO模型。李瀅棠[32]認為果蔬品供應鏈網(wǎng)絡中的某節(jié)點的新鮮度因子的大小取決于其上游的節(jié)點的果蔬品新鮮度因子的大小，并通過θi=f{θi-1}來表達果蔬品新鮮度的迭代關系， 并在此基礎上研究了供應鏈協(xié)同決策的問題。

本文借鑒新鮮度因子的概念，將運輸設施i對易腐品新鮮度的影響Δθi定義為：Δθi=eηti-ui。 其中η表示易腐品新鮮度隨著時間衰減的速度，η>0，η越大表示易腐品新鮮度衰減速度越快，η由易腐品的種類決定。ηti-ui≤0即保鮮技術僅能起到保持易腐品新鮮度的作用，無法使易腐品新鮮度提高。本文定義易腐品新鮮度對價格的影響為：Δp=aΔθ，其中a為新鮮度對價格的影響系數(shù)，a>0，易腐品的種類不同，a值也將不同。

定義1 對于i∈L，j∈N，易腐品運輸設施選擇問題定義為：

(1)

(2)

xij≤yi?i∈L,j∈N

(3)

xij,yi=0或1

(4)

(5)

其中yi=1時,表示運輸設施i開放,可以被使用,i∈L，否則yi=0。xij=1時，表示零售商j選擇運輸設施i，?i∈L,j∈N；否則xij=0。

目標函數(shù)(1)表示總費用(包括固定費用， 變動成本和因新鮮度下降導致的價值損失)最??；約束(2)-(3)保證了每個零售商僅被一個開放的運輸設施服務；約束(5)確保零售商的總需求不超過其所選定的運輸設施的容量。

上述模型的目的是對考慮容量限制的運輸設施選擇問題，找一個極小化總費用的最佳方案。考慮對應于選擇的運輸設施，是否總費用能夠被公平地、平穩(wěn)地在所有零售商之間進行分攤。

即可行聯(lián)盟內(nèi)所有零售商的運輸需求總和不能超過所有種類的運輸設施的最小容量，Ω為所有可行聯(lián)盟的集合。對于所有的可行聯(lián)盟T∈Ω：

對于所有S?Ω，S可以劃分成有限個可行的子聯(lián)盟，且各個可行子聯(lián)盟之間互不相交，那么就記這種劃分的集合為P(S,Ω)，則：

注意到當S∈Ω時，P(S,Ω)={S}。因為考慮了容量限制，所以大聯(lián)盟N?Ω，則必然存在劃分p*，使大聯(lián)盟的費用最小，也即：

xij≤yi?i∈L,j∈R。

xij,yi=0或1。

3 易腐品聯(lián)合運輸費用分攤博弈的特征

(1)對于所有S,T∈Ω，S∩T=φ且{S∪T}∈Ω，則有：

和

因為{S∪T}∈Ω，則

和

那么，我們有：

(6)

和

(7)

若FCS>FCT，則Δθ(tS,uS)<Δθ(tT,uT)，所以(6)<0。也即：

(8)

若FCS

(9)

(2)對于所有S,T∈Ω，S∩T=φ且{S∪T}?Ω，則聯(lián)盟S∩T可以劃分為有限個可行子聯(lián)盟R，且各個子聯(lián)盟之間互不相交，這種劃分記為P(S∪T,Ω)，那么

因為{S∪T}∈P(S∪T,Ω)，易得：

(3)對于所有的S,T?Ω，S∩T=φ，則有S∪T?Ω。不可行聯(lián)盟S的劃分為P(S,Ω)；T的劃分為P(T,Ω)；S∪T的劃分為P(S∪T,Ω)。

因為(P(T,Ω)∪P(S,Ω))?P(S∪T,Ω)，所以

(4)對于所有S∈Ω，T?Ω，且滿足S∩T=φ和S∪T?Ω。則聯(lián)盟S的劃分為P(S,Ω)，聯(lián)盟S∪T的劃分為P(S∪T,Ω)。

因為對于所有的p(S,Ω)∈P(S,Ω)，都滿足(p(S,Ω)∪T)∈P(S∪T,Ω)。易得：

命題1說明不同的零售商之間合作選擇同一運輸設施來運輸他們需要的易腐品會更節(jié)省成本，進而說明易腐品零售商之間的合作是有意義的。

命題2 若S?T∈Ω， 則對應于c(S)和c(T)的新鮮度衰減程度Δθ(tS,uS)和Δθ(tT,uT)，有Δθ(tS,uS)≥Δθ(tT,uT)。

證明：因為

(10)

(11)

(12)

(13)

從而可得：

其中，不等式的左側(cè)由式(12)減去式(11)得到，而右側(cè)由式(13)減去式(10)得到。整理后可得Δθ(tS,uS)≥Δθ(tT,uT)。命題2得證。

命題2說明運輸量越大的聯(lián)盟更愿意選擇固定成本(FC)等大,但運輸時間更短,保鮮技術更好的運輸設施來減少易腐品運輸過程中因易腐品新鮮度下降造成的損耗。

證明：令

而

由于

所以

又由于

所以

綜上可得：

aΔθ(tT∪{i},uT∪{i})d{i}≤h(T,{i})≤aΔθ(tT,uT)d{i}

同理，我們有

aΔθ(tS∪{i},uS∪{i})d{i}≤h(S,{i})≤aΔθ(tS,uS)d{i}

容易得到

h(S,{i})-h(T,{i})≥ad{i}[Δθ(tS∪{i},uS∪{i})-Δθ(tT,uT)]

(14)

又因為

因此可得：

(15)

當Δθ(tT,uT)≤Δθ(tS∪{i},uS∪{i})，由式(14)得h(S,{i})-h(T,{i})≥0；否則，由式(15)得h(S,{i})-h(T,{i})≥0。即：

恒成立。命題3得證。

命題3說明一個易腐品零售商或可行聯(lián)盟更愿意加入規(guī)模更大的可行聯(lián)盟。下面的命題給出了限制核非空的充分條件。

Rl(T∪{i})=Rl(T)或Rl(T)?Rl(T∪{i})。

因為Rl(T),Rl(S),Rl(T∪{i}),Rl(S∪{i})∈Ω，l=(1,2,…,k)，因此由命題3易得下面的式子成立：對每個l=1,2,…,k，

c(Rl(T)∪{i})-c(Rl(T))≤c(Rl(S)∪{i})-c(Rl(S))

(16)

4 實例分析

易腐品零售商N={1,2,3,4}，4個零售商各自的需求d={1.8,3.2,1.9,2.2}。

運輸設施集L={A,B,C}，有固定成本FC={FCA,FCB,FCC}={0.8,3.7,6.2}，單位時間的變動成本VC={VCA,VCB,VCC}={1.5,1.4,1.3}，運輸時間t={tA,tB,tC}={3.5,2.4,1.7}，保險技術因子u={uA,uB,uC}={1.25,1.29,1.37}，載荷量Q={QA,QB,QC}={4,5,4}。

假定所有的易腐品零售商運輸同一種易腐品，則新鮮度對價格的影響系數(shù)a和易腐品新鮮度隨著時間衰減速度η是統(tǒng)一的，a=8,η=0.1。此時，容易得到可行聯(lián)盟集為：

Ω={{1},{2},{3},{4},{1,3},{1,4}}。

所有可行聯(lián)盟選擇各個運輸設施所產(chǎn)生的總成本計算如表1。

表1 可行聯(lián)盟選擇各個運輸設施所產(chǎn)生的總成本

x1+x2+x3+x4=46.30

其中x(S)=∑i∈Sxi。該限制核非空，x1={5.0582,16.02,12.23,12.9918}位于限制核里。

我們分別計算Shapley值φ(S)，τ-值和核仁η(S)(見表3)。

表2 限制博弈的特征函數(shù)值

表3 限制博弈的一些解

由表3可以知道：τ-值τ(S)和核仁η(S)和Shapley值φ(S)都不在和核心中。

5 結語

隨著社會經(jīng)濟的發(fā)展，人們對易腐品的需求越來越大，而質(zhì)量要求也越來越高。因為易腐品的運輸呈運量小批量化的特點，所以易腐品零售商采用聯(lián)合運輸，共同選擇性能好的運輸設施。 本文考慮了運輸設施的保鮮技術對易腐品新鮮度的影響，建立考慮容量限制的易腐品運輸設施選擇問題模型，并借鑒限制博弈的可行聯(lián)盟的思想將該模型的費用分攤問題轉(zhuǎn)化為限制博弈模型，最后通過證明該限制博弈的凹性，得到了該限制核非空的充分條件。研究結果表明，在多個零售商合作選擇運輸設施來運輸生鮮農(nóng)產(chǎn)品時， 則傾向于選擇一個租金較昂貴的運輸設施，此時來獲得更短的運輸時間和更好的保鮮技術來降低總成本。本文研究的易腐品運輸設施選擇問題只是一類情形。事實上，有時產(chǎn)品質(zhì)量等因素也有限制要求，此類約束的運輸設施選擇博弈還待進一步研究。

致謝： 感謝評審專家的仔細閱讀和有價值的建議。