, , ,

(石家莊鐵道大學(xué) 機(jī)械工程學(xué)院，河北 石家莊 050043)

基于改進(jìn)蟻群算法的裝配線VRPTD問題研究

劉凱,牛江川,申永軍,韓彥軍

(石家莊鐵道大學(xué) 機(jī)械工程學(xué)院，河北 石家莊 050043)

采用改進(jìn)蟻群算法求解了裝配線物料配送的VRPTD問題(帶最后期限時(shí)間窗的車輛路徑問題)。通過信息素動(dòng)態(tài)更新設(shè)計(jì)，使改進(jìn)蟻群算法具有自適應(yīng)性，克服了傳統(tǒng)蟻群算法在遍歷尋優(yōu)過程中容易出現(xiàn)停滯和陷入局部最優(yōu)解的缺點(diǎn)。通過進(jìn)一步對(duì)啟發(fā)函數(shù)可見度進(jìn)行改進(jìn)設(shè)計(jì)，提高了算法的全局搜索能力。仿真結(jié)果表明，改進(jìn)蟻群算法可以很好地求解裝配線VRPTD問題，這對(duì)實(shí)際應(yīng)用有一定的參考價(jià)值。

改進(jìn)蟻群算法；裝配線物料配送；帶最后期限時(shí)間窗的車輛路徑問題

0 引言

在準(zhǔn)時(shí)化生產(chǎn)模式下，需要對(duì)裝配線上的各類物料實(shí)施多品種、小批量的準(zhǔn)時(shí)配送。在正確的時(shí)間，將正確的物料配送至正確的工位是保證裝配線順利進(jìn)行的關(guān)鍵[1]。

針對(duì)物流配送車輛路徑問題(VRP)，許多學(xué)者根據(jù)實(shí)際情況提出了解決方案：楊斯淇[2]針對(duì)生產(chǎn)車間VRP問題，建立了牽引車配送路線問題的數(shù)學(xué)模型，結(jié)合使用遺傳算法和插入法，對(duì)傳統(tǒng)的遺傳算法做了改進(jìn)，簡(jiǎn)化了求解過程；任星球[1]建立了帶緩存區(qū)配送方式下的牽引車配送路徑模型，設(shè)計(jì)混合量子進(jìn)化算法解決裝配線VRP問題。針對(duì)裝配線物料配送帶最后期限時(shí)間窗的車輛路徑問題(VRPTD)的研究，徐智慧等人[3]建立了基于災(zāi)后物資供應(yīng)的VRPTD模型，采用遺傳算法求解，對(duì)應(yīng)急物資的調(diào)度有指導(dǎo)意義；趙思敏[4]考慮糧食應(yīng)急物流道路阻塞與時(shí)間的相關(guān)函數(shù)，建立以滿意度最大為目標(biāo)的VRPTD模型，通過遺傳算法與蟻群算法的演示程序?qū)蓚€(gè)算法進(jìn)行對(duì)比，結(jié)果表明相同的前提條件下，蟻群算法在求解速度、最優(yōu)解質(zhì)量和算法穩(wěn)定性等方面優(yōu)于遺傳算法。吳雋等[5]針對(duì)物流配送中的帶時(shí)間窗的車輛路徑問題(VRPTW)，提出了一種改進(jìn)的最大最小蟻群算法，引入了局部搜索策略二次優(yōu)化(2-opt)，算法尋優(yōu)過程得到了優(yōu)化；Du et al[6]提出了貪婪策略與蟻群算法相結(jié)合的自適應(yīng)蟻群算法，效果優(yōu)于傳統(tǒng)的自適應(yīng)蟻群算法。

本文采用改進(jìn)蟻群算法對(duì)裝配線VRPTD問題進(jìn)行了優(yōu)化研究，通過信息素動(dòng)態(tài)更新、啟發(fā)函數(shù)ηij的改進(jìn)設(shè)計(jì)，使算法具有自適應(yīng)性，在一定程度上克服了傳統(tǒng)蟻群算法在遍歷尋優(yōu)過程中容易出現(xiàn)停滯和陷入局部最優(yōu)解的缺點(diǎn)。

1 牽引車物料配送的VRPTD數(shù)學(xué)模型

已知緩存區(qū)、工位和道路條件，在每個(gè)工位段需求和服務(wù)時(shí)間窗已知的條件下，對(duì)m輛額定載重量為Q(單位kg)的運(yùn)輸車輛，n個(gè)工位，確定運(yùn)輸車輛的最佳配送路線。設(shè)n個(gè)工位集合V={v1,v2,…,vn}，V中兩個(gè)工位集合D={Dij|vi，vj∈V}，工位i、j坐標(biāo)分別為(xi,yi)、(xj,yj)，兩工位間距離為

