考慮出庫(kù)不確定性的船舶舾裝件立庫(kù)入庫(kù)優(yōu)化

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

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

隨著信息科技的迅猛發(fā)展和管理系統(tǒng)的高度信息化,自動(dòng)化立體倉(cāng)庫(kù)逐漸成為制造型企業(yè)進(jìn)行倉(cāng)儲(chǔ)管理的重要設(shè)施,其高度自動(dòng)化的管理方式與管理能力影響著企業(yè)倉(cāng)儲(chǔ)管理系統(tǒng)的整體效率[1]。船舶行業(yè)近年來(lái)也逐步引入了自動(dòng)化立體倉(cāng)庫(kù),用于儲(chǔ)存例如UPS和分電箱等部分尺寸合適的舾裝件。

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

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

綜上所述,本文不同于現(xiàn)有文獻(xiàn)中對(duì)需求的確定性假設(shè),而是假設(shè)各類舾裝件出庫(kù)頻次的需求未知,僅可獲得其均值和方差的模糊估計(jì),在這個(gè)基礎(chǔ)上,根據(jù)舾裝件立庫(kù)存儲(chǔ)需求的獨(dú)特性,提出以立體倉(cāng)庫(kù)貨架安全性、舾裝件齊配就近性以及舾裝件出庫(kù)高效性為優(yōu)化目標(biāo)的多目標(biāo)立體倉(cāng)庫(kù)貨位分配優(yōu)化模型。本文首先將建立各個(gè)優(yōu)化目標(biāo)的確定性模型,然后結(jié)合出庫(kù)計(jì)劃的不確定性,構(gòu)造了出庫(kù)頻率分布的模糊集,將出庫(kù)高效性目標(biāo)的模型轉(zhuǎn)化為分布式魯棒優(yōu)化模型,進(jìn)一步根據(jù)模型數(shù)學(xué)結(jié)構(gòu)的特點(diǎn),設(shè)計(jì)了利用遺傳算法熱啟動(dòng)的分支定價(jià)算法,該算法一方面克服了啟發(fā)式算法無(wú)法獲得精確解的缺點(diǎn),另一方面克服了傳統(tǒng)優(yōu)化算法求解時(shí)間過長(zhǎng)的問題,可以在有效的時(shí)間內(nèi)求得模型的精確解。最后,通過數(shù)值算例證明了該算法對(duì)求解實(shí)際問題的有效性和高效性。

1 舾裝件立體倉(cāng)庫(kù)入庫(kù)規(guī)劃模型

1.1 模型假設(shè)

假設(shè)舾裝件立體倉(cāng)庫(kù)的貨架共有a排,每排貨架有b列c層,每次入庫(kù)舾裝件共有d種;每個(gè)貨位坐標(biāo)設(shè)為(l,m,n),其中l(wèi)=1,2,…,a,m=1,2,…,b,n=1,2,…,c。假設(shè)每排貨架分配專屬堆垛機(jī)進(jìn)行出入庫(kù)操作,即在執(zhí)行出入庫(kù)操作時(shí),各貨架對(duì)應(yīng)的堆垛機(jī)可同時(shí)進(jìn)行動(dòng)作,但對(duì)于同一排貨架,堆垛機(jī)每次僅能進(jìn)行一種動(dòng)作(取或存一個(gè)貨位存儲(chǔ)的舾裝件)。

假設(shè)每個(gè)貨位高度為L(zhǎng)0,長(zhǎng)度為L(zhǎng)1,寬度為L(zhǎng)2,貨位(l,m,n)對(duì)應(yīng)的質(zhì)量承載上限為Qlmn,該貨位的可使用狀態(tài)為Nlmn,若該貨位可用,則Nlmn=1,若該貨位不可用,則Nlmn=0。

1.2 貨位分配規(guī)則建模

