考慮出庫不確定性的船舶舾裝件立庫入庫優化

趙天毅, 李娜, 李明昊, 蔣祖華

(1.上海交通大學 機械與動力工程學院, 上海 200240; 2.招商局重工(江蘇)有限公司, 江蘇 南通 226113)

隨著信息科技的迅猛發展和管理系統的高度信息化,自動化立體倉庫逐漸成為制造型企業進行倉儲管理的重要設施,其高度自動化的管理方式與管理能力影響著企業倉儲管理系統的整體效率[1]。船舶行業近年來也逐步引入了自動化立體倉庫,用于儲存例如UPS和分電箱等部分尺寸合適的舾裝件。

對舾裝件立體倉庫貨位的貨位分配進行優化可以提高倉庫出入庫與管理效率,實現對生產需求的快速響應,具有重要的現實意義。然而,由于船舶行業按訂單生產,訂單船型及數量隨市場需求的波動而頻繁變化,且船舶的生產周期較長[2],因此生產過程具有較高程度的不確定性,導致其舾裝件出庫計劃往往有較多的不確定性。同時,生產所需的舾裝件具有品種多,標準化程度低的特點,因此雖然出庫總量大,但是單個種類的舾裝件使用頻率不高,其出庫計劃數據也相對較少,這種情況下,需求不僅不確定,而且難以通過歷史數據進行準確預測。此外,舾裝件出庫的效率評估也與一般的庫存問題不同,由于多種舾裝件需要在同一時間點用托盤配齊,進而服務后續生產過程,齊配效率的考慮與提高成為了舾裝件入庫優化的獨特特點。因此,本文希望構建模型和算法對舾裝件立體倉庫獨特的入庫貨位分配優化問題進行深入的研究。

近年,針對立體倉庫倉儲貨位分配策略優化問題的研究大部分假設立庫出庫計劃需求為確定性計劃,構建確定性優化模型,并根據問題的實際屬性設計目標,探索相應的算法進行優化求解。楊瑋等[3]以指令分組、貨位分配及子行程作業模式與順序3個角度進行優化,將優化方法與堆垛機運作規律相結合,構建了以提高多載具進出庫作業效率為優化目標的集成優化模型。高楠等[4]考慮了存儲安全性、存儲效率以及倉庫工人的有效工作時間,針對揀選型自動化立體倉庫貨位分配問題,設計了遺傳算法進行優化。吳炳等[5]針對存儲特殊材料(鋁型材)的自動化立體倉庫進行研究,結合鋁型材尺寸與重量的特點,以貨架穩定性、貨架平衡性以及出入庫效率為主要目標,通過模擬退火算法與遺傳算法結合的方法對立體倉庫進行貨位優化。黃鵬等[6]建立了以出入庫效率、貨架穩定性和堆垛機負載均衡為優化目標的貨位分配優化模型,并將遺傳算法和延遲接受爬山算法相結合,提出了求解模型的兩階段混合算法。Yang等[7]根據倉儲空間分配原則,以貨架穩定性和存取效率為優化目標,設計了倉儲位置分配優化函數,通過分析出庫作業策略,建立了數學模型對貨位分配進行優化。Yan等[8]運用動態的貨位分配策略,構建了立體倉庫多目標貨位分配模型,對電子產品在立體倉庫中的倉儲優化和貨位分配問題進行研究。Quintanilla等[9]以最大化倉庫貨位空間利用率為目標,通過基于鄰域搜索的元啟發式算法對貨位分配問題進行優化。Li等[10]基于ABC分類法以及貨物間的相關關系,針對動態貨位分配問題,設計了基于數據挖掘的啟發式算法(PABH)對問題進行求解。Zhang等[11]考慮了不同貨物需求之間的相關性,以最小化堆垛機行駛距離為目標,設計了啟發式算法和仿真優化的方法對立體倉庫貨位進行分配。

綜上所述,本文不同于現有文獻中對需求的確定性假設,而是假設各類舾裝件出庫頻次的需求未知,僅可獲得其均值和方差的模糊估計,在這個基礎上,根據舾裝件立庫存儲需求的獨特性,提出以立體倉庫貨架安全性、舾裝件齊配就近性以及舾裝件出庫高效性為優化目標的多目標立體倉庫貨位分配優化模型。本文首先將建立各個優化目標的確定性模型,然后結合出庫計劃的不確定性,構造了出庫頻率分布的模糊集,將出庫高效性目標的模型轉化為分布式魯棒優化模型,進一步根據模型數學結構的特點,設計了利用遺傳算法熱啟動的分支定價算法,該算法一方面克服了啟發式算法無法獲得精確解的缺點,另一方面克服了傳統優化算法求解時間過長的問題,可以在有效的時間內求得模型的精確解。最后,通過數值算例證明了該算法對求解實際問題的有效性和高效性。

