多產(chǎn)品報童問題的直接搜索算法求解

郝 爽 張大力 董 明

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

0 引言

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

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

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

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

1 模型

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

具有資源約束的多產(chǎn)品報童問題描述如下:零售商同時銷售n種產(chǎn)品,產(chǎn)品間不存在需求的替代及互補效應;零售商在銷售期前決定各種產(chǎn)品的訂貨量Qi,i=1,…,n;對于產(chǎn)品i,其需求量xi為隨機變量,具有概率密度函數(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 隨機黑箱多產(chǎn)品報童問題

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

(4)

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

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

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

(5)

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

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

[0] 初始化

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

[1] 基于方向的搜索

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

[2] 判斷終止條件

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

[3] 更新樣本

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

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

(6)

3 算例分析

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

(7)

(8)

(9)

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

本文的測試問題取自文獻[7],并考慮了更加豐富的需求分布組合。假設零售商銷售2種產(chǎn)品,產(chǎn)品的成本結構為:售價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)訂貨量

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

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

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

4 結語

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

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