楊烈兵，呂 宏

?

鋰電池化成庫雙工位堆垛機路徑優(yōu)化研究

楊烈兵，呂 宏*

（昆明理工大學 機電工程學院，云南 昆明 650504）

隨著鋰電池行業(yè)的發(fā)展，鋰電池物流已成為鋰電行業(yè)的重要組成部分。而立體倉庫是鋰電物流的核心，堆垛機作為立體倉庫的主要搬運工具，其搬運的效率直接影響立體倉庫的整體效率。本文以鋰電池化成庫為例，對化成庫中雙工位堆垛機存取貨路徑進行研究。結合雙工位堆垛機存取貨特點，提出以堆垛機運行總路程為優(yōu)化目標的模型，并采用遺傳算法對模型進行優(yōu)化仿真。最后對仿真結果及優(yōu)化前的最鄰存取貨策略和隨機存取貨策略進行對比分析，結果說明遺傳算法能有效的實現雙工位堆垛機的路徑優(yōu)化，是提高立體倉庫出入庫效率的一種有效方法。

鋰電池；化成庫；雙工位堆垛機；路徑優(yōu)化

0 引言

近年來，我國新能源汽車高速發(fā)展，國家對新能源行業(yè)的大力扶持引發(fā)了鋰電行業(yè)的增長勢頭，為了應對鋰電的迅猛發(fā)展，相應的鋰電物流成長迅速，已經成為鋰電行業(yè)的重要組成部分。自動化立體倉庫作為物流自動化系統(tǒng)的一個核心和樞紐，具有很高的空間利用率和很強的出入庫能力，是物流系統(tǒng)實現物流合理化的關鍵所在。而堆垛機是立體倉庫中的主要搬運設備，由于倉庫的搬運量很大，而堆垛機容量又有限，堆垛機在整個物流周期中的行駛時間占比較大，如果堆垛機的調度不當，會嚴重影響堆垛機的工作效率，進而直接影響立體倉庫的整體效率。因此，堆垛機路徑優(yōu)化顯得尤其重要。

堆垛機路徑優(yōu)化的研究已有很多，馬清[1]等運用啟發(fā)式算法解決以揀貨時間最少為目標的數學模型。劉劍[2]等運用遺傳算法解決立體倉庫堆垛機揀選作業(yè)調度問題，并加入任務等待時間以解決部分任務等待時間過長問題。俞雷霖[3]等提出了一種求解自動化立體倉庫貨位分配與優(yōu)化的混合禁忌搜索算法，實現堆垛機對所有出入庫零件的操作運行距離之和最短。CHANG[4]等為自動化倉庫揀選作業(yè)創(chuàng)建了含裝箱約束條件的多目標優(yōu)化新型數學模型，用遺傳算法對該數學模型進行了求解。DE KOSTER[5]等運用分枝定界法將需要揀選的貨物分為不同批次揀選，依次建立優(yōu)化模型。王小偉[6]等將單巷道雙堆垛機作業(yè)路徑優(yōu)化問題簡化成一個中心點車輛路由問題，并設計最大最小蟻群算法對兩臺堆垛機的作業(yè)路徑進行優(yōu)化。

從目前已有的研究可以看出，堆垛機的路徑優(yōu)化主要分為兩種：一種堆垛機上周轉箱容量較大，一次作業(yè)可以在立體倉庫中對多個貨位進行揀選操作，但不考慮堆垛機在一次作業(yè)中需要同時存取時的問題，王進業(yè)[7]等提出將它轉化為TSP問題進行優(yōu)化求解。另一種堆垛機由于貨物種類不同，一次只能搬取一個托盤單位的貨物，比如立體車庫以及鋰電池等，以托盤等載體完成貨物存取的情況，這種堆垛機存取作業(yè)比較簡單，效率也較低，因此大多采用復合作業(yè)的方式，一次作業(yè)過程中完成貨物的存放和取出，李建國[8]等提出了一種基于遺傳算法的堆垛機路徑優(yōu)化方案來提高立體車庫的整體運行效率。本文以鋰電化成庫為例，鋰電行業(yè)中貨物以托盤為單位，堆垛機一次只能搬運一個托盤的貨物，但鋰電池由于工藝要求一般倉庫規(guī)模較大，對堆垛機效率要求較高，因此不少鋰電庫采用雙工位堆垛機以提高效率。本文主要工作就是對鋰電化成庫中的雙工位堆垛機存取路徑進行優(yōu)化研究。

1 鋰電池化成庫模型

