基于變鄰域NSGA-Ⅱ算法的多目標貨位優化研究*

羅 煥，閆富乾，宋小欣，張 劍

（西南交通大學 先進設計與制造技術研究所，成都 610000）

0 引言

隨著經濟環境和相關政策的影響，全球倉儲業的效率和管理水平得到迅速提高并穩步發展。各倉儲企業不斷追求倉儲的自動化與無人化，以釋放勞動力、提高倉儲作業運轉效率等，促使自動化立體倉庫的貨位優化成為研究熱點[1]。

焦玉玲等[2]針對自動化立體倉庫的工作效率和安全性要求，以出入庫作業時間、整體貨架的等效重心和相關產品的相對積累程度為多目標函數，建立了多目標貨位分配優化的數學模型，提出了多種群遺傳算法進行求解；唐文獻等[3]提出自動化立體倉庫分區存放策略，以多巷道貨架為對象，開展貨位優化研究。蔡錦文等[4]在傳統的以存儲頻率為中心的存儲分配策略的基礎上，考慮了工作負載平衡問題，提出了兩種新的自動化倉庫存儲分配策略；楊瑋等[5]以出庫效率和貨物重量為目標將倉庫進行分區，然后對比HPSO、GA、PSO三種算法的求解效果；宋賀騰等[6]以堆垛機的立體倉庫貨架重心最低和總取貨時間最短為目標，同時保證調整時間最短，采用改進自適應遺傳算法進行求解。

綜上所述，目前國內外學者在構建貨位優化模型時，多以出入庫效率為首選目標，再進行目標和約束擴展，而現有文獻往往忽略了同類貨物在倉庫中的分布情況以及各條巷道堆垛機工作量均衡問題，導致倉庫作業過于集中和不平衡，容易造成通道堵塞[7]。為此，本文以出入庫效率、貨架穩定性、同類貨物就近存放和堆垛機工作量均衡創建多目標優化數學模型，提出一種變鄰域NSGA-Ⅱ算法對遺傳操作后的部分個體進行變鄰域操作，以增強算法的求解搜索能力，并通過實例驗證了算法的有效性。

1 貨位分配模型

1.1 問題描述

自動化立體倉庫由貨架、堆垛機、傳送帶組成如圖1所示。貨位分配優化問題可以描述為：已知一系列貨物的類型、重量和出入庫頻率等相關屬性，按照一定的貨位分配原則，通過傳送帶和巷道堆垛機將這些貨物放置在第x排y列z層的貨位上，以實現同類貨物在各巷道兩側的貨架上分布均勻，各巷道堆垛機工作量均衡，同類貨物就近存放，提高貨架整體穩定性和貨物出入庫效率。

圖1 自動化立體倉庫示意圖

貨位分配過程滿足如下假設：每個貨位只存放一個貨物；堆垛機和傳送帶以平均速度運行，不考慮啟動和停止時間且可存取巷道左右兩排貨架上的一個貨物；不考慮貨架自身、貨箱以及托盤的重量，且貨物重量不影響存取時間，貨位重心位于該貨位的幾何中心；巷道為單向出口，出入庫口位置坐標為（0,0,0）。

1.2 符號說明

模型中相關參數說明：

x：倉庫第x排貨架，x={1,2,3….X}；

y：倉庫第y列貨架，y={1,2,3….Y}；

z：倉庫第z層貨架，z={1,2,3….Z}；

vx：傳送帶沿水平方向的平均速度；

vy：堆垛機沿巷道方向的平均速度；

vz：堆垛機沿豎直方向的平均速度；

pji：i類貨物中第j個貨物的出入庫頻率；

mji：i類貨物中第j個貨物的重量；

L：貨位的寬度；

L0：巷道寬度；

J：第i類貨物的總數；j={1,2,3….J}；

h：巷道序號，h={1,2,3….H}；

H：巷道總數；

G（x）max：第x排貨架的最大承重；

(Ai,Bi,Ci)：第i類貨物的中心坐標；

(xji,yji,zji)：第i類第j個貨物的貨位坐標；

t(xji,yji,zji)：第i類貨物中第j個貨物從倉庫出口到貨位的時間。

1.3 數學模型

式(1)為多目標函數集合，表示出入庫效率、貨架整體重心、同類貨物間距離、巷道堆垛機工作量均衡最小化，其中各部分計算如式(2)～(5)所示，式(2)表示出入庫效率f1，式(3)表示貨架整體重心f2，式(4)表示同類貨物間距離f3，式(5)表示巷道堆垛機工作量f4。式(6)表示第i類貨物中j貨物入庫所消耗時間。

約束條件：

其中：式(7)表示貨架x存放貨物總重量不能超過貨架最大承重；式(8)表示貨物j是否在巷道h中。

2 變鄰域NSGA-II算法

傳統的多目標優化是將不同的目標分配一定的權重以轉化為單目標優化，而目標的權重系數往往根據經驗或試錯法得出，難以適應問題的變化和需求，采用NSGA-II可以優化出適用多目標問題的非支配解種群[8]，其主要思想是對種群中個體的各個目標函數值進行非支配解分層，同層個體為非支配關系，其非支配解更傾向于選擇擁擠度大的個體以得到目標函數最優值。本文提出一種變鄰域NSGA-Ⅱ算法對遺傳操作后的部分個體進行變鄰域操作以增強其搜索能力，其算法流程圖如圖2所示。

圖2 變鄰域NSGA-Ⅱ算法

變鄰域NSGA-Ⅱ算法步驟如下：

1）初始化參數：設置種群大小PopSize，交叉概率為Pc，變異概率為Pm，最大迭代次數為Gmax，最優前端個體系數PF，鄰域初始種群大小VNSize，變鄰域最大循環次數VNS_Gmax。

