柔性生產線立體庫垛機路徑優化研究

吳佳秜， 王方

（1.成都農業科技職業學院機電技術分院，成都611130；2.四川日機密封件股份有限公司技術部，成都610045）

0 引言

自動化立體倉庫是現代物流以及機械自動化程度較高的企業所配備的大型系統，其運行效率的高低直接影響到企業效益的高低。而衡量立體倉庫運行效率高低的一項重要指標是巷道中垛機的運動路徑的長短。如何優化垛機的運動路徑成為了熱門研究對象。

目前國內外大多自動化立體倉庫是由高度對稱的立體貨架構成，對于這類傳統立體倉庫的貨位優化研究也是比較成熟的。Dranzen等[1]應用遺傳算法解決了基于類存儲系統的AS/RS中的排序問題，進而提高了生產效率。Robert等[2]采取WES（Warehouse Execution System）連接了WCS（Warehouse Control System） 和WMS（Warehouse Management System），使WES不僅僅起到橋梁的作用，還優化了AS/RS中垛機運行時間。曾強等[3]針對自動化立體倉庫有貨位載重約束的貨位分配問題，提出了一種多目標——出庫時間最短、貨架穩定性最高的優化方法。鐘科艾等[4]以某卷煙廠的立體倉庫為研究對象，依據產品周轉率、產品相關性和貨架穩定性來確立具體的優化目標。魏林等[5]通過分類分區的方法實現了整體出入庫效率的提高和各個巷道作業時間的平衡。

一般的立體倉庫有多排貨架，相鄰貨架間由垛機運輸物料，而垛機的出入口一般放置在貨架的一端或者兩端。如果立體倉庫夠高，將按層增加垛機的出入口，以便提高立體倉庫的出入庫效率。但是現實生產應用中，有一些立體倉庫的構造相對特殊，它們跟生產線聯系緊密，特別設置了“緩沖層”以增加立體倉庫與生產線的銜接出入口，使得立體倉庫不再僅僅是由兩端出入口來與生產線連接，如圖1所示。

為提高生產線的生產效率，就必須提高與之聯系緊密的立體倉庫的出入庫效率。目前對這類特殊化構造的立體倉庫的研究很少，而現有一些特殊化的立體倉庫基本按照傳統先進先出的原則簡單地運轉，不僅效率低，而且對于整個生產過程來講，可能導致生產線上加工中心（或員工）待工時間過長，造成資源浪費，成本浪費。

圖1 柔性生產線與立體倉庫示意圖

1 問題描述

1.1 工作流程分析

這類特殊化構造的立體倉庫與柔性生產線聯系緊密，整個柔性生產線的簡單流程圖如圖2所示。

圖2 柔性生產線與立體庫之間流程的簡單示意圖

根據加工中心的工作狀態，來決定立體倉庫垛機的運動。當某加工中心快完成其當前的工序操 作時，該加工中心的工作狀態就被置為“加工中心上料”，立體倉庫垛機接收該信號后，會判斷是哪個加工中心發出的信號，然后再在立體倉庫中找出最近的物料并將它搬運至緩沖層。生產線上的機器人再將物料搬送至加工中心。如此循環，直至該生產任務完成后，關閉柔性生產線。

由此可見，生產任務的大小、加工中心個數及其工作效率、緩沖層貨位的利用均對立體倉庫垛機的運動路徑產生一定影響。

1.2 過程建模及優化策略

1.2.1 假定條件

1）從某時刻開始，立體倉庫及生產線上的所有設備均處于可用狀態；2）立體倉庫不存在物料缺貨情況，物料加工完成后不回庫；3）生產線上加工中心可對任意物料進行加工，而且各個加工中心的工作效率相同。

1.2.2 計算符號

1）當前生產任務清單里包含物料總數M個（種群大小）；2）表示物料m在貨位（i,j,k）上，i為貨架序號，j為層序號，k為列序號，I,J,K分別為各序號最大值；3）Vx表示垛機水平速度；Vy表示垛機垂直速度；Vz表示垛機伸縮速度；單個貨位長度為Lo，高度為Ho。這些屬于立體倉庫的物理構造，其數值都是已知數；4）D（p,q）表示垛機位于第p層的第q列。

1.3 模型建立

簡單以二維平面圖來分析立體倉庫的運動路徑。立體倉庫的二維平面圖如圖3所示，圖中最底層表示“緩沖層”貨位，緩沖層之上為立體倉庫擺放物料的貨位。

假定某次生產任務中物料在如圖4所示貨位平面圖中，其中斜線方框表示該貨位有物料，其余方框表示該貨位沒有物料；圖5為物料搬運方向圖，圖中箭頭表示貨位上的物料搬運方向。

圖3 立體倉庫二維平面圖

圖4 物料貨位平面圖

圖5 物料搬運方向圖

2 算法選用及改進

2.1 算法選用

由簡記的目標函數可以看出，為優化目標函數，盡量使得總運行時間最小，其實質是最小化|p-j|與|q-k|的值，即優化垛機的運動路徑。剝離出運動路徑中的M系列值與D系列的值，不難發現M系列的值類似TSP問題中的城市，D系列的值看作是兩“城市”間必須經過的某個“加油站”，故此類立體倉庫的垛機路徑優化問題屬于NP-hard問題。

由于NP-hard問題的大量實例不能用精確算法求解，即便用目前的高級計算機來窮舉精確算法的結果，也非常耗時，故只能用有效的近似算法求解。而遺傳算法只需要影響搜索方向的目標函數和相應的適應度函數，就能在搜索域內找出近優解。

2.2 算法改進策略