圖1是鋰電化成庫結構圖，它主要由以下幾部分組成：（1）貨架，用于存放電池的貨架，每個貨格一個貨位，每個貨位存放一托盤單位電池，由巷道數、列數和層數決定可以存放電池的數量；（2）堆垛機，運送電池托盤，往返于出入庫口和貨位之間，通過貨叉的伸縮完成貨物的存放與取出；（3）出入庫臺，，出入庫臺與輸送線連接，存放和取出貨物均由出入庫臺進出倉庫；（4）管理控制中心，包括整個立體倉庫的信息、數據處理、監(jiān)控、操作臺等。堆垛機由計算機控制，按照計算機的指令依次對電池進行存取，由于短時間內存取任務較多，出入庫的順序不同，堆垛機所運行的路徑和時間也會不同，合理的作業(yè)路徑能有效提高堆垛機的作業(yè)效率。

圖2鋰電化成庫平面簡化圖，貨位號從出入庫口開始順序順序排列直到倉庫頂層。其運行過程主要依靠堆垛機沿X軸的水平方向和Y軸的垂直方向在巷道中移動到達貨物所在的層列，然后再通過貨叉的橫移動作實現貨物的存取。

圖1 鋰電化成庫結構圖

圖2 立體倉庫貨位表示圖

文中鋰電池化成庫為同端出入庫式，堆垛機以托盤為單位進行搬運，貨架每個貨位只能存放一托盤電池，且倉庫規(guī)模大，搬運量大。堆垛機為雙工位堆垛機，即堆垛機上有兩個工位，最多只能同時有兩個電池托盤在堆垛機上，一次作業(yè)做多完成兩托盤電池的入庫和兩托盤電池的出庫。，雙工位堆垛機進行一次滿載作業(yè)時，如圖3所示，執(zhí)行作業(yè)時堆垛機從出入庫臺O點取電池托盤依次進入A4點存放電池，B4點存或取電池，C4點存或取電池，D4點取電池，最后返回O點將所取電池放置出入庫臺，運出倉庫。所運行的總路程為：

同樣，當存取貨物數量少于4時，堆垛機取貨路徑有以下幾種情況，如圖4所示，搬運不同數量所走的總路程分別為：

2 數學模型

結合雙工位堆垛機實際情況可知，雙工位堆垛機存取貨具有一定的條件限制[9]，即每次最多存兩個貨物取兩個貨物，且當需要存兩個貨物時堆垛機第一個到達的貨物必須為存貨位置；需要取兩個貨物時，堆垛機到達的最后一個貨位必須為取貨位置。固定貨架及堆垛機運行參數作如下設定。

圖4 堆垛機未滿載時作業(yè)方式

設定1：考慮到曲線運動的復雜性，本文貨物在出入庫時是按照直線運動；

設定2：一個巷道只有一臺堆垛機，雙工位堆垛機兩個并排工位在模型中看做一個點存取貨；

設定3：貨位間距為常數，貨格高度為H，貨格寬度為L；

設定4：設入口處為O，坐標為（0,0）；

設定5：堆垛機存取電池，存取任務足夠時優(yōu)先進行復合作業(yè)。

根據模型假設的基本描述，本文模型主要優(yōu)化目標是優(yōu)化堆垛機的作業(yè)路徑，縮短堆垛機搬運總路程，提高出入庫的效率。堆垛機一次作業(yè)要存取的貨物共j個，堆垛機從出入庫臺O（0,0）點取需要存的貨物依次經過第i個作業(yè)貨位i（Xi，Yi），直到到達最后一個作業(yè)貨位j（Xj，Yj）完成操作，最后返回O（0,0）完成一次作業(yè)。一次遍歷j個貨位的存取貨作業(yè)所走的路程為：

在一批存取貨任務中，設存貨任務m個，取貨任務n個

則這批存取貨任務中堆垛機總運行路徑為：

upint為向上取整，完成一批任務的存取作業(yè)，可以對每次存取作業(yè)的路徑進行優(yōu)化，合理安排存取貨位順序，使堆垛機運行總路徑最短。

3 遺傳算法的設計

3.1 染色體編碼設計

模型采用實數編碼方式，染色體信息包括貨位編碼、存取貨需求以及貨位操作順序。編碼[10-11]由兩層組成，上層表示需要存取貨物的貨位編號，下層采用0-1編碼，編號0表示需要存入貨物的貨位，編號1表示需要取出貨物的貨位。編碼方式如下：

1：一條染色體表示一種堆垛機完成一次任務所有貨物存取的路徑。

2：一條染色體可以分為n段，每段代表一個基因，每個基因表示堆垛機一次作業(yè)存取貨的路徑，其中n表示染色體中堆垛機從出庫臺取貨存入倉庫，再從倉庫取出貨物到出庫臺的作業(yè)次數。

3：每段基因由上下兩層組成，上層表示貨位編號，下層表示所對應的貨位存取貨需求，0表示需要存貨，1表示需要取貨。

4：每段基因長度為1-4，最多存在兩個存兩個取，即下層編碼最多兩個1，兩個0；且存在兩個存貨時，第一個編碼必為0，存在兩個取貨時，最后一個編碼必為1。

