胡小建, 劉婷婷

(1.合肥工業(yè)大學 管理學院,安徽 合肥 230009; 2.過程優(yōu)化與智能決策教育部重點實驗室,安徽 合肥 230009)

數(shù)字化車間(digital workshop,DS)建設是制造企業(yè)走向智能制造的起點。《中國制造2025》中明確指出:“推進制造過程智能化,在重點領域試點建設智能工廠/數(shù)字化車間。”物料的倉儲和配送是數(shù)字化車間保證生產(chǎn)的重要環(huán)節(jié),兩者密不可分,倉配一體化就是建立一種協(xié)同機制,以倉輔配,以配定倉,優(yōu)化制造流程,降本增效。

現(xiàn)有文獻對物料倉儲與配送問題的研究頗多。在物料配送方面,物料配送路徑優(yōu)化問題是車輛路徑問題(vehiacle routing problem,VRP)[1]的一個經(jīng)典變種問題,文獻[2]考慮車輛負載均衡,用混合多目標進化算法有效減少了總行駛距離;文獻[3]以配送時間和作業(yè)人數(shù)為優(yōu)化目標對該問題進行研究。帶時間窗的車輛路徑優(yōu)化問題(vehicle routing problem with time window,VRPTW)由文獻[4]提出,學者們在此基礎上構建了很多不同的VRPTW優(yōu)化模型,如帶混合時間窗[5]、帶軟時間窗[6]和帶時間窗的同時取送貨的車輛路徑優(yōu)化模型[7]等。針對物料的倉儲問題,數(shù)字化車間一般配備的都是自動化立體倉庫(automated storage and retrieval system,AS/RS),文獻[8]對立庫系統(tǒng)進行了綜述分析；文獻[9]用遺傳算法求解多目標貨位優(yōu)化問題;文獻[10]和文獻[11]建立了多目標優(yōu)化模型,前者考慮出入庫效率和貨架穩(wěn)定性,在算法上使用了病毒協(xié)同遺傳算法,后者考慮物料周轉率和相關性,在算法上使用了基于Pareto保持和模擬退火算法。而在倉配一體化問題上,現(xiàn)有文獻大多針對電商領域,對于制造業(yè)中的生產(chǎn)物流倉配一體化問題的研究相對較少。

本文以安徽博一流體傳動股份有限公司(以下簡稱為BY)的數(shù)字化車間為例,研究生產(chǎn)物料的配送和倉儲一體化問題,結合生產(chǎn)物流的特性提出倉配整體解決方案,先求解數(shù)字化車間工位的配送問題,確定出配送效率最高的配送方案,再基于確定出的配送方案以及數(shù)字化車間的庫位、工位的分布特點建立2層布爾圍道矩陣進行約束,最后采用改進遺傳算法進行求解,得到倉配一體化方案,具有一定的創(chuàng)新性和實際應用價值。

1 數(shù)字化車間倉配一體化方案

本文從配送效率和倉儲效率出發(fā),提出在生產(chǎn)車間內(nèi)部的倉配一體化物流方案。該方案主要分為2個階段：

(1) 配送路徑優(yōu)化。根據(jù)生產(chǎn)訂單要求,采用倒排的方法明確各工位的需求時間窗和需求數(shù)量,保證在時間窗允許的范圍內(nèi)尋找小車配送各工位物料的最優(yōu)方案和最佳配送路徑,確保生產(chǎn)效率不受影響。

(2) 立庫的貨位分配優(yōu)化。根據(jù)配送需求信息,建立物料出庫的時間和順序等約束,在滿足配送需求的情況下以堆垛機運行功率和時間最小為目標尋找物料的最優(yōu)存儲貨位和揀選路徑。該方案將生產(chǎn)物流中的倉儲、配送問題進行關聯(lián),互相約束,使生產(chǎn)物流達到整體最優(yōu)。

1.1 生產(chǎn)物料配送路徑規(guī)劃模型

本文首先建立物料配送路徑規(guī)劃模型,考慮物料配送所需小車數(shù)量和需求時間窗,以此達到配送時間最短的要求,獲取物料出庫的準確時間和順序,此為方案的第1層。

