楊雷博，周俊

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

0 引言

隨著客戶個性化定制的興起，多品種、小批量的混流生產(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]針對行駛時間區(qū)間不確定的路徑問題提出了將不確定行駛時間由區(qū)間數(shù)表示，并借助魯棒優(yōu)化的方法，建立了裝配線路徑規(guī)劃模型，最后設(shè)計了一種混合遺傳算法求解此模型；文獻(xiàn)[5]設(shè)計了一種雙層遞進(jìn)的進(jìn)化優(yōu)化算法，并根據(jù)問題建立了以配送距離最短、配送次數(shù)最少和車輛利用率最大為優(yōu)化目標(biāo)的物料配送路徑模型，最后用設(shè)計的算法對模型進(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è)計了以小車配送距離最短和線邊庫存最小為優(yōu)化目標(biāo)的規(guī)劃模型，根據(jù)實際布局設(shè)計柵格環(huán)境地圖，并通過改進(jìn)的蟻群算法對模型進(jìn)行了求解；文獻(xiàn)[8]考慮了離散型車間余-廢料回收率低、成本高的問題，針對這個問題建立了一個物料再循環(huán)的路徑優(yōu)化問題模型，最后借助遺傳算法求解了問題模型。

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

1 模型建立

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

1）單車運載力要大于單個配送點的需求量。

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

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

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

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

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

相關(guān)約束：

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

2 基本蟻群算法

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

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

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

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

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

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

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

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

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

3.2.1 變異算子

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

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

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

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

4）驗證變異后的路徑是否符合約束。

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

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

3.2.2 信息素平滑

由于蟻群算法具有依靠信息素濃度選擇的正反饋機(jī)制，經(jīng)多次迭代后螞蟻都會集中到一條當(dāng)前最好的路徑，此時這條路徑上的信息素濃度最高，而其它路徑上的信息素濃度就偏低，這樣算法一旦陷入局部最優(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 案例分析

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

表1 各工位組物料需求

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

圖2 車間布局柵格圖

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

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

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