考慮工位優先級的智能車間雙向物料配送路徑規劃*

童傅嬌,徐 進,張守京

(西安工程大學 機電工程學院,陜西 西安 710048)

0 引 言

車間物料配送路徑優化問題是指在一定條件約束下,按照工位物料需求規劃小車的配送路徑,使其按照規劃路徑進行物料配送,并達到一定的優化目標。隨著互聯網與傳統產業的融合發展,機械車間高度靈活的個性化和數字化的產品與服務的生產模式已逐漸取代傳統生產模式。生產模式的不斷變化,在一定程度上使得機械車間環境更為復雜,生產物流的流暢性難以保證。同時,由于機械車間內各類不確定問題頻繁發生,物料配送方案對實際工況的適應程度大大降低[1，2]。針對上述問題,國內外學者對該問題的各類影響因素進行了大量的研究。

如在準時制配送方面,不少學者考慮了以配送時間窗為約束[3],如采用混合時間窗[4]、模糊軟時間窗[5]、正態模糊隸屬度[6]等來表示工位的滿意度。在不確定因素方面,蔣增強等人[7]針對不確定環境下的物料配送問題設計了動態周期的物料配送策略。ALNAHHAL M等人[8]考慮機器故障、停線、產品報廢等生產線不確定因素,提出了一種動態配送策略。李思國等人[9]對離散制造車間的實時物料配送路徑進行了優化。在多目標優化方面,劉愛軍等人[10]考慮到柔性車間中存在的動態多目標問題,提出了基于事件驅動和循環驅動的混合重調度策略。夏揚坤等人[11]以配送總成本和小車數量為優化目標,建立了求解配送路徑規劃問題的數學模型。WANG H F等人[12]以總成本最小和車輛數最少為目標,通過建立相應模型進行了求解。在對車間物料循環配送、回收方面,周蓉等人[13]提出了車輛裝卸一體化路徑問題。張守京等人[14]在分析車間物料循環的基礎上,提出了一種車間物料配送與余廢料回收協同的路徑優化方法。在求解算法方面,多以群智能算法為主,局部鄰域搜索算法使用較少。BANOS R等人[15]在車輛行駛路徑長度和車輛負載兩個方面進行了綜合權衡,以構建問題模型,并采用改進的多目標遺傳算法對模型進行了求解。孫寶鳳等人[16]針對動態取送路徑下的各種實時信息傳遞對問題的作用和影響,設計了禁忌搜索算法以對模型進行求解。LI Guang-qiang等人[17]提出了通過改進的AFSA對路徑規劃問題進行求解,并驗證了算法的有效性。

通過對上述文獻的研究及對機械車間現狀的分析基礎上,筆者總結出目前機械車間物料配送仍存在以下問題:

(1)配送時間未滿足工位需求時間要求,工位服務滿意度較低;

(2)物料配送多以單向需求配送為主,未考慮將回收與需求協同規劃;

(3)當出現緊急訂單、催單、撤單等現象時,未考慮按照工位物料需求緊急度,對工位進行配送。

針對上述問題,筆者提出一種考慮工位優先級的車間雙向物料配送策略,同時以物料配送總成本最小為優化目標建立數學模型,并借用遺傳禁忌搜索混合算法對問題進行求解,最后通過仿真實驗證明混合算法的有效性。

1 問題描述與模型建立

1.1 問題描述

考慮工位優先級及車間雙向物料配送路徑優化問題是指在滿足自動引導小車(automatic guided vehicle,AGV)裝載量、時間窗約束等限制條件下,車間物料配送在考慮工位優先級及車間雙向物料配送情況下實現AGV配送路徑最優、工位滿意度最高及總成本最低。其中,工位優先級是指當出現生產擾動如緊急訂單、催單、撤單等現象時,工位之間對物料的需求緊急程度不一,服務緊急訂單和催單的工位對物料的需求更為迫切,因此需要先對這些工位進行配送。而對于撤單的工位,可以延后對這些工位的物料配送。上述生產擾動對工位物料配送緊急程度造成一定影響,即對工位配送時間有更急迫或緩和的需求。因此，筆者以工位最佳配送時間作為工位配送優先級的參數,工位最佳配送時間越小則工位優先級更高;車間雙向物料配送是指在給工位配送物料時,同時將工位的成品進行轉運和余廢料的回收,形成雙向物料流的物料配送模式。

