黃 鵬，姚錫凡，胡曉陽，曾中榮

(1.華南理工大學(xué) 機械與汽車工程學(xué)院，廣東 廣州 510640；2.廣東世創(chuàng)金屬科技股份有限公司，廣東 佛山 528300)

0 引言

新技術(shù)和新業(yè)態(tài)的高速發(fā)展及產(chǎn)品生產(chǎn)周期不斷縮短，迫使許多制造企業(yè)向智能化轉(zhuǎn)型。智能工廠是智能制造和企業(yè)智能化轉(zhuǎn)型的核心主題之一。立體倉庫作為連接生產(chǎn)與銷售間物料流轉(zhuǎn)的重要環(huán)節(jié)之一，是智能工廠的重要組成部分，受到許多研究者的關(guān)注。相對傳統(tǒng)的倉儲方式，立體倉庫有許多優(yōu)點，如節(jié)約勞動力成本與建筑面積，提升倉庫作業(yè)效率，提升倉儲作業(yè)的可靠性和穩(wěn)定性[1-2]。如何讓立體倉庫更快速地響應(yīng)銷售和生產(chǎn)的需求是當(dāng)前倉儲行業(yè)的研究熱點之一，其中制約倉庫作業(yè)效率的主要因素之一就是貨位分配的質(zhì)量。

大量的智能優(yōu)化算法被用于求解倉庫中的優(yōu)化問題[3-4]。根據(jù)REYES等[5]在貨位分配問題上的研究結(jié)論，許多文獻使用遺傳算法(Genetic Algorithm, GA)、禁忌搜索(Taboo Search, TS)等元啟發(fā)式方法優(yōu)化求解倉庫貨位分配問題。貨位分配優(yōu)化問題中常見的優(yōu)化目標(biāo)是出入庫效率最高、貨架穩(wěn)定性最大、產(chǎn)品關(guān)聯(lián)度高、能耗最小等。曹現(xiàn)剛等[6]、ZHANG等[7]和郭娟等[8]都針對立體倉庫貨位分配問題建立考慮出入庫效率、貨架穩(wěn)定性和貨物相關(guān)性的多目標(biāo)模型。其中：曹現(xiàn)剛等[6]和ZHANG等[7]都采用了改進遺傳算法求解貨位分配優(yōu)化模型，曹現(xiàn)剛等[6]在遺傳算法中融合模擬退火機制增強遺傳算法的搜索能力；ZHANG等[7]在遺傳交叉和變異中采用了自適應(yīng)算子以提升子代解的質(zhì)量；而郭娟等[8]采用了融合非支配排序方法的粒子群算法求解多目標(biāo)貨位分配模型，并對改進粒子群算法進行了案例驗證。ENE等[9]則關(guān)注立體倉庫作業(yè)能量消耗問題，建立了最小化能量消耗的貨位分配優(yōu)化模型，采用了遺傳算法對該模型進行優(yōu)化求解，以滿足立體倉庫的環(huán)保節(jié)能需求。劉愷文等[10]針對立體倉庫作業(yè)過程建立了能量消耗模型，采用一種基于levy飛行搜索策略的改進灰狼算法對立體倉庫作業(yè)能量優(yōu)化模型進行求解，并通過仿真實驗驗證了其算法的有效性。

除了上述優(yōu)化原則外，許多研究人員在貨位分配優(yōu)化問題中考慮倉儲流程約束和倉庫物理空間約束，建立了更加切合實際情況的貨位分配優(yōu)化模型；TU等[11]在貨位分配優(yōu)化模型中添加揀貨負載均衡和補貨時間約束，提出了啟發(fā)式多目標(biāo)遺傳算法對模型進行優(yōu)化求解，并結(jié)合案例驗證了該算法的有效性；YANG等[12]建立了集成存取作業(yè)調(diào)度的貨位分配優(yōu)化模型，針對不同規(guī)模的優(yōu)化問題設(shè)計了不同的禁忌搜索算法，并對算法參數(shù)的敏感性進行實驗分析；唐文獻等[13]針對船舶工業(yè)立體倉庫，考慮物品分巷道存儲原則，提出一種細菌覓食算法求解多目標(biāo)貨位分配模型；XIE等[14]針對分組約束的貨位分配問題提出一種鄰域受限的鄰域搜索算法，并對比了數(shù)學(xué)規(guī)劃法，結(jié)果顯示其設(shè)計的算法性能更加優(yōu)異，是一種有效求解帶分組約束貨位分配問題的算法；GUERRIERO等[15]和QUINTANILLA等[16]將倉庫空間利用率視為貨位分配問題的優(yōu)化目標(biāo)，并設(shè)計了啟發(fā)式、元啟發(fā)式及局部搜索算法求解貨位分配優(yōu)化問題，驗證了局部搜索算法能夠解決貨位分配優(yōu)化問題；HE等[17]開發(fā)了一種基于鄰域變異算子的粒子群算法求解帶空間順序約束的貨位分配問題，并對該算法進行了數(shù)值實驗，其實驗結(jié)果顯示，帶有擾動的鄰域變異算子能夠有效地跳出局部最優(yōu)解，增強了算法的全局搜索能力；蔡安江等[18]則研究了雙出口立體倉庫貨位分配問題，提出一種改進蛙跳算法求解多目標(biāo)貨位分配模型，并通過實驗驗證了該算法的有效性。