傳統的遺傳算法（Genetic Algorithms,GA）通過“交叉→變異→新種群→選擇”來進行。通常情況下，傳統的遺傳算法只是被看作單個染色體，而且染色體上的遺傳基因采用相同的遺傳算子。

根據基因遺傳學，顯性基因在父代的等位基因完成交叉后，受其影響的表現型必然是顯性的表現型，如人類血型A/B型為顯性，O型為隱性。本文創新性地提出在單染色體的多段基因上，將顯性基因與隱性基因加以區別。將總路徑中D系列的值作為顯性基因，M系列的值作為隱性基因，那么“顯性基因”在經過交叉遺傳時不至于因為相同的遺傳算子而導致早熟（陷入局部最優的困境），“隱性基因”在逐代優化后就趨于穩定。經過N代遺傳后，子代始終具備“顯性基因”的表現型以及將這種“顯性基因”遺傳給下一代的能力。

2.2.1 普通基因的交叉算子與顯性基因的交叉算子

普通基因的交叉算子：在父代染色體上的普通基因段通過簡單的等位基因交叉互換原則，形成子代染色體上的普通基因段。例如將D系列的值按照從右到左（或從左到右）的順序作為普通基因的交叉算子。

顯性基因的交叉算子：在父代染色體上的顯性基因段經過重排列等處理，選出該段基因中最優的基因表達式，遺傳給子代，其顯性基因段在整個染色體上的位置段不變，這樣在子代中就會有更加優質的個體。例如將D系列的值優化順序作為顯性基因的交叉算子。

2.2.2 普通基因的變異算子與顯性基因的變異算子

普通基因的變異算子：遺傳中的基因變異是以某種概率發生的，假定普通遺傳基因發生變異的可能性為pm。普通基因的變異算子為在整個染色體上的位置出現個別基因段對調現象。

顯性基因的變異算子：類似普通基因的變異算子，只是這種變異發生在顯性基因段。在整個染色體上表現為顯性基因段的個別基因對調現象。

2.2.3 形成新的種群

父代染色體經過交叉和變異后，會形成新的完整染色體。而新的染色體會更適應實際工程中的目標優化函數，經過N代遺傳后，子代染色體基因順序趨于某一確定的順序，這個最終穩定的染色體就是前面目標優化函數的最優解或近優解。

2.2.4 選擇

根據適應度來選擇優劣的個體。適應度的表達式可以根據優化目標中的約束條件來自定義，如果違背了約束條件則其適應度就為0，該個體即被淘汰。如果能很好地滿足優化目標的條件，則適應度高，子代個體也就越優質。

適應度函數：

2.3 改進后的遺傳算法步驟

Step 1:按照生產訂單生成任務種群，迭代次數自定義；Step 2:按照種群規模，隨機生成種群的染色體集；Step 3:進入迭代循環；Step 4:在每代中計算各個體的適應度值，當適應度值高于平均值的時候，就評為優秀個體，有進行遺傳子代的資格；Step 5:進行交叉、變異、選擇；Step 6：是否滿足終止條件。

3 模擬仿真結果對比

3.1 實例描述

根據假定條件和符號的定義，參考立體倉庫垛機的物理屬性，設定“計算符號”這節第三點的各符號值，通過VS程序模擬傳統遺傳算法（Traditional GA）和改進后的遺傳算法（Improved GA），算出固定種群100個、隨機種群100個、隨機種群200個、隨機種群300個、隨機種群400個經過這兩種遺傳算法優化后，立體倉庫垛機的總運行時間。

3.2 普通遺傳結果與改進后的遺傳算法結果

其三維柱狀圖如圖6所示。

3.3 對比說明

表1 各種群10次優化前后結果的平均值

固定初始化種群，就好像是某次生產任務里包含立體倉庫中M個物料，即種群大小為M，在立體倉庫貨位是固定的。

普通遺傳算法優化后立體倉庫中垛機的運動路徑為:（1,2）（0,1）（1,3）（0,2）...（1,58）（0,34）（2,1）（0,35）...（2,49）（0,59）（2,51）（0,1）...（7,58）（0,41）。

改進的遺傳算法優化后立體倉庫中垛機的運動路徑為 :（1,2）（0,2）（1,3）（0,3）...（1,58）（0,58）（2,1）（0,1）...（2,49）（0,59）（2,51）（0,51）...（7,58）（0,58）。

經過“顯性基因”的持續優化后，其運動路徑大為減少，垛機的效率大幅提高，從而整條柔性生產線的生產效率也得到提高。隨著種群大小增加，改進的遺傳算法的優化效果更加明顯。

圖6 三維樹狀圖

4 結語

本文考慮到該類特殊化構造的立體倉庫的特點，創新性地提出了基于緩沖策略的“顯性基因”持續優化并遺傳給子代的遺傳算法，經過N代遺傳后，“顯性基因”將突出目標函數“帶出”局部最優的困境。改進后的遺傳算法重點解決了立體倉庫垛機的路徑優化問題，并通過與普通遺傳算法對比，驗證了該算法對垛機的路徑優化有顯著的改善效果。立體倉庫及整條柔性生產線的工作效率均得到大幅度的提高。

結合本文研究結果，下一步的研究工作：1）如果柔性生產線上的物料均在立體倉庫中周轉，即加工中心加工完物料后，物料放回立體倉庫中，那么在該類特殊化構造的立體倉庫中的“緩沖層”需要預留出回庫的貨位；2）加入“創新基因”，在求解工程問題上，通過訓練學習過程，讓機器人等智能設備具備自定義的“創新能力”——發現求解過程中出現的特殊解、異常解等，并能智能規避、解決這些問題。