多產品報童問題的直接搜索算法求解

郝 爽 張大力 董 明

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

0 引言

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

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

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

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

1 模型

1.1 具有資源約束的多產品報童問題

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

(1)

產品i的期望收益為:

(2)

具有資源約束的多產品報童問題優化模型為:

(3)

2.2 隨機黑箱多產品報童問題

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

(4)

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

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

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

(5)

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

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

[0] 初始化

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

[1] 基于方向的搜索

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

[2] 判斷終止條件

如果Δk+1<Δtol,停止循環。

[3] 更新樣本

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

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

(6)

3 算例分析

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

(7)

(8)

(9)

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

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

圖1 產品需求分布及無約束最優訂貨量

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

表1 算法1與啟發式算法的對比

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

4 結語

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

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