涂海寧，劉 佩，黃 劍

(1.南昌大學(xué)機電工程學(xué)院，南昌 330031; 2.溫州靜音汽車軸承有限公司，浙江 溫州 325000)

0 引言

制造業(yè)的整個生產(chǎn)過程都是圍繞著物料進行的，物料的準時準點配送是車間正常作業(yè)的前提。Yi C F提出的準時化生產(chǎn)系統(tǒng)指出，提高物料運輸效率、降低庫存可以有效地降低物流成本、加快生產(chǎn)節(jié)奏[1]。因此，在競爭日益激烈的市場環(huán)境下，企業(yè)要想以更低的成本快速響應(yīng)市場和客戶的生產(chǎn)需求，對物料配送這一環(huán)節(jié)進行優(yōu)化研究尤為必要。

物料配送優(yōu)化的核心是配送路徑的規(guī)劃，屬于帶容量限制的車輛尋跡問題，該問題的研究目的可以描述為在滿足約束條件的情況下，找到一條最優(yōu)路徑，從而實現(xiàn)如配送路程短、配送速度快和配送成本低等目標。目前用來解決路徑優(yōu)化問題的有以人工勢場法[2]和A～*算法[3]為代表的經(jīng)典算法，以及時下比較流行的遺傳算法[4]、蟻群算法[5]、神經(jīng)網(wǎng)絡(luò)算法[6]、粒子群算法[7]和模擬退火算法[8]等智能算法。其中蟻群算法非常適合解決路徑優(yōu)化問題，因其具有并行性、收斂速度快等特點，并且與其他啟發(fā)式算法結(jié)合程度高，但是在求解過程中，迭代一定次數(shù)后，算法容易陷入停滯狀態(tài)，同時求解過程中參數(shù)的確定也多憑經(jīng)驗而定，主觀性較強，因此，本文在針對物料配送路徑優(yōu)化問題進行研究的同時，提出了一種基于粒子群算法調(diào)參的混合蟻群算法：首先，引入動態(tài)調(diào)整慣性因子的粒子群算法以確定蟻群算法的初始參數(shù)，代替?zhèn)鹘y(tǒng)依靠經(jīng)驗取參的方法；其次，針對蟻群算法在算法中期容易停滯的現(xiàn)象，改進了蟻群算法的狀態(tài)轉(zhuǎn)移方程，增大探索新解的概率；最后，利用狼群分食原則對信息素更新規(guī)則進行改進，提高收斂速度。比較有效的解決了上述問題。

1 問題描述及其數(shù)學(xué)模型的構(gòu)建

某電器公司以生產(chǎn)中大型開關(guān)柜為主，客戶需求總的來說呈現(xiàn)出小批量、多品種的特點，使得生產(chǎn)工藝比較復(fù)雜，生產(chǎn)裝配過程中需要大量的零部件供應(yīng)。但是在實際生產(chǎn)中，由于生產(chǎn)工藝仍沿用著傳統(tǒng)的物料配送方式，補充零部件不及時，導(dǎo)致生產(chǎn)效率低下，因此亟需優(yōu)化物料配送方式。

車間物料配送需要滿足各工位對時間窗的需求，時間窗即時間段，表示物料只能在規(guī)定的時間段內(nèi)送達，太早導(dǎo)致線邊庫存積壓，太晚則不能滿足及時生產(chǎn)的需求。由于每個工位的生產(chǎn)節(jié)拍不同，同一時間需要的物料也不盡相同，同時由于送料車本身有容量限制，不能一次性滿足所有工位的物料需求，就需要在盡可能滿載的情況下準時給多個有需求的工位提供物料，并滿足最短送料總路徑、最少送料車的條件。

假設(shè)生產(chǎn)車間有N個工位，物料配送部門有V輛載重均為C的物料配送車，目標函數(shù)：

(1)

s.t.

(2)

(3)

(4)

(5)

(6)

tei≤ti≤tli(i=1,2,…,N)