考慮工位優先級及車間雙向物料配送的配送策略示意圖如圖1所示。

圖1 配送策略示意圖

配送小車裝載工位需求的物料從配送中心出發對工位進行服務,工位上的數字代表小車服務順序,該順序按照工位優先級進行排序,在對各工位進行配送服務的同時,以“先卸后裝”的方式將工位產生的成品及余廢料轉運與回收。

其問題約束如下:

(1)加工車間內只有一個配送中心0,且小車的起止點均為配送中心;

(2)配送小車k均相同,小車最大載重Q、最大路程等信息已知,車輛數量K能滿足所有客戶點需求。小車行駛速度v恒定;

(3)小車按照“先配送后回收”的順序對N個工位進行服務,即對于既有物料需求,又有成品轉運或余廢料回收的雙向需求工位,按照先物料卸載,后成品轉運或余廢料回收的裝載順序進行服務;而對于只有物料需求或成品裝運、余廢料回收的單向需求工位,直接進行服務。上述任務均需滿足小車容量限制;

(4)車間內工位物料需求信息、工位優先級、配送中心與工位坐標均已知,配送路徑中所有節點可互相連通;

(5)工位配送滿足時間窗約束,違反時間窗約束則設置懲罰。

1.2 模型建立

根據以上論述,考慮工位優先級及車間雙向物料配送路徑優化模型表示如下:

(1)

(2)

(3)

pi+si≤qi,?i∈N；

(4)

(5)

x0ik=xi0k,?i∈N,?k∈K;

(6)

(7)

(8)

xijk、xik、yik∈{0,1}.

(9)

式中:C—總配送成本;qi—工位i的物料需求量;pi—工位i的成品轉運量;si—工位i的余廢料回收量;dij—工位i與j之間的曼哈頓距離;d0i—配送中心到工位i的距離;ci—工位i的時間窗懲罰成本;t—小車到達工位時間;RTi—工位i可接受的最早配送時間;LTi—工位i可接受的最晚配送時間;Ii,Ij—工位i,j的優先級參數;u—車輛單次派遣成本;λ—每千米運輸成本;α—物料早到工位的懲罰因子;β—物料晚到工位的懲罰因子;i,j—工位編號;x,y—關聯系數。

模型中,目標函數式(1)表示AGV配送總成本最小,其中包括AGV派遣成本,配送距離成本,時間窗懲罰成本;約束式(2)表示每輛小車的裝載容量不能超過小車最大裝載量;約束式(3)表示每個工位只被服務1次且僅有1輛小車執行任務;約束式(4)表示任一工位的回收量及轉運量不超過該工位的需求量;約束式(5)表示到達工位和離開工位的小車相同;約束式(6)表示所有車輛均從原配送中心出發并最終全部返回原配送中心;約束式(7)表示小車按照工位的優先級進行配送,對于任意工位i與j,若工位i的優先級大于工位j,即工位i的最佳配送時間小于工位j時,優先執行工位i的任務;約束式(8)為時間窗約束,物料在時間窗外送達工位將進行懲罰;約束式(9)為決策變量屬性。

2 模型求解

遺傳算法(genetic algorithm,GA)在解決物料配送路徑優化問題具有一定優勢[18，19],雖然目前禁忌搜索算法(tabu search algorithm,TSA)在解決物料配送路徑優化問題中使用較少,但TSA在該類型問題表現的有效性已被許多研究證明[20,21]。因此,筆者在已有的研究基礎上,采用遺傳禁忌混合算法(genetic taboo hybrid algorithm,GTHA)對所述模型進行求解,具體求解過程如下。

2.1 遺傳算法設計

