柔性生產(chǎn)線立體庫垛機路徑優(yōu)化研究
2020-3-3 來源： 成都農(nóng)業(yè)科技機電分院 .四川日機密封件 作者：吳佳 王方
摘要：隨著柔性制造系統(tǒng)的不斷發(fā)展，在其制造生產(chǎn)線上配備自動化立體倉庫可以減少生產(chǎn)線上物料的搬運時間，進而提高整條生產(chǎn)線的生產(chǎn)效率。自動化立體倉庫作為柔性生產(chǎn)線的重要環(huán)節(jié)，其自身的工作效率將直接影響到整條柔性生產(chǎn)線的工作效率，故優(yōu)化自動化立體倉庫垛機的路徑成為一個研究熱點。針對某類具備“緩沖層”的自動化立體倉庫，基于緩沖策略，提出了改進的遺傳算法來優(yōu)化垛機路徑。“緩沖層”起到過渡作用，減少柔性生產(chǎn)線上加工中心的待工時間。通過VS程序仿真，驗證了該算法的可行性，實現(xiàn)了立體倉庫中垛機的運動路徑優(yōu)化。
關(guān)鍵詞：自動化立體倉庫；緩沖策略；遺傳算法；路徑優(yōu)化
0 引 言
自動化立體倉庫是現(xiàn)代物流以及機械自動化程度較高的企業(yè)所配備的大型系統(tǒng)，其運行效率的高低直接影響到企業(yè)效益的高低。而衡量立體倉庫運行效率高低的一項重要指標(biāo)是巷道中垛機的運動路徑的長短。如何優(yōu)化垛機的運動路徑成為了熱門研究對象。
目前國內(nèi)外大多自動化立體倉庫是由高度對稱的立體貨架構(gòu)成，對于這類傳統(tǒng)立體倉庫的貨位優(yōu)化研究也是比較成熟的。Dranzen等[1]應(yīng)用遺傳算法解決了基于類存儲系統(tǒng)的AS/RS中的排序問題，進而提高了生產(chǎn)效率。Robert等[2]采取WES（Warehouse Execution System）連接了WCS （Warehouse Control System ） 和 WMS（WarehouseManagement System），使WES不僅僅起到橋梁的作用，還優(yōu)化了AS/RS中垛機運行時間。曾強等[3]針對自動化立體倉庫有貨位載重約束的貨位分配問題，提出了一種多目標(biāo)———出庫時間最短、貨架穩(wěn)定性最高的優(yōu)化方法。鐘科艾等[4]以某卷煙廠的立體倉庫為研究對象，依據(jù)產(chǎn)品周轉(zhuǎn)率、產(chǎn)品相關(guān)性和貨架穩(wěn)定性來確立具體的優(yōu)化目標(biāo)。魏林等[5]通過分類分區(qū)的方法實現(xiàn)了整體出入庫效率的提高和各個巷道作業(yè)時間的平衡。
一般的立體倉庫有多排貨架，相鄰貨架間由垛機運輸物料，而垛機的出入口一般放置在貨架的一端或者兩端。如果立體倉庫夠高，將按層增加垛機的出入口，以便提高立體倉庫的出入庫效率。但是現(xiàn)實生產(chǎn)應(yīng)用中，有一些立體倉庫的構(gòu)造相對特殊，它們跟生產(chǎn)線聯(lián)系緊密，特別設(shè)置了“緩沖層”以增加立體倉庫與生產(chǎn)線的銜接出入口，使得立體倉庫不再僅僅是由兩端出入口來與生產(chǎn)線連接，如圖1所示
圖 1 柔性生產(chǎn)線與立體倉庫示意圖
1.垛機 2．立體倉庫 3．緩沖層 4．加工中心5．機器人導(dǎo)軌 6．機器人
為提 高 生產(chǎn)線的生產(chǎn)效率，就必須提高與之聯(lián)系緊密的立體倉庫的出入庫效率。目前對這類特殊化構(gòu)造的立體倉庫的研究很少，而現(xiàn)有一些特殊化的立體倉庫基本按照傳統(tǒng)先進先出的原則簡單地運轉(zhuǎn)，不僅效率低，而且對于整個生產(chǎn)過程來講，可能導(dǎo)致生產(chǎn)線上加工中心（或員工）待工時間過長，造成資源浪費，成本浪費。
1、 問題描述
1.1 工作流程分析
這類特殊化構(gòu)造的立體倉庫與柔性生產(chǎn)線聯(lián)系緊密，整個柔性生產(chǎn)線的簡單流程圖如圖2所示。
圖2 柔性生產(chǎn)線與立體庫之間流程的簡單示意圖
根據(jù)加工中心的工作狀態(tài) ，來決定立體倉庫垛機的運動 。 加工中心快完成其當(dāng)前的工序操作時 ，該加工中心的工作狀態(tài)就被 置為 “ 加工 中 心上料”，立體倉庫垛機接收該信號后，會判斷是哪個加工中心發(fā)出的信號，然后再在立體倉庫中找出最近的物料并將它搬運至緩沖層。生產(chǎn)線上的機器人再將物料搬送至加工中心。如此循環(huán)，直至該生產(chǎn)任務(wù)完成后，關(guān)閉柔性生產(chǎn)線。
由此可見，生產(chǎn)任務(wù)的大小、加工中心個數(shù)及其工作效率、緩沖層貨位的利用均對立體倉庫垛機的運動路徑產(chǎn)生一定影響。
1.2 過程建模及優(yōu)化策略
1.2.1 假定條件
1）從某時刻開始，立體倉庫及生產(chǎn)線上的所有設(shè)備均處于可用狀態(tài)；2）立體倉庫不存在物料缺貨情況，物料加工完成后不回庫；3） 生產(chǎn)線上加工中心可對任意物料進行加工，而且各個加工中心的工作效率相同。
1.2.2 計算符號
1） 當(dāng)前生產(chǎn)任務(wù)清單里包含物料總數(shù)M個（種群大小）；2）Mm（i,j,k）表示物料m在貨位（i,j,k）上，i為貨架序號，j為層序號，k為列序號，I,J,K分別為各序號最大值；3）Vx表示垛機水平速度；Vy表示垛機垂直速度；Vz表示垛機伸縮速度；單個貨位長度為Lo，高度為Ho。這些屬于立體倉庫的物理構(gòu)造，其數(shù)值都是已知數(shù)；4）D（p,q）表示垛機位于第p層的第q列。
圖3 立體倉庫二維平面圖
圖4 物料貨位平面圖
圖5 物料搬運方向圖
1.3 模型建立
簡單以二維平面圖來分析立體倉庫的運動路徑。立體倉庫的二維平面圖如圖3所示，圖中最底層表示“緩沖層”貨位，緩沖層之上為立體倉庫擺放物料的貨位。假定某次生產(chǎn)任務(wù)中物料在如圖4所示貨位平面圖中，其中斜線方框表示該貨位有物料，其余方框表示該貨位沒有物料；圖5為物料搬運方向圖，圖中箭頭表示貨位上的物料搬運方向。某物料Mm（i,j,k）經(jīng)立體倉庫垛機搬運至緩沖層Dm（p,q）的時間記為Tm，即單次搬運時間，等于物料所在貨位與緩沖層目標(biāo)貨位之間的水平與垂直運動時間的最大值，
2 、算法選用及改進
2.1 算法選用
由簡記的目標(biāo)函數(shù)可以看出，為優(yōu)化目標(biāo)函數(shù)，盡量使得總運行時間最小，其實質(zhì)是最小化|p-j|與|q-k|的值，即優(yōu)化垛機的運動路徑。剝離出運動路徑中的M系列值與D系列的值，不難發(fā)現(xiàn)M系列的值類似TSP問題中的城市，D系列的值看作是兩“城市”間必須經(jīng)過的某個“加油站”，故此類立體倉庫的垛機路徑優(yōu)化問題屬于NP-hard問題。
由于NP-hard問題的大量實例不能用精確算法求解，即便用目前的高級計算機來窮舉精確算法的結(jié)果，也非常耗時，故只能用有效的近似算法求解。而遺傳算法只需要影響搜索方向的目標(biāo)函數(shù)和相應(yīng)的適應(yīng)度函數(shù)，就能在搜索域內(nèi)找出近優(yōu)解。
2.2 算法改進策略
傳統(tǒng)的遺傳算法（Genetic Algorithms, GA）通過“交叉→變異→新種群→選擇”來進行。通常情況下，傳統(tǒng)的遺傳算法只是被看作單個染色體，而且染色體上的遺傳基因采用相同的遺傳算子。
根據(jù)基因遺傳學(xué)，顯性基因在父代的等位基因完成交叉后，受其影響的表現(xiàn)型必然是顯性的表現(xiàn)型，如人類血型A/B型為顯性，O型為隱性。本文創(chuàng)新性地提出在單染色體的多段基因上，將顯性基因與隱性基因加以區(qū)別。將總路徑中D系列的值作為顯性基因，M系列的值作為隱性基因，那么“顯性基因”在經(jīng)過交叉遺傳時不至于因為相同的遺傳算子而導(dǎo)致早熟（陷入局部最優(yōu)的困境），“隱性基因”在逐代優(yōu)化后就趨于穩(wěn)定。經(jīng)過N代遺傳后，子代始終具備“顯性基因”的表現(xiàn)型以及將這種“顯性基因”遺傳給下一代的能力。
2.2.1 普通基因的交叉算子與顯性基因的交叉算子
普通基因的交叉算子：在父代染色體上的普通基因段通過簡單的等位基因交叉互換原則，形成子代染色體上的普通基因段。例如將D系列的值按照從右到左（或從左到右）的順序作為普通基因的交叉算子。顯性基因的交叉算子：在父代染色體上的顯性基因段經(jīng)過重排列等處理，選出該段基因中最優(yōu)的基因表達式，遺傳給子代，其顯性基因段在整個染色體上的位置段不變，這樣在子代中就會有更加優(yōu)質(zhì)的個體。例如將D系列的值優(yōu)化順序作為顯性基因的交叉算子。
2.2.2 普通基因的變異算子與顯性基因的變異算子
普通基因的變異算子：遺傳中的基因變異是以某種概率發(fā)生的，假定普通遺傳基因發(fā)生變異的可能性為pm。普通基因的變異算子為在整個染色體上的位置出現(xiàn)個別基因段對調(diào)現(xiàn)象。
顯性基因的變異算子：類似普通基因的變異算子，只是這種變異發(fā)生在顯性基因段。在整個染色體上表現(xiàn)為顯性基因段的個別基因?qū)φ{(diào)現(xiàn)象。
2.2.3 形成新的種群
父代染色體經(jīng)過交叉和變異后，會形成新的完整染色體。而新的染色體會更適應(yīng)實際工程中的目標(biāo)優(yōu)化函數(shù)，經(jīng)過N代遺傳后，子代染色體基因順序趨于某一確定的順序，這個最終穩(wěn)定的染色體就是前面目標(biāo)優(yōu)化函數(shù)的最優(yōu)解或近優(yōu)解。
2.2.4 選擇
根據(jù)適應(yīng)度來選擇優(yōu)劣的個體。適應(yīng)度的表達式可以根據(jù)優(yōu)化目標(biāo)中的約束條件來自定義，如果違背了約束條件則其適應(yīng)度就為0，該個體即被淘汰。如果能很好地滿足優(yōu)化目標(biāo)的條件，則適應(yīng)度高，子代個體也就越優(yōu)質(zhì)。
適應(yīng)度函數(shù)：
2.3 改進后的遺傳算法步驟
Step 1: 按照生產(chǎn)訂單生成任務(wù)種群，迭代次數(shù)自定義；Step 2: 按照種群規(guī)模，隨機生成種群的染色體集；Step 3: 進入迭代循環(huán)；Step 4: 在每代中計算各個體的適應(yīng)度值，當(dāng)適應(yīng)度值高于平均值的時候，就評為優(yōu)秀個體，有進行遺傳子代的資格；Step 5: 進行交叉、變異、選擇；Step 6：是否滿足終止條件。
3 、模擬仿真結(jié)果對比
3.1 實例描述
根據(jù)假定條件和符號的定義，參考立體倉庫垛機的物理屬性，設(shè)定“計算符號”這節(jié)第三點的各符號值，通過VS程序模擬傳統(tǒng)遺傳算法（Traditional GA）和改進后的遺傳算法（Improved GA），算出固定種群100個、隨機種群100個、隨機種群200個、隨機種群300個、隨機種群400個經(jīng)過這兩種遺傳算法優(yōu)化后，立體倉庫垛機的總運行時間。
3.2 普通遺傳結(jié)果與改進后的遺傳算法結(jié)果
其三維柱狀圖如圖6所示。
圖6 三維樹狀圖
3.3 對比說明
表1 各種群10次優(yōu)化前后結(jié)果的平均值
固定初始化種群，就好像是某次生產(chǎn)任務(wù)里包含立體倉庫中M個物料，即種群大小為M，在立體倉庫貨位是固定的。普通遺傳算法優(yōu)化后立體倉庫中垛機的運動路徑為:（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）。改進的遺傳算法優(yōu)化后立體倉庫中垛機的運動路徑為 :（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）。經(jīng)過“顯性基因”的持續(xù)優(yōu)化后，其運動路徑大為減少，垛機的效率大幅提高，從而整條柔性生產(chǎn)線的生產(chǎn)效率也得到提高。隨著種群大小增加，改進的遺傳算法的優(yōu)化效果更加明顯。
4、 結(jié) 語
本文考慮到該類特殊化構(gòu)造的立體倉庫的特點，創(chuàng)新性地提出了基于緩沖策略的“顯性基因”持續(xù)優(yōu)化并遺傳給子代的遺傳算法，經(jīng)過N代遺傳后，“顯性基因”將突出目標(biāo)函數(shù)“帶出”局部最優(yōu)的困境。改進后的遺傳算法重點解決了立體倉庫垛機的路徑優(yōu)化問題，并通過與普通遺傳算法對比，驗證了該算法對垛機的路徑優(yōu)化有顯著的改善效果。立體倉庫及整條柔性生產(chǎn)線的工作效率均得到大幅度的提高。
結(jié)合本文研究結(jié)果，下一步的研究工作：1）如果柔性生產(chǎn)線上的物料均在立體倉庫中周轉(zhuǎn)，即加工中心加工完物料后，物料放回立體倉庫中，那么在該類特殊化構(gòu)造的立體倉庫中的“緩沖層”需要預(yù)留出回庫的貨位；2）加入“創(chuàng)新基因”，在求解工程問題上，通過訓(xùn)練學(xué)習(xí)過程，讓機器人等智能設(shè)備具備自定義的“創(chuàng)新能力”———發(fā)現(xiàn)求解過程中出現(xiàn)的特殊解、異常解等，并能智能規(guī)避、解決這些問題。
投稿箱：
如果您有機床行業(yè)、企業(yè)相關(guān)新聞稿件發(fā)表，或進行資訊合作，歡迎聯(lián)系本網(wǎng)編輯部， 郵箱：skjcsc@vip.sina.com
如果您有機床行業(yè)、企業(yè)相關(guān)新聞稿件發(fā)表，或進行資訊合作，歡迎聯(lián)系本網(wǎng)編輯部， 郵箱：skjcsc@vip.sina.com
更多相關(guān)信息
業(yè)界視點
| 更多
行業(yè)數(shù)據(jù)
| 更多
- 2025年5月 新能源汽車銷量情況
- 2025年5月 新能源汽車產(chǎn)量數(shù)據(jù)
- 2025年5月 基本型乘用車（轎車）產(chǎn)量數(shù)據(jù)
- 2025年5月 軸承出口情況
- 2025年5月 分地區(qū)金屬切削機床產(chǎn)量數(shù)據(jù)
- 2025年5月 金屬切削機床產(chǎn)量數(shù)據(jù)
- 2025年4月 新能源汽車銷量情況
- 2025年4月 新能源汽車產(chǎn)量數(shù)據(jù)
- 2025年4月 基本型乘用車（轎車）產(chǎn)量數(shù)據(jù)
- 2025年4月 軸承出口情況
- 2025年4月 分地區(qū)金屬切削機床產(chǎn)量數(shù)據(jù)
- 2025年4月 金屬切削機床產(chǎn)量數(shù)據(jù)
- 2025年1月 新能源汽車銷量情況