無統計信息假設下的多階段報童決策

張 永，張衛國，徐維軍

(1. 廣東工業大學管理學院， 廣東 廣州 510520；2. 華南理工大學工商管理學院， 廣東 廣州 510640)

?

無統計信息假設下的多階段報童決策

張 永1，張衛國2，徐維軍2

(1. 廣東工業大學管理學院， 廣東 廣州 510520；2. 華南理工大學工商管理學院， 廣東 廣州 510640)

在不對需求做任何統計假設的情形下，該文用理論計算科學興起的集成專家意見的弱集成算法研究多階段報童決策。弱集成算法是一種指數加權平均集成方法，在一定的初始權重下，根據損失函數在線調整專家意見的權重。基于收益損失函數和固定訂購量的專家意見，得到了與從累積收益角度研究相一致的決策方法；并擴展研究了帶有回收價值的情形。理論上證明了決策方法的累積收益損失幾乎不超過最優專家意見的累積收益損失。通過數值算例驗證了決策方法的可行性和合理性，探討了賣出價和成本價等因素對競爭性能的影響，說明了回收價值的引入大大提高了決策方法的競爭性能，具有重要的現實意義。

多階段報童問題；回收價值；無統計假設；弱集成算法；收益損失函數

1 引言

報童問題是一類特殊的庫存問題，是近年來庫存決策研究的一個熱點。報紙屬于短周期產品，具有很強的時效性，即當天的報紙只在當天有價值，過期后將沒有價值。若訂購的報紙量多于實際需求量，則剩余報紙的價值為零。在單周期、只訂購一次貨時，面臨不確定型需求的情況下，傳統報童模型解決如何確定最優訂貨量使得期望收益最大化。該模型反映出決策者在庫存成本和缺貨損失之間的權衡；眾多研究都是基于傳統報童模型構建更加貼近現實的模型[1-3]。由于結構簡單而又有良好的性質, 報童模型在管理者的決策中發揮重要的作用并且廣泛應用于各種環境中，如庫存控制，生產計劃，收益管理和股票市場等。因此，眾多研究對報童模型做更深一步的細致研究，從多個方向加以擴展，對于供應鏈領域的研究具有重要的意義[4-7]。報童決策問題的研究對類似庫存決策問題具有重要意義，如各種雜志預定、餐館食物預定、機票預定。

研究報童問題的傳統方法是假設需求服從一定的統計分布，并在此基礎上尋找最優決策方法。但實際需求無任何規律可循，很難用一個合適的概率分布來刻畫。在這種情形下，決策者唯一能獲得的是歷史需求數據，并根據它來進行決策。實際需求的統計分布無法獲得時，研究報童問題的一個傳統方法是貝葉斯決策；應用這個方法進行決策時，決策者只知道需求服從一類分布但不知道其具體參數，在初始化參數下根據獲得的歷史數據逐步計算后驗分布來調整參數。Scarf[8-9]給出了一類具有指數分布的貝葉斯決策方法，Karlin[10]和Iglehart[11]等也用貝葉斯方法對報童問題進行了研究，其中Iglehart[11]擴展了Scarf的研究結果。基于經驗分布的方法也用來研究無統計假設的庫存問題[12]。O’Neil[13]比較了無統計假設和隨機算法下的多階段報童問題。Huh等[14-16]在僅有歷史需求數據下給出了庫存決策的新方法及理論。最近，Zhu Zhisu[17]等給出了有限統計信息下的報童優化方法；Kwon和Cheong[18]給出了免運費時，無統計假設下的報童決策方法。

