改進(jìn)蟻群算法下的車間物料配送路徑規(guī)劃研究

楊雷博，周俊

(上海工程技術(shù)大學(xué) 機(jī)械與汽車工程學(xué)院，上海 201620)

0 引言

隨著客戶個(gè)性化定制的興起，多品種、小批量的混流生產(chǎn)日漸成為滿足市場需求的重要途經(jīng)[1]，混流生產(chǎn)是一種在同一條生產(chǎn)線上對多種產(chǎn)品進(jìn)行生產(chǎn)的生產(chǎn)方式，在混流生產(chǎn)過程中物料配送效率的高低會直接影響到物料配送周期、生產(chǎn)節(jié)拍、庫存水平等，較高的物料配送效率會為混流企業(yè)帶來巨大的效益，節(jié)約大量的成本。而提高效率的關(guān)鍵一環(huán)就是要對物料配送的路徑進(jìn)行研究，因此對車間物料配送路徑的研究是非常有必要的。

目前對車間物料配送路徑規(guī)劃方面的研究有很多，文獻(xiàn)[2]針對不確定因素進(jìn)行考慮，建立了機(jī)會約束規(guī)劃模型，并提出了一種改進(jìn)的傳統(tǒng)混合智能算法，最后用該算法對模型進(jìn)行了求解；文獻(xiàn)[3]以車輛路徑規(guī)劃問題(Vehicle Routing Problem，VRP)基礎(chǔ)，建立了物料配送路徑規(guī)劃模型，并對蟻群算法做出了改進(jìn)，用改進(jìn)的蟻群算法對模型進(jìn)行了求解；文獻(xiàn)[4]針對行駛時(shí)間區(qū)間不確定的路徑問題提出了將不確定行駛時(shí)間由區(qū)間數(shù)表示，并借助魯棒優(yōu)化的方法，建立了裝配線路徑規(guī)劃模型，最后設(shè)計(jì)了一種混合遺傳算法求解此模型；文獻(xiàn)[5]設(shè)計(jì)了一種雙層遞進(jìn)的進(jìn)化優(yōu)化算法，并根據(jù)問題建立了以配送距離最短、配送次數(shù)最少和車輛利用率最大為優(yōu)化目標(biāo)的物料配送路徑模型，最后用設(shè)計(jì)的算法對模型進(jìn)行了求解；文獻(xiàn)[6]對粒子群優(yōu)化算法進(jìn)行了改進(jìn)，并用改進(jìn)的算法求解了以物料配送路徑最短的優(yōu)化目標(biāo)模型；文獻(xiàn)[7]針對農(nóng)用機(jī)械混流車間配送路徑規(guī)劃難、線邊庫存高的問題，設(shè)計(jì)了以小車配送距離最短和線邊庫存最小為優(yōu)化目標(biāo)的規(guī)劃模型，根據(jù)實(shí)際布局設(shè)計(jì)柵格環(huán)境地圖，并通過改進(jìn)的蟻群算法對模型進(jìn)行了求解；文獻(xiàn)[8]考慮了離散型車間余-廢料回收率低、成本高的問題，針對這個(gè)問題建立了一個(gè)物料再循環(huán)的路徑優(yōu)化問題模型，最后借助遺傳算法求解了問題模型。

綜上所述，以上研究雖對問題模型都取得了較好的解，但在實(shí)際的混流車間生產(chǎn)過程中，由于工位布局的影響，實(shí)際的配送距離會大于兩點(diǎn)距離公式計(jì)算的距離，而距離對小車的配送時(shí)間又會有巨大影響，為使實(shí)際的配送距離最短就需要考慮在各需求點(diǎn)時(shí)間窗約束下的實(shí)際車間布局，而以上研究并沒有將混流車間工位的實(shí)際布局和時(shí)間窗因素進(jìn)行有效的結(jié)合，因此為更好的解決混流車間物料配送在時(shí)間窗約束下的路徑規(guī)劃問題，本文將借助柵格化后的車間布局柵格地圖[9]，通過對蟻群轉(zhuǎn)移規(guī)則和信息素更新規(guī)則進(jìn)行改進(jìn)，并用改進(jìn)后的蟻群算法對模型進(jìn)行求解，使達(dá)到配送路徑最短，所用配送小車數(shù)量最少，實(shí)現(xiàn)配送成本最低的優(yōu)化目標(biāo)要求。

