郝 爽 張大力 董 明

(上海交通大學(xué) 安泰經(jīng)濟(jì)與管理學(xué)院,上海 200030)

0 引言

報(bào)童問(wèn)題是經(jīng)典的隨機(jī)庫(kù)存管理模型,其基本假設(shè)為產(chǎn)品需求為分布已知的隨機(jī)變量,當(dāng)訂貨量過(guò)剩時(shí),未售出的商品具有一定的殘值,當(dāng)訂貨量不足時(shí),未滿足的需求將產(chǎn)生懲罰成本,零售商需事先決定產(chǎn)品的訂貨量以最大化期望收益。

報(bào)童問(wèn)題假設(shè)產(chǎn)品需求為分布已知的隨機(jī)變量,在實(shí)踐中難以直接運(yùn)用,解決方法主要有三類(lèi):一是利用歷史數(shù)據(jù)對(duì)需求的分布類(lèi)型、未知參數(shù)進(jìn)行估計(jì),或以經(jīng)驗(yàn)分布對(duì)需求的累積分布進(jìn)行近似,此類(lèi)方法的求解效果依賴(lài)于估計(jì)量的質(zhì)量,在小樣本情況下求解質(zhì)量較差;二是各類(lèi)數(shù)據(jù)驅(qū)動(dòng)方法的應(yīng)用,即利用機(jī)器學(xué)習(xí)或人工智能算法對(duì)需求進(jìn)行預(yù)測(cè),或?qū)︻A(yù)測(cè)模型及庫(kù)存決策進(jìn)行聯(lián)合優(yōu)化,由于訓(xùn)練預(yù)測(cè)模型需要使用大量歷史數(shù)據(jù),以及與需求相關(guān)的其他類(lèi)型數(shù)據(jù),所以此類(lèi)方法對(duì)于數(shù)據(jù)的質(zhì)量及規(guī)模具有更高的要求,實(shí)際應(yīng)用的難度更大;三是魯棒優(yōu)化方法,即利用歷史數(shù)據(jù)的統(tǒng)計(jì)特征構(gòu)建滿足條件的分布集合,并最大化最差情況的期望收益,但所得的解往往過(guò)于保守,實(shí)際應(yīng)用價(jià)值不高。

實(shí)踐中零售商通常同時(shí)銷(xiāo)售多種產(chǎn)品且面臨某種資源約束,例如采購(gòu)成本不能超過(guò)預(yù)算或庫(kù)存容量不能超過(guò)最大庫(kù)容,因此多產(chǎn)品報(bào)童問(wèn)題的應(yīng)用更為廣泛。多產(chǎn)品報(bào)童問(wèn)題可分解為報(bào)童問(wèn)題,并分別計(jì)算各產(chǎn)品的最優(yōu)訂貨量,若能夠滿足資源約束則求得最優(yōu),否則可通過(guò)拉格朗日乘子法求解,但高效準(zhǔn)確求解拉格朗日乘子較為困難。文獻(xiàn)[5]、[6]分別求解了產(chǎn)品需求服從特定類(lèi)型分布且參數(shù)已知時(shí)的多產(chǎn)品報(bào)童問(wèn)題,文獻(xiàn)[7]設(shè)計(jì)了多種啟發(fā)式方法求解多產(chǎn)品報(bào)童問(wèn)題,其中部分方法僅使用需求量的均值和方差,因而簡(jiǎn)單易用,數(shù)值實(shí)驗(yàn)表明在不假設(shè)需求量分布已知的前提下,文獻(xiàn)[7]的啟發(fā)式算法可求得較好的近似解。

有別于上述研究,本文假設(shè)零售商僅有各商品需求量的少量歷史數(shù)據(jù)且商品需求量的分布未知,將零售商的收益視作隨機(jī)黑箱函數(shù),利用直接搜索算法進(jìn)行求解。在直接搜索算法的每輪迭代中,通過(guò)控制樣本的數(shù)量,利用有限的歷史數(shù)據(jù)構(gòu)造期望收益的樣本均值近似。本文提出的方法無(wú)須假設(shè)商品需求分布已知,數(shù)值實(shí)驗(yàn)表明在歷史數(shù)據(jù)有限的情況下本方法仍然可以求得高質(zhì)量的近似解。

1 模型

1.1 具有資源約束的多產(chǎn)品報(bào)童問(wèn)題