近年來計算機學科興起的在線算法與競爭分析[19-21]為無統計假設的庫存決策問題提供了研究思路和方法。在線算法將在線的收益(成本)與離線的收益(成本)做比較，并用競爭比來衡量在線算法的競爭性能。基于在線算法的思想，Wanger[22]引入績效比研究收益優化下的多階段庫存決策問題，并將其推廣到可耐性產品的情形。Wagner[23]進一步用競爭比分析方法研究了成本優化下的多階段庫存決策。張桂清等[24-25]用競爭比分析法研究了單階段報童決策問題，分別給出了一般預期和概率預期下的風險算法。Ball等[26]和Van den Heuvel等[27]也是基于競爭比分析和在線算法研究不確定和不完全信息下的庫存決策及相關問題。本文用集成專家意見預測算法研究多階段報童決策；它與上述文獻的不同之處是在無任何統計假設及信息下，僅僅依靠歷史需求數據給出多階段報童決策，研究方法不同。張桂清[25]雖然也是基于在線算法思想給出的決策，但它一方面包含了決策者對未來需求的預期，另外一方面它研究的是單階段的報童決策問題。因此本文基于集成專家預測算法研究了更貼近現實的報童問題。

集成專家意見進行預測是理論計算科學研究的一個熱點[28]，它考慮每個專家的意見，通過賦予權重體現對專家的信任程度，并采用一定的方法集成這些專家意見。集成專家意見方法的研究具有較強的實際意義，因為現實決策中存在著眾多專家意見。集成算法AA (Aggregating Algorithm)是研究學者Vovk提出的一種集成專家意見在線預測方法，它采用指數加權平均法集成專家意見[29]。弱集成算法WAA (Weak Aggregating Algorithm)[30]是基于AA擴展的。Levina等[31]將WAA應用到多階段報童決策，給出了具體的決策方法、并證明了該決策方法的累積收益近似于最優專家意見的累積收益。該方法不對需求做任何統計假設，在僅有歷史需求數據下給出決策。考慮到現實決策中決策者的后悔度，本文在Levina等[31]的基礎上，進一步通過定義收益損失函數研究WAA在多階段報童問題中的應用。將收益損失函數定義為離線收益與決策收益的差值，相當于后悔度。基于收益損失函數和固定訂購量策略的專家意見，不僅得到了與從累積收益角度研究相一致的結論，并擴展研究了帶有回收價值的情形，給出了無統計假設下的具體決策方法。理論上證明了本文給出的決策方法的累積收益損失漸近于最優專家意見的累積收益損失。最后通過具體算例進一步驗證了本文給出的決策方法具有較好的競爭性能，討論了報紙的賣出價、成本價及回收價值對累積收益的影響；擴展了多階段報童決策的研究思路和方法，具有重要的現實意義。

2 基于弱集成算法和固定訂購量策略的決策方法

2.1 基于累積損失的弱集成算法

AA是理論計算機學科興起的集成專家意見的在線序列決策算法[29]。它用損失函數來衡量每個專家意見的優劣，通過在線方式計算每個專家意見的損失并逐步調整對每個專家意見的信任程度。通常損失越大的專家，對其信任程度越小。對專家的信任程度通過對其賦予的權重體現出來。采用指數加權來集成專家意見，并用學習率參數控制每個專家權重更新的幅度。WAA與AA相似，不同之處在于WAA的學習率與在線決策的時間段n相關而AA的學習率是一固定常數[30]。重要的是AA要求損失函數具有混合性(Mixability)，如對數損失函數和平方損失函數是具有混合性的、絕對值損失函數不具有混合性。而WAA的改進可以避免這一局限，使得它可以應用到眾多的決策問題中。

(1)

是專家θ,θ∈Θ在前n-1階段的累積損失。根據Kalnishkan[30]，可將WAA的偽代碼描述如下。

WAA的偽代碼

(1)計算標準化權重

(3)在線決策者集成專家意見給出決策

(4)獲得實際結果wn∈Ω；

(6) 更新在線決策者的累積損失

Ln=Ln-1+λ(rn,wn)

引理1 若損失函數λ是關于r的凸函數，則WAA的累積損失滿足:

(2)

引理2 當0≤λ≤L，其中L為一固定常數，

則對于所有的N有

(3)

2.2 基于收益損失函數和固定訂購量策略的決策方法

(4)

(5)