1 模型建立

車間物料配送問題是一種結(jié)合實(shí)際車間布局的VRP問題[10]，本文由最短配送距離和最少車輛使用數(shù)目確定出最小配送成本，并以此為優(yōu)化目標(biāo)，同時(shí)考慮各工位的實(shí)際需求和時(shí)間窗約束建立數(shù)學(xué)模型。模型假設(shè)配送小車有m輛，配送點(diǎn)有n個(gè)，小車從物料倉庫裝載后出發(fā)，依次在合理的約束下對每個(gè)配送點(diǎn)進(jìn)行配送，直到小車空載后再次回到物料倉庫，至此一次配送結(jié)束。此外，在建模前需要滿足以下相關(guān)假設(shè)：

1）單車運(yùn)載力要大于單個(gè)配送點(diǎn)的需求量。

2）配送中心能夠滿足所有配送點(diǎn)需求，無缺貨。

3）車輛完成配送后直接返回配送中心。

根據(jù)以上條件建立問題模型：

設(shè)i、j為需求點(diǎn)，其中i=0或j=0為物料倉庫；k為配送小車；xijk為小車k由需求點(diǎn)i到需求點(diǎn)j；Sij為需求點(diǎn)i到j(luò)的距離；Ca為單位配送距離的成本，Ca=1；Cb為每輛車的成本，Cb=1000；yik為需求點(diǎn)i由小車k配送；ai為需求點(diǎn)i所需物料的數(shù)量；vi為需求點(diǎn)i單位物料體積；li與ri分別為需求點(diǎn)i的左時(shí)間窗和右時(shí)間窗；tik為小車k到達(dá)需求點(diǎn)i的時(shí)間。

優(yōu)化目標(biāo)：

相關(guān)約束：

上述優(yōu)化模型中，式(1)表示優(yōu)化目標(biāo)；式(2)表示一個(gè)需求點(diǎn)由一輛小車配送；式(3)～式(5)表示對所有需求點(diǎn)的配送，且需求點(diǎn)都只能被配送一次；式(6)表示小車的限載量；式(7)表示時(shí)間窗要求；式(8)～式(9)表示變量之間的關(guān)系。

2 基本蟻群算法

蟻群算法最早是由Dorigo提出來的[11]，它的基本思想是通過一群人工螞蟻相互協(xié)作來完成最優(yōu)解的尋找，每只人工蟻按著一定的轉(zhuǎn)移規(guī)則選擇相應(yīng)的移動目標(biāo)點(diǎn)，并在移動過程中釋放信息素，人工蟻通過信息素交換信息，從而達(dá)到相互協(xié)作的目的。蟻群算法中τij為信息素濃度；nij為能見度因素；α為啟發(fā)因子；β為期望因子；P為信息素保留因子；Δτij為信息素增加量。以下為基本蟻群算法的算式[12]：

其中式(10)表示蟻群的轉(zhuǎn)移規(guī)則；式(11)～式(12)表示信息素更新規(guī)則；式(13)表示蟻周系統(tǒng)模型。

3 改進(jìn)蟻群算法

蟻群算法因?yàn)槭且环N正反饋算法，在算法的計(jì)算過程中，如果有一個(gè)解一直為最優(yōu)，則算法就很容易的陷入到局部最優(yōu)解中，為防止算法陷入局部最優(yōu)。主要對算法進(jìn)行以下改進(jìn)。

3.1 狀態(tài)轉(zhuǎn)移規(guī)則的改進(jìn)

