童傅嬌,徐 進(jìn),張守京

(西安工程大學(xué) 機(jī)電工程學(xué)院,陜西 西安 710048)

0 引 言

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

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

通過對上述文獻(xiàn)的研究及對機(jī)械車間現(xiàn)狀的分析基礎(chǔ)上,筆者總結(jié)出目前機(jī)械車間物料配送仍存在以下問題:

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

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

(3)當(dāng)出現(xiàn)緊急訂單、催單、撤單等現(xiàn)象時(shí),未考慮按照工位物料需求緊急度,對工位進(jìn)行配送。

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

1 問題描述與模型建立

1.1 問題描述

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

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

圖1 配送策略示意圖

配送小車裝載工位需求的物料從配送中心出發(fā)對工位進(jìn)行服務(wù),工位上的數(shù)字代表小車服務(wù)順序,該順序按照工位優(yōu)先級進(jìn)行排序,在對各工位進(jìn)行配送服務(wù)的同時(shí),以“先卸后裝”的方式將工位產(chǎn)生的成品及余廢料轉(zhuǎn)運(yùn)與回收。

其問題約束如下:

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

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

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

(4)車間內(nèi)工位物料需求信息、工位優(yōu)先級、配送中心與工位坐標(biāo)均已知,配送路徑中所有節(jié)點(diǎn)可互相連通;

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

1.2 模型建立

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

(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的成品轉(zhuǎn)運(yùn)量;si—工位i的余廢料回收量;dij—工位i與j之間的曼哈頓距離;d0i—配送中心到工位i的距離;ci—工位i的時(shí)間窗懲罰成本;t—小車到達(dá)工位時(shí)間;RTi—工位i可接受的最早配送時(shí)間;LTi—工位i可接受的最晚配送時(shí)間;Ii,Ij—工位i,j的優(yōu)先級參數(shù);u—車輛單次派遣成本;λ—每千米運(yùn)輸成本;α—物料早到工位的懲罰因子;β—物料晚到工位的懲罰因子;i,j—工位編號;x,y—關(guān)聯(lián)系數(shù)。

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

2 模型求解

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

2.1 遺傳算法設(shè)計(jì)

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

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

其中:Nkq—第k輛車的第q個(gè)配送任務(wù)是為工位點(diǎn)Nkq進(jìn)行物料配送及回收;0—配送中心。

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

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

圖2中帶有*號的工位表示該工位有成品轉(zhuǎn)運(yùn)或物料回收需求,則小車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 確定初始種群

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

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

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

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

(4)重復(fù)上述操作,直到達(dá)到初始種群規(guī)模。

2.1.2 適應(yīng)度函數(shù)

以總成本的倒數(shù)作為適應(yīng)度函數(shù)的評價(jià)值,表示為成本越低的種群個(gè)體適應(yīng)度越好:

(10)

2.1.3 選擇操作

選擇操作是將精英保留策略與輪盤賭選擇相互結(jié)合。首先保留適應(yīng)度最大的個(gè)體,即精英個(gè)體,剩余個(gè)體采用輪盤賭法進(jìn)行篩選。

2.1.4 交叉操作

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

2.1.5 變異操作

筆者選擇交換變異法進(jìn)行變異操作,以變異概率Pm選擇個(gè)體。變異操作示意圖如圖4所示。

圖3 交叉操作示意圖

圖4 變異操作示意圖

遺傳算法具有較強(qiáng)的全局搜索特性,但易提前收斂,結(jié)合TSA算法較強(qiáng)的局部搜索特性,筆者在遺傳算法逐漸收斂時(shí)引入禁忌搜索算法,對求解結(jié)果進(jìn)行二次優(yōu)化。

2.2 禁忌搜索算法設(shè)計(jì)

禁忌搜索算法的思想為:

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

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

遺傳算法由于其群智能算法特性易陷入局部最優(yōu),當(dāng)算法求解逐漸收斂時(shí)插入禁忌搜索算法可避免這一狀況,從而獲得更優(yōu)解。禁忌搜索算法二次優(yōu)化求解結(jié)果實(shí)現(xiàn)步驟如下:

(1)根據(jù)遺傳算法當(dāng)前產(chǎn)生所有個(gè)體,建立禁忌搜索集合NS;

(2)選擇集合NS中某個(gè)個(gè)體ti,置空禁忌表并設(shè)置最優(yōu)狀態(tài)為空;

(3)由選擇的ti構(gòu)造領(lǐng)域解,并確定其候選解;

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

(5)如果對ti的搜索達(dá)到最大迭代次數(shù),則結(jié)束對ti的搜索,并轉(zhuǎn)到后一步。否則轉(zhuǎn)到第3步。

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

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

GTHA流程圖如圖5所示。

圖5 GTHA流程圖

3 實(shí)例驗(yàn)證與分析

3.1 實(shí)驗(yàn)設(shè)置

針對本文研究問題,筆者采用文獻(xiàn)[22]中的原始實(shí)例進(jìn)行驗(yàn)證,并按照本文研究問題特點(diǎn),對原始數(shù)據(jù)進(jìn)行適當(dāng)調(diào)整。

某電動(dòng)車機(jī)械零件加工車間示意圖如圖6所示。

圖6 車間生產(chǎn)示意圖

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

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

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

3.2 結(jié)果對比與分析

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

圖7 遺傳算法收斂曲線

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

圖8 混合算法收斂曲線

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

在20次實(shí)驗(yàn)中,遺傳算法與GTHA求解結(jié)果即成本對比圖如圖9所示。

圖9 成本對比圖

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

取20次實(shí)驗(yàn)中的一次,其求解結(jié)果匯總表如表2所示。

表2 求解結(jié)果匯總表

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

上述求解結(jié)果表明了考慮工位優(yōu)先級的車間雙向物料配送策略在復(fù)雜生產(chǎn)車間應(yīng)用的有效性,也驗(yàn)證了混合算法的優(yōu)良性。

4 結(jié)束語

針對日益復(fù)雜環(huán)境下機(jī)械生產(chǎn)車間工位物料需求響應(yīng)慢、運(yùn)輸小車?yán)寐实偷葐栴},筆者提出了考慮工位優(yōu)先級的車間雙向物料配送策略并建立相應(yīng)優(yōu)化模型,采用遺傳禁忌搜索混合算法對優(yōu)化模型求解,并利用MATLAB對實(shí)例進(jìn)行了仿真驗(yàn)證。

研究結(jié)果表明:

(1)通過約束工位優(yōu)先級,滿足了對工位物料需求緊急程度的及時(shí)響應(yīng);車間內(nèi)雙向物料配送模式,提升了配送小車的利用率,同時(shí)實(shí)現(xiàn)了對工位產(chǎn)生的成品轉(zhuǎn)運(yùn)及余廢料及時(shí)回收;

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

為了更進(jìn)一步適應(yīng)日益復(fù)雜的機(jī)械車間生產(chǎn)環(huán)境,未來筆者將研究動(dòng)態(tài)物料需求及不同物料類型下的車間物料配送路徑規(guī)劃問題。