不難發(fā)現(xiàn)，許多貨位分配優(yōu)化文獻將出入庫效率、貨架穩(wěn)定性、貨物相關(guān)性或空間利用率作為優(yōu)化重心，而忽略了貨架間貨物分布的失衡和堆垛機負載均衡問題。此外，立體倉庫貨位分配問題的研究大量應(yīng)用元啟發(fā)式智能優(yōu)化算法，如遺傳算法等。然而，智能優(yōu)化算法的優(yōu)點和缺陷都比較明顯，實際應(yīng)用需要考慮各個算法的特性，如算法的收斂速度、適用問題規(guī)模等因素。針對貨位分配這類離散優(yōu)化問題而言，連續(xù)型智能優(yōu)化算法需要在求解過程中設(shè)計離散化環(huán)節(jié)。離散化環(huán)節(jié)需要特別關(guān)注，因為不合理的離散化可能會抑制優(yōu)化算法的性能。同時，一些研究表明，針對離散優(yōu)化問題開發(fā)有效的局部搜索算子增強算法的局部搜索能力是極其重要的[16-17]。延遲接受爬山(Late Acceptance Hill-Climbing, LAHC)算法在車間調(diào)度領(lǐng)域被證明是一種高效的迭代鄰域搜索算法[19]，而在貨位分配問題上卻沒有得到有效運用?？紤]當(dāng)前的研究現(xiàn)狀，本文建立了考慮堆垛機負載均衡的多目標(biāo)立體倉庫貨位分配優(yōu)化模型，并提出一種集成GA和LAHC算法優(yōu)勢的兩階段混合優(yōu)化算法。通過仿真實驗結(jié)果表明，該兩階段混合算法較好地集成了GA算法的全局探索能力和LAHC算法的強大局部搜索能力，能夠有效解決立體倉庫貨位分配問題。

1 場景及數(shù)學(xué)建模

立體倉庫主要由貨架、堆垛機、出入庫平臺和運輸設(shè)備(自動導(dǎo)引小車、傳送帶、升降機等)組成。S金屬公司是廣東一家大型的金屬加工與設(shè)備生產(chǎn)企業(yè)，該公司計劃在其新廠區(qū)建設(shè)一個中型立體倉庫，用于廠內(nèi)物料中轉(zhuǎn)。該公司計劃建設(shè)的立體倉庫布局與YUE等[20]所提及的倉庫相似，但是將立體倉庫的倉儲部分與物料流動環(huán)節(jié)進行了重新布局，以節(jié)省更多建筑面積。如圖1所示，立體倉庫的存儲區(qū)域與物料處理區(qū)域分布在不同的樓層，二者通過升降機實現(xiàn)物料轉(zhuǎn)移與流通。物料處理樓層包含了DE KOSTER等[21]所提及的接收、打包、揀選等主要倉儲活動。在物料處理過程中大量應(yīng)用自動導(dǎo)引小車(Automated Guided Vehicle, AGV)，以減少傳送帶的使用，提升倉庫的物料轉(zhuǎn)運的柔性度。就單個貨架而言，貨架的出入庫平臺與升降機相連，實現(xiàn)貨架與物料處理層的鏈接與流轉(zhuǎn)。

貨位分配作為倉儲流程的起點，其結(jié)果的好壞會對后續(xù)環(huán)節(jié)產(chǎn)生影響[22]。合理的貨位分配與設(shè)置是提升立體倉庫倉儲效率的關(guān)鍵之一。貨位分配主要為入庫物料安排恰當(dāng)合理的倉儲貨位，以提升后續(xù)倉儲操作的效率。貨位分配問題是分配問題的變種之一，已被證明是NP-Hard問題[23]。為了更好地管理倉庫，提升倉庫作業(yè)效率，大量的貨位分配策略被提出，如“最短路徑”、“重心最低”、“先進先出” 等。這些分配策略體現(xiàn)了倉庫管理者對倉庫不同性能的重視程度，即倉庫運作過程中的優(yōu)化目標(biāo)。為了使立體倉庫更好地適應(yīng)公司的實際需求，本研究在貨位分配中的優(yōu)化目標(biāo)主要基于效率最高原則、貨架穩(wěn)定性原則和堆垛機負載均衡原則。

1.1 模型建立

假設(shè)立體倉庫有Nx個貨架，每個貨架有Ny列、Nz層，所有貨位長、寬、高均相等長度均為L，用Vy、Vz表示堆垛機在y軸和z軸方向上的運行速度，同時不考慮模型中堆垛機的加減速和啟停特性，并約定每個貨位只能存放一種物品，且一個入庫托盤被視為一個入庫訂單，即將入庫物料以入庫托盤為單位重新劃分入庫訂單。因為立體倉庫存儲部分與物料中轉(zhuǎn)處理環(huán)節(jié)分離，所以不考慮不同貨架間的距離。為了建立立體倉庫模型，使用表1中的符號及其定義。

表1 立體倉庫模型的符號定義與描述

立體倉庫貨位分配問題中常見的優(yōu)化原則是 “效率優(yōu)先原則”和“貨架穩(wěn)定性原則”，但在金屬工業(yè)環(huán)境下堆垛機的負載均衡也尤為重要。依照立體倉庫平穩(wěn)、安全運行的要求和S公司實際需求，下面構(gòu)建考慮立體倉庫出庫效率、貨架穩(wěn)定性及堆垛機負載均衡需求的多目標(biāo)優(yōu)化模型。

(1)效率優(yōu)先原則