針對本文出現的配送車輛容量約束問題,物料配送無法一次完成,而需要多車輛同時配送的情況,編碼需要更直觀地體現各車輛的配送路徑,所以筆者采用自然數編碼。染色體編碼結構如下:

0,Ni1,Ni2,...,Nio,0,Nj1,Nj2,...,Njp,0,Nk1,Nk2,...,Nkq,0...

其中:Nkq—第k輛車的第q個配送任務是為工位點Nkq進行物料配送及回收;0—配送中心。

由3輛車對工位進行物料配送的染色體編碼示意圖如圖2所示。

022*55*77*0166*99*33*44*88*0

圖2中帶有*號的工位表示該工位有成品轉運或物料回收需求,則小車1的配送路徑為0-2-2*-5-5*-7-7*-0,小車2的配送路徑為0-1-6-6*-9-9*-3-3*-0,小車3的配送路徑為0-4-4*-8-8*-0。

2.1.1 確定初始種群

采用隨機生成100條染色體的方式確定初始種群,初始種群中編號為[1～N],由于存在裝載容量的約束,需對初始種群中的每條染色體所包含的工位進行車輛分配,以確定每條路徑所包含的工位。初始種群染色體車輛分配步驟如下:

(1)隨機選取100條染色體中的一條染色體個體;

(2)首先對該染色體所包含的工位按照工位優先級進行排序,即每個小車優先配送優先級高的工位;

(3)然后按照車輛的裝載能力將染色體上的工位分配給小車,達到小車的裝載能力后,將剩下的工位分別給另一輛小車。以此方式,完成該染色體上的工位分配;

(4)重復上述操作,直到達到初始種群規模。

2.1.2 適應度函數

以總成本的倒數作為適應度函數的評價值,表示為成本越低的種群個體適應度越好:

(10)

2.1.3 選擇操作

選擇操作是將精英保留策略與輪盤賭選擇相互結合。首先保留適應度最大的個體,即精英個體,剩余個體采用輪盤賭法進行篩選。

2.1.4 交叉操作

筆者選擇部分匹配交叉算子,以概率Pc選擇個體。交叉操作示意圖如圖3所示。

2.1.5 變異操作

筆者選擇交換變異法進行變異操作,以變異概率Pm選擇個體。變異操作示意圖如圖4所示。

圖3 交叉操作示意圖

圖4 變異操作示意圖

遺傳算法具有較強的全局搜索特性,但易提前收斂,結合TSA算法較強的局部搜索特性,筆者在遺傳算法逐漸收斂時引入禁忌搜索算法,對求解結果進行二次優化。

2.2 禁忌搜索算法設計

禁忌搜索算法的思想為:

(1)以遺傳算法收斂時的求解結果作為禁忌搜索算法的初始解,通過遍歷所有工位,將工位從當前路徑移除,然后依次插入到其他路徑的可行位置中構造鄰域解,最后以總成本最低選擇最優解;

(2)建立禁忌表記錄和選擇優化流程,該禁忌表不僅可以防止禁忌搜索算法陷入局部優化,而且指明了下一步搜索方向。

遺傳算法由于其群智能算法特性易陷入局部最優,當算法求解逐漸收斂時插入禁忌搜索算法可避免這一狀況,從而獲得更優解。禁忌搜索算法二次優化求解結果實現步驟如下:

(1)根據遺傳算法當前產生所有個體,建立禁忌搜索集合NS;

(2)選擇集合NS中某個個體ti,置空禁忌表并設置最優狀態為空;

(3)由選擇的ti構造領域解,并確定其候選解;

(4)禁忌處理和特赦操作。當出現一個解的目標值優于之前任何一個最佳候選解時,進行特赦操作,然后將該解作為當前最優解,并放入禁忌表中。若不存在此解,則從所有鄰域解中選擇非約束最優解作為特赦,同時將其放入禁忌表中,并釋放滿足禁忌步長T的對象;

(5)如果對ti的搜索達到最大迭代次數,則結束對ti的搜索,并轉到后一步。否則轉到第3步。