1.1.1 配送路徑規(guī)劃問題描述

數(shù)字化生產(chǎn)車間有緩存物料的立庫1個、小車k輛和裝配工位m個。立庫存儲來自零件庫的齊套物料,物料均以工裝板/周轉箱為單位。在一個配送周期內(nèi),每個工位都有齊套物料配送需求。任意工位的配送任務可以由任一配送工具執(zhí)行且只能配送1次,在配送過程中,通過生產(chǎn)排程可知第i個工位最早接收物料的時間為Ai和最晚接收物料的時間為Bi,即存在1個服務時間窗[Ai,Bi],物料到達工位i的時間必須在時間窗內(nèi),早于或晚于時間窗要求都會給生產(chǎn)進度帶來影響。要求車間在滿足上述約束條件的前提下,將生產(chǎn)物料配送至各個工位,目標是用最短的運行時間滿足生產(chǎn)車間的物料需求,最終形成一條最優(yōu)的物料配送方案。由于實際情況的復雜性和不確定因素,為有效描述該問題,現(xiàn)做如下假設:

(1) 物料配送前明確配送路線和行駛時間,不考慮因漏裝物料導致的往返情況。

(2) 生產(chǎn)計劃是己知的,立庫的物料完全能夠滿足生產(chǎn)現(xiàn)場的生產(chǎn)需求,車間能夠平穩(wěn)連續(xù)地生產(chǎn)。

(3) 各個物料需求點已知且需求量均為齊套物料,且物料需求點的時間窗和初始位置到各工位的移動時間已知,由上文建模計算得出。

(4) 用于配送的小車類型和承載能力相同,保持勻速運動,且一定能承載所有物料。

(5) 物料出庫位置固定,小車初始位置記為S0,為加工車間的工位進行物料配送作業(yè),當小車完成該次配送作業(yè)中的全部任務,會回到初始位置,等待執(zhí)行下一次配送作業(yè)。

1.1.2 配送路徑規(guī)劃模型構建

假設小車勻速運動,速度記為V,清洗時間固定,記為Tw,有k輛配送工具,T為配送工具從立庫初始位置S0到各工位的時間矩陣,si為小車卸貨時間,裝車時間忽略不計,共有q輛配送工具,d為小車k從初始位置的出發(fā)時刻。

目標為最小化物料配送總時間，表示為:

(1)

其中:從左至右依次表示物料從倉儲區(qū)初始位置到工位i的總配送時間、需要清洗的物料的總清洗時間、小車k從工位i到工位j的總配送時間、物料卸貨時間以及配送時間點不在服務時間窗內(nèi)的懲罰時間;yik、xijk、zi為決策變量。當工位i由小車k進行配送時,yik取值為1,否則為0;當小車k由工位i配送到工位j時,xijk取值為1,否則為0;當物料需要清洗時,zi取值為1,否則為0。物料配送到第j個工位的時間點為:

(2)

約束條件如下:

(3)

(4)

(5)

C?D

(6)

Ai≤ti≤Bi

(7)

其中,i=1,2,…,m。

(3)式表示工位i對應的物料且只能由1輛運輸工具運輸;(4)式、(5)式表示運輸工具從起始位置出發(fā)最后回到起始位置;(6)式表示若不能在規(guī)定時間窗內(nèi)配送,則懲罰,C、D分別為早到和遲到的懲罰因子;(7)式表示物料到達工位時間點需在時間窗內(nèi)。

1.2 基于物料配送需求的貨位分配優(yōu)化模型

通過上述物料配送路徑優(yōu)化,即可確定每種物料出庫的順序及時間要求等,以此為基礎利用多色集合理論對貨位分配進行約束,再通過目標函數(shù)優(yōu)化確定貨位分配方案,此為倉配一體化方案的第2層。

1.2.1 物料貨位分配優(yōu)化問題描述