具有資源約束的多產(chǎn)品報(bào)童問(wèn)題描述如下:零售商同時(shí)銷(xiāo)售n種產(chǎn)品,產(chǎn)品間不存在需求的替代及互補(bǔ)效應(yīng);零售商在銷(xiāo)售期前決定各種產(chǎn)品的訂貨量Qi,i=1,…,n;對(duì)于產(chǎn)品i,其需求量xi為隨機(jī)變量,具有概率密度函數(shù)fi(·);產(chǎn)品i的采購(gòu)成本、銷(xiāo)售價(jià)格、未售出殘值及缺貨懲罰分別為vi、pi、gi、Bi;零售商具有某種資源約束,其資源總量為S,單位產(chǎn)品i的資源消耗量為si。產(chǎn)品i的收益函數(shù)為:

(1)

產(chǎn)品i的期望收益為:

(2)

具有資源約束的多產(chǎn)品報(bào)童問(wèn)題優(yōu)化模型為:

(3)

2.2 隨機(jī)黑箱多產(chǎn)品報(bào)童問(wèn)題

minG(Q1,…,Qn)=E[g(Q1,…,Qn,x1,…,xn)]

(4)

將多產(chǎn)品報(bào)童問(wèn)題視作隨機(jī)黑箱問(wèn)題為建模及實(shí)際應(yīng)用提供了諸多便利。首先,隨機(jī)黑箱問(wèn)題假設(shè)隨機(jī)參數(shù)的分布未知,避免了由參數(shù)估計(jì)造成的解的質(zhì)量下降;其次隨機(jī)黑箱問(wèn)題不要求目標(biāo)函數(shù)具有明確的表達(dá)式,對(duì)于替代性需求、需求依賴(lài)價(jià)格、存在其他隨機(jī)參數(shù)等不同類(lèi)型的報(bào)童問(wèn)題同樣適用,擴(kuò)展了模型的應(yīng)用范圍。

2 具有可變樣本量的直接搜索算法

由于黑箱函數(shù)的表達(dá)式未知,無(wú)法利用各類(lèi)基于梯度的優(yōu)化方法求解,所以其求解主要通過(guò)各類(lèi)無(wú)梯度優(yōu)化方法,包括隨機(jī)近似、響應(yīng)面法、信賴(lài)域法及各類(lèi)直接搜索算法,例如單純形搜索、廣義模式搜索、網(wǎng)格自適應(yīng)搜索,其中直接搜索算法由于易于實(shí)現(xiàn)、魯棒性強(qiáng),得到了廣泛應(yīng)用。

(5)

其中,Q={Q1,…,Qn}。Levi等研究得出了達(dá)到給定近似精度所需的樣本數(shù)量,但實(shí)際問(wèn)題中的樣本數(shù)量往往較少,難以滿足精度要求。本文依據(jù)Hao等提出的直接搜索算法框架,針對(duì)問(wèn)題(4)設(shè)計(jì)了具有可變樣本數(shù)量的直接搜索算法,步驟如下:

算法1 具有可變樣本數(shù)量的直接搜索算法

[0] 初始化

循環(huán):在第k(k=0,1,…)次迭代中,執(zhí)行以下步驟:

[1] 基于方向的搜索

3.否則記k輪迭代搜索失敗,保持當(dāng)前解不變,縮小搜索步長(zhǎng)Δk+1=θΔk,θ<1。

[2] 判斷終止條件

如果Δk+1<Δtol,停止循環(huán)。

[3] 更新樣本

1.如果搜索成功,保持樣本不變,返回步驟[1]。

2.否則,令k+1輪的樣本數(shù)量為

(6)

3 算例分析

本章通過(guò)數(shù)值實(shí)驗(yàn)證明在產(chǎn)品需求分布未知且產(chǎn)品需求量歷史數(shù)據(jù)有限的條件下,算法1可有效求解具有資源約束的多產(chǎn)品報(bào)童問(wèn)題,且結(jié)果優(yōu)于文獻(xiàn)[7]提出的啟發(fā)式算法。

(7)

(8)

(9)

其中:H1基于產(chǎn)品成本結(jié)構(gòu)、需求分布均相同的假設(shè);H2基于產(chǎn)品需求均服從均勻分布的假設(shè),產(chǎn)品的成本結(jié)構(gòu)可以不同;H3在H1的基礎(chǔ)上進(jìn)一步考慮了產(chǎn)品成本結(jié)構(gòu)的差異;不滿足其假設(shè)時(shí),H1、H2、H3所得結(jié)果均為近似解,但具有運(yùn)算簡(jiǎn)單、無(wú)須已知需求分布的優(yōu)點(diǎn)。在實(shí)際運(yùn)用中,需求量的均值、標(biāo)準(zhǔn)差可利用歷史需求進(jìn)行估計(jì),無(wú)約束最優(yōu)訂貨量可通過(guò)歷史需求的經(jīng)驗(yàn)分布確定。