(7)

其中，i,j為工位節(jié)點，為0時表示倉庫；v為送料車代號；dij為工位i到工位j的距離；xijv為決策變量，當(dāng)送料車v從工位i到工位j依次送料時為1，否則為0；yiv為決策變量，當(dāng)送料車v完成工位i的送料時為1，否則為0；ci表示第i個工位的物料需求量；ti為送料車到達工位i的時間，tei和tli分別為允許送料車到達工位i的最早時間和最晚時間。

式(1)為目標函數(shù)，表示物料配送路徑的最小值；式(2)表示每次由一輛送料車完成各個需求點的物料配送；式(3)表示送料車單次配送量不得超過其核載；式(4)表示所有送料車均從倉庫出發(fā)；式(5)表示送料車完成送料后返回倉庫；式(6)表示到達每個工位的送料車數(shù)與離開的相等，即網(wǎng)絡(luò)流平衡；式(7)為時間窗限制。

2 改進的蟻群算法

蟻群算法是模擬自然界中蟻群找尋最短路徑覓食的過程，螞蟻通過分泌信息素來實現(xiàn)蟻群內(nèi)的合作，其他螞蟻受其附近的信息素影響，傾向于沿著濃度更高的路徑覓食，從而影響到本身的行進路線。較短路徑上的螞蟻越來越多，該路徑上的信息素越來越濃，增大了其他螞蟻選擇該路線的可能性，如此反復(fù)，最終實現(xiàn)蟻群統(tǒng)一在最短路線上采食。

可以看出，影響螞蟻走向的是信息素和螞蟻自身決策，這種決策稱為啟發(fā)式信息，信息素使群體的結(jié)果收斂，啟發(fā)式信息作為個體對其他可能路徑的探索。螞蟻v從節(jié)點i移動到j(luò)的可能性稱為狀態(tài)轉(zhuǎn)移概率，在基本蟻群算法中，表示如下：

(8)

式中，t表示算法迭代次數(shù)，τij(t)表示路徑i到j(luò)上的信息素濃度，ηij(t)表示啟發(fā)式函數(shù)，α為信息素啟發(fā)因子，β是期望啟發(fā)因子；allowedv表示螞蟻可以選擇的節(jié)點集合，allowedv=N-tabuv,N為所有節(jié)點的集合，tabuv表示螞蟻已經(jīng)訪問過的節(jié)點。啟發(fā)式函數(shù)η和信息素濃度τ更新函數(shù)分別如下：

(9)

τij(t+1)=ρτij(t)+Δτij

(10)

式中，dij表示節(jié)點i到j(luò)的距離；ρ∈[0,1]表示信息素揮發(fā)系數(shù)，通常設(shè)τij(0)為常數(shù)，Δτij表示遍歷完所有節(jié)點后，所有螞蟻在節(jié)點i到j(luò)的路徑上所釋放信息素的剩余總量，即：

其中，Δτij表示第v只螞蟻在經(jīng)過路徑i到j(luò)時釋放的信息素，有蟻周模型、蟻量模型和蟻密模型三種更新方式：

2.1 選擇概率的改進

按照式(8)狀態(tài)轉(zhuǎn)移概率方程可以發(fā)現(xiàn)，整個蟻群搜索過程穩(wěn)定在一個比較大的范圍，這有利于算法迭代初期增大蟻群選擇較優(yōu)解的概率、加快算法的收斂速度，但是在算法的中期，搜索進入了停滯狀態(tài)，因為算法陷入了局部最優(yōu)的困境。因此，有必要增加螞蟻探索新解的可能性，從而逃離困境。

在螞蟻進行下一步路徑更新之前，進行一次隨機選擇，這個選擇決定螞蟻是按照狀態(tài)轉(zhuǎn)移概率來實現(xiàn)對已知信息的利用，還是無視信息進行新路徑的探索。引入概率閾值q0∈(0,1)，以此來決定利用和探索的占比，螞蟻選擇的下一節(jié)點則可以表示為：

