基于改進(jìn)蟻群算法的物料配送方法

涂海寧，劉 佩，黃 劍

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

0 引言

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

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

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

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

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

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

(1)

s.t.

(2)

(3)

(4)

(5)

(6)

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

(7)

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

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

2 改進(jìn)的蟻群算法

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

可以看出，影響螞蟻?zhàn)呦虻氖切畔⑺睾臀浵佔(zhàn)陨頉Q策，這種決策稱為啟發(fā)式信息，信息素使群體的結(jié)果收斂，啟發(fā)式信息作為個(gè)體對(duì)其他可能路徑的探索。螞蟻v從節(jié)點(diǎn)i移動(dòng)到j(luò)的可能性稱為狀態(tài)轉(zhuǎn)移概率，在基本蟻群算法中，表示如下：

(8)

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

(9)

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

(10)

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

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

2.1 選擇概率的改進(jìn)

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

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

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

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

2.2 基于狼群分食原則改進(jìn)信息素更新

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

(11)

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

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

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

(12)

(13)

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

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

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

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

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

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

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

圖1 改進(jìn)蟻群算法流程圖

3 實(shí)例驗(yàn)證

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

表1 物料需求表

表2 工位距離表

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

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

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

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

圖2 兩種算法的收斂軌跡

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

4 結(jié)束語(yǔ)

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