(1)

模型滿足以下約束條件：

(1) 物料配送不考慮車間內(nèi)通行路線的限制，各個(gè)工位間的距離為理想的直線距離。

(2) 每個(gè)工位的需求量均不超過運(yùn)輸車輛的額定載重量，即max(qi)≤Q，其中第i個(gè)工位的需求量為qi(i=1,…,n)，qi的單位為kg。

(3) 每一個(gè)工位所需的物料只能由一臺(tái)車配送完成，每輛車可以配送多個(gè)工位，且所有車輛配送路線均起止于緩存區(qū)。

(4) 每個(gè)工位都有最后服務(wù)期限的時(shí)間窗[0,bi]，物料配送必須在此時(shí)間窗內(nèi)完成，否則將受到懲罰。

在建立數(shù)學(xué)模型之前，需要確定緩存區(qū)使用車輛數(shù)，使用文獻(xiàn)[1]中的公式來(lái)確定需要的車輛數(shù)m

(2)

式中，qi(i=1,…,n)為第i個(gè)工位的需求量；Q為車輛的額定載重量；a取0.85，約束條件越多，車輛裝卸物料越復(fù)雜，a值越小[7]。

引入0-1變量，yik表示工位i所需要的物料由運(yùn)輸車k配送。當(dāng)工位i由運(yùn)輸車k配送時(shí)yik=1，否則yik=0。

在滿足上述約束條件下，確定運(yùn)輸車輛的最佳配送路線，使總行駛距離最小，確定總行駛距離為目標(biāo)函數(shù)f，數(shù)學(xué)模型如下

(3)

式中，當(dāng)運(yùn)輸車k從i行駛到j(luò)時(shí)xijk=1，否則為0。并滿足以下約束條件

(4)

式中，下標(biāo)0表示緩存區(qū)，式(4)保證了有m輛運(yùn)輸車從緩存區(qū)出發(fā)，進(jìn)行物料配送。

(5)

式(5)保證了每一個(gè)工位都有一輛車負(fù)責(zé)物料配送。

(6)

(7)

式(6)、式(7)保證每個(gè)工位只有一輛車執(zhí)行物料配送任務(wù)。

(8)

式中，Q為每輛車的額定載重量。車輛的運(yùn)送總質(zhì)量應(yīng)不超過車輛的最大載重，式(8)保證每條路徑上車輛的裝載量約束。

(9)

式中，p為n個(gè)工位中任意一個(gè)工位，式(9)保證每輛車到達(dá)某工位后仍從該工位離開。

(10)

式中，sik為運(yùn)輸車k在sik時(shí)刻配送物料至工位i，sik∈[0,bi]；K為很大的正數(shù)。式(10)保證車輛不早于sik+tij到達(dá)工位j。

(11)

式中，u為運(yùn)輸車的恒定速度；tij為運(yùn)輸車從工位i到工位j的行駛時(shí)間。

2 VRPTD問題蟻群算法的設(shè)計(jì)與改進(jìn)

2.1蟻群算法設(shè)計(jì)

(12)

式中，信息啟發(fā)因子α和期望啟發(fā)因子β分別表示信息素和期望值的相對(duì)重要程度，α值越大，表示信息素濃度在狀態(tài)轉(zhuǎn)移中起的作用越大，同樣β值越大，表示啟發(fā)函數(shù)在狀態(tài)轉(zhuǎn)移中起的作用越大，即螞蟻會(huì)以較大的概率轉(zhuǎn)移到距離較短的工位。

(13)

式中，allowedk為螞蟻k下一步能選擇的工位集合；V={v1,v2,…,vn}為工位集合。開始時(shí)，allowedk中有(n-1)個(gè)元素，隨著迭代次數(shù)的增加，allowedk中的元素逐漸減少，直至為空，即表示此時(shí)螞蟻已遍歷完集合中所有工位。禁忌表Tabuk存儲(chǔ)并記錄螞蟻k走過的工位。

(14)

螞蟻每完成一次循環(huán)，需要考慮信息素的揮發(fā)，螞蟻在釋放信息素的同時(shí)，各個(gè)工位路徑上的信息素也在逐漸消失，需要實(shí)時(shí)更新各個(gè)工位路徑上的信息素[10]。

(15)

2.2算法改進(jìn)

2.2.1 信息素動(dòng)態(tài)更新改進(jìn)