(6)如果NS中所有對象均以完成禁忌搜索操作,則輸出優化結果。否則跳轉至禁忌搜索第2步。

2.3 遺傳禁忌搜索混合算法流程圖

GTHA流程圖如圖5所示。

圖5 GTHA流程圖

3 實例驗證與分析

3.1 實驗設置

針對本文研究問題,筆者采用文獻[22]中的原始實例進行驗證,并按照本文研究問題特點,對原始數據進行適當調整。

某電動車機械零件加工車間示意圖如圖6所示。

圖6 車間生產示意圖

該車間擁有5條生產線,在某一時段,車間有45個工位需要物料的配送或余廢料回收服務。車間下方包括配送中心及物料倉庫,在進行物料配送及回收服務時,AGV從配送中心0出發,在對所有需求工位進行服務過后,將轉運的成品及回收的余廢料送至物料倉庫0’后最終返回配送中心。在實驗中,以物料最佳配送時間作為工位優先級的參數,最佳配送時間越小,表示工位優先級越高。為了使計算更貼切現實生產車間,工位之間的距離計算采用曼哈頓距離計算方法。本文采用Matlab2016b對實例進行驗證,相關參數設置為:Q=1 000單位,v=5 000 m/h,u=250元/次,λ=1.5元/km,α=60,β=900;GA種群規模n=100,Pc=0.9,Pm=0.08,最大迭代次數C=500;TSA最大迭代次數I=500,禁忌步長T=20。

車間內配送中心、物料倉庫及工位信息表如表1所示。

表1 配送中心、物料倉庫及工位信息表

3.2 結果對比與分析

為使求解結果不失一般性,筆者用GTHA隨機求解20次,取20次平均結果,平均總成本為5 158.1元,工位優先服務率為61%;以同種情況下僅用遺傳算法進行求解,取20次平均結果,平均總成本為5 546.6元,工位優先服務率為65%。遺傳算法收斂曲線如圖7所示。

圖7 遺傳算法收斂曲線

由圖7可知,遺傳算法在20次仿真中,平均200代開始收斂,圖中上下兩條收斂曲線分別代表各代平均成本和最小成本。GTHA混合算法收斂曲線如圖8所示。

圖8 混合算法收斂曲線

由圖8可知,GTHA有兩次收斂現象,第一次收斂平均在第20代,第二次平均收斂在第250代,圖中迭代曲線表示各代最小成本曲線。

在20次實驗中,遺傳算法與GTHA求解結果即成本對比圖如圖9所示。

圖9 成本對比圖

由圖9可知,GTHA求解的結果均優于僅使用遺傳算法求解的結果,證明了混合算法的優良性。

取20次實驗中的一次,其求解結果匯總表如表2所示。

表2 求解結果匯總表

由表2結果可知,利用GTHA及僅使用遺傳算法求解結果均為5輛小車進行服務,但使用GTHA比僅使用遺傳算法成本降低了399.5元,且工位優先服務率提高了3%。

上述求解結果表明了考慮工位優先級的車間雙向物料配送策略在復雜生產車間應用的有效性,也驗證了混合算法的優良性。

4 結束語

針對日益復雜環境下機械生產車間工位物料需求響應慢、運輸小車利用率低等問題,筆者提出了考慮工位優先級的車間雙向物料配送策略并建立相應優化模型,采用遺傳禁忌搜索混合算法對優化模型求解,并利用MATLAB對實例進行了仿真驗證。

研究結果表明:

(1)通過約束工位優先級,滿足了對工位物料需求緊急程度的及時響應;車間內雙向物料配送模式,提升了配送小車的利用率,同時實現了對工位產生的成品轉運及余廢料及時回收;

(2)以總配送成本最低建立目標模型,采用遺傳禁忌搜索混合算法對優化模型進行了求解。與僅使用遺傳算法對比,混合算法分別使成本降低了399.5元,工位優先服務率提高了3%,證明了混合算法的優良性。

為了更進一步適應日益復雜的機械車間生產環境,未來筆者將研究動態物料需求及不同物料類型下的車間物料配送路徑規劃問題。