當q(dx)是[0,U]上的均勻分布時，采用文獻[31]給出的求解方法。在第n階段，前n-1階段的實際需求di, 1≤i≤n-1是可獲得的數據序列，設其順序統計量為d(1),…,d(n-1)，令d(0)=0，d(n)=U，則：

(6)

其中：

(6)中第3個等式成立只因當d(k)≤x≤d(k+1)時，有：

采用類似的方法，可得：

其中:

所以有:

(7)

可見從收益損失研究得到的結論與從收益研究得到的結論一致[31]，當決策者需要從成本角度分析或強調收益損失時，可用本文給出的方法進行決策，并稱此方法為waa。

對于無統計假設下多階段報童決策方法waa，定理1應用WAA，分析了waa的競爭性能。以最優專家意見的累積收益損失為基準，得到了決策方法waa實現的累積收益損失上界。

定理1 當專家意見為集合Θ=[0,U]時，則對任意N， 決策方法waa實現的累積收益損失滿足

(8)

其中Λ=max{p-c,c}和Δ=max{(p-c)U,cU}。

證明 首先給出專家意見為x時，對應收益損失函數λ的上界，即有:

0≤λ≤Δ, Δ=max{(p-c)U,cU}。

事實上，由損失函數的定義(4)式知在任意一個階段，專家意見的最小損失值為0，最大損失值為Δ。因為最壞情形有兩種：一種是當實際需求為U卻訂購0，此時的損失為(p-c)U；另外一種是當實際需求為0卻訂購U，此時的損失為cU。圖1給出了收益損失函數λ與專家意見為x的關系(需求為d)。由圖1也可得出上述結論。

圖1 收益損失λ與專家意見x的函數關系

(9)

式(9)對所有的x成立，故有:

證畢。

定理1說明了決策方法waa的累積收益損失趨近于最優專家意見的累積收益損失。事實上，有:

(10)

3 帶有回收價值的決策方法及競爭性能分析

考慮到環保科學技術的發展和資源的再生利用，引入回收價值對前面的多階段報童決策模型進行擴展研究。假設每單位報紙的回收價值為s，一般地有關系式p>c>s成立，而且s相對來說比較小，稱此問題為多階段報童決策的擴展模型。

(11)

(12)

進一步，根據前面的假設知：

(13)

其中：

(13)中第3個等式成立是因為d(k)≤x≤d(k+1)時，有：

類似地，有：

其中：

所以有：

(14)

因此，(14)給出了帶有回收價值的多階段報童決策方法，記此方法為ewaa。定理2以最優專家意見的累積收益損失為基準，得到了決策方法ewaa實現的累積收益損失上界。

定理2 當固定訂購量專家為集合Θ=[0,U]時，對任意N，ewaa的累積收益損失滿足

(15)

圖2 擴展模型的收益損失與專家意見x的函數關系

根據引理2有：

(16)

式(16)對所有的x成立，因此有：

(17)

4 數值算例

為驗證本文給出決策方法的競爭性能，考慮應用WAA對某公司在未來200天內的報紙需求量進行預測的具體算例。其中每天報紙的最大需求量為U=3 (單位: 百份)，因此專家意見有4個，其對應的策略分別為固定訂購θ=0, 1, 2, 3單位份。在[0, 3]上隨機產生了200個隨機整數，并把它作為該公司在200天內的實際報紙需求序列。分別考慮有無回收價值的情形。表1和2分別給出了決策方法waa和ewaa及各自對應的4個專家意見(分別用exi和eexi，i=1,2,3,4表示)分別在天數N=25，N=50，N=100和N=200時的累積收益損失和累積收益。

