改進蟻群算法下的車間物料配送路徑規劃研究

楊雷博，周俊

(上海工程技術大學 機械與汽車工程學院，上海 201620)

0 引言

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

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

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

1 模型建立

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

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

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

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

根據以上條件建立問題模型：

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

優化目標：

相關約束：

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

2 基本蟻群算法

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

其中式(10)表示蟻群的轉移規則；式(11)～式(12)表示信息素更新規則；式(13)表示蟻周系統模型。

3 改進蟻群算法

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

3.1 狀態轉移規則的改進

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

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

3.2 信息素更新規則的改進

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

3.2.1 變異算子

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

1）首先，隨機產生一個變異概率，并與設定值作比較，大于設定值進行變異，否則不進行。

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

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

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

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

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

3.2.2 信息素平滑

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

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

圖1 改進后的蟻群算法流程圖

4 案例分析

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

表1 各工位組物料需求

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

圖2 車間布局柵格圖

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

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

從表3結果的對比中能發現，在10次運算中算法改進后較改進前平均距離減少了65.5m，其中基礎蟻群算法的最短距離為1365m；改進蟻群算法對應最短距離為1335m，改進前后最優路徑距離縮短了30m。

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

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

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

圖4 改進后的蟻群算法的迭代曲線

優解，出現搜索停滯，相比基本蟻群算法的最優解，改進的蟻群算法最低成本降低了30。在所需最小車輛數目為2的條件下，這兩種算法對應各自的最優配送路徑為：

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

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

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

5 結語

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