本文的測(cè)試問(wèn)題取自文獻(xiàn)[7],并考慮了更加豐富的需求分布組合。假設(shè)零售商銷(xiāo)售2種產(chǎn)品,產(chǎn)品的成本結(jié)構(gòu)為:售價(jià)p1=4,p2=3,成本v1=v2=2,殘值g1=1,g2=0,缺貨懲罰B1=B2=0,零售商的資源總量S=80,產(chǎn)品的資源需求為s1=1,s2=2。產(chǎn)品的需求分布分別考慮4種可能,均勻分布U(20,80)、正態(tài)分布N(50,100)、三角分布(左偏)Tri(20,35,80)、三角分布(右偏)Tri(20,65,80),共形成16組測(cè)試問(wèn)題,各問(wèn)題中的產(chǎn)品需求分布及無(wú)約束最優(yōu)訂貨量如圖1所示。

圖1 產(chǎn)品需求分布及無(wú)約束最優(yōu)訂貨量

試驗(yàn)中首先為產(chǎn)品i=1,2分別生成服從4種分布的1000條需求作為共同的歷史需求及測(cè)試數(shù)據(jù),針對(duì)每個(gè)問(wèn)題分別考慮歷史需求的數(shù)量Nhist=10,30,50,為產(chǎn)品i=1,2分別生成30組對(duì)應(yīng)數(shù)量的歷史數(shù)據(jù),利用啟發(fā)式算法H1、H2、H3及算法1分別求解。

表1 算法1與啟發(fā)式算法的對(duì)比

實(shí)驗(yàn)結(jié)果表明:(1)產(chǎn)品的成本結(jié)構(gòu)對(duì)算法 1 的影響較小,對(duì)于啟發(fā)式算法H1、H3的影響較大,本例中產(chǎn)品的成本結(jié)構(gòu)具有較大差異,因此在所有測(cè)試問(wèn)題中,算法1均優(yōu)于啟發(fā)式算法H3及啟發(fā)式算法H1;(2)歷史數(shù)據(jù)量Nhist=10時(shí),H2在 12個(gè)問(wèn)題中優(yōu)于算法1,隨著歷史數(shù)據(jù)量的增加,算法1逐漸優(yōu)于H2,當(dāng)歷史數(shù)據(jù)量Nhist=30時(shí),H2在5個(gè)問(wèn)題中優(yōu)于算法1,當(dāng)歷史數(shù)據(jù)量Nhist=50時(shí),H2僅在2 個(gè)真實(shí)分布包含均勻分布的問(wèn)題中優(yōu)于算法1,表明算法1受產(chǎn)品需求分布的影響較小。

4 結(jié)語(yǔ)

產(chǎn)品需求分布已知的假設(shè)影響了報(bào)童模型在實(shí)際中的應(yīng)用效果。當(dāng)歷史數(shù)據(jù)充足時(shí),可利用機(jī)器學(xué)習(xí)、人工智能算法估計(jì)需求分布或預(yù)測(cè)未來(lái)需求;

當(dāng)歷史數(shù)據(jù)有限時(shí),除少數(shù)啟發(fā)式算法外尚無(wú)有效的解決方法。本文在商品需求分布未知的前提下,將具有資源約束的多產(chǎn)品報(bào)童問(wèn)題視作隨機(jī)黑箱優(yōu)化問(wèn)題,在基于方向的直接搜索算法框架下設(shè)計(jì)了具有可變樣本量的直接搜索算法,依據(jù)算法的迭代結(jié)果確定下一輪迭代所需的樣本數(shù)量,通過(guò)重抽樣方法從有限的歷史數(shù)據(jù)中產(chǎn)生樣本。本文提出的方法,不依賴(lài)于產(chǎn)品分布及產(chǎn)品成本結(jié)構(gòu)等假設(shè),數(shù)值實(shí)驗(yàn)結(jié)果表明,本文提出的算法可利用有限的歷史數(shù)據(jù)求解具有資源約束的多產(chǎn)品報(bào)童問(wèn)題,且求解效果整體上優(yōu)于已有的方法。