蟻群算法中信息素?fù)]發(fā)系數(shù)的大小直接關(guān)系到蟻群算法的全局搜索能力和收斂速度[11]。當(dāng)問題規(guī)模較大時(shí)，由于信息素?fù)]發(fā)系數(shù)的存在，從未被搜索到的路徑上的信息素濃度會(huì)逐漸減小到接近于0。當(dāng)信息素?fù)]發(fā)系數(shù)過小時(shí)，路徑上的信息素濃度增大會(huì)使以前搜索過的路徑再次被選擇的可能性增大，從而降低了算法的全局搜索能力，增大信息素?fù)]發(fā)系數(shù)雖然可以提高算法的全局搜索能力，但又會(huì)使算法的搜索速度降低[8]。因此，通過改變信息素?fù)]發(fā)系數(shù)，提出了一種信息素?fù)]發(fā)系數(shù)自適應(yīng)變化的蟻群算法，希望通過自適應(yīng)的改變信息素?fù)]發(fā)系數(shù)提高算法的全局搜索能力。

當(dāng)求得的最優(yōu)解在連續(xù)若干代內(nèi)沒有明顯改進(jìn)時(shí)，按式(16)對(duì)信息素?fù)]發(fā)系數(shù)進(jìn)行更新。

(16)

式中，信息素?fù)]發(fā)系數(shù)ρ應(yīng)在初始給定最大值和最小值之間取值；參數(shù)0.95是信息素?fù)]發(fā)系數(shù)更新系數(shù)，每次下降5%，直到小于信息素?fù)]發(fā)系數(shù)的最小值ρmin，ρmin可以防止因信息素?fù)]發(fā)系數(shù)過小而降低算法的收斂速度。

本算法與基本蟻群算法相比取消了信息素的局部更新即二次優(yōu)化2-opt操作，而是進(jìn)行信息素的全局更新以此來(lái)提高算法的收斂速度。

2.2.2 啟發(fā)函數(shù)的改進(jìn)

(17)

改進(jìn)后的可見度，有助于提高算法解決帶最后期限時(shí)間窗的車輛路徑問題的全局性。

2.3算法實(shí)現(xiàn)流程

基于上述設(shè)計(jì)，改進(jìn)后的蟻群算法求解VRPTD問題步驟如下，其算法流程如圖1所示。

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

(1) 初始化參數(shù)。開始計(jì)算之前，需要對(duì)相關(guān)參數(shù)進(jìn)行初始化，如螞蟻數(shù)目n、車輛數(shù)目m、重要度系數(shù)α、能見度系數(shù)β、權(quán)重系數(shù)γ、揮發(fā)系數(shù)ρ、最小揮發(fā)系數(shù)ρmin、最大迭代次數(shù)NC_max、車輛載重量Q、車輛裝載量load_w等。

(2) 構(gòu)建解空間。將未服務(wù)的工位放入V={v1,v2,…,vn}中，對(duì)于螞蟻k(k=1,…,n)按照公式(12)計(jì)算下一個(gè)要服務(wù)的工位，直到所有螞蟻訪問完所有工位。

(3) 容量和時(shí)間判斷。設(shè)置螞蟻的禁忌表索引號(hào)k=1，每服務(wù)一個(gè)工位，判斷容量和時(shí)間是否符合要求，符合則將服務(wù)過的工位置于當(dāng)前tabu(k)中，不符合則跳轉(zhuǎn)到第2步。

(4) 更新信息素。計(jì)算各個(gè)螞蟻?zhàn)哌^的路徑長(zhǎng)度，計(jì)算當(dāng)前迭代次數(shù)中的最短路徑。同時(shí)根據(jù)公式(15)、公式(16)、公式(16)對(duì)各個(gè)工位路徑上的信息素進(jìn)行更新。

(5) 判斷終止條件。當(dāng)?shù)?jì)數(shù)器NC

3 算法測(cè)試及結(jié)果分析

3.1算法測(cè)試

為了測(cè)試改進(jìn)后的蟻群算法求解VRPTD問題的效果，分別用基本蟻群算法和改進(jìn)后的蟻群算法求解25個(gè)客戶點(diǎn)的Solomon基準(zhǔn)實(shí)例[12]。Solomon例庫(kù)有C型、R型、RC型3種，它們之間的區(qū)別在于客戶點(diǎn)坐標(biāo)的設(shè)置方式和時(shí)間窗的設(shè)置不同。C型例庫(kù)按照結(jié)構(gòu)性方式來(lái)設(shè)置客戶坐標(biāo)，R型例庫(kù)則是以均勻分布的方式來(lái)設(shè)置客戶坐標(biāo)，而RC型例庫(kù)則是按以上兩種例庫(kù)混合的方式來(lái)設(shè)置客戶坐標(biāo)[13-14]。

