郝 爽 張大力 董 明

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

0 引言

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

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

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

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

1 模型

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

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

(1)

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

(2)

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

(3)

2.2 隨機(jī)黑箱多產(chǎn)品報童問題

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

(4)

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

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

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

(5)

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

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

[0] 初始化

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

[1] 基于方向的搜索

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

[2] 判斷終止條件

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

[3] 更新樣本

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

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

(6)

3 算例分析

本章通過數(shù)值實(shí)驗(yàn)證明在產(chǎn)品需求分布未知且產(chǎn)品需求量歷史數(shù)據(jù)有限的條件下,算法1可有效求解具有資源約束的多產(chǎ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è)時,H1、H2、H3所得結(jié)果均為近似解,但具有運(yùn)算簡單、無須已知需求分布的優(yōu)點(diǎn)。在實(shí)際運(yùn)用中,需求量的均值、標(biāo)準(zhǔn)差可利用歷史需求進(jìn)行估計(jì),無約束最優(yōu)訂貨量可通過歷史需求的經(jīng)驗(yàn)分布確定。

本文的測試問題取自文獻(xiàn)[7],并考慮了更加豐富的需求分布組合。假設(shè)零售商銷售2種產(chǎn)品,產(chǎn)品的成本結(jié)構(gòu)為:售價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組測試問題,各問題中的產(chǎn)品需求分布及無約束最優(yōu)訂貨量如圖1所示。

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

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

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

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

4 結(jié)語

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

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