1 舾裝件立體倉庫入庫規劃模型

1.1 模型假設

假設舾裝件立體倉庫的貨架共有a排,每排貨架有b列c層,每次入庫舾裝件共有d種;每個貨位坐標設為(l,m,n),其中l=1,2,…,a,m=1,2,…,b,n=1,2,…,c。假設每排貨架分配專屬堆垛機進行出入庫操作,即在執行出入庫操作時,各貨架對應的堆垛機可同時進行動作,但對于同一排貨架,堆垛機每次僅能進行一種動作(取或存一個貨位存儲的舾裝件)。

假設每個貨位高度為L0,長度為L1,寬度為L2,貨位(l,m,n)對應的質量承載上限為Qlmn,該貨位的可使用狀態為Nlmn,若該貨位可用,則Nlmn=1,若該貨位不可用,則Nlmn=0。

1.2 貨位分配規則建模

通過對舾裝件立體倉庫存儲的實際場景進行研究和分析,發現船舶舾裝件倉庫貨位分配主要需要考慮3個因素。首先需要保證倉庫貨架中貨位的穩定性,若貨架不穩定,在自動化管理的過程中極有可能會出現安全問題。其次,由于出庫齊配率是舾裝件庫存評價的重要指標,該指標對于后續項目的繼續進行有著重要影響,因此提高舾裝件齊配率,對于存儲舾裝件的立體倉庫貨位規劃具有十分重要的意義。此外,舾裝件出庫速度也是評價倉庫貨位規劃效果的一個直接且重要的指標,舾裝件的出庫速度是影響船舶生產過程的關鍵因素之一。因此,本研究采用了貨位穩定性原則、舾裝件齊配就近原則和舾裝件出庫速度最快原則作為貨位分配的優化目標。

1.2.1 貨位穩定性原則

為了保證貨架在倉儲管理過程中的穩定性,貨位分配應按照“質量較大的物品分配較低層的貨位,質量較輕的物品分配較高層的貨位”的規則,從而使貨架整體更加穩定。尤其是舾裝件類型較多,不同類型舾裝件的質量差別較大。例如,分電箱的整托存儲質量為100 kg,而UPS的整托存儲質量為1 000 kg,因此為保證整個貨架的穩定性,應按照“貨架重心越低則貨位越穩定”的原則,將UPS存儲在低層貨位,將分電箱存儲在相對較高層的貨位。立體倉庫整體貨架重心可以通過托盤上舾裝件質量與所對應的貨位層數的乘積來表示,該乘積的值越小則代表舾裝件立體倉庫中該貨架的整體重心越低,該立體倉庫貨位更穩定。根據此規則,將貨位穩定性原則建立數學模型為:

1.2.2 齊配就近性原則

船舶生產過程中,當且僅當同一托盤的舾裝件配齊時,該托盤的舾裝件才會出庫。因此對于出庫時常放于同一托盤的舾裝件,要盡可能靠近存放,以便于進行同時的存取操作,進而提高出庫時舾裝件的齊配率。舾裝件齊配就近性可以通過計算舾裝件存儲貨位和與其常放于即同一托盤(即同托)的舾裝件的距離進行衡量。本文結合船廠實際情況,最終通過計算舾裝件距離該類同托舾裝件中心貨位坐標的距離對齊配就近性進行評估。根據此規則,將齊配就近性原則建立數學模型為:

(m-mk)(n-nk)

1.2.3 出庫速度最快原則

出庫速度是衡量貨位分配的重要指標之一,立體倉庫管理中,出庫速度取決于堆垛機搬運過程的速度,而堆垛機搬運舾裝件的速度與堆垛機移動距離以及貨叉的操作距離有關,因此物品存放位置會直接影響堆垛機運行速度和效率。為了提高舾裝件出庫速度,應該將出庫頻率高的舾裝件分配靠近巷道出入口的貨位。根據此規則,將出庫速度最快原則建立數學模型,其中出庫頻率為不確定參數:

由于在入庫操作時往往無法獲得未來出庫計劃的準確信息,僅能通過歷史數據對未來出庫計劃進行估計,因此要使模型在實際應用中具有較好的效果,需要大量的舾裝件歷史出庫計劃數據對出庫頻率概率分布進行描述。然而在實際情況中,因為舾裝件種類多且標準化程度不高,所以部分舾裝件的使用頻率不高,導致該類舾裝件歷史出庫計劃數據較少,難以通過歷史數據對該類舾裝件的出庫頻率進行準確預測,也無法通過歷史數據對出庫頻率的概率分布進行較為準確的描述,所以如果直接使用歷史數據的期望值作為出庫頻率進行貨位分配有可能會使決策的實際效果較差。為了解決這一問題,本文利用分布式魯棒優化的方法對該目標函數進行轉換。分布式魯棒優化首先基于可以觀察到的數據建立不確定參數的模糊集,該模糊集包含了真實的不確定參數分布,然后通過考慮該模糊集中的最差情況得到穩健性較強且可靠性較高的決策,因此該方法可以通過有限的不確定參數概率分布信息實現統計與優化之間的平衡[12],可以應用于歷史數據不足以刻畫全部分布信息的情況。轉換后的模型可以在計算中減少歷史數據數量的影響,并在沒有具體概率分布假設的情況下對決策進行優化。

在本文所考慮的問題中,由于單個種類的舾裝件出庫數據有限,很難進行分布的擬合;而矩信息則可以由數據中直接進行無偏估計,故考慮基于矩信息的模糊集構建方法。

該模糊集包含了期望和方差符合歷史數據情況的所有分布函數,因此也包含了出庫頻率的真實分布。通過分布式魯棒優化,目標函數f3可以轉化為:

命題1f3可以轉化為a個獨立的目標函數之和,即:

證明：設l為被分配到貨架l上的所有舾裝件的出庫頻率的聯合分布,集合Kl為該貨架上的舾裝件因此模糊集Zl為模糊集Z在l上的投影:

證畢。

根據文獻[13]中的引理1,可以得到命題2。

1.3 多目標舾裝件立體倉庫貨位分配模型

在對舾裝件立體倉庫貨位分配進行優化時,需要同時考慮貨位穩定性原則、舾裝件齊配就近原則和舾裝件出庫速度最快原則,因此貨位分配模型中需要同時優化f1、f2、f33個目標函數,即:

約束條件為:

(1)

(2)

(3)

(4)

(5)

式中:約束(2)要求每個貨位僅能存儲一類舾裝件,約束(3)要求每個舾裝件只能分配到一個貨位,約束(4)要求舾裝件不能分配到無法放置貨物的貨位且存儲的總質量不能超過所分配的貨位的質量上限,約束(5)定義了決策變量的定義域。

為3個目標函數分配3個不同的權重系數ω1、ω2、ω3作為影響因子,采用權值分配的方法將多目標優化問題轉換成單目標函數求極值的問題。由于3個目標函數的量綱不同,為了使目標函數值具有可比性和物理意義,對f1、f2、f3進行歸一化處理,消除量綱的影響,轉化為:

最終,多目標優化模型形式為:

2 基于遺傳算法熱啟動的分支定價算法

舾裝件立體倉庫入庫規劃模型可以通過商業求解器直接進行求解,但若貨架數量過多,模型的求解難度會大大增加。而本文模型的數學結構具有可分解性,因此可將問題基于不同貨架分解為相互關聯的單貨架入庫貨位分配優化問題?；谶@一特點,設計了分支定價算法對問題進行求解,以加快模型的求解速度。而分支定價算法的收斂速度與初始解的質量有關,因此本文設計了遺傳算法對分支定價算法進行熱啟動,即通過遺傳算法得到一個次優解并將這個解作為分支定價算法的初始解,以實現在實際應用中大規模問題的實時優化。

2.1 Set Partitioning主問題模型

設所有滿足貨位分配模型約束條件的可行貨位分配方案集合為Ψ,其中φ∈Ψ表示可行的單貨架貨位分配方案。本文所求解的問題可以轉化為從可行貨位分配方案集合Ψ中選擇若干個單貨架貨位分配方案φ組合組成一個可行解并且使得貨位分配模型中的目標函數值最小。

為了便于描述Set Partitioning主問題的形式,定義當第k類舾裝件被分配到貨架時δkl=1,否則δkl=0,cl為可行貨架貨位分配方案φl對應的目標函數值。通過上述定義,可以將舾裝件立體倉庫入庫規劃模型轉化為下面的Set Partitioning模型,并將其定義為分支定價算法的主問題 (master problem,MP):

(6)

(7)

(8)

φl={0,1},?l∈{1,2,…,a}

