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

, , ,

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

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

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

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

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

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

0 引言

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

針對物流配送車輛路徑問題(VRP)，許多學(xué)者根據(jù)實際情況提出了解決方案：楊斯淇[2]針對生產(chǎn)車間VRP問題，建立了牽引車配送路線問題的數(shù)學(xué)模型，結(jié)合使用遺傳算法和插入法，對傳統(tǒng)的遺傳算法做了改進(jìn)，簡化了求解過程；任星球[1]建立了帶緩存區(qū)配送方式下的牽引車配送路徑模型，設(shè)計混合量子進(jìn)化算法解決裝配線VRP問題。針對裝配線物料配送帶最后期限時間窗的車輛路徑問題(VRPTD)的研究，徐智慧等人[3]建立了基于災(zāi)后物資供應(yīng)的VRPTD模型，采用遺傳算法求解，對應(yīng)急物資的調(diào)度有指導(dǎo)意義；趙思敏[4]考慮糧食應(yīng)急物流道路阻塞與時間的相關(guān)函數(shù)，建立以滿意度最大為目標(biāo)的VRPTD模型，通過遺傳算法與蟻群算法的演示程序?qū)蓚€算法進(jìn)行對比，結(jié)果表明相同的前提條件下，蟻群算法在求解速度、最優(yōu)解質(zhì)量和算法穩(wěn)定性等方面優(yōu)于遺傳算法。吳雋等[5]針對物流配送中的帶時間窗的車輛路徑問題(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)蟻群算法對裝配線VRPTD問題進(jìn)行了優(yōu)化研究，通過信息素動態(tài)更新、啟發(fā)函數(shù)ηij的改進(jìn)設(shè)計，使算法具有自適應(yīng)性，在一定程度上克服了傳統(tǒng)蟻群算法在遍歷尋優(yōu)過程中容易出現(xiàn)停滯和陷入局部最優(yōu)解的缺點。

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

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

(1)

模型滿足以下約束條件：

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

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

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

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

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

(2)

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

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

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

(3)

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

(4)

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

(5)

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

(6)

(7)

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

(8)

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

(9)

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

(10)

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

(11)

式中，u為運輸車的恒定速度；tij為運輸車從工位i到工位j的行駛時間。

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

2.1蟻群算法設(shè)計

(12)

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

(13)

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

(14)

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

(15)

2.2算法改進(jìn)

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

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

當(dāng)求得的最優(yōu)解在連續(xù)若干代內(nèi)沒有明顯改進(jìn)時，按式(16)對信息素?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)行信息素的全局更新以此來提高算法的收斂速度。

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

(17)

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

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

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

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

(1) 初始化參數(shù)。開始計算之前，需要對相關(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}中，對于螞蟻k(k=1,…,n)按照公式(12)計算下一個要服務(wù)的工位，直到所有螞蟻訪問完所有工位。

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

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

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

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

3.1算法測試

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

采用Matlab對改進(jìn)蟻群算法進(jìn)行測試，各個參數(shù)設(shè)置如下：螞蟻數(shù)目n=25，車輛數(shù)目m依具體情況而定，實例C101、R101、RC101分別對應(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。測試結(jié)果如表1所示。

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

3.2算例實現(xiàn)

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

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

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

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

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

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

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

由圖2可以看出，傳統(tǒng)的蟻群算法求解VRPTD問題時，最終求得的最短距離在2 700 m左右，在第10次迭代的時候，找到了最優(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次迭代的時候找到了最優(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)前后最短路徑對比，如圖6所示。

圖6 最短路徑前后對比

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

4 結(jié)論

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

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

[2]楊斯淇.基于遺傳算法的制造企業(yè)生產(chǎn)物流牽引車配送路線優(yōu)化研究[D].長春:吉林大學(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)蟻群算法的有時間窗車輛路徑優(yōu)化[J].湖北工業(yè)大學(xué)學(xué)報,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)化計算方法[M].北京:清華大學(xué)出版社,1999.

[8]石華瑀.改進(jìn)的蟻群算法在實際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é)報,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é)報:自然科學(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)隊領(lǐng)軍人才培育計劃(LJRC018)；河北省教育廳自然科學(xué)青年基金 (QN2014151)

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