在數(shù)字化生產(chǎn)車間內(nèi)部,立庫往往起到緩存物料的作用。根據(jù)當前生產(chǎn)周期內(nèi)的訂單需求,物料事先齊套完成,進行入庫,并根據(jù)方案第1層產(chǎn)生的物料配送順序和產(chǎn)線實時需求生成出庫任務,堆垛機按照順序進行揀選并送至立庫出口,即上文小車的起始位置S0。單排貨架示意圖如圖1所示。

圖1 單排貨架示意圖

1.2.2 物料貨位分配優(yōu)化模型構建

根據(jù)分巷道存放原則,同類型的貨物均勻分布到每個巷道的2排貨架上,因此,這里只考慮單排貨架,貨架共有S列Q層。立庫中堆垛機水平及豎直方向均保持勻速運動,移動速度分別為V1、V2,水平及豎直方向的移動時間記為T1、T2。每個庫位大小相同,寬為L,高為H。將距離近似為橫縱坐標值,則第a層b列的庫位坐標記為(bL,aH)。g為重力加速度,P為堆垛機牽引功率,堆垛機水平及豎直方向做功分別記為W1、W2,M為物料質量。為了提高立庫運行效率,本文以堆垛機運行時間和能耗為優(yōu)化目標,建立優(yōu)化模型。

最小化堆垛機能耗F1為:

(8)

最小化物料出庫時間F2為:

(9)

約束條件為:

1≤i≤n,i為編號為i的貨位,n為任務單上待揀選的貨位數(shù);

2≤i≤PQ,PQ為貨架上總的貨位數(shù)量。

綜上所述,針對不同的優(yōu)化目標分別建立目標函數(shù),形成了多目標優(yōu)化問題模型。綜合考慮所得的均衡解即為全局最優(yōu)解。

2 求解數(shù)字化車間倉配一體化問題

2.1 算法流程

本文設計了求解數(shù)字化車間倉配一體化問題的兩階段遺傳算法。

第1階段根據(jù)一個生產(chǎn)訂單的需求,通過配送路徑規(guī)劃確定所需小車數(shù)量和物料需求時間窗。

第2階段根據(jù)路徑優(yōu)化結果對立庫作業(yè)進行規(guī)劃,以此優(yōu)化整個生產(chǎn)車間內(nèi)部的倉配問題。算法流程如圖2所示。

圖2 算法流程

2.2 算法設計

2.2.1 第1階段配送路徑遺傳算法

(1) 編碼設計。采用自然數(shù)編碼的方式。假設該生產(chǎn)車間一共有8個工位,分別用0～8來表示物料配送初始位置和各個工位。假設要使用3輛配送工具才能完成配送任務,根據(jù)規(guī)則可知,其中一條染色體可以表示為(0,3,5,0,8,7,2,0,1,4,6,0),子路徑如圖3所示。

圖3 第1階段遺傳算法中的染色體

(2) 初始種群。隨機生成包含1～8且不重復的自然數(shù)排列組合,即是一個基因段,開頭和末尾為0,再把k-1個0隨機加入該數(shù)列中,且0不連續(xù)。這樣就構成1個滿足約束條件的染色體,重復上述步驟直到產(chǎn)生足夠多的染色體。

(3) 適應度函數(shù)設計。將(1)式加1后再取倒,防止正向溢出,即

(10)

(4) 選擇。采用輪盤賭法,每個個體被選擇的概率與其適應度值成正比,然后每次從父代種群中選擇2個個體進入交叉變異操作。

(5) 交叉。本階段采用換位交叉的操作方式。換位交叉可以加速算法的收斂,根據(jù)交叉概率替換群體中的一些染色體,可以避免隨機交叉可能帶來的不良影響,提高群體整體的性能。

(6) 變異。為了提高變異后染色體的多樣性,本文采用旋轉變異的操作方式,在求解過程中克服早熟,避免陷入局部最優(yōu)。

(7) 結束。將得到的子代與父代個體的適應度值進行大小比較并替代。根據(jù)設置的最大迭代次數(shù)直到輸出最優(yōu)解或近似最優(yōu)解為止。

2.2.2 第2階段基于多色集合約束的遺傳算法