固定貨架的立體倉庫中，提升作業(yè)效率的有效方法是減少貨物在堆垛機上的處理時間，即將貨物放置于距離出入庫平臺更近的貨位。在堆垛機能夠在y軸與z軸同時運動的情況下，從貨位(x,y,z)到達出入庫平臺原點(0,0,0)所花費的時間

(1)

根據(jù)效率優(yōu)先原則，出入庫頻次高的貨物需要放置在離出入庫平臺較近的貨位上，以此減少倉庫中出入庫操作的時間，實現(xiàn)作業(yè)效率最大化。為了實現(xiàn)倉庫效率最大化，構(gòu)建了效率最大化貨位分配目標(biāo)函數(shù)，如式(2)所示：

(2)

式中Pi≠0。

(2)貨架穩(wěn)定性原則

貨架穩(wěn)定性原則主要考慮立體倉庫在使用過程貨架的穩(wěn)定性需求。貨架的穩(wěn)定性和貨架內(nèi)倉儲貨物的分布有關(guān)，貨物分布越集中在貨架的低層，貨架的穩(wěn)定性越強，因此要保證貨架的穩(wěn)定性就要遵循“下重上輕”原則。受此啟發(fā)，本文設(shè)計了貨架穩(wěn)定性貨位分配優(yōu)化目標(biāo)函數(shù),如式(3)所示：

(3)

(3)堆垛機負載均衡原則

堆垛機負載均衡原則主要為了均衡每個過道內(nèi)的出入庫任務(wù)數(shù)量，避免托盤在一個巷道內(nèi)堆積、堆垛機超負荷工作而影響作業(yè)效率及堆垛機壽命。同時，對于大中型立體倉庫而言，貨物分散在不同貨架更有利于倉庫運作。項前等[24]設(shè)計了以貨架中占用貨位數(shù)量的標(biāo)準(zhǔn)差來反映作業(yè)的均衡程度的堆垛機負載均衡目標(biāo)函數(shù)，但仍難以完全反映不同過道的負載情況。本文對其設(shè)計的優(yōu)化函數(shù)進行了改進，改進后的堆垛機負載均衡函數(shù)如式(4)～式(8)所示：

(4)

(5)

(6)

(7)

(8)

改進后的堆垛機負載均衡優(yōu)化目標(biāo)函數(shù)，不但考慮了貨架中貨物的數(shù)量均衡，而且考慮了貨架中物料出入庫頻率的均衡，能夠更加全面地反映貨架的出入庫負載差異。同時，該優(yōu)化函數(shù)有利于物料的分散，避免物料頻率分布不均造成的巷道堵塞或者堆垛機損耗不均衡的問題。

(4)約束條件

優(yōu)化過程中，參數(shù)需要滿足立體倉庫的約束條件，避免出現(xiàn)不合法的優(yōu)化結(jié)果。根據(jù)倉庫配置參數(shù)和貨位分配原則，對上述目標(biāo)函數(shù)中的變量作了一些約束。具體約束條件如式(9)和式(10)所示：

(9)

(10)

以上約束條件保證了貨位變量不會超出倉庫配置，且保證貨位與貨物一一對應(yīng)的關(guān)系，不會出現(xiàn)一對多的情況。式(9)表示每個入庫托盤訂單只能放在一個貨位，而式(10)則要求每個任意貨位只能存放一個入庫托盤訂單。同時，在整個貨位優(yōu)化過程中，約定入庫訂單托盤的數(shù)量不會超過可用貨位的數(shù)量，即N小于等于當(dāng)前倉庫空閑貨位數(shù)量。

為簡化模型的求解，采用權(quán)重系數(shù)變化法對多個優(yōu)化目標(biāo)進行線性化。該方法將不同優(yōu)化目標(biāo)賦予不同的權(quán)重wj，最終優(yōu)化目標(biāo)表示為不同優(yōu)化目標(biāo)的線性加權(quán)。權(quán)重系數(shù)法求解多目標(biāo)優(yōu)化的描述如式(11)所示：

s.t.

(11)

通過分析S公司對立體倉庫運作過程中的需求，利用層次分析法獲得不同優(yōu)化目標(biāo)的權(quán)重。最終的立體倉庫貨位分配模型利用權(quán)重均衡了3個優(yōu)化目標(biāo)，實現(xiàn)了不同優(yōu)化目標(biāo)的均衡。所建立的立體倉庫優(yōu)化模型如式(12)～式(15)所示：

minf(i,x,y,z,nx)=ω1×f1(i,x,y,z)+ω2×
f2(i,x,y,z)+ω3×f3(x,nx),

(12)

(13)

s.t.

(14)

(15)

多目標(biāo)進行線性加權(quán)時，為了消除不同目標(biāo)量綱的影響，本文對以上3個優(yōu)化目標(biāo)函數(shù)均進行歸一化處理。考慮歸一化處理過程中可能出現(xiàn)數(shù)值溢出現(xiàn)象，將各個目標(biāo)函數(shù)值歸一化的公式如式(16)所示：

(16)

在對多目標(biāo)進行線性化前需要確定各個目標(biāo)函數(shù)的極值范圍。由于大型立體倉庫貨位優(yōu)化問題很難獲取問題的精確解，本研究通過單目標(biāo)優(yōu)化實驗獲得各個優(yōu)化目標(biāo)的極值。同時，為了增加實驗獲取各目標(biāo)函數(shù)極值范圍的魯棒性，對實驗獲得的最大值進行放大，最小值進行縮小。

2 基于遺傳算法和延遲接受爬山算法的混合算法

