汽車裝配車間流水線物料問題配送研究*

張若冰，田 博，孫源龍，常 亮※

（1.西藏大學理學院，拉薩 850000；2.西藏大學信息科學技術學院，拉薩 850000）

0 引言

汽車制造有沖壓、焊接、涂裝和總裝四大關鍵工藝，其中總裝車間的占地面積最大、工人數量最多，迫切需要數學建模技術幫助降本增效。總裝指將內外全部飾件裝配到車身上的一種工藝，通常圍繞流水線展開，線上的每個工位負責裝配固定的物料。為防止停線影響生產效率，需要及時補充工位上的物料，此物料補充工作稱為運輸，一般由拖車完成。拖車接收到任務指令后，需要進行如下操作。（1）取料：前往目標物料的存儲位，將物料裝載至拖車；（2）配送：將物料運送至目標工位和卸載。需要注意的是，在不超過小車容量的情況下，多個任務可同時進行。

劉奎武等［1］研究的組合藥裝盒多向輸送生產線的問題，較好地解決了多條流水線之間的貨物運輸問題，但不適合原料到生產工位之間的運輸問題。廈門大學的楊鈺琳[2]以0-1整數規劃問題研究的汽車公司總裝混流裝配線平衡問題，使得混流總裝線的運行更加平穩和高效。但是沒有滿足本題目中的工位分區和倉儲點到生產工位的約束條件。

本文研究的問題假設將兩條流水線上的工位分成若干個區域，并由一個小車負責此區域的貨物搬運，將III區對應序號的貨物搬運至I區和II區對應編號的工位進行生產，具體分布如圖1所示。

圖1 有效點分布

在規劃配送路線較短的方法中，本文采用蟻群算法，將搜索的過程不斷收斂，直至找到最優解，在搜索路徑問題上具有優勢。多項活動同時運算，極大地提高了運行效率。并對傳統蟻群算法進行了改進，在約束條件中添加了時間窗，降低了流水線停線的可能。

1 轉運車輛分組

由于流水線區域可使用的拖車數量有限，為了避免拖車路線可能出現的情況過于復雜繁瑣，需要首先對拖車進行分組后再進行流水線貨物調配。

1.1 廣度優先搜索分配方案

廣度優先算法是圖搜索算法中常見的一種，以客觀的方法搜索圖中數據的所有頂點，并計算從起始點到各頂點所需遍歷得到的最小邊數值[3-4]。其屬于一種盲目搜尋法，目的是系統地展開并檢查圖中的所有節點，以找尋結果。換句話說，它并不考慮結果的可能位置，徹底地搜索整張圖，直到找到結果為止[5]。

在I區域和II區域，相隔兩個工位點的距離在水平方向上為20 m，兩個工位之間的距離在垂直方向上為10 m；在III區域，相隔兩個工位點的距離在水平方向上為20 m，兩個工位之間的距離在垂直方向上為20 m。故在計算過程中，可認為其為矩形區域進行計算，最后通過計算其在橫向和縱向的行走步數來計算其距離，具體流程如圖2所示。根據圖中所示流程，對48個工位分別進行路線規劃，途徑工作點和路線如表1所示。

圖2 車輛調度路線最短距離計算方法流程

表1 路線規劃結果（部分）

1.2 TSP模型分配方案

TSP問題是在信息學競賽問題中，常見的圖論經典組合優化問題。

問題假設有72個點（48個工位點和24個儲貨點），點i和j之間的距離Ci,j，目標是找到一條閉合的路線，并保證這條路線的總距離最短。這個問題就可以描述成將若干個點認為一個集合V={1,2,3,…,n}。頂點之間的距離為：

事實上，對于任何兩個點i和城市j來說，要么這條旅行路線包含該路線，要么不包含該路線。故引入0-1變量xij，1表示包含該路線，0表示不包含該路線。即目標就是在求：

而在本模型中，由于貨物調配過程中，走得不一定是閉環路線，因此在建模中，可以去除TSP模型中的消除約束。從而引入了DFJformulation模型對問題進行了求解。則TSP的整體規劃模型為：

經過DFJ進行處理，以拖車的行駛路線最短為試探性條件，對其承包區進行劃分，得到結果如表2所示。

表2 基于TPS的承包區劃分結果Tab.2 Division results of contracting area based on TPS

1.3 結果分析和檢驗

經過對比，發現兩種方案得到的結果中，只有I-7和II-6的劃分區域存在差異，說明模型合理、結果準確。經過實際分析，推測可能差異來自于路線行駛方案中，方法二并未考慮每輛車到達其目標的對應倉儲點的最優路徑，而是單純考慮了整個閉環路線的距離和最短造成的。所以最終以BFS得到的分配方案為最終方案。

2 物料調配方案規劃

在本文研究的汽車組裝車間物料配送問題中，設R={r1,r2,…,r24}代表24個工作位點以O為坐標原點的位置，而S為道路關鍵節點的點集，記為S={sA,sB,…,sN}，先有24個不同配料的倉庫，要進行物料配送的工作點記為N(i=1,2,…,N)以及所需的拖車數量，每量拖車裝載4個工作點的物料量，且每輛小車可以運送多個工位，同時每個工位可以由不同車輛進行運送即不采取承包制運行，當工作位得到足夠原料后即為配送任務結束，在物料運送過程中。在盡量減少停線現象的發生并滿足約束條件的情況下，建立以配送總成本最低為目標的配送拖車路徑優化模型。