(1) 基于約束模型進行染色體編碼。倉配一體化問題的解包含工位所需物料的出庫順序及庫區(qū)的選擇2部分內(nèi)容。為了反映這2個部分,采用基于工位和庫區(qū)的2層編碼方式。

第1層采用基于優(yōu)先權規(guī)則的自然編碼方法。各基因對應的工位按照矩陣M1的行對應的工位的排序依次放置,基因值為優(yōu)先權隨機數(shù)。若有10種物料,則在{1,…,10}中產(chǎn)生不同的隨機數(shù)作為基因，即

(11)

第2層采用實數(shù)編碼,為第1層編碼對應各物料存儲的庫區(qū)。通過搜索矩陣M2獲得基因,各物料的基因從矩陣M2中對應的統(tǒng)一顏色中為1的個人顏色所對應的庫區(qū)編號中隨機獲取,以保證每個基因是有效的。

(12)

(2) 初始種群。按照上面編碼規(guī)則,利用計算機隨機產(chǎn)生初始種群,每個染色體由長度各不重復的基因值組成。這個初始種群經(jīng)過選擇、交叉和變異操作,循環(huán)若干代后得到一個最優(yōu)解。采用以上編碼方式解決上述問題的一種編碼方案見表1所列，即一條染色體。

表1 物料編碼方案示例

(3) 計算適應度。目標函數(shù)分別是求最短時間和最低能耗,均求最小值。選用權重系數(shù)法給各目標函數(shù)賦權將其轉換為單目標問題,先采用極差法去量綱，即

(13)

其中:f為目標函數(shù);fmin、fmax分別為目標函數(shù)的最小值和最大值。2個目標函數(shù)通過轉換后分別記為f1′、f2′,完成去量綱操作;再主觀賦權,系數(shù)均為0.5,因此,組合后的單目標函數(shù)為:

minF3=0.5f1′+0.5f2′

(14)

為防止正向溢出對目標函數(shù)加1后再取倒作為適應度函數(shù)。本文的加權重系數(shù)后的單目標適應度函數(shù)為:

(15)

(4)選擇、交叉、變異。根據(jù)適應度值大小在父種群中選擇特定數(shù)量的個體遺傳到下一代子種群進行交叉和變異操作。交叉和變異算子分別采用循環(huán)交叉算法和換序變異算法,自適應交叉概率c及變異概率d計算公式如下:

(16)

(17)

其中,c1、c2、d1、d2為常數(shù)。

(5) 結束。設置遺傳代數(shù),當達到設置的遺傳代數(shù)則終止算法。

3 算例與結果分析

3.1 配送路徑規(guī)劃算例求解

本文以BY數(shù)字化生產(chǎn)車間為例,根據(jù)上文提出的第1層遺傳算法解決路徑最優(yōu)問題。根據(jù)實地調(diào)研,已知該車間有1個立庫、8個工位,清洗時間Tw固定為1 min,裝貨時間忽略不計,卸貨時間si固定為1.5 min,早到懲罰因子的取值為60 min,遲到懲罰因子的取值為90 min,8個工位對應的時間窗分別為[0,6]、[3,6]、[5,8]、[2,6]、[3,9]、[6,9]、[6,12]、[5,13]。初始位置至工位及工位間配送時間見表2所列。

將表2中數(shù)據(jù)代入模型,設置如下遺傳算法參數(shù):初始種群大小為50,交叉概率為0.9,變異概率為0.1。將上述參數(shù)分別代入Matlab程序中,經(jīng)多次實驗,確定遺傳迭代次數(shù)為200次。

表2 初始位置至工位及工位間配送時間 單位:min

為了確定運輸工具數(shù)量k,本文在編程時分別考慮了1～3輛車的情況,優(yōu)化及迭代過程如圖4所示。

圖4 物料配送路徑優(yōu)化及迭代過程

輸出路徑方案見表3所列。

表3 路徑方案