(9)

約束(7)表示每類待入庫舾裝件只能分配到一個貨架,約束(8)規定了立體倉庫中年貨架總數量的上限,約束(9)定義了決策變量的定義域。

2.2 子問題模型

令ε0、εk分別是約束(7)和約束(8)對應的對偶變量,那么主問題MP的檢驗數(reduced cost)為:

(10)

(11)

(12)

(13)

(14)

(15)

式(10)表示在可行貨架貨位分配集合Ψ中找到使得檢驗數最小的可行單貨架貨位分配方案。在求解子問題時,若目標函數值小于零,則將對應的最優解作為新的列加入到主問題中進行迭代求解,以使LMP 問題的目標函數值達到更優。若在求解子問題時不能找到使得目標函數值小于零的解,說明當前的結果已是LMP 問題的最優解。

2.3 分支策略

為了快速得到混合整數規劃問題的整數解,本文在分支定界算法框架中使用了局部深度優先搜索策略[14]。該策略使用最佳優先準則選擇分支定界樹中的一個子節點,并使用深度優先策略探索該節點上的子樹。如果其父節點的下界和未探測節點的最佳下界在給定的容差范圍內,則對該節點所對應的子樹進行搜索。當子樹的局部搜索完成后,使用最佳優先準則選擇下一個節點進行搜索。重復此過程,直到完成搜索。這種混合搜索策略可以通過使用最佳優先準則控制搜索節點的總數量,從而加快算法的收斂速度。

2.4 熱啟動遺傳算法設計

本文設計了遺傳算法對貨位分配模型進行求解,以獲得較優的貨位分配方案作為分支定價算法的初始解,對分支定價算法進行熱啟動,從而進一步加快分支定價算法的求解速度。遺傳算法的設計如下。

編碼方案:采用整數編碼的方式,每一條染色體都代表立體倉庫中舾裝件的貨位分配方案?；蛑禐榘艛?、列數、層數等信息的貨位存儲坐標。例如,1號基因值為(1,1,1)表示1號舾裝件的分配貨位為1排1列1層。

選擇操作:采用輪盤選擇法對染色體進行選擇,選擇適應度函數較大的一組(2個)個體,分別作為父染色體和母染色體。

交叉操作:根據交叉概率(本文設置交叉概率為0.5)將選擇操作得到的2個染色體的某一基因進行互換,從而產生2個新的舾裝件分配方案。例如,將父染色體的3號基因值與母染色體的4號基因值進行互換。

變異操作:根據變異概率(本文設置變異概率為0.3)選擇染色體上2個不同位置的基因進行互換,即相當于互換一個舾裝件分配方案中的2個舾裝件對應的貨位。例如,將染色體的1號基因值與4號基因值進行互換。

終止條件:迭代總數達到300,或者在5次迭代中最優適應度函數值沒有得到提升。

3 數值實驗

3.1 算法能力分析

本文使用Python語言對基于遺傳算法熱啟動的分支定價算法進行編寫。運行環境采用i7-8750 @2.20 GHz的CPU 8.00 GB 內存。本文分別使用基于隨機初始解的分支定價算法(B&P)、基于遺傳算法熱啟動的分支定價算法(B&PGA)和Gurobi對貨架數量不同的隨機算例進行求解。其中,每種貨架數量進行3次不同隨機算例的運算,并取3次求解時間的平均值作為最終的求解時間,比較3種方法的求解時間,對算法能力進行分析。實驗結果如表1所示,實驗中的求解時間以秒為單位進行統計,設置求解時間上限為2 000 s,即超過2 000 s則算法停止運行,并將結果計為>2 000。

表1 不同貨架數量下算法求解時間比較Table 1 Comparison of algorithm solution time under different shelf numbers

結果表明,當貨架數量較小時,Gurobi算法的平均求解時間略短于2種分支定價算法的平均求解時間。然而,當貨架數量大于6時(符合船廠倉庫一般規模),2種分支定價算法求解速度更快,且求解時間隨貨架數量增加的增長率低于Gurobi算法。同時,表中數據表明B&PGA算法的求解速度總是比B&P算法的速度快,在實驗中有17%～50%的速度提升,效率提升效果明顯。因此,可以得出結論通過遺傳算法對分支定價算法進行熱啟動可以進一步加快算法的求解速度。綜上所述,本文設計的基于遺傳算法熱啟動的分支定價算法能夠有效解決船廠的實際問題。

3.2 貨位優化效果分析

