萬 林，張志文，楊曉英

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

0 引言

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

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

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

1 問題描述

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

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

2 優(yōu)化模型

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

2.1 相關假設

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

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

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

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

4）倉庫備貨能力充足。

2.2 符號定義

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

j={j，k | j，k=1，2，…，m}：工位集合，車間內(nèi)工位數(shù)量為m；

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

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

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

V：配送小車裝載空間；

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

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

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

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

R：生產(chǎn)節(jié)拍；

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

cd：單位距離配送成本；

2.3 數(shù)學模型

目標函數(shù)：

相關約束：

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

3 蟻群算法設計

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

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

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

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

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

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

7）當?shù)h(huán)次數(shù)NK>NKmax，則停止迭代循環(huán)，輸出螞蟻走過的路徑和路徑總長度，此時最后一次迭代結果即為最優(yōu)配送路徑。

4 實例分析

4.1 實例數(shù)據(jù)

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

表1 工位段物料需求情況

4.2 實驗結果

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

圖1 倉庫到后箱組合區(qū)配送路徑

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

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

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

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

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

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

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

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

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

5 結束語

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