表1和2中的結果首先驗證了用累積收益損失和用累積收益得到的結論是相同的，這從累積收益損失函數的定義(4)和(11)式也可看出：離線收益是累積收益損失與累積收益的和，且第一個專家意見ex1或eex1的累積收益損失即是離線收益，因為第一個專家意見在每天的訂購量都是0，遭受的損失即是離線收益。重要的是，從表1和2中可以看出決策方法waa和ewaa的累積收益損失與最優專家意見的累積收益損失總是相差很小。對于算例中給出的N=25, 50, 100, 200，決策方法waa的累積收益損失與其對應最優專家意見的累積收益損失差值最大為4；決策方法ewaa的累積收益損失與其對應最優專家意見的累積收益損失差值都是-0.5。說明了在未來信息一無所知且不對報紙需求量做任何統計假設下，決策方法waa或ewaa的累積收益損失近似于最優專家意見的累積收益損失。同時也說明了考慮回收價值的ewaa決策方法的累積收益損失小于最優專家意見的累積收益損失，具有更好的競爭性能。這是因為有回收價值時，訂購過多的報紙具有價值，從而能獲得更多的收益。另外，表1中waa的累積收益損失與ex1的累積收益損失比值總是大于50%，而表2中ewaa的累積收益損失與eex1的累積收益損失比值總是小于50%，這說明了回收價值的引入能夠使得累積收益損失大大減少，具有重要的意義。比較表1和2還可看出最優專家意見的不同。在表1中，當N=25和N=50時，最優專家意見是ex3；當N=100和N=200時，最優專家意見是ex2。在表2中，最優專家意見都是eex3，說明了引入回收價值后的最優專家意見是穩定的，進一步說明了回收價值在應用WAA進行報童決策中具有重要的作用。

為了更為直觀的說明在多階段報童決策中，無統計信息假設的決策方法waa和ewaa能夠追蹤最優專家意見。圖3給出了waa和4個專家意見在200天內的日累積收益損失和累積收益比較，圖4給出了ewaa和4個專家意見在200天內的日累積收益損失和累積收益比較。圖3左邊的累積收益損失比較表明了waa對最優專家意見的追蹤：大概在第100天之前，專家意見ex3的累積收益損失最小；在第100天之后，專家意見ex2的累積收益損失最小，可看出表示waa決策方法的累積收益損失的紅色線越來越靠近表示專家意見ex2的累積收益損失的藍綠線，圖3右邊的累積收益比較圖進一步驗證了該結論。圖4中的累積收益損失和累積收益比較圖也說明了決策方法ewaa與最優專家意見的漸進性。比較圖3和4，說明了回收價值的引入使得累積收益損失減少，從而使得累積收益增加。

表1 決策方法waa和4個專家意見的累積收益損失、累積收益和離線收益(p=1.5, c=1.0)

表2 決策方法ewaa和4個專家意見的累積收益損失、累積收益和離線收益(p=1.5,c=1.0,s=0.5)

圖3 決策方法waa和4個專家意見在200天內的日累積收益損失和累積收益比較

表3 決策方法waa、ewaa及對應專家意見在不同參數組合下的累積收益損失比較

pcswaaex1ex2ex3ex4ewaaeex1eex2eex3eex41.51.00.3123178.5119131.5244.5101.2178.5110.9100.9171.31.51.00.5123178.5119131.5244.580178.5105.580.5122.51.50.80.5122.1249.9150.4122.9195.977.4249.990.4101.973.92.01.00.5160357211161245116.5357197.5110123

表3給出了waa、ewaa及對應專家意見在不同參數組合下的累積收益損失比較。表3得到了與直覺相一致的結果：當不考慮回收價值時，p越大或c越小，waa的累積收益損失與最大累積收益損失的比值越小，決策方法waa表現出越好的競爭性能；當考慮回收價值時，s越大或p越大或c越小，ewaa的累積收益損失與最大累積收益損失的比值越小，決策方法ewaa表現出越好的競爭性能。

5 結語