如圖5所示，堆垛機從出入庫臺搬貨依次進入4號貨位存貨，12號貨位取貨，7號貨位存貨，5號貨位取貨，最后將所取貨物搬回出入庫臺運出立體倉庫，完成一次作業(yè)。然后重新搬取貨物依次進入9號貨位存貨，3號貨位存貨，6號貨位取貨，1號貨位取貨，完成第二次作業(yè)。整條染色體表示一批貨物存取貨路徑方案。

圖5 貨位編碼方式

3.2 種群初始化

初始化種群時，先設置種群規(guī)模為M，然后采用隨機配的方法產生種群[12]，將需要作業(yè)的貨位隨機分配，為了避免產生不可行解，需保證每個基因片段中最多存在兩個存貨貨位與兩個取貨貨位，且存在兩個存貨貨位時第一個必須為存貨貨位，存在兩個取貨貨位時最后一個貨位必須為取貨貨位。

3.3 定義適應度函數

適應度函數[13]用來區(qū)分種群中個體好壞的標準，本文目標是求堆垛機總路程S最小值，因此把函數值的倒數作為個體適應度值，函數值越小，適應度值越大，個體越優(yōu)秀。

3.4 選擇操作

選擇操作就是按照優(yōu)勝劣汰的原則對種群中的基因進行篩選，適應度越高的個體被選中的幾率越大，保證優(yōu)秀基因的延續(xù)。本文采用輪盤賭法，從舊群體中以一定的概率選擇優(yōu)良個體組成新的群體，每個染色體被選中的概率為

3.5 交叉操作

本文采用部分映射雜交，確定交叉操作的父代，將父代樣本兩兩分組，每組進行以下過程：首先，每隔4個貨位劃分一個基因片段，然后從待交配的2個父代中隨機選擇一個基因片段進行交叉，剩余基因片段不變。

交叉后同一個個體中有重復的貨位編號，用*號表示，有沖突的貨位采用部分映射的方法消除沖突，即利用交換片段的貨位碼值對應關系進行映射。交叉操作過程如圖6所示。

3.6 變異操作

變異操作是模擬自然界生物進化中的個體基因突變，目的是為了保持種群多樣性。本文的變異策略為隨機選擇染色體中兩個貨位碼值相同的位置進行對換，如選擇貨位碼值均為1的12和6兩個貨位的位置進行對換，得到變異后的染色體。操作過程如圖7所示。

4 仿真結果與分析

本文采用MATLAB對模型進行仿真，遺傳算法參數設定如下：

貨架每個貨格高度H=460 mm，貨格寬度L= 810 mm。以堆垛機運行的路徑最短為目標進行仿真，選取倉庫一批存取貨任務，12個存貨任務，10個取貨任務，相應貨位編號信息如表2和表3所示。

圖8為堆垛機隨機策略運行軌跡圖，即隨機挑選貨位進行存取貨作業(yè)的運行軌跡圖，堆垛機運行路徑依次為106-78-127-42 65-28-151-91 87-57-21-81110-71-43-178 93-166-140-130 142-174，運行總路程為153019 mm。

圖6 交叉操作

圖7 變異操作Figure

表1 遺傳算法參數選取

Tab.1 Selection of genetic algorithm parameters

表2 存貨信息表

Tab.2 Inventory Information Table

表3 取貨信息表

Tab.3 Pickup Information Table

圖9為堆垛機最鄰策略運行軌跡圖，即隨機選取第一個存貨任務，然后依次選取最鄰近的可作業(yè)貨位進行操作，直至遍歷所有任務貨位的軌跡圖。堆垛機運行路徑依次為87-71-106-140 174-142- 178-127 57-91-93-42 110-78-130-81 43-28-65-21 166-151，運行的總路程為116549 mm。

圖8 隨機策略堆垛機運行軌跡圖

圖9 最鄰策略堆垛機運行軌跡圖

圖10為遺傳算法優(yōu)化后得到的存取貨任務軌跡圖，堆垛機運行路徑依次為142-178-174-140 87-106-71-21 43-42-57-91 151-166-130-127 78-81-65-28 110-93，運行總路程為107232 mm。

圖10 遺傳算法優(yōu)化后堆垛機運行軌跡圖

由以上3張堆垛機運行軌跡圖，可以明顯看出經過遺傳算法改進后的堆垛機存取路徑明顯優(yōu)于隨機存取和最鄰策略存取的路徑。遺傳算法改進后的路徑相比隨機存取路徑減少了29.92%，相比最鄰存取策略路徑減少了7.99%。對比有效驗證了遺傳算法在雙工位堆垛機路徑優(yōu)化的實用性及優(yōu)越性，為雙工位以及多工位堆垛機的路徑優(yōu)化提供一定的參考價值。