由此可以看出,1輛車無法滿足產(chǎn)線需求,3輛車不僅固定成本高,時間上也不是最優(yōu)的,啟用2輛小車的結果是最優(yōu)的。最小配送時間為24.5 min,對應染色體為(0,2,8,7,6,5, 0,1,3,4,0), 經(jīng)過解碼,得到配送路徑如下:

k1:m2→m8→m7→m6→m5;

k2:m1→m3→m4。

3.2 基于配送需求約束的貨位分配算例求解

根據(jù)實地調(diào)研,BY數(shù)字化生產(chǎn)車間立庫分為6個庫區(qū),共計140個庫位,每個庫區(qū)可存儲的物料不同,實際的物料可存儲庫區(qū)情況及庫區(qū)的出庫時間，見表4所列。

表4 工位存儲庫區(qū)和出庫時間

假設某批次的出庫任務需要從6個庫區(qū)中的16個貨位(不包括I/O)里揀選貨物。再根據(jù)第2階段的數(shù)學模型求解結果,可知物料的出庫順序如下:21-81-71-61-51-11-31-41-22-82-72-62-52-12-32-42。

依據(jù)該順序選擇庫區(qū)進行編碼,建立約束并且基于該約束的模型進行求解算法的選擇和設計。假設數(shù)字化車間立體倉庫中堆垛機的水平行走速度為V1=60 m/min,垂直提升速度為V2=40 m/min,每個貨位的寬度L=0.8 m,高度H=0.56 m,堆垛機能耗P=200 kW,g=9.8 m/s2,M=2 kg。以布爾圍道矩陣中的約束為依據(jù),對物料的貨位分配及堆垛機的揀選路徑進行規(guī)劃,設I/O的編號為1,坐標為(0,1)。設置遺傳算法的參數(shù):初始種群大小為50,染色體長度為17;自適應交叉概率常量c1設為0.3,c2設為0.7,自適應變異概率常量d1設為0.01,d2為0.05。將上述參數(shù)分別帶入Matlab程序中,經(jīng)多次實驗,確定遺傳迭代次數(shù)為500次。

以多目標最優(yōu)為目標,算法在搜索過程中每代的最優(yōu)解以及種群均值的跟蹤圖如圖5所示。

圖5 目標最優(yōu)解和種群均值跟蹤圖

可以看出,遺傳算法對該目標結果有較好的優(yōu)化結果,最優(yōu)目標函數(shù)值從優(yōu)化前的0.272 9,經(jīng)過優(yōu)化后降到0.131 0,下降了約52%,表明方法是有效的,保證配送需求的同時提高了立庫作業(yè)效率和運行成本,優(yōu)化后的貨位分配和揀貨路徑情況，見表5所列。

表5 貨位分配結果

本部分采用基于約束模型的遺傳算法求解方式運行10次，與傳統(tǒng)遺傳算法對比結果見表6所列。由表6可知,本文基于多色集合約束的遺傳算法有效加快了收斂速度。

表6 改進的遺傳算法效果對比

4 結 論

本文提出了BY數(shù)字化生產(chǎn)車間倉配一體化方案,構建了針對配送路徑和貨位分配2個層次的模型,將生產(chǎn)車間內(nèi)部倉儲和配送作業(yè)聯(lián)動,滿足物料準時配送的要求且使得配送路徑最短、貨位分配最優(yōu)。本文的主要貢獻如下:① 設計了基于多色集合約束的兩階段遺傳算法進行求解,通過多色集合理論將配送需求作為約束來影響貨位分配,使倉儲和配送有機融合,互相影響;② 通過Matlab仿真驗證了模型和算法的有效性,并結合BY公司的實際算例給出了整體的優(yōu)化方案,有效提高了配送和倉儲效率,降低了生產(chǎn)物流成本。本文的方案不僅對BY公司適用,對其他制造業(yè)的生產(chǎn)車間物流優(yōu)化也有一定的借鑒意義。

本文考慮的主要是流水線加工方式,對離散型生產(chǎn)車間的優(yōu)化還需要進一步探索,且本文考慮的工位數(shù)及物料數(shù)量都很有限,對大規(guī)模倉配一體化的生產(chǎn)車間是否適用還需要進一步驗證。