決策變量為：

以上構建的關于路徑優化的數學模型中，式（8）中包含了配送拖車的行駛成本與軟時間懲罰成本，將其作為本次規劃模型的總成本；式（9）表示配送小車能夠配送的物料量小于最大限度，在本題中以最多運載4個工作點的物料量為準，即Q≤4；式（10）表示只能由一輛小車完成一個工位其工作點物料的物料配送，排除兩輛車同時為一個工作點配送物料的情況；式（11）表示僅從倉庫到達工作點完成裝卸即為完成整個配送流程；式（12）表示將支路進行消除；式（13）表示到達的配送拖車與離開工位的為同一輛；最后式（14）～（15）為決策變量。

Maro Dorigo模擬自然界中蟻群覓食過程中搜尋可行路徑的方式提出蟻群算法，其全局優化能力較強，因此非常適合用于優化sink移動距離[6-7]。而本題目中和傳統的蟻群算法還存在著時間窗和路線的限制，因此在蟻群算法訓練過程中，還加入了時間窗時序限制和廣度優先搜索算法對其路線的是否聯通進行判斷，避免出現由于連通性問題導致的路線無法行駛，出現的路程差造成了結果的錯誤。

蟻群算法是基于自然界中蟻群的覓食活動建立的[8-9]。螞蟻尋找食物的運動過程中會釋放一種信息素，蟻群根據信息素可以確定從蟻巢到食物的路線。在單位時間內，路徑越短，到達的螞蟻越多、信息素濃度更高，蟻群趨向于信息素濃度更高的路徑，即可以找到到達食物的最短路徑。這個過程的本質可以概括為以下幾點：（1）信息素濃度越高，被選中的幾率越大，以此作為蟻群算法中路徑的選擇機制；（2）更新后的路徑越短，該路徑上的信息素增長越快；（3）螞蟻個體之間通過信息素交流，以此作為蟻群算法中的協同工作機制。

2.1 計算方法的設計和計算機實現

將本題目需求與蟻群算法相結合，以48個工位、24個倉儲點為限制條件，按照問題一中劃分的承包區結果。圖3所示為調度方案生成流程。

圖3 調度方案生成流程

2.2 方案測試結果

假設有6輛可用拖車，23個節點有貨物需求，具體需求用例如表3所示。

表3 任務訓練測試集

根據上述方法及其限制條件，得到了如表4所示的規劃方案。由表可知，拖車1出現了在第72 s完成工位I-19的配送后，無法在79 s前順利達到I-1位置，導致了I-1工位缺少原料，出現2 s的停線情況。通過分析是由于在模型中對時間窗寬度較小的工位進行轉移導致的。

表4 任務結果

3 停線問題優化

隨著工作的進行，設工位點i其時間窗寬度為widthi=li-ei，在該轉移規則下，配送拖車會優先選擇配送時間窗寬度差相對較小的工位點，其中pkij(t)表示蟻群算法中螞蟻k從工位點i轉移到工位點j的狀態轉移概率，則轉移規則如下：

式中：τij為信息素濃度；ηij為啟發式因子，ηij與dij的關系為；α為該軌跡的相對重要性，即為信息素的加權值；β為能見度的相對重要性，即為能見度的加權值；γ為等待配送的工位服務順序，也就是時間窗跨度的重要因子。其為隨機變量并在[0，1]上服從均勻分布；allowedk為螞蟻k在下一步移動中可以選擇的點的集合[10]，從而求出狀態轉移概率，選用輪盤賭法計算選擇下次移動的工位點j的概率，直至配料運送完畢，之后使另一輛車繼續上步，直至所有配送工位點被訪問完成為止。

除此之外，本團隊還在蟻群算法中添加了所有螞蟻完成移動返回原起點后，對殘留于路徑上的信息素再進行不斷更新，因此路徑（i，j）在時刻t+1時的信息量可進行進一步調整為：

式中：信息素在路徑（i，j）上的增量是信息素蒸發因子；ρ為信息素蒸發因子；(1-ρ)為信息素殘留因子[11-12]；Δτij(t)為信息素在路徑（i，j）上的增量；在初始時刻，Δτij(0)=0，Δτkij為在這個循環中，第k只螞蟻在路徑（i，j）上留下的信息量，若螞蟻沒有經過次路徑，則Δτij=0，Δτij表示為：

將上述轉移規則進行調整后，本模型再次對上述假設進行方案分配，測試結果如表5所示。通過對轉移規則改進對任務的配送方案分配結果可見，改正后的新方案，最終分配的方案避免了停線的情況，也降低了停線的風險。

表5 任務3結果（基于改進模型）

4 結束語

本文通過對有限轉運條件和儲存位置固定的生產流水線進行問題假設，并針對問題將有限的轉運能力分配到不同的生產工位，從而更好地利用優先的轉運能力；并針對有限的轉與能力，通過多模式優化和動態規劃模型，規劃物料倉儲點最少的儲存方案，采用蟻群算法進行了轉運方案的規劃，同時針對停線的風險，引入軟時間懲罰成本進行了針對性的優化，增添了路徑信息素不斷更新的機制。在貼近實際的同時，通過模擬任務需求表明該方法對于流水線的配送問題存在較好的解決能力。