通過對(duì)舾裝件立體倉(cāng)庫(kù)存儲(chǔ)的實(shí)際場(chǎng)景進(jìn)行研究和分析,發(fā)現(xiàn)船舶舾裝件倉(cāng)庫(kù)貨位分配主要需要考慮3個(gè)因素。首先需要保證倉(cāng)庫(kù)貨架中貨位的穩(wěn)定性,若貨架不穩(wěn)定,在自動(dòng)化管理的過程中極有可能會(huì)出現(xiàn)安全問題。其次,由于出庫(kù)齊配率是舾裝件庫(kù)存評(píng)價(jià)的重要指標(biāo),該指標(biāo)對(duì)于后續(xù)項(xiàng)目的繼續(xù)進(jìn)行有著重要影響,因此提高舾裝件齊配率,對(duì)于存儲(chǔ)舾裝件的立體倉(cāng)庫(kù)貨位規(guī)劃具有十分重要的意義。此外,舾裝件出庫(kù)速度也是評(píng)價(jià)倉(cāng)庫(kù)貨位規(guī)劃效果的一個(gè)直接且重要的指標(biāo),舾裝件的出庫(kù)速度是影響船舶生產(chǎn)過程的關(guān)鍵因素之一。因此,本研究采用了貨位穩(wěn)定性原則、舾裝件齊配就近原則和舾裝件出庫(kù)速度最快原則作為貨位分配的優(yōu)化目標(biāo)。

1.2.1 貨位穩(wěn)定性原則

為了保證貨架在倉(cāng)儲(chǔ)管理過程中的穩(wěn)定性,貨位分配應(yīng)按照“質(zhì)量較大的物品分配較低層的貨位,質(zhì)量較輕的物品分配較高層的貨位”的規(guī)則,從而使貨架整體更加穩(wěn)定。尤其是舾裝件類型較多,不同類型舾裝件的質(zhì)量差別較大。例如,分電箱的整托存儲(chǔ)質(zhì)量為100 kg,而UPS的整托存儲(chǔ)質(zhì)量為1 000 kg,因此為保證整個(gè)貨架的穩(wěn)定性,應(yīng)按照“貨架重心越低則貨位越穩(wěn)定”的原則,將UPS存儲(chǔ)在低層貨位,將分電箱存儲(chǔ)在相對(duì)較高層的貨位。立體倉(cāng)庫(kù)整體貨架重心可以通過托盤上舾裝件質(zhì)量與所對(duì)應(yīng)的貨位層數(shù)的乘積來(lái)表示,該乘積的值越小則代表舾裝件立體倉(cāng)庫(kù)中該貨架的整體重心越低,該立體倉(cāng)庫(kù)貨位更穩(wěn)定。根據(jù)此規(guī)則,將貨位穩(wěn)定性原則建立數(shù)學(xué)模型為:

1.2.2 齊配就近性原則

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

(m-mk)(n-nk)

1.2.3 出庫(kù)速度最快原則

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

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

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

該模糊集包含了期望和方差符合歷史數(shù)據(jù)情況的所有分布函數(shù),因此也包含了出庫(kù)頻率的真實(shí)分布。通過分布式魯棒優(yōu)化,目標(biāo)函數(shù)f3可以轉(zhuǎn)化為:

命題1f3可以轉(zhuǎn)化為a個(gè)獨(dú)立的目標(biāo)函數(shù)之和,即:

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

證畢。

根據(jù)文獻(xiàn)[13]中的引理1,可以得到命題2。

1.3 多目標(biāo)舾裝件立體倉(cāng)庫(kù)貨位分配模型

在對(duì)舾裝件立體倉(cāng)庫(kù)貨位分配進(jìn)行優(yōu)化時(shí),需要同時(shí)考慮貨位穩(wěn)定性原則、舾裝件齊配就近原則和舾裝件出庫(kù)速度最快原則,因此貨位分配模型中需要同時(shí)優(yōu)化f1、f2、f33個(gè)目標(biāo)函數(shù),即:

約束條件為:

(1)

(2)

(3)

(4)

(5)

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

為3個(gè)目標(biāo)函數(shù)分配3個(gè)不同的權(quán)重系數(shù)ω1、ω2、ω3作為影響因子,采用權(quán)值分配的方法將多目標(biāo)優(yōu)化問題轉(zhuǎn)換成單目標(biāo)函數(shù)求極值的問題。由于3個(gè)目標(biāo)函數(shù)的量綱不同,為了使目標(biāo)函數(shù)值具有可比性和物理意義,對(duì)f1、f2、f3進(jìn)行歸一化處理,消除量綱的影響,轉(zhuǎn)化為:

最終,多目標(biāo)優(yōu)化模型形式為:

2 基于遺傳算法熱啟動(dòng)的分支定價(jià)算法

