基于蟻群算法的農機混流車間配送路徑研究

萬 林，張志文，楊曉英

（河南科技大學 機電工程學院，洛陽 471003）

0 引言

農機裝備生產受市場需求和國家政策影響較大，機型和配置更新換代速度快，農機裝備需求針對性較強，針對不同地域、環境、作業需求都需要選配不同的機型，造成了生產轉換快、動態性強等特點。隨著市場競爭和客戶個性化需求的加劇，多品種小批量的混流生產已經成為企業滿足市場多樣化需求、提高裝配效率和加快企業響應速度的重要手段。多種機型共線裝配造成了混流裝配線工位需求隨生產轉換發生變化，造成配送路徑難以規劃的問題，傳統企業一般采用大量儲備線邊庫存的方法，造成了高昂的庫存成本，因此對混流裝配車間配送車輛的配送路徑進行合理的規劃，對企業降低庫存和配送成本有重要意義。

近年來針對配送路徑優化主要有以下研究，徐海寧、徐星[1]針對混流裝配準時化配送，結合遺傳算法改進蟻群算法，對模型求解。王力鋒、楊華玲等[2]對最優網絡路徑選取，構建了車輛調度數學模型，實現配送路徑最優化。針對復雜環境下路徑尋找困難，王欽釗、程金勇、李小龍[3]采用基于勢場優化的蟻群路徑規劃算法。賴智銘、郭躬德[4]改進了蟻群的回退策略，提出了二次優化，Rajappa G P，Wilck J H，Bell J E等[5]在標準路徑規劃問題上，對遺傳算法和混合元啟發式算法進行測試，尋找最優解決方案。以上學者的研究都實現了提高尋路的收斂速度和尋優能力。針對制造業的生產配送路徑優化，王楠、李世其、王峻峰[6]建立了適用于汽車總裝線物料配送路徑規劃的混合時間窗模型，提出了改進遺傳算法，朱永國、李俊杰、劉春鋒[7]等針對飛機裝配過程中裝配工位物料需求時間模糊化現象，建立了基于正態模糊時間窗約束的配送路徑規劃模型，采用遺傳算法進行了求解，夏揚坤、符卓、謝九勇[8]將多自動導引車物料配送路徑規劃問題歸結為一種帶軟時間窗的需求依訂單拆分車輛路徑問題，設計了一種自適應禁忌搜索算法，李思國、郭宇、王益聰等[9]針對離散制造車間環境復雜以工作中心為物料配送基礎結合物料配送時間窗要求，以最小物料配送成本為優化目標,建立了車間實時環境下的物料配送模型，采用改進遺傳算法對模型進行求解。Emde S，Boysen N[10]通過設計配送小火車的運行路線和到達站點時間，實現準時化配送，并設計優化模型計算精確解。

綜上所述，近年來針對制造車間路徑規劃的研究主要是結合工位需求的配送路徑建模，并使用智能算法求解，但大多數研究并未考慮車間內實際布局和道路規劃。本文以農機混流車間配送路徑規劃為研究對象，結合混流車間布局的復雜性，考慮線邊空間和配送運載能力，以最小配送距離和線邊庫存為優化目標，建立物料配送和線邊儲存優化模型，設計改進蟻群算法求解最優配送路徑，通過實例數據計算驗證，確定最優配送 方案。

1 問題描述

農機混流裝配車間路徑規劃是配送車輛從倉庫出發，根據工位物料需求，確定配送小車需要配送的物料和需要服務的工位，通過合理規劃配送路徑和配送數量，在符合約束和確保生產的前提下，產生最少的配送成本和線邊庫存成本。

由于農業機械作業對象種類多，作業環境復雜，農機裝備制造存在機型多，選配多的問題，在混流生產中體現出物料種類多，工位需求變動大等特點，因此大量線邊庫存和固定路徑的周期性配送不能滿足動態化的生產要求，需要根據工位物料需求變化，調整配送小車裝載的物料型號和配送路徑。同時生產車間路徑規劃受到車間布局和道路規劃影響，導致配送小車在實際配送中存在不可行區域，加大了最優路徑規劃的難度。

2 優化模型

為解決配送路徑規劃困難，實現小批量多頻次配送，減少線邊庫存，考慮各工位生產物料需求和配送小車的運載能力，以最小配送距離和線邊庫存為優化目標，建立優化模型。

2.1 相關假設

模型假設車間有n輛配送小車對m個工位進行配送，小車從倉庫出發，根據某段時間的工位物料需求，配送若干工位后，空載返回倉庫，在配送中滿足以下假設條件：

1）本文所針對的物料主要是體積中等，型號種類復雜的裝配件和自制件，每個工位僅裝配一種物料。

2）在配送中一輛配送小車可以一次對多個工位進行服務，但一個工位一次只接受一輛小車服務。

3）物料體積、配送小車容量和線邊儲存空間已知且設定為標準料箱大小的整數倍。

4）倉庫備貨能力充足。

2.2 符號定義

i= {i | i=1，2，…，n}：配送小車集合，車間內配送小車數量為n；

j={j，k | j，k=1，2，…，m}：工位集合，車間內工位數量為m；

djk：j工位到k工位距離；

Li：i小車的總配送距離；

Λj：j工位線邊儲存空間；

V：配送小車裝載空間；

vj：j工位單位物料占用標準空間；

s：配送小車的運行速度；

Tload：配送小車服務工位時間；

qij：小車i對j工位一次配送的物料數量；

R：生產節拍；

cs：單位物料線邊庫存成本；

cd：單位距離配送成本；

2.3 數學模型

目標函數：

相關約束：