本研究提出一種基于GA和LAHC算法的兩階段混合算法求解建立的立體倉庫貨位分配優(yōu)化模型。為了集成GA算法的收斂能力和LAHC算法的局部搜索能力，混合算法分成GA和LAHC兩個階段，以最大化兩種算法的尋優(yōu)效率。GA階段，利用遺傳算法優(yōu)秀的收斂能力，快速獲得一個相對較好的初始解。然后，利用LAHC算法在上述初始解的鄰域中搜索獲得最優(yōu)解。根據(jù)GA和LAHC算法的流程，本研究設(shè)計的兩階段混合算法的偽代碼如下：

算法1GA-LAHC算法。

輸入：種群大小Pn、最大迭代次數(shù)Maxgen、變異概率Pm、交叉概率Pc；初始化歷史列表大小H和最大迭代次數(shù)maxiter;

輸出：找到的最優(yōu)解。

/* ---------------GA階段 ----------------*/

初始化種群

gen← 0

Repeat: %重復(fù)

計算種群中個體的適應(yīng)度值，并對種群進行聯(lián)賽選擇

隨機選擇一個個體替換為全局最優(yōu)解

初始化一個空的新種群,Newpop

i← 0

Repeat： %重復(fù)

if Random(0,1)>Pcthen

隨機從種群中選擇兩個個體,E1,E2

C1,C2←Crossover(E1,E2)

C1,C2←Repair(C1,C2)

end

if Random(0,1)>Pmthen

隨機選擇一個個體,E3

C3←Mutation(E3)

end

將子代添加到新種群中,更新Newpop

i←i+ 1

untili≥Pn

gen←gen+ 1

untilgen≥Maxgen

/* --------------- LAHC階段 ----------------*/

短碼轉(zhuǎn)換為長碼，并將轉(zhuǎn)換后的長碼作為初始解X

計算初始解的目標(biāo)函數(shù)值f(X)

X*←X

f(X*) ←f(X)

初始化歷史目標(biāo)值列表，Lh←f(X),?h∈{1,2,…,H-1,H}

j← 0

nidle← 0

Repeat： %重復(fù)

生產(chǎn)一個鄰域解Y,并計算目標(biāo)函數(shù)值f(Y)

iff(Y) ≥f(X) then

nidle←nidle+ 1

else

nidle← 0

end

iff(Y)

X*←Y,f(X*) ←f(Y)

end

h← 1 +jmodH%取余

iff(Y)

X←Y,f(X) ←f(Y)

end

iff(Y)

更新歷史列表，Lh←f(Y)

end

j←j+ 1

untilj≥maxiterornidle≥0.02 *maxiter

終止算法輸出最優(yōu)解

2.1 問題編碼

求解離散問題整數(shù)序列編碼方法被大量應(yīng)用，如旅行商問題、車間調(diào)度問題、貨位分配問題等。求解貨位分配問題存在多種整數(shù)序列編碼方式。在混合算法中采用了其中兩種編碼方法，如圖2所示。兩種編碼在使用前均需對入庫托盤訂單和倉庫貨位進行整數(shù)編碼?；谌霂煊唵蔚恼麛?shù)序列編碼是以入庫訂單數(shù)作為編碼長度，為每一個入庫托盤訂單分配一個貨位編號?；谕斜P訂單的編碼能夠減少編碼的長度，在大規(guī)模問題上能夠有效提升算法的效率，但不利于算法的全局探索。而基于貨位的編碼是以可用貨位數(shù)量作為編碼長度，將入庫訂單分配給不同的貨位。基于可用貨位的編碼方式，有利于算法全局搜索，但是需要添加大量的啞訂單，增加了算法的解碼復(fù)雜度。

為了進一步利用兩種編碼的長處，在混合算法中同時利用了這兩種編碼方法，即兩階段編碼。GA階段采用基于入庫訂單的編碼方法，利用遺傳算法種群的優(yōu)勢來彌補編碼全局搜索能力的不足；LAHC階段則采用基于可用貨位的編碼方式，以充分發(fā)揮延遲接受爬山算法的局部搜索能力。因此，算法中存在問題編碼的轉(zhuǎn)換過程，編碼轉(zhuǎn)換過程如圖3所示。編碼轉(zhuǎn)換的過程中需要使用啞訂單占據(jù)多余的貨位，其中啞訂單的編號約定為0。

2.2 GA階段

遺傳算法是模擬達爾文生物進化論和生物遺傳機理的生物進化計算模型，是一種模擬自然進化過程的智能優(yōu)化算法。遺傳算法的操作包含了生物進化的必須條件繁殖(交叉、變異)和生存(選擇)。交叉過程中兩個個體在基因?qū)用姘l(fā)生交換，產(chǎn)生兩個子代個體。常見的遺傳交叉操作分為單點交叉(Single Point Crossover, SPX)和多點交叉。值得注意的是，離散優(yōu)化問題雙親交叉操作容易產(chǎn)生非法解，這需要設(shè)計相應(yīng)的染色體修復(fù)規(guī)則以修復(fù)非法解。GA階段解的修復(fù)規(guī)則是將重復(fù)的貨位編碼隨機替換為可行貨位編碼，子代通過選擇機制決定自身基因傳遞的可能性。GA-LAHC算法的選擇機制是精英保留和錦標(biāo)賽選擇機制，而變異操作則針對單個個體進行，個體有一定的概率能夠提升自身的適應(yīng)值(生存概率)。遺傳算法中變異方式主要有單點變異和多點變異。GA-LAHC算法的變異采用了單點變異(引入新貨位編號)和兩點變異(交換貨位編號)。在大規(guī)模立體倉庫貨位分配問題中，一次變異帶來的效用極其有限。因此，GA-LAHC算法GA階段的重點在交叉操作。事實上，GA-LAHC算法GA階段的目的是為LAHC算法提供初始解。