本節基于某船廠真實數據對模型和算法的有效性進行驗證,根據船廠專家的建議,選擇VDR系統、氣象傳真系統、MCT以及雷達系統等舾裝件作為研究對象。通過其立體倉庫設計規劃獲得包括立體倉庫貨位數量以及尺寸等貨位信息,通過計劃存入立體倉庫的舾裝件規劃獲得舾裝件尺寸和質量等數據,通過相關舾裝件的歷史出入庫信息獲得不同舾裝件出庫頻率的期望和方差等分布信息的估計值。部分舾裝件優化前的貨位信息如表2所示。

表2 優化前部分舾裝件貨位信息Table 2 Outfitting information examples before optimization

通過調整不同貨位分配原則在目標函數中的影響因子大小,分別對貨位分配進行優化,并對優化結果進行分析。本文共考慮了3種不同的權重分配情景,其中,情景Ⅰ(以貨位穩定性原則為主)中的ω1、ω2和ω3分別為0.8、0.1和0.1,情景Ⅱ(以齊配就近性原則為主)中的ω1、ω2和ω3別為0.1、0.8和0.1,情景Ⅲ(以出庫速度最快原則為主)中的ω1、ω2和ω3別為0.1、0.1和0.8。算例的優化結果如表3、4所示。從表中可以看出,優化后的目標函數值與優化前相比,都得到了明顯的提升,表明貨位分配結果在優化后得到了明顯的改進。其中,在不同的權重分配下,貨位穩定性原則的優化效果最好,即倉儲安全性的提升效果最明顯。

表3 優化前后貨位分配總評價指標比較Table 3 Comparison of total evaluation indexes of cargo space allocation

表4 優化前后子目標函數差值Table 4 Differences of sub-objective functions before and after optimization

3.3 出庫不確定性影響分析

本文考慮到出庫頻率分布信息難以通過歷史數據進行準確刻畫的情況,構造了出庫頻率分布的均值-方差模糊集,并通過分布式魯棒優化的方法對模型進行了轉化,以使貨位分配決策表現更好。為了驗證該方法的有效性,對使用分布式魯棒優化方法的模型(distributionally robust model, DRM)以及使用歷史數據期望進行決策的模型(expectation model, EM)的解進行了比較和分析。本實驗首先使用DRM和EM 2種模型對現有貨位進行了優化,其3個優化原則的權重均設為0.33。然后根據歷史出庫數據的期望值,改變出庫數據的方差,模擬200次出庫操作,基于模擬的出庫數據計算目標函數值的期望,并將其中出庫速度最快原則對應指標作為評價指標,對2種模型進行了比較。本實驗分別比較了出庫數量服從正態分布、指數分布和韋布爾分布3種不同分布的情況下,隨著變異系數(Coefficient of Variation)的增加,DRM與EM 2種模型評價指標的差值,其中,變異系數相當于出庫頻率的不確定性越高。實驗結果如表5～7所示。

表5 出庫數量服從正態分布的評價指標比較Table 5 Comparison of evaluation indicators when outgoing quantity obeying normal distribution

表7 出庫數量服從韋布爾分布的評價指標比較Table 7 Comparison of evaluation indicators when outgoing quantity obeying Weibull distribution

由此可知,出庫數據服從正態分布、指數分布和韋布爾分布時,不同變異系數下DRM的評價指標(出庫速度原則對應的目標函數值)都要低于EM的評價指標,且差值隨著變異系數的增加而增加。因此,本文提出的模型的表現要優于使用期望值進行貨位優化的方法,且出庫數據的離散程度越高,使用分布式魯棒優化的模型優化效果越好。

4 結論

1) 針對船舶舾裝件立體倉庫的入庫貨位分配優化問題,對舾裝件齊配率這一舾裝件倉儲管理的關鍵評價指標進行了優化。

2) 考慮了由于舾裝件種類多、標準化程度低導致的舾裝件出庫頻率的分布信息難以通過歷史出庫計劃數據進行準確預測的問題,根據歷史數據的期望和方差構建了出庫頻率分布的模糊集,并通過分布式魯棒優化的方法對出庫速度評價指標進行了轉化,最終建立了以貨位穩定性原則、舾裝件齊配就近原則和舾裝件出庫速度最快原則為優化目標的多目標優化模型。

3) 設計了通過遺傳算法進行熱啟動的分支定價算法對模型進行求解,實現了對大規模問題的高效求解。

4) 通過數值實驗證明了方法的有效性,該方法對真實案例中的舾裝件立體倉庫貨位分配問題具有明顯的優化效果。