式(1)為目標函數，包括線邊庫存成本和配送成本，式(2)表示一個工位只接受一臺配送車輛服務，式(3)為所有需求工位都安排了配送車輛，式(4)為配送時間要求，表示物料需求有一定的時間窗，式(5)和式(6)表示配送物料不能超過配送運載能力和線邊庫存空間。

3 蟻群算法設計

由于小車裝載和路徑調度問題屬于NP-Hard問題，因此在大規模問題中，精確算法很難快速獲得理想的解，蟻群算法在路徑規劃等領域具有較強的全局搜索能力，因此本文設計了結合車間物流配送特點的改進蟻群優化算法。

2）設置地形圖矩陣，將車間布局和道路規劃通過01矩陣表現，矩陣中1表示為障礙物，是螞蟻不可行區域，0為道路和空地。設置螞蟻路徑起始點為倉庫，將各工位位置轉換成坐標形式，放入地形圖矩陣中，通過地形圖計算螞蟻在兩工位間的實際路徑距離和節點之間的可見度。

3）存儲每一代每只螞蟻的爬行路徑和爬行路線長度，螞蟻已經訪問過的工位設置為工位集合禁忌表，并由此獲得螞蟻下一步可以訪問的工位集合allowdn，

4）改進蟻群算法的路徑選擇概率，結合配送小車的配送能力約束和各車間工位的物料需求情況改變螞蟻的選擇概率，在此加入式(7)和式(8)，使螞蟻在選擇時，具有提高裝載率的偏向，然后通過式(9)計算螞蟻i的轉移概率，并使用輪盤賭法選擇下一個訪問的 工位。

5）根據之前螞蟻的路徑選擇，進行局部信息素更新，直到配送過程中所有螞蟻都生成網絡路徑。

6）根據螞蟻的路徑選擇信息，進行網絡全局信息素更新后，計算物流配送過程中螞蟻經過的最短網絡路徑總長度。

7）當迭代循環次數NK>NKmax，則停止迭代循環，輸出螞蟻走過的路徑和路徑總長度，此時最后一次迭代結果即為最優配送路徑。

4 實例分析

4.1 實例數據

實例選取某拖拉機總裝車間現場生產數據，實驗中的配送為車間內生產配送，主要是指從總裝車間倉庫配送到各裝配工位的過程，該車間布局主要由總裝線、駕駛室組合區、前箱組合區，后箱組合區、前后箱組合線等裝配線組成，根據裝配線的工藝裝配順序要求、物料需求時間窗和物料管理劃分，將有工藝要求和距離相近的工位整合，最終設定為7個工位段，且4個組合區的物料必須先于總裝區到達。在計算中設置配送車輛容量V=600，生產節拍R=2.5分鐘，Tload=3分鐘，配送小車行駛速度為s=1m/s，單位配送距離成本cd=1，線邊庫存成本cs=1，工位段需求情況如表1所示。

表1 工位段物料需求情況

4.2 實驗結果

在實際生產中，由于受到車間內布局和道路情況影響，導致實際配送距離大于坐標直接計算結果，車間各工位之間的實際配送距離不能用坐標直接計算，本文在蟻群算法中設置車間柵格地形圖，設定配送小車可以運行的路線，通過計算確定各工位間的最短配送距離,代替傳統蟻群算法中城市位置用橫縱坐標計算的方法。地形圖中黑色部分代表配送小車不可行駛區域，圖形中設定每單位方塊的邊長為10米，計算倉庫到達后箱組合區工位的最短配送車間柵格地形路線如圖1所示，計算過程如圖2所示，最短路徑距離為250米，同理可以計算獲得各工位之間配送距離如表2所示。設置算法參數α=1，β=5，γ=0.2，蟻群規模m=10，最大迭代次數K=100。使用Matlab7.0進行實例計算。

圖1 倉庫到后箱組合區配送路徑

圖2 倉庫到后箱組合區配送路徑計算

表2 倉庫和各工位配送距離表

當蟻群算法不考慮裝載能力和工位需求時，1臺配送小車對7個工位段進行配送，得到最短路徑的配送方案是：1-3-5-6-7-4-2-1，此時配送距離為1210米，小車配送時間和裝卸貨時間總和為2290秒，但此時配送不能滿足工藝順序和物料數量需求。

因此改進后的蟻群算法在螞蟻進行輪盤賭選擇下一個將到達的工位時，需要對比工位的物料需求和螞蟻剩余的運載能力，若余下工位全部不能滿足裝載要求，則螞蟻將返回倉庫，重新裝載后出發配送。

改進后蟻群算法計算最優路徑為1-5-7-3-1-2-6-4-1，此時滿足約束條件且成本最低的配送方案為2臺配送小車，配送路徑為：

車輛一配送路徑是：1-5-7-3-1，即倉庫-后箱組合-發動機組合-總裝A區-倉庫，每次迭代螞蟻配送最短距離和平均距離計算過程如圖3所示，最終最短配送距離830米，配送時間和工位服務時間為1370秒，裝載率為83%。

車輛二配送路徑是：1-2-6-4-1，即倉庫-駕駛室組合-前箱組合-總裝B區-倉庫，最短配送距離為590米，配送時間和工位服務時間總和為1130秒，裝載率為83%。

考慮配送寬放時間后，可以設置為配送間隔期25分鐘，每種物料單次配送量10個，總配送距離為1420米，此時總成本為1820，實現了配送路徑優化和線邊庫存量減少。

圖3 車輛一配送距離迭代變化圖

5 結束語

針對農機裝備混流車間線邊庫存量大，配送路徑難規劃的問題，研究了優化目標為配送距離和線邊庫存量的配送模型，設計了結合配送能力的改進蟻群算法，以某拖拉機總裝車間配送數據實例分析，確定了最優配送路徑和配送期量，為農機裝備混流生產配送路徑優化提供理論依據。