本文將理論計算機學科興起的集成專家意見算法應用到多階段報童及帶有回收價值的決策問題中。在收益損失函數的基礎上，研究了如何用WAA集成固定訂購量專家意見，給出了具體的決策方法；證明了決策方法的累積收益損失漸近于最優專家意見的累積收益損失，并通過具體算例進一步驗證策略的合理性和可行性，說明了回收價值的引入能夠提高決策方法的競爭性能。該文給出的策略簡單可行，對類似庫存決策具有重要意義。在實際的序列決策中，同一個專家可能會在不同的階段給出不同的訂購量，稱之為超級專家意見。因此，在本文基礎上，進一步研究如何用WAA集成超級專家意見更具有重要現實意義。另外，用WAA研究報童問題的眾多擴展問題也是值得思考的一個重要方向。

圖4 決策方法ewaa和4個專家意見在200天內的日累積收益損失和累積收益比較

[1]PetruzziNC,DadaM.Pricingandnewsvendorproblem:Areviewwithextension[J].OperationsResearch, 1999, 47( 2) : 183-149.

[2]SilverEA,PykeDF,PetersonRP.Inventorymanagementandproductionplanningandscheduling[M].NewYork:JohnWiley, 1998.

[3]KhoujaM.Thesingle-period(news-vendor)problem:Literaturereviewandsuggestionsforfutureresearch[J].Omega, 1999, 27(5): 537-553.

[4] 汪小京, 劉志學, 鄭長征. 多類顧客環境下報童模型中庫存分配策略研究[J]. 中國管理科學, 2010, 18(4): 65-72.

[5] 黃松, 楊超, 張曦. 考慮戰略顧客行為帶預算約束的多產品報童問題[J]. 中國管理科學, 2011, 19(3): 70-78.

[6] 許民利, 李展. 基于CVaR準則具有預算約束和損失約束的報童決策[J]. 控制與決策, 2013, 28(11): 1614-1622.

[7] 周艷菊，應仁仁，陳曉紅，等. 基于前景理論的兩產品報童的訂貨模型[J]. 管理科學學報, 2013, 16(11): 17-29.

[8]ScarfH.SomeremarksonBayessolutionstotheinventoryproblem[J].NavalResearchLogisticsQuarterly, 1960, 7(4): 591-596.

[9]ScarfH.Bayessolutiontothestatisticalinventoryproblem[J].AnnalsofMathematicalStatistics, 1959, 30(2): 490-508.

[10]KarlinS.Dynamicinventorypolicywithvaryingstochasticdemands[J].ManagementScience, 1960, 6(3): 231-258.

[11]IglehartDL.Thedynamicinventoryproblemwithunknowndemanddistribution[J].ManagementScience, 1964, 10(3): 429-440.

[12]LiyanageLH,ShanthikumarJG.Apracticalinventorycontrolpolicyusingoperationalstatistics[J].OperationsResearchLetters, 2005, 33(4): 341-348.

[13]O’NeilS,ChaudharyA.Comparingonlinelearningalgorithmstostochasticapproachesforthemulti-periodnewsvendorproblem[C].ProceedingsoftheTenthWorkshoponAlgorithmEngineeringandExperiments,SanFrancisco,California,January19,2008.

[14]HuhWT,JanakiramanG,MuckstadtJA,etal.Anadaptivealgorithmforfindingtheoptimalbase-stockpolicyinlostsalesinventorysystemswithcensoreddemand[J].MathematicsofOperationsResearch, 2009, 34 (2): 397-416.

[15]HuhWT,LeviR,RusmevichientongP,etal.Adaptivedata-driveninventorycontrolpoliciesbasedonKaplan-Meierestimatorforcensoreddemand[J].OperationsResearch, 2011, 59(4): 929-941.

[16]HuhWT,RusmevichientongP.Anon-parametricasymptoticanalysisofinventoryplanningwithcensoreddemand[J].MathematicsofOperationsResearch, 2009, 34 (1): 103-123.

[17]ZhuZhisu,ZhangJiawei,YeYinyu.Newsvendoroptimizationwithlimiteddistributioninformation[J].OptimizationMethodsandSoftware, 2013, 28(3): 640-667.

[18]KwonK,CheongT.Aminimaxdistribution-freeprocedureforanewsvendorproblemwithfreeshipping[J].EuropeanJournalofOperationalResearch, 2014, 232(1): 234-240.