為了最大程度地利用遺傳算法的搜索能力，在最短時間內(nèi)為延遲接受爬山算法提供盡可能優(yōu)異的初始解，需要對遺傳算法的交叉、變異操作進行改進。因為GA階段的主要目的是快速獲得一個相對優(yōu)異的解，所以改進的重點不在變異操作中。而遺傳算法出色的收斂能力主要來源于交叉操作，設(shè)計一種高效的交叉算子有利于算法的快速收斂。同時常規(guī)的雙親交叉只利用了個體層面的信息，而忽略了雙親個體基因?qū)用嫘畔⒌睦谩Ｊ艿紹ENNACEUR等[25]貪婪交叉算子的啟發(fā)，本文設(shè)計了一種基于貨位貪婪的交叉算子(Position Greedy Crossover, PGX)，以提升遺傳算法的收斂和信息利用能力。

2.2.1 貨位貪婪交叉

貨位貪婪交叉算子在交叉過程中會利用個體中的每個基因信息，并對占優(yōu)基因進行貪婪遺傳操作。但這樣處理會導(dǎo)致優(yōu)勢貨位的大量重復(fù)，不利于算法的全局探索和貨架間負載均衡，如圖4中的子代存在多個9號貨位(占優(yōu)基因)。為了保證倉庫內(nèi)各個堆垛機的負載相對均衡和保留弱化優(yōu)勢基因，對貨位貪婪進行限制。限制條件與貨架儲貨狀態(tài)有關(guān)，其定義如式(17)所示：

(17)

式中：SCx表示貨架x的競爭力；ˉP、Px分別表示倉庫所有貨架貨物出入庫頻率的均值和x貨架內(nèi)出入庫頻率總和；Ox表示為x貨架內(nèi)存儲貨物的總數(shù)。貨位貪婪的交叉算子具體過程如圖4所示。

進行PGX交叉時，從種群中隨機選取兩個個體作為父代，同一個入庫訂單在滿足貨架競爭條件下進行貨位編號貪婪交叉。貨位交叉過程，貨位分配會在貨架競爭規(guī)則下向貨位使用量少、貨架內(nèi)貨物出入庫頻率低的貨架傾斜。交叉過程中，在滿足貨位競爭通過計算父代中兩個貨位在當(dāng)前訂單的競爭值大小做出貨位決策。交叉過程的表達式如式(18)所示：

(18)

式中:Li表示子代入庫托盤訂單i選定的貨位編號;l1、l2分別表示父代個體1入庫托盤訂單基因i的貨位編號和父代個體2入庫托盤訂單基因i的貨位編號;ly、lz分別表示貨位y軸和z軸上的值。通過貨位貪婪交叉算子能夠賦予遺傳算法更快速收斂的能力。同時，由于貨位貪婪交叉算子強化了遺傳算法對基因?qū)用嫘畔⒌睦茫z傳算法的優(yōu)化能力也得到了提升。

2.3 LAHC階段

應(yīng)用PGX交叉的遺傳算法雖然提升了收斂速度和對基因信息的利用率。但PGX交叉算子的引入不能改變遺傳算法在大規(guī)模問題上容易陷入局部最優(yōu)解的特性。遺傳算法交叉的本質(zhì)是舊解的拆解和個體舊基因重構(gòu)。這種大范圍的調(diào)整不利于算法的局部搜索，且容易產(chǎn)生大量重復(fù)搜索。雖然遺傳算法存在變異機制，但由于交叉操作的進行，變異操作的效果將大大減弱?？紤]到遺傳算法局部搜索能力的缺陷，引入一種強有效的局部搜索機制就顯得十分重要。延遲接受爬山算法作為一種迭代局部搜索算法，具有很強的局部探索能力。此外，該算法利用目標(biāo)值作為當(dāng)前解的跳躍約束，同時延遲接受爬山算法引入歷史列表(搜索值列表)，極大地增加了當(dāng)前解跳躍的靈活度，減小了跳出當(dāng)前解的難度。

(1)初始化

LAHC算法的初始解是從GA中獲得，將GA算法當(dāng)前全局最優(yōu)解編碼轉(zhuǎn)換成長編碼形式作為LAHC算法的初始解。

(2)鄰域生成

LAHC算法是一種鄰域搜索算法，需要對算法的鄰域探索方法進行約定。鄰域搜索算子與遺傳算法中的兩點變異方法相似，在搜索過程中直接交換染色體內(nèi)兩基因的值，實現(xiàn)一次鄰域搜索。由于解的結(jié)構(gòu)中含有大量的啞訂單，即虛擬的占位訂單，為了減少無謂鄰域搜索，本文對鄰域搜索的起點作了約束，即在換位條件中約定交換基因值的兩點中至少有一個基因位置的基因值不為0。

3 仿真數(shù)據(jù)案例分析與實驗

3.1 實驗平臺

仿真實驗在Pycharm環(huán)境中進行，使用的計算機硬件配置為Intel Core @i5-8 300H 2.3 GHz，16 G RAM；仿真實驗中立體倉庫各個參數(shù)如表2所示。

表2 立體倉庫參數(shù)表