5 結語

堆垛機出入庫出入庫效率問題一直是立體倉庫優(yōu)化研究的重點，不同的出入庫方式，不同的出入庫路徑都會對立體倉庫的整體效率產生影響。本文針對鋰電池化成庫的運行特點以及雙工位堆垛機存取貨的特殊性，將遺傳算法應用到雙工位堆垛機存取貨的路徑優(yōu)化中，從仿真結果來看，得到了較好的存取車順序，減少了堆垛機的運行總路程。驗證了遺傳算法在雙工位堆垛機的路徑優(yōu)化問題中的可行性。另外，一些對模型簡化的條件假設會對貨物出入庫效率產生不同影響，這些問題的解決還需要做進一步研究。

[1] 馬清悅, 張紀會, 宋曉鵬, 等. 基于啟發(fā)式算法的自動化立體倉庫揀貨路徑優(yōu)化研究[J]. 青島大學學報, 2012, 27(3): 31-34.

[2] 劉劍, 王鑫, 張冬梅, 等. 基于遺傳算法的立體倉庫堆垛機路徑優(yōu)化[J]. 沈陽建筑大學學報, 2010, 26(5): 1006- 1011.

[3] 俞雷霖, 葉衛(wèi)東, 陸志強. 基于混合禁忌搜索算法的自動化立體倉庫的貨位分配與優(yōu)化研究[J]. 制造業(yè)自動化, 2008.

[4] CHANG Faliang, LIU Zengxiao. Research on order picking optimization problem of automated warehouse[J]. Systems Engineering Theory&Practice, 2007, 27(2): 139-143.

[5] DE KOSTER R, le DUC T, ROODBERGEN K J. Design and control of warehouse order picking: A literature review[J]. European Journal of Operational Research, 2007, 182(2): 481-501.

[6] 王小偉, 張秋菊等. 單巷道雙堆垛機作業(yè)路徑優(yōu)化問題研究[J]. 電子設計工程, 2016, 24(2): 68-75.

[7] 王進業(yè), 宋宇博. 旁通式自動化立體倉庫揀選作業(yè)和出口選擇的組合優(yōu)化[J]. 河北科技大學學報, 2015, 36(1): 36-40.

[8] 李建國, 梁英, 劉日等. 基于遺傳算法的巷道堆垛式立體車庫路徑優(yōu)化[J]. 起重運輸機械, 2016, (12): 59-63.

[9] 趙乃剛. 一種新的基于模擬退火的粒子群算法[J]. 軟件, 2015, 36(7): 1-4.

[10] 聶敬云, 李春青, 李威威, 等. 關于遺傳算法優(yōu)化的最小二乘支持向量機在MBR 仿真預測中的研究[J]. 軟件, 2015, 36(5): 40-44.

[11] 王占中, 趙利英, 曹寧博等. 基于多層編碼遺傳算法的危險品運輸調度模型[J]. 吉林大學學報(工學版), 2017,47(3): 751-755.

[12] 張然, 溫向明, 路兆銘. 基于混合遺傳算法的無線回傳網絡部署[J]. 軟件, 2015, 36(12): 25-30.

[13] 羅辭勇, 盧斌, 劉飛. 一種求解TsP初始化種群問題的鄰域法[J]. 重慶大學學報, 2009, 32(11): 131-1315.

Research on Path Optimization of Double-Station Stacker for Lithium Battery Pe-formation Warehouse

YANG Lie-bing, LV Hong*

(College of mechanical and electrical engineering, Kunming University of Science and Technology Yunnan Kunming 650504)

With the development of the lithium battery industry, lithium battery logistics has become an important part of the lithium battery industry. The Automated Warehouse is the core of lithium battery logistics. As the main handling tool of the Automated Warehouse, the Stacker directly affects the overall efficiency of the Automated Warehouse. This paper takes the lithium battery into a library as an example to study the discharge and stock path of the duble station stacker in the pe-formation warehouse. Combined with the characteristics of double-station stacker accessing goods, a model with the total distance of the stacker running as the goal is proposed, and the genetic algorithm is used to optimize the model. Finally, the simulation results and the optimal neighboring access strategy and random access strategy before optimization are compared. The results show that the genetic algorithm can effectively realize the path optimization of the double-station stacker, which is proved to be a effective method to improve the efficiency of the warehouse.

Lithium battery; Pe-formation warehouse; Double station stacker; Path optimization

TP391.9

A

10.3969/j.issn.1003-6970.2018.10.031

楊烈兵，男，研究生在讀，主要研究方向：人因工程。

呂宏，女，副教授，主要研究方向：企業(yè)集成及信息化工程、人因工程。

楊烈兵，呂宏. 鋰電池化成庫雙工位堆垛機路徑優(yōu)化研究[J]. 軟件，2018，39（10）：164-169