采用Matlab對(duì)改進(jìn)蟻群算法進(jìn)行測(cè)試，各個(gè)參數(shù)設(shè)置如下：螞蟻數(shù)目n=25，車輛數(shù)目m依具體情況而定，實(shí)例C101、R101、RC101分別對(duì)應(yīng)的車輛數(shù)目為3、2、15，重要度系數(shù)α=3，能見度系數(shù)β=2，權(quán)重系數(shù)γ=2，揮發(fā)系數(shù)ρ=0.5，最小揮發(fā)系數(shù)ρmin=0.05，最大迭代次數(shù)NC_max=100，車輛載重量Q=200，車輛裝載量load_w=0。測(cè)試結(jié)果如表1所示。

表1 Solomon C型、R型、RC數(shù)據(jù)集測(cè)試結(jié)果對(duì)比

3.2算例實(shí)現(xiàn)

由于Solomon測(cè)試?yán)龓?kù)中，C型數(shù)據(jù)集、R型數(shù)據(jù)集、RC型數(shù)據(jù)集每個(gè)工位處的服務(wù)時(shí)間分別為90、10、10，不是隨機(jī)變化的。故采用如下算例，進(jìn)一步對(duì)改進(jìn)算法的有效性進(jìn)行驗(yàn)證。具體算例數(shù)據(jù)如表2所示。

表2 某裝配線工位點(diǎn)數(shù)據(jù)

螞蟻數(shù)目n=31，車輛數(shù)目m=9，算法其它初始設(shè)置與上例相同。經(jīng)過仿真分析，分析結(jié)果如表3所示。

表3 算例仿真結(jié)果對(duì)比

采用基本蟻群算法，迭代過程中最短距離、平均距離變化和路徑規(guī)劃結(jié)果，如圖2和圖3所示。

圖2 基本蟻群算法最短距離、平均距離變化

圖3 基本蟻群算法路徑規(guī)劃結(jié)果

由圖2可以看出，傳統(tǒng)的蟻群算法求解VRPTD問題時(shí)，最終求得的最短距離在2 700 m左右，在第10次迭代的時(shí)候，找到了最優(yōu)解，求解效率較高。由圖3可以看出，基本蟻群算法求得的路徑規(guī)劃結(jié)果有重復(fù)的路徑出現(xiàn)，求解結(jié)果還有優(yōu)化的空間。

采用改進(jìn)蟻群算法，迭代過程中最短距離、平均距離變化和路徑規(guī)劃結(jié)果，如圖4和圖5所示。

圖4 改進(jìn)蟻群算法最短距離、平均距離變化

圖5 改進(jìn)蟻群算法路徑規(guī)劃結(jié)果

由圖4可以看出，改進(jìn)后的蟻群算法求得的最短距離在2 600 m左右，縮短了近100 m，第20次迭代的時(shí)候找到了最優(yōu)解，尋優(yōu)效率沒有改進(jìn)前高，但尋優(yōu)結(jié)果較改進(jìn)前好。由圖5可以看出，改進(jìn)后蟻群算法求得的路徑規(guī)劃結(jié)果避免了重復(fù)路徑的出現(xiàn)，進(jìn)一步優(yōu)化了求解結(jié)果。

算法改進(jìn)前后最短路徑對(duì)比，如圖6所示。

圖6 最短路徑前后對(duì)比

由圖6知，改進(jìn)后的蟻群算法求解結(jié)果優(yōu)于基本蟻群算法求解結(jié)果。迭代初期，改進(jìn)后的蟻群算法尋優(yōu)效率并沒有傳統(tǒng)蟻群算法高，但是隨著迭代次數(shù)的增加，改進(jìn)后的蟻群算法由于對(duì)當(dāng)前最優(yōu)路徑上信息素的充分利用，擴(kuò)大了解的搜索空間，提高了算法的全局遍歷性，并沒有陷入局部最優(yōu)解的死循環(huán)。

4 結(jié)論

通過對(duì)傳統(tǒng)蟻群算法信息素更新和可見度設(shè)計(jì)方面進(jìn)行改進(jìn)，求解裝配線物料配送優(yōu)化問題。并通過實(shí)例對(duì)算法改進(jìn)前后進(jìn)行了對(duì)比分析，分析結(jié)果表明，改進(jìn)后的蟻群算法在求解裝配線VRPTD問題時(shí)不僅對(duì)解決蟻群算法的停滯問題非常有效，而且提高了運(yùn)算精度，增大了收斂到全局最優(yōu)解的可能性,有效地解決搜索停滯、早熟問題，對(duì)生產(chǎn)實(shí)際有一定的指導(dǎo)意義。