本研究的優(yōu)化入庫訂單中包含498種商品，2 302個入庫托盤訂單，需將這些入庫托盤訂單在上述的5 040個貨位的立體倉庫中進行貨位分配優(yōu)化。入庫托盤信息包括物料編號、出入庫頻次、質(zhì)量等。

3.2 實驗與結(jié)果分析

根據(jù)層次分析法，將目標(biāo)1～目標(biāo)3分配的權(quán)重分別設(shè)置為0.388 8、0.277 7和0.333 5。進行仿真案例優(yōu)化實驗前，需要對所建立模型的有效性進行驗證，以保證優(yōu)化結(jié)果的可靠性。模型驗證完成后，對混合算法進行有效性驗證實驗及參數(shù)敏感性分析實驗。

3.2.1 模型驗證實驗

根據(jù)SARGENT等[26]闡述的模型驗證和檢驗方法，模型驗證采用案例驗證法。模型驗證實驗使用一個小規(guī)模案例在IBM公司開發(fā)Cplex軟件中進行求解驗證。驗證案例包含4個貨架，每個貨架有6列5層30個貨位。案例需為35個入庫托盤訂單分配倉儲貨位。入庫訂單信息如表3所示。

表3 模型驗證案例待分配訂單信息

Cplex軟件的優(yōu)化流程主要包括3個步驟：定義變量和加載數(shù)據(jù)、明確優(yōu)化目標(biāo)、添加約束?？紤]到堆垛機均衡目標(biāo)涉及到了多個貨架的倉儲數(shù)量及其訂單物料的出入庫頻次，且優(yōu)化目標(biāo)公式較為復(fù)雜，直接添加該優(yōu)化目標(biāo)有一定難度。針對堆垛機負載均衡優(yōu)化目標(biāo)，在實際模型測驗中將其轉(zhuǎn)化成優(yōu)化模型約束。出入庫效率和貨架穩(wěn)定性的優(yōu)化目標(biāo)則參考Cplex多目標(biāo)建模指導(dǎo)文件，進行配置兩個優(yōu)化目標(biāo)的屬性。

為了檢驗Cplex優(yōu)化結(jié)果的質(zhì)量，利用延遲接受爬山算法進行優(yōu)化對比實驗。LAHC算法最大迭代次數(shù)設(shè)置為10 000 000，歷史列表長度設(shè)置為50。LAHC算法優(yōu)化結(jié)果與Cplex求解結(jié)果對比如表4所示。針對同一入庫訂單的分配比較了貨位出入時間和貨位重心，將各自優(yōu)勢貨位進行加粗顯示，相應(yīng)的訂單編號帶*號。加粗顯示的貨位表明該貨位至少在一個優(yōu)化目標(biāo)上優(yōu)于另一種分配方案。結(jié)果表明Cplex模型解在23個貨位分配優(yōu)于LAHC所得最優(yōu)解。Cplex模型求解結(jié)果也印證了模型能夠求解，且求解結(jié)果優(yōu)于LAHC算法。

表4 模型驗證結(jié)果對比

3.2.2 算法驗證與分析

在混合算法有效性驗證實驗中，對比了單點交叉遺傳算法(GA-SPX)、改進遺傳算法(GA-PGX)、LAHC算法及改進粒子群優(yōu)化(Improved Particle Swarm Optimization, IPSO)算法。IPSO算法流程和參數(shù)可參考文獻[17]，實驗中算法最大迭代次數(shù)統(tǒng)一為300次。GA算法種群設(shè)置Pn=100,Maxgen=300,Pc=0.6，Pm=0.95。算法的基準(zhǔn)設(shè)置為進行20次隨機存儲策略(Random Storage Policy,RSP)所得的平均值。算法有效性驗證實驗重復(fù)進行了20次，實驗所得結(jié)果如表5所示。

表5 算法有效性驗證實驗結(jié)果

根據(jù)表5的數(shù)據(jù)，GA-LAHC混合算法在求解精度和穩(wěn)定性上遠優(yōu)于GA-SPX和GA-PGX。GA-LAHC算法的求解質(zhì)量較RSP和GA-PGX分別提升了80%和50%以上。與LAHC相比，GA-LAHC算法在穩(wěn)定性和求解質(zhì)量上都有所提升，其中求解質(zhì)量提升相對較大。GA-LAHC算法優(yōu)化結(jié)果比LAHC算法提升了5%，少數(shù)情況下求解質(zhì)量提升達13%；在算法穩(wěn)定性上，GA-LAHC算法的穩(wěn)定性與LAHC相比，提升不大。GA-LAHC較GA-SPX在求解精度和穩(wěn)定性上都有較大的提升。IPSO在求解結(jié)果上稍優(yōu)于GA-SPX，但求解穩(wěn)定性遠優(yōu)于GA-SPX。這是因為IPSO針對集裝箱貨位優(yōu)化改進的策略不適應(yīng)立體倉庫貨位優(yōu)化場景。相對其他算法來說，IPSO在求解穩(wěn)定性上具有一定的優(yōu)勢。

為了更加直觀地展現(xiàn)這幾種算法的性能，對以上幾種算法的收斂過程進行了可視化，結(jié)果如圖5和圖6所示。根據(jù)圖5和圖6可知，IPSO表現(xiàn)與GA-SPX相差不大，但是IPSO搜索最優(yōu)解的能力優(yōu)于GA-SPX。這是因為IPSO利用了新的拓撲結(jié)構(gòu)來引導(dǎo)粒子跳出局部最優(yōu)解。但由于案例和解編碼的調(diào)整，IPSO算法的性能無法完全釋放。根據(jù)“No Free Lunch”定理可以推斷，如果對IPSO進行針對性改進，IPSO也能取得相對較好的優(yōu)化效果。