[19]SleatorD,TarjanR.Amortizedefficiencyoflistupdateandpagingrules[J].CommunicationsoftheACM, 1985, 28(2): 202-208.

[20]KarlinAR,ManasseMS,RudolphL,etal.Competitivesnoopycaching[J].Algorithmica, 1988, 3(1): 79-119.

[21]BorodinA,El-YanivR.Onlinecomputationandcompetitiveanalysis[M].Cambridge:CambridgeUniversityPress, 1998.

[22]WagnerMR.Fullydistribution-freeprofitmaximization:theinventorymanagementcase[J].MathematicsofOperationsResearch, 2010, 35 (4): 728-741.

[23]WagnerMR.Onlinelot-sizingproblemswithordering,holdingandshortagecosts[J].OperationsResearchLetters, 2011, 39(2): 144-149.

[24] 張桂清，徐寅峰. 報童問題的最優競爭比策略及其風險補償模型[J]. 管理學報, 2011, 8(1): 97-102.

[25] 張桂清，徐寅峰. 概率預期下在線報童問題的最小風險策略[J]. 中國管理科學, 2010, 18(6): 131-137.

[26]BallM,QueyranneM.Towardrobustrevenuemanagement:Competitiveanalysisofonlinebooking[J].OperationsResearch, 2009, 57 (4): 950-963.

[27]VandenHeuvelW,WagelmansAPM.Worstcaseanalysisforageneralclassofon-linelot-sizingheuristics[J].OperationsResearch, 2010, 58 (1): 59-67.

[28]Cesa-BianchiN,LugosiG.Prediction,learning,andgames[M].Cambridge:CambridgeUniversityPress, 2006.

[29]VovkV.Competitiveon-linestatistics[J].InternationalStatisticalReview, 2001, 69(2): 213-248.

[30]KalnishkanY,VyuginMV.Theweakaggregatingalgorithmandweakmixability[J].TheJournalofComputerandSystemSciences, 2008, 74(8): 1228-1244.

[31]LevinaT,LevinY,McGillJ,etal.Weakaggregatingalgorithmforthedistribution-freeperishableinventoryproblem[J].OperationsResearchLetters, 2010, 38(6): 516-521.

Decision-makingforMulti-periodNewsvendorProblemWithoutStatisticalInformationAssumption

ZHANG Yong1，ZHANG Wei-guo2，XU Wei-jun2

(1. School of Management, Guangdong University of Technology, Guangzhou 510520, China;2.School of Business Administration, South China University of Technology, Guangzhou 510640, China)

The Weak Aggregating Algorithm (WAA) of prediction with expert advices, which advanced in computer science, is applied to study the multi-period newsvendor problem without making statistical assumption. WAA is an exponentially weighted average algorithm that updates the expert advice’s weight according to loss function with initial weights distribution. Based on the return loss function and the expert advice of fixed stock level strategy, the decision-making method is used in this paper, which is in accord with the conclusions obtained using return function; and the case with salvage value is extended. Theoretically, it is proved that the cumulative loss the proposed decision-making method achieved does exceed that of the best expert advice. Numerical examples are presented to further illustrate the feasibility and rationality of the proposed decision-making method and explore the effect of selling and cost price on competitive performance；the results show that the introduction of salvage value greatly improves the competitive performance of the proposed decision-making method and thus presents important practical significance.

multi-period newsvendor problem; salvage value；no statistical assumption; weak aggregating algorithm；return loss function

1003-207(2015)05-0107-09

10.16381/j.cnki.issn1003-207x.2015.05.014

2013-05-01；

2014-02-07

教育部人文社會科學研究項目(13YJC630234, 11YJC630225)；廣東省高等學校優秀青年教師培養計劃(Yq2013062，Yq2013060)；國家自然科學基金資助項目(71471065，71301029)

張永(1981-)，女(漢族)，河南人，廣東工業大學管理學院副教授，研究方向：金融工程與在線金融算法.

F224.10

A