[1]任星球.制造企業(yè)裝配線物料準(zhǔn)時(shí)配送優(yōu)化研究[D].杭州:浙江工業(yè)大學(xué),2011.

[2]楊斯淇.基于遺傳算法的制造企業(yè)生產(chǎn)物流牽引車配送路線優(yōu)化研究[D].長(zhǎng)春:吉林大學(xué),2008.

[3]Zhihui X, Zhongning F. Study on emergency response of vehicle routing based on multi-commodity dispatch VRPTD model[C]//Transportation, Mechanical, and Electrical Engineering (TMEE),2011 International Conference on. IEEE,2011: 568-571.

[4]趙思敏.糧食應(yīng)急物流系統(tǒng)的網(wǎng)絡(luò)構(gòu)建及路徑優(yōu)化[D].武漢:武漢理工大學(xué),2011.

[5]吳雋,陳定方,李文鋒,等.基于改進(jìn)蟻群算法的有時(shí)間窗車輛路徑優(yōu)化[J].湖北工業(yè)大學(xué)學(xué)報(bào),2008(3):9-12.

[6]Du D P, Zu Y R. Ubiquitous Computing Application and Wireless Sensor [M]. Berlin : Springer Netherlands,2015:663-670.

[7]邢文訓(xùn),謝金星.現(xiàn)代優(yōu)化計(jì)算方法[M].北京:清華大學(xué)出版社,1999.

[8]石華瑀.改進(jìn)的蟻群算法在實(shí)際VRP中的應(yīng)用研究[D].濟(jì)南:山東大學(xué),2012:33-34.

[9]Yi Y, Lin X, Sheng K, et al. Intelligent computing theories and methodologies[C].Berlin:[s.n.],2015:11-22.

[10]段海濱.蟻群算法原理及應(yīng)用[M].北京:科學(xué)出版社,2005.

[11]吳小菁.基于揮發(fā)系數(shù)的自適應(yīng)蟻群算法[J].福建金融管理干部學(xué)院學(xué)報(bào),2010,1(1):54-58.

[12]Solomon Marius M. Algorithms for the vehicle routing and scheduling problem with time window con straints[J]. Operations Research,1987,35(2):254-265.

[13]Abdulkader M M S, Gajpal Y, Elmekkawy T Y. Hybridized ant colony algorithm for the multi compartment vehicle routing problem[J]. Applied Soft Computing, 2015, 37:196-203.

[14]劉凱,牛江川,申永軍,等.基于遺傳粒子群算法的堆垛機(jī)作業(yè)路徑優(yōu)化[J].石家莊鐵道大學(xué)學(xué)報(bào):自然科學(xué)版,2016,29(2):67-71.

StudyofAssemblyLineVRPTDProblemBasedonImprovedAntColonyAlgorithm

LiuKai,NiuJiangchuan,ShenYongjun,HanYanjun

(School of Mechanical Engineering, Shijiazhuang Tiedao University, Shijiazhuang 050043, China)

The distribution of materials for VRPTD(assembly lines with the deadline time windows vehicle routing problem) is studied by improved ant colony algorithm. By pheromone dynamically updated design, the improved ant algorithm is adaptive, which overcomes the shortcomings of the traditional ant colony optimization algorithm that traversal process is prone to stagnation and falling into local optima. The design of the heuristic function of the visibility, which based on further improvement, had improved the global search capability. The simulation results show that the algorithm can solve the problem of assembly line VRPTD, which has a certain reference value for practical application.

improved ant colony algorithm;assembly line material feeding;VRPTD

TH165.1

： A

： 2095-0373(2017)03-0055-07

2017-03-26責(zé)任編輯:車軒玉

10.13319/j.cnki.sjztddxxbzrb.2017.03.11

河北省自然科學(xué)基金(F2013210109)；河北省高等學(xué)校創(chuàng)新團(tuán)隊(duì)領(lǐng)軍人才培育計(jì)劃(LJRC018)；河北省教育廳自然科學(xué)青年基金 (QN2014151)

劉凱(1988-),男，碩士研究生,主要從事企業(yè)信息化與協(xié)調(diào)管理技術(shù)的研究。E-mail: lk1256229856@126.com 劉 凱,牛江川, 申永軍,等.基于改進(jìn)蟻群算法的裝配線VRPTD問題研究[J].石家莊鐵道大學(xué)學(xué)報(bào):自然科學(xué)版,2017,30(3):55-61.