就LAHC算法而言，由圖5可以看出LAHC算法在求解貨位分配問題上的求解質(zhì)量不劣于GA-LAHC算法。LHAC算法優(yōu)化結(jié)果在RSP存儲策略的基礎(chǔ)上提升了79%，優(yōu)化性能略遜色于GA-LAHC。從實驗結(jié)果上看，LAHC算法能夠解決立體倉庫貨位分配問題。但觀察LAHC算法的收斂曲線不難發(fā)現(xiàn)，LAHC算法存在收斂較慢的缺點。結(jié)合圖5和圖6的收斂曲線，可以發(fā)現(xiàn)GA-PGX算法收斂速度優(yōu)于其他算法(GA-LAHC除外)。此外，算法收斂曲線可以驗證GA-LAHC算法很好地融合了GA和LAHC算法的優(yōu)點。

由圖5不難觀察到，GA-LAHC算法在GA階段的收斂速度要快于LAHC算法。為了定量分析GA-LAHC算法與LAHC算法在GA階段的收斂速度，設(shè)計了收斂速度對比實驗。收斂速度對比實驗中，LAHC的終止條件設(shè)定為運行20次GA算法所得最優(yōu)目標(biāo)函數(shù)值的均值。記錄GA算法和LAHC算法所用的CPU時間，將LAHC算法所耗時間與GA算法CPU時間的差作為節(jié)省時間。為避免出現(xiàn)偶然性，LAHC算法也進行20次。算法收斂速度對比實驗結(jié)果如表6和圖7所示。分析表6的數(shù)據(jù)可得，GA-PGX算法增加迭代次數(shù)與節(jié)約時間收益成反比，且隨著迭代次數(shù)增加，節(jié)約時間收益加速減少。這是因為PGX交叉算子加強了對個體基因信息的利用，強勢基因的支配地位很難出現(xiàn)松動。然而，混合算法GA階段的任務(wù)是獲得較好的初始解。根據(jù)GA的收斂曲線可知，盲目增加GA算法的最大迭代次數(shù)只會浪費大量的計算資源，而初始解的質(zhì)量沒有明顯提升。LAHC算法優(yōu)異的鄰域搜索能力，配合歷史列表中以目標(biāo)函數(shù)值為導(dǎo)向的超平面能夠快速地跳出局部最優(yōu)解，極大地改善了GA局部搜索能力弱的問題。根據(jù)圖7的結(jié)果，合理設(shè)置GA的迭代次數(shù)能夠加速GA-LAHC算法的收斂。

表6 算法收斂速度對比結(jié)果

3.2.3 算法參數(shù)敏感性實驗

GA-LAHC算法融合了GA和LAHC算法，參數(shù)選擇也變得更加復(fù)雜。為了更好地確定GA-LAHC算法的參數(shù)，本文對算法的參數(shù)進行敏感性分析，以確定最佳的參數(shù)組合。本文提出的混合算法在GA階段的目的是生成一個較好的初始解。因此，GA階段不考慮遺傳算法變異概率對算法局部搜索能力的影響。根據(jù)前文對算法的描述，對混合算法的中GA種群大小Pn、GA交叉概率Pc、GA最大迭代次數(shù)Maxgen、歷史列表長度H和LAHC算法最大迭代次數(shù)maxiter進行敏感性分析。參數(shù)敏感性分析實驗分別進行20次，如表7所示為參數(shù)敏感性分析的統(tǒng)計結(jié)果。同時，為了更加直觀地展現(xiàn)各個參數(shù)對算法的影響，將所有實驗結(jié)果以散點柱形圖的形式呈現(xiàn)，結(jié)果如圖8所示。

表7 GA-LAHC算法參數(shù)敏感性實驗

從圖8不難發(fā)現(xiàn)，GA參數(shù)對GA-LAHC算法的穩(wěn)定性影響較大，而對算法求解精度影響較小。由圖8a和表7可知，GA種群規(guī)模增大到一定程度上可以提升算法求解穩(wěn)定性。GA階段種群規(guī)模對應(yīng)GA的搜索空間大小。增加GA種群規(guī)模意味著擴大搜索空間，GA獲得解的多樣性就會增加。這導(dǎo)致了種群規(guī)模增加混合算法獲得解的離群值惡化，而解的聚集度增加的現(xiàn)象。考慮計算時間和算法穩(wěn)定性的均衡，最佳的種群數(shù)量應(yīng)定為100。其次，GA階段的交叉概率影響了GA算法的全局探索能力，對LAHC階段初始解的質(zhì)量有較大影響。就Pc的數(shù)值而言，Pc值越小交叉的概率就越大，種群內(nèi)進行的交叉次數(shù)就越多。結(jié)合圖9中不同交叉概率的GA-PGX收斂特性可以發(fā)現(xiàn)，當(dāng)Pc超過一定閾值時GA-PGX在小迭代次數(shù)下目標(biāo)函數(shù)值沒有顯著提升。結(jié)合圖8b和圖9可以推測閾值在0.4～0.7之間。為了保證算法的穩(wěn)定性和求解速度，本文設(shè)定的最佳交叉概率為0.6。根據(jù)圖7和圖8c所示的結(jié)果，兩個實驗都證明了在迭代次數(shù)滿足GA獲得較好初始解的前提下，增加GA算法的迭代次數(shù)對算法求解質(zhì)量的影響很小。綜上可知，本文提出的GA-LAHC算法在GA階段的最佳參數(shù)組合為：Pn= 100;Pc= 0.6;Maxgen= 20。