轉(zhuǎn)移規(guī)則決定著螞蟻下一步的走向，蟻群算法只考慮了信息素濃度和啟發(fā)函數(shù)兩種因素，而在實(shí)際的車間物料配送中，由于配送點(diǎn)的物料服務(wù)需求時(shí)間窗約束對螞蟻的選擇也會造成一定的影響，時(shí)間窗越窄表示配送點(diǎn)對物料的需求越緊迫，小車等待時(shí)間過長也會造成配送效率的下降，因此本文選擇在狀態(tài)選擇規(guī)則中加入等待時(shí)間(wait)和時(shí)間窗寬度(width)兩種因素[13]，對規(guī)則進(jìn)行優(yōu)化。改進(jìn)的轉(zhuǎn)移規(guī)則如下：

式中γ、δ分別為等待時(shí)間因子和時(shí)間窗寬度因子。式(14)為改進(jìn)的蟻群轉(zhuǎn)移規(guī)則；式(15)為小車的等待時(shí)間；式(16)為需求點(diǎn)的時(shí)間窗寬度。

3.2 信息素更新規(guī)則的改進(jìn)

為了防止算法陷入局部最優(yōu)解，出現(xiàn)搜索停滯，本文引入了遺傳算法中的變異算子和信息素平滑機(jī)制來提高算法的搜索能力。在改進(jìn)之前首先要對物料倉庫和配送點(diǎn)進(jìn)行自然編碼，用0表示物料倉庫，用1,2,...n表示物料需求點(diǎn)，m輛小車從物料倉庫出發(fā)對n個(gè)物料需求點(diǎn)配送，在滿足約束的情況下配送完回到物料倉庫，形成相應(yīng)的配送路徑,其路徑表示(0,x1,x2,...xs,0,xi,...xk，0,...)。

3.2.1 變異算子

在所有螞蟻都形成各自的配送路徑后，分別對各個(gè)螞蟻的路徑按一定概率進(jìn)行變異，具體步驟如下：

1）首先，隨機(jī)產(chǎn)生一個(gè)變異概率，并與設(shè)定值作比較，大于設(shè)定值進(jìn)行變異，否則不進(jìn)行。

2）變異點(diǎn)確定：隨機(jī)選取一個(gè)當(dāng)前路徑中的點(diǎn)，以(123456789)為例，選取第四位為變異點(diǎn)，此時(shí)路徑為(12356789)。

3）將2中選取的變異點(diǎn)隨機(jī)插入到當(dāng)前路徑中，例如插入第六位與第七位之間，形成變異后的路徑為(123567489)。

4）驗(yàn)證變異后的路徑是否符合約束。

5）將變異后的路徑和變異前的路徑作比較，并保留最優(yōu)路徑。

6）按照上述步驟完成所有螞蟻的路徑變異，則變異結(jié)束。

3.2.2 信息素平滑

由于蟻群算法具有依靠信息素濃度選擇的正反饋機(jī)制，經(jīng)多次迭代后螞蟻都會集中到一條當(dāng)前最好的路徑，此時(shí)這條路徑上的信息素濃度最高，而其它路徑上的信息素濃度就偏低，這樣算法一旦陷入局部最優(yōu)解就會很難跳出來。為防止此種現(xiàn)象出現(xiàn)本文引入了信息素平滑機(jī)制[14,15]對算法進(jìn)行改進(jìn)，如果連著多次迭代的最優(yōu)解都相同，則借助以下公式對信息素進(jìn)行平滑：

其中為平滑后的信息素濃度；τij(t)為平滑前的信息素濃度；δ(0<δ<1)為平滑程度控制參數(shù)。改進(jìn)的蟻群算法流程：首先設(shè)置參數(shù)并初始化，然后構(gòu)造每只螞蟻的路徑，構(gòu)造完成后對路徑進(jìn)行變異，并判斷變異是否有效，接著進(jìn)行信息素全局更新，判斷N次最優(yōu)解是否有變化，沒變化就進(jìn)行平滑，最后判斷是否滿足終止條件。具體如圖1所示。

圖1 改進(jìn)后的蟻群算法流程圖

4 案例分析