式中，隨機變量q∈[0,1]，J表示按照基本蟻群算法的選擇概率螞蟻將要移動的下一節(jié)點。顯然，通過控制q0的值即可決定是利用累積信息還是搜索新路徑。在算法初期需要蟻群積累有效信息，實現(xiàn)較快的收斂速度，故可將q0的值調(diào)大；到了算法中期，通過將q0值設(shè)置為較小值來擴大搜索空間；到了后期，恢復(fù)q0為初始值，再次加快收斂速度。具體實現(xiàn)如下：

其中，NCmax為最大迭代次數(shù)。

2.2 基于狼群分食原則改進信息素更新

狼群捉住獵物之后，首先由強壯的狼分食，然后才輪到瘦弱的狼，這樣才能保證狼群擁有持續(xù)捕殺新獵物的能力?；谶@樣一種“先強后弱”的原則，對信息素更新模型進行優(yōu)化，在每次循環(huán)中選出局部最優(yōu)、最差路徑上的螞蟻，并確定其數(shù)量，增大最優(yōu)螞蟻的影響力，淘汰最差螞蟻釋放的信息素，以此來提高算法的收斂速度。得出的信息素濃度更新公式如下：

(11)

2.3 基于粒子群算法的參數(shù)優(yōu)化

蟻群算法模型中，參數(shù)的選擇對算法的收斂性和全局尋優(yōu)影響明顯，本文針對式(8)狀態(tài)轉(zhuǎn)移概率方程中的參數(shù)信息素啟發(fā)因子α和期望啟發(fā)因子β、式(10)信息素濃度更新模型中的信息素揮發(fā)系數(shù)ρ和蟻周模型中的信息素常量Q這4個參數(shù)進行選擇方法的優(yōu)化。在傳統(tǒng)蟻群算法中，參數(shù)組的確定多為依據(jù)實驗，而這四個參數(shù)聯(lián)系緊密，難以用數(shù)學(xué)模型進行統(tǒng)一描述，本文采用粒子群算法(Particle Swarm Optimization，PSO)進行參數(shù)組的最終確定。

粒子群算法是由埃伯哈特和肯尼迪在1995年提出的一種進化計算技術(shù)，具有易于實現(xiàn)、精度高、收斂速度快的特點[9]。粒子群算法通過觀察動物群體行為，共享群體中的個體信息，使整個集群的無序運動在問題解空間中逐漸演變?yōu)橛行?，從而得到較好的結(jié)果。PSO通過迭代在隨機解中進行尋優(yōu)，根據(jù)適應(yīng)度評估解的質(zhì)量，它通過遵循當(dāng)前最優(yōu)值來找到全局最優(yōu)解[10]。PSO速度和位置的更新公式如下：

(12)

(13)

在蟻群算法的參數(shù)優(yōu)化中，將粒子定義為四維坐標，初始坐標值分別對應(yīng)蟻群算法的待優(yōu)化參數(shù)α、β、ρ、Q，然后將尋優(yōu)后的坐標反饋給蟻群算法進行路徑規(guī)劃，將得到的最短路徑長度作為粒子群算法的評價函數(shù)。改進蟻群算法的詳細步驟如下：

步驟1：初始化全局參數(shù)，如迭代次數(shù)k、粒子的數(shù)量N、位置X、粒子速度Vi和上述其他系數(shù)；

步驟2：將蟻群算法的4個待確定參數(shù)α、β、ρ、Q粒子作為位置向量的4個維度，運行蟻群算法開始路徑規(guī)劃；

步驟3：將步驟2得到的最短路徑的倒數(shù)作為粒子群算法的評價函數(shù)，更新個體最優(yōu)值Pib和全局最優(yōu)值G；

步驟4：根據(jù)式(12)和式(13)更新粒子的位置和速度，其中慣性因子采用動態(tài)調(diào)整的方法，從而提高運行速度，調(diào)整方法如下：