LAHC算法的參數(shù)較少，主要有歷史列表長度H和最大迭代次數(shù)maxiter。歷史列表存放了LAHC算法搜索過的目標(biāo)函數(shù)值，限制了LAHC算法可接受鄰域解的范圍。在相同的條件下，歷史列表長度越大，LAHC可接受鄰域就越豐富，鄰域生成難度越小，具有更強的局部探索能力。同時，歷史列表長度約束了搜索步長，搜索步長越小，探索難度越低，求解穩(wěn)定性就越高。圖8e定性地驗證了，H越大搜索效率越低。但需要注意的是過小的H會使得算法鄰域搜索難度過大，導(dǎo)致算法極易陷入局部最優(yōu)，且難以通過簡單鄰域跳出局部最優(yōu)解。當(dāng)H=1時，LAHC退化成完全隨機搜索算法。而maxiter決定了LAHC算法探索鄰域的最大次數(shù)，探索次數(shù)增加能夠獲得更優(yōu)解的概率也增加，圖8d也驗證了這個結(jié)論。觀察圖8d可以發(fā)現(xiàn)，隨著迭代次數(shù)的增加求解質(zhì)量的提升幅度在減少。根據(jù)對LAHC參數(shù)敏感分析的結(jié)論，考慮到算法的優(yōu)化成本，本文設(shè)H=5，maxiter=250 000。

GA-LAHC算法能夠求解立體倉庫貨位分配問題，這是因為算法集成了GA的全局探索能力和LAHC的鄰域搜索能力?；旌纤惴ㄗ顑?yōu)解的提升依賴LAHC算法。LAHC算法核心在于其利用目標(biāo)函數(shù)值為導(dǎo)向的變鄰域局部搜索方式。當(dāng)前解通過鄰域生成算子試探比當(dāng)前解更優(yōu)或歷史記錄更優(yōu)的鄰域結(jié)構(gòu)，產(chǎn)生更好的鄰域解。歷史列表一方面用來記錄算法搜索歷史；另一方面其作為當(dāng)前解轉(zhuǎn)換結(jié)構(gòu)的約束條件，限制了可接受的鄰域結(jié)構(gòu)，引導(dǎo)算法向更優(yōu)的目標(biāo)值探索。LAHC算法的搜索方式能夠求取最優(yōu)解的前提是當(dāng)前解能夠通過一系列鄰域結(jié)構(gòu)轉(zhuǎn)換成最優(yōu)解的結(jié)構(gòu)，即要滿足更優(yōu)解是較優(yōu)解的鄰域之一的條件。GA-LAHC算法和LAHC算法在貨位分配問題上取得較好的優(yōu)化結(jié)果，也從側(cè)面印證了貨位分配問題滿足LAHC算法的前提條件。但對比模型驗證和算法驗證求解效果可以發(fā)現(xiàn)，在不同問題規(guī)模小貨位分配問題解空間的連續(xù)性有一定的差異。小規(guī)模問題上，以目標(biāo)函數(shù)值為導(dǎo)向解空間連續(xù)性不足，導(dǎo)致簡單的鄰域生成方式難以獲得較滿意的優(yōu)化結(jié)果。LAHC算法的缺點在于單點探索方式效率較低，這也是LAHC算法前期收斂速度不如GA的主要原因。而GA-LAHC算法利用了GA的全局探索能力來解決LAHC前期收斂速度較慢的問題，為LAHC局部搜索提供較好的初始解?？偟膩碚f，GA-LAHC算法結(jié)合了GA和LAHC算法的優(yōu)點，同時也能夠有效地優(yōu)化求解立體倉庫貨位分配問題。

4 結(jié)束語

本研究在立體倉庫貨位優(yōu)化的常見原則的基礎(chǔ)上，考慮堆垛機的負載均衡，設(shè)計了包含出入庫效率、貨架穩(wěn)定性和堆垛機負載均衡的多目標(biāo)優(yōu)化模型，并提出一種基于改進GA和LAHC算法的兩階段混合算法。該算法解決了LAHC算法收斂速度較慢和GA局部搜索能力弱的問題，同時提升了算法的求解穩(wěn)定性和精度。GA-LAHC算法較好地集成了GA算法和LAHC算法的優(yōu)點。在一個5 040貨位的仿真案例中，GA-LAHC算法的最優(yōu)解比GA-PGX和RSP分別提升了56%和80%。在求解精度上，GA-LAHC比LAHC算法求解結(jié)果提升了5.9%，可以有效求解立體倉庫貨位分配問題。同時，對比IPSO算法的求解結(jié)果，GA-LAHC在求解精度上有明顯優(yōu)勢，但在求解穩(wěn)定性上差距不是很大。總的來說，GA-LAHC算法能夠求解所建立的立體倉庫貨位優(yōu)化模型，并取得相對較好的優(yōu)化結(jié)果。

盡管所提出GA-LAHC算法的有效性得到了初步驗證，但與實際應(yīng)用需求仍有一定的差距，同時所采用的鄰域搜索算子還過于簡單，沒有充分利用領(lǐng)域知識。在后續(xù)研究中可以增加約束和優(yōu)化目標(biāo)，以更加接近實際情況；其次，利用領(lǐng)域知識設(shè)計更加高效復(fù)雜的鄰域搜索算子，提高算法在不同問題規(guī)模的適應(yīng)性，提升算法的實效性。