為檢驗(yàn)算法的可行性，并評估改進(jìn)后算法的優(yōu)越性，本文選取了某發(fā)動機(jī)裝配車間為實(shí)例進(jìn)行驗(yàn)證。該車間按照物料管理要求，可將距離和工藝要求以及時(shí)間窗相近的工位點(diǎn)進(jìn)行整合，最終形成9個(gè)工位組。根據(jù)生產(chǎn)計(jì)劃可得到各工位組一天的物料需求和對應(yīng)時(shí)間窗。如表1所示，其中0為物料倉庫；1～9為工位組。

表1 各工位組物料需求

在實(shí)際的混流車間中由于受到道路和工位布局的影響，配送路徑并不能按照兩點(diǎn)公式進(jìn)行計(jì)算，這就會使得實(shí)際的配送路程遠(yuǎn)遠(yuǎn)大于理論值。因此為更好反應(yīng)實(shí)際情況本文采用柵格化后的車間布局圖，將布局分為可行區(qū)域和不可行區(qū)域，其中白色為可行區(qū)域，黑色為不可行區(qū)域，并設(shè)定每小格邊長為10米。柵格化后的地圖如圖2。在圖2的基礎(chǔ)上由蟻群算法分別計(jì)算出物料倉庫到各工位組以及各工位組之間的最短路徑距離，最終可獲得各工位組相對距離表，第一列和第一行為工位組，0為物料倉庫。具體如表2，其中第一行、第一列為物料倉庫和工位組，中間數(shù)據(jù)為相對距離。

圖2 車間布局柵格圖

表2 物料倉庫和各工位相對距離 (m)

在MATLAB R2018a平臺上實(shí)例計(jì)算，參數(shù)設(shè)置分別為α=1，β=3，γ=3，δ=3，蟻群數(shù)量為50，最大迭代次數(shù)為100。將基本蟻群算法和改進(jìn)蟻群算法(式14)在平臺上分別運(yùn)算10次，得到在各自算法下的最短配送總距離，如表3所示。

從表3結(jié)果的對比中能發(fā)現(xiàn)，在10次運(yùn)算中算法改進(jìn)后較改進(jìn)前平均距離減少了65.5m，其中基礎(chǔ)蟻群算法的最短距離為1365m；改進(jìn)蟻群算法對應(yīng)最短距離為1335m，改進(jìn)前后最優(yōu)路徑距離縮短了30m。

表3 兩種算法下的總配送距離

如圖3、圖4所示，分別為基本的蟻群算法和改進(jìn)的蟻群算法的迭代曲線。

圖3 基本蟻群算法的迭代曲線

圖4 改進(jìn)后的蟻群算法的迭代曲線

優(yōu)解，出現(xiàn)搜索停滯，相比基本蟻群算法的最優(yōu)解，改進(jìn)的蟻群算法最低成本降低了30。在所需最小車輛數(shù)目為2的條件下，這兩種算法對應(yīng)各自的最優(yōu)配送路徑為：

基礎(chǔ)蟻群算法：第一輛，0-5-3-6-4-2-1-0；第二輛，0-7-8-9-0。

改進(jìn)的蟻群算法：第一輛，0-3-7-8-6-4-2-1-0；第二輛，0-5-9-0。

由此說明了本文的蟻群算法對模型的求解具有良好的性能。

5 結(jié)語

本文針對混流生產(chǎn)車間物料配送的準(zhǔn)時(shí)化，路徑的多樣化問題，建立了混流車間的物料配送路徑優(yōu)化模型，并對蟻群算法中的轉(zhuǎn)移規(guī)則和信息素更新規(guī)則進(jìn)行了改進(jìn)，使得算法在符合物料配送實(shí)際情況的同時(shí)也提高了算法的全局搜索能力。最后結(jié)合實(shí)際案例分析結(jié)果表明，改進(jìn)算法能收斂到更好的解，與基礎(chǔ)的蟻群算法相比改進(jìn)蟻群算法配送成本更低，為制造企業(yè)進(jìn)行車間物料配送路徑規(guī)劃提供了參考。