式中，f為目標函數(shù)值，fmin表示粒子群的最小值，favg則為平均數(shù)；

步驟5：if迭代次數(shù)未完成，跳至步驟2；else，算法結(jié)束，全局最優(yōu)粒子的坐標即最佳參數(shù)。算法流程圖如圖1所示。

圖1 改進蟻群算法流程圖

3 實例驗證

以某電氣柜裝配車間的物料配送為例，采用第二章所述數(shù)學(xué)模型，利用第三章改進的蟻群算法，結(jié)合車間的現(xiàn)場數(shù)據(jù)進行配送路徑優(yōu)化，實驗數(shù)據(jù)見表1、表2。本次實驗基于MATLAB-R2014a進行編程，運行環(huán)境為：Windows 10(64位OS)，內(nèi)存8 GB，處理器為英特爾酷睿i5-6300HQ @2.30 GHz。

表1 物料需求表

表2 工位距離表

首先設(shè)置實驗參數(shù)。蟻群算法的循環(huán)次數(shù)取NCmax=100，螞蟻數(shù)量設(shè)置為節(jié)點的1.5倍，即15，α、β、ρ、Q由粒子群算法確定最終值，此次試驗設(shè)定范圍為：α∈[1,4]，β∈[3,4.5]，ρ∈[0.4,0.8]，Q∈[10,100]；粒子群算法中，粒子越多，搜索范圍越廣，越容易找到全局最優(yōu)解，但也會導(dǎo)致計算時間更長，本次實驗取25，c1、c2均取1.496 1，ωmax=0.95，ωmin=0.4。

粒子群算法迭代10次得出的蟻群算法最佳參數(shù)組合基本穩(wěn)定在一個范圍內(nèi)，最終取值為：α=1.15、β=3.46、ρ=0.87、Q=74.65。作為對比，將參數(shù)組分別應(yīng)用到改進蟻群算法和傳統(tǒng)蟻群算法中，運行10次，求出的結(jié)果見表3。

表3 兩種算法的最優(yōu)結(jié)果

10次試驗中，基本蟻群算法的最優(yōu)解有9次穩(wěn)定在920 m，最優(yōu)路徑為0-2-1-3-0-7-6-4-9-10-0-5-8-0，三次運輸?shù)难b載率分別為94.67%、95.17%、82.3%；改進蟻群算法的最優(yōu)解有7次穩(wěn)定在753 m，最優(yōu)路徑為0-2-1-3-0-5-6-4-0-7-9-10-8-0，三次運輸?shù)难b載率分別為94.67%、87.5%、90%，可以看出，改進的蟻群算法具有比基本算法更好的優(yōu)化能力。取第7次試驗的結(jié)果作為對比，改進算法和基本算法的收斂軌跡對比圖如圖2所示。

圖2 兩種算法的收斂軌跡

可以看出，迭代前期改進算法的收斂速度大于基本蟻群算法，在迭代到前中期后，基本蟻群算法結(jié)束了尋優(yōu)，而改進算法在陷入了一段停滯后搜索到了更優(yōu)的解。通過動態(tài)調(diào)整粒子群算法的慣性因子，改進算法運行的總時間減少至稍大于基本算法，符合工廠的實際生產(chǎn)需求。

4 結(jié)束語

本文基于多品種、小批量的生產(chǎn)特點建立了物料配送路徑優(yōu)化的數(shù)學(xué)模型，根據(jù)模型的特點提出一種改進的蟻群算法進行求解，算法改進了狀態(tài)轉(zhuǎn)移概率，并基于狼群分食的原則進行信息素的更新。結(jié)尾通過一個實例對模型和算法進行仿真，結(jié)果表明模型對解決實際路徑優(yōu)化問題是可行的，改進蟻群算法在實際工程應(yīng)用允許的時間延遲下，尋優(yōu)效果提升明顯，整體性能優(yōu)于傳統(tǒng)蟻群算法，具有一定的理論和實踐價值。