2）初始化種群：采用實數編碼隨機生成初始種群Initial_Pop。

3）目標函數值的計算：根據式(2)～式(5)計算四個目標函數值f1、f2、f3、f4。

4）非支配排序和擁擠度計算：

（1）非支配排序：根據目標函數值進行個體序值的計算。

（2）擁擠距離計算：對四個目標分別計算相應的擁擠距離，再將四個目標函數的擁擠距離相加得到最后的擁擠距離。

5）遺傳操作：

（1）選擇操作：錦標賽選擇。根據序值和擁擠度進行選擇操作，對于種群中的兩個隨機個體，當序值不同時，序值小的個體將被選中；當序值相同時，擁擠距離大的個體將被選中。

（2）交叉：單點交叉。并運用同位基因的思想進行交叉前的處理。

（3）變異：為避免在前兩個操作中優秀基因的丟失，選擇隨機性更大的對調基因位的變異方式。

6）變領域操作：從變異后種群中隨機選部分個體進行變鄰域操作。首先，隨機選擇一種鄰域結構對初始鄰域種群進行鄰域操作，再將變鄰域產生的種群與初始鄰域種群進行合并，對合并后的種群進行選擇得到新一代鄰域種群。最后，判斷是否滿足鄰域終止條件，滿足則結束，不滿足則返回再執行變鄰域操作直到滿足鄰域終止條件。

7）種群合并：將變領域搜索產生的個體與變異之后未進行變鄰域操作的個體合并再與初始父種群合并。

8）生成新種群：根據父代種群規模對合并后的種群進行修剪生成新的父代種群。

9）判斷是否達到終止條件，若滿足則結束，否則，轉去執行步驟5）。

2.1 染色體編碼

本文針對貨位優化設計了一種基于貨位和貨物類型順序的編碼方式。貨位由倉庫貨架的排、列、層組成，則每條染色體長度為3N，N為貨物總數。如圖3 所示，假設一批貨物分為兩類，第一類貨物總數為4在貨架上的貨位為(1,2,1)，(2,4,5)，(4,3,1)，(5,4,3)，第二類貨物總數為3在貨架上的貨位為(1,4,3)，(1,5,3)，(3,4,1)。

圖3 染色體編碼

2.2 變鄰域操作

設計三種鄰域結構進行變鄰域操作：

1）鄰域1：前插入操作，從染色體基因序列中隨機選擇兩個不同的基因位點，在前基因位之前插入后基因，如圖4所示。

圖4 前插入變鄰域操作

2）領域2：后插入操作，從染色體基因序列中隨機選擇兩個不同的基因位點，在后基因位之前插入前基因，如圖5所示。

圖5 后插入變鄰域操作

3）領域3：基因片段倒序，從染色體基因序列中隨機選擇兩個不同的基因位點，然后將基因片段進行倒序操作，如圖6所示。

圖6 基因片段倒序變鄰域操作

3 實例驗證及分析

為了檢驗優化模型的有效性和變鄰域NSGA-Ⅱ算法的優越性，以某車間自動化立體倉庫的實際數據進行了實驗分析。

1）數據與參數

自動化立體倉庫共3條巷道和一條傳送帶，即巷道編號h從1到3，堆垛機工作巷道的寬度為1.5m。倉庫貨架6排6列5層，每個貨位的長、寬、高都為1m，傳送帶平均速度Vx=1.5m/s，堆垛機沿巷道方向平均速度Vy=1m/s，堆垛機沿巷道豎直方向平均速度Vz=0.5m/s。貨架平面布局圖如圖7所示。有5種類型的貨物共100個需要分配到合適的倉庫位置。貨物基礎信息如表1所示。NSGA-Ⅱ算法和變鄰域NSGA-Ⅱ算法參數賦值如表2所示。

表1 貨物信息表

表2 變鄰域NSGA-Ⅱ算法參數賦值及含義

圖7 貨架平面布局圖

2）實驗結果與分析

通過上文的方法進行編碼和求解，先運用NSGA-Ⅱ算法求解無巷道堆垛機工作量平衡目標和考慮巷道堆垛機工作量平衡目標，驗證模型的有效性；再運用變鄰域NSGA-Ⅱ算法求解考慮巷道堆垛機工作量平衡目標，并與NSGA-Ⅱ算法求解結果進行對比，驗證算法的優越性。應用MATLAB R2014a軟件編程實現算法，分別運行10次取運行結果的平均值進行比較，如表3所示。

通過表3對比NSGA-Ⅱ算法求解考慮和不考慮巷道堆垛機工作量均衡目標可以得到，出入庫效率、貨架整體重心、同類貨物間距離變化很小，而巷道堆垛機工作量平衡性提高了13.06%。通過對比變鄰域NSGA-Ⅱ算法與NSGA-Ⅱ算法求解考慮巷道堆垛機工作量均衡目標的計算結果可以看出，其他目標值變化不大，而巷道堆垛機工作量平衡性提高了54.39%，得到極大地提高。顯而易見，所提出的變鄰域NSGA-Ⅱ算法優化結果更好。

表3 變鄰域NSGA-Ⅱ與NSGA-Ⅱ計算結果對比表

4 結語

本文基于巷道堆垛機工作量均衡進行貨位分配并創建多目標優化數學模型，采用變鄰域NSGA-Ⅱ算法對遺傳操作后的個體進行變鄰域操作以增強算法搜索能力，實驗結果表明改進算法結果更優，而考慮巷道平衡后各條巷道的堆垛機工作量更加均衡，各類貨物在各條巷道的分布也更加合理。