舾裝件立體倉(cāng)庫(kù)入庫(kù)規(guī)劃模型可以通過商業(yè)求解器直接進(jìn)行求解,但若貨架數(shù)量過多,模型的求解難度會(huì)大大增加。而本文模型的數(shù)學(xué)結(jié)構(gòu)具有可分解性,因此可將問題基于不同貨架分解為相互關(guān)聯(lián)的單貨架入庫(kù)貨位分配優(yōu)化問題?；谶@一特點(diǎn),設(shè)計(jì)了分支定價(jià)算法對(duì)問題進(jìn)行求解,以加快模型的求解速度。而分支定價(jià)算法的收斂速度與初始解的質(zhì)量有關(guān),因此本文設(shè)計(jì)了遺傳算法對(duì)分支定價(jià)算法進(jìn)行熱啟動(dòng),即通過遺傳算法得到一個(gè)次優(yōu)解并將這個(gè)解作為分支定價(jià)算法的初始解,以實(shí)現(xiàn)在實(shí)際應(yīng)用中大規(guī)模問題的實(shí)時(shí)優(yōu)化。

2.1 Set Partitioning主問題模型

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

為了便于描述Set Partitioning主問題的形式,定義當(dāng)?shù)趉類舾裝件被分配到貨架時(shí)δkl=1,否則δkl=0,cl為可行貨架貨位分配方案φl(shuí)對(duì)應(yīng)的目標(biāo)函數(shù)值。通過上述定義,可以將舾裝件立體倉(cāng)庫(kù)入庫(kù)規(guī)劃模型轉(zhuǎn)化為下面的Set Partitioning模型,并將其定義為分支定價(jià)算法的主問題 (master problem,MP):

(6)

(7)

(8)

φl(shuí)={0,1},?l∈{1,2,…,a}

(9)

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

2.2 子問題模型

令ε0、εk分別是約束(7)和約束(8)對(duì)應(yīng)的對(duì)偶變量,那么主問題MP的檢驗(yàn)數(shù)(reduced cost)為:

(10)

(11)

(12)

(13)

(14)

(15)

式(10)表示在可行貨架貨位分配集合Ψ中找到使得檢驗(yàn)數(shù)最小的可行單貨架貨位分配方案。在求解子問題時(shí),若目標(biāo)函數(shù)值小于零,則將對(duì)應(yīng)的最優(yōu)解作為新的列加入到主問題中進(jìn)行迭代求解,以使LMP 問題的目標(biāo)函數(shù)值達(dá)到更優(yōu)。若在求解子問題時(shí)不能找到使得目標(biāo)函數(shù)值小于零的解,說明當(dāng)前的結(jié)果已是LMP 問題的最優(yōu)解。

2.3 分支策略

為了快速得到混合整數(shù)規(guī)劃問題的整數(shù)解,本文在分支定界算法框架中使用了局部深度優(yōu)先搜索策略[14]。該策略使用最佳優(yōu)先準(zhǔn)則選擇分支定界樹中的一個(gè)子節(jié)點(diǎn),并使用深度優(yōu)先策略探索該節(jié)點(diǎn)上的子樹。如果其父節(jié)點(diǎn)的下界和未探測(cè)節(jié)點(diǎn)的最佳下界在給定的容差范圍內(nèi),則對(duì)該節(jié)點(diǎn)所對(duì)應(yīng)的子樹進(jìn)行搜索。當(dāng)子樹的局部搜索完成后,使用最佳優(yōu)先準(zhǔn)則選擇下一個(gè)節(jié)點(diǎn)進(jìn)行搜索。重復(fù)此過程,直到完成搜索。這種混合搜索策略可以通過使用最佳優(yōu)先準(zhǔn)則控制搜索節(jié)點(diǎn)的總數(shù)量,從而加快算法的收斂速度。

2.4 熱啟動(dòng)遺傳算法設(shè)計(jì)

本文設(shè)計(jì)了遺傳算法對(duì)貨位分配模型進(jìn)行求解,以獲得較優(yōu)的貨位分配方案作為分支定價(jià)算法的初始解,對(duì)分支定價(jià)算法進(jìn)行熱啟動(dòng),從而進(jìn)一步加快分支定價(jià)算法的求解速度。遺傳算法的設(shè)計(jì)如下。

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

選擇操作:采用輪盤選擇法對(duì)染色體進(jìn)行選擇,選擇適應(yīng)度函數(shù)較大的一組(2個(gè))個(gè)體,分別作為父染色體和母染色體。

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

變異操作:根據(jù)變異概率(本文設(shè)置變異概率為0.3)選擇染色體上2個(gè)不同位置的基因進(jìn)行互換,即相當(dāng)于互換一個(gè)舾裝件分配方案中的2個(gè)舾裝件對(duì)應(yīng)的貨位。例如,將染色體的1號(hào)基因值與4號(hào)基因值進(jìn)行互換。

終止條件:迭代總數(shù)達(dá)到300,或者在5次迭代中最優(yōu)適應(yīng)度函數(shù)值沒有得到提升。

3 數(shù)值實(shí)驗(yàn)

3.1 算法能力分析

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

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

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

3.2 貨位優(yōu)化效果分析

本節(jié)基于某船廠真實(shí)數(shù)據(jù)對(duì)模型和算法的有效性進(jìn)行驗(yàn)證,根據(jù)船廠專家的建議,選擇VDR系統(tǒng)、氣象傳真系統(tǒng)、MCT以及雷達(dá)系統(tǒng)等舾裝件作為研究對(duì)象。通過其立體倉(cāng)庫(kù)設(shè)計(jì)規(guī)劃獲得包括立體倉(cāng)庫(kù)貨位數(shù)量以及尺寸等貨位信息,通過計(jì)劃存入立體倉(cāng)庫(kù)的舾裝件規(guī)劃獲得舾裝件尺寸和質(zhì)量等數(shù)據(jù),通過相關(guān)舾裝件的歷史出入庫(kù)信息獲得不同舾裝件出庫(kù)頻率的期望和方差等分布信息的估計(jì)值。部分舾裝件優(yōu)化前的貨位信息如表2所示。

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

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

表3 優(yōu)化前后貨位分配總評(píng)價(jià)指標(biāo)比較Table 3 Comparison of total evaluation indexes of cargo space allocation

表4 優(yōu)化前后子目標(biāo)函數(shù)差值Table 4 Differences of sub-objective functions before and after optimization

3.3 出庫(kù)不確定性影響分析

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

表5 出庫(kù)數(shù)量服從正態(tài)分布的評(píng)價(jià)指標(biāo)比較Table 5 Comparison of evaluation indicators when outgoing quantity obeying normal distribution

表7 出庫(kù)數(shù)量服從韋布爾分布的評(píng)價(jià)指標(biāo)比較Table 7 Comparison of evaluation indicators when outgoing quantity obeying Weibull distribution

由此可知,出庫(kù)數(shù)據(jù)服從正態(tài)分布、指數(shù)分布和韋布爾分布時(shí),不同變異系數(shù)下DRM的評(píng)價(jià)指標(biāo)(出庫(kù)速度原則對(duì)應(yīng)的目標(biāo)函數(shù)值)都要低于EM的評(píng)價(jià)指標(biāo),且差值隨著變異系數(shù)的增加而增加。因此,本文提出的模型的表現(xiàn)要優(yōu)于使用期望值進(jìn)行貨位優(yōu)化的方法,且出庫(kù)數(shù)據(jù)的離散程度越高,使用分布式魯棒優(yōu)化的模型優(yōu)化效果越好。

4 結(jié)論

1) 針對(duì)船舶舾裝件立體倉(cāng)庫(kù)的入庫(kù)貨位分配優(yōu)化問題,對(duì)舾裝件齊配率這一舾裝件倉(cāng)儲(chǔ)管理的關(guān)鍵評(píng)價(jià)指標(biāo)進(jìn)行了優(yōu)化。

2) 考慮了由于舾裝件種類多、標(biāo)準(zhǔn)化程度低導(dǎo)致的舾裝件出庫(kù)頻率的分布信息難以通過歷史出庫(kù)計(jì)劃數(shù)據(jù)進(jìn)行準(zhǔn)確預(yù)測(cè)的問題,根據(jù)歷史數(shù)據(jù)的期望和方差構(gòu)建了出庫(kù)頻率分布的模糊集,并通過分布式魯棒優(yōu)化的方法對(duì)出庫(kù)速度評(píng)價(jià)指標(biāo)進(jìn)行了轉(zhuǎn)化,最終建立了以貨位穩(wěn)定性原則、舾裝件齊配就近原則和舾裝件出庫(kù)速度最快原則為優(yōu)化目標(biāo)的多目標(biāo)優(yōu)化模型。

3) 設(shè)計(jì)了通過遺傳算法進(jìn)行熱啟動(dòng)的分支定價(jià)算法對(duì)模型進(jìn)行求解,實(shí)現(xiàn)了對(duì)大規(guī)模問題的高效求解。

4) 通過數(shù)值實(shí)驗(yàn)證明了方法的有效性,該方法對(duì)真實(shí)案例中的舾裝件立體倉(cāng)庫(kù)貨位分配問題具有明顯的優(yōu)化效果。