車輛路徑問(wèn)題的離散細(xì)菌菌落算法

摘 要：為了豐富解決車輛路徑優(yōu)化問(wèn)題的方式，提出一種融入了局部搜索的離散型細(xì)菌菌落優(yōu)化算法。首先設(shè)計(jì)了算法的個(gè)體編碼方式和進(jìn)化模式；然后融入局部搜索方式來(lái)加速算法尋優(yōu)的效率；最后將該算法應(yīng)用于帶時(shí)間窗的車輛路徑問(wèn)題，并采用solomon數(shù)據(jù)驗(yàn)證，通過(guò)與其他算法進(jìn)行比較，驗(yàn)證算法的可行性。

關(guān)鍵詞：細(xì)菌菌落算法；車輛路徑問(wèn)題；離散型優(yōu)化；局部搜索

中圖分類號(hào)：TP312

隨著物流業(yè)在現(xiàn)代經(jīng)濟(jì)中地位的上升，物流配送系統(tǒng)的完善與發(fā)展已經(jīng)成為眾多國(guó)內(nèi)外學(xué)者研究的熱點(diǎn)。車輛路徑優(yōu)化問(wèn)題是影響物流配送水平的重要因素，合理的車輛行駛路徑可以在提高服務(wù)質(zhì)量的同時(shí)，降低企業(yè)的運(yùn)營(yíng)成本。為此，Dantzig和Ramser于1959年首次提出車輛路徑優(yōu)化問(wèn)題（Vehicle Routine Problem，簡(jiǎn)稱VRP）。VRP問(wèn)題已被證明是np難題，經(jīng)過(guò)廣大學(xué)者的多年研究，求VRP問(wèn)題

1 問(wèn)題描述與數(shù)學(xué)模型

車輛路徑中的客戶點(diǎn)作為細(xì)菌位置矢量的編碼，去除中間的編碼轉(zhuǎn)換，使得細(xì)菌可以直接在路徑問(wèn)題的解空間中對(duì)最優(yōu)解進(jìn)行優(yōu)化搜索。所以，要用細(xì)菌算法來(lái)解絕問(wèn)題，就必須設(shè)計(jì)出合適的個(gè)體表達(dá)方式。在文獻(xiàn)[6-8]中采用了LOV編碼方式，該規(guī)則先根據(jù)個(gè)體位置分量在連續(xù)空間中的大小進(jìn)行排序，并將排序后的序列作為問(wèn)題的一個(gè)可行解，因此算法本質(zhì)上還是在連續(xù)空間中對(duì)最優(yōu)解進(jìn)行搜索。由于算法搜索空間和實(shí)際排序問(wèn)題的離散解空間之間不存在嚴(yán)格的對(duì)應(yīng)關(guān)系，所以個(gè)體在連續(xù)空間中所得到解的優(yōu)劣性無(wú)法通過(guò)LOV編碼直接反映到排序問(wèn)題的解空間中。車輛路徑問(wèn)題本質(zhì)上也是一種排序問(wèn)題，顯然這些算法還是利用連續(xù)函數(shù)優(yōu)化的方法解決這類問(wèn)題，不可避免地存在一定程度的不足。

根據(jù)群集優(yōu)化算法的基本原理，個(gè)體會(huì)向群體或個(gè)體歷史最優(yōu)位置移動(dòng)，在連續(xù)空間中，可以通過(guò)簡(jiǎn)單的向量加減來(lái)實(shí)現(xiàn)優(yōu)化，但無(wú)法直接將其運(yùn)用到離散空間中。因此，本文需要對(duì)離散個(gè)體的這種移動(dòng)方式重新定義。

圖1反應(yīng)的是適應(yīng)值fitness與迭代次數(shù)的關(guān)系。由圖可看出，迭代初始時(shí)適應(yīng)值隨迭代次數(shù)的增加有所減小在200次時(shí)趨于平穩(wěn)，此時(shí)算法有陷入局部最優(yōu)的可能，通過(guò)設(shè)置最大迭代數(shù)可突破這種狀態(tài)，跳出局部最優(yōu)進(jìn)而找到更好的解。本文的迭代進(jìn)程除了可以設(shè)置精度要求和最大迭代次數(shù)來(lái)結(jié)束外，還可以通過(guò)設(shè)置細(xì)菌壽命自然結(jié)束算法。

圖2反應(yīng)的是最大種群規(guī)模數(shù)SN與k之間的關(guān)系。由圖可看出，種群數(shù)量的變化基本與培養(yǎng)基中細(xì)菌菌落規(guī)模的變化一致。

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

本文的離散細(xì)菌聚落優(yōu)化算法，可以在解空間中直接對(duì)最優(yōu)解進(jìn)行優(yōu)化，并且具有一定的搜索能力和穩(wěn)定性。通過(guò)Solomon數(shù)據(jù)對(duì)算法進(jìn)行驗(yàn)證，與S-PSO和I-PSO算法的對(duì)比中可以看出算法具有一定的優(yōu)越性。但算法的各參數(shù)還有待進(jìn)一步調(diào)試，算法的進(jìn)化機(jī)制有一定的進(jìn)步空間，各種算法的間優(yōu)點(diǎn)的融合必然會(huì)提高解決問(wèn)題的效率和精度。

參考文獻(xiàn)：

[1]李琳，劉士新，唐加福.改進(jìn)的蟻群算法求解帶時(shí)間窗的車輛路徑問(wèn)題[J].控制與決策.2010（09）：1379-1383.

[2]徐杰，黃德先.基于混合粒子群算法的多目標(biāo)車輛路徑研究[J].計(jì)算機(jī)集成制造系統(tǒng)，2007（03）：573-584.

[3]蔣忠中，汪定偉.物流配送車輛路徑優(yōu)化的模糊規(guī)劃模型與算法[J].系統(tǒng)仿真學(xué)報(bào)，2006（11）：3301-3304.

[4]李明，楊成梧.細(xì)菌菌落優(yōu)化算法[J].控制理論與應(yīng)用，2011（02）：223-228.

[5]宋德羅，孔德福等.一種離散細(xì)菌菌落優(yōu)化算法研究[J].軟件導(dǎo)刊，2013（12）：52-54.

[6]Yue-Jiao Gong， Jun Zhang， Ou Liu， et al. Optimizing the Vehicle Routing Problem With Time Windows： A Discrete Particle Swarm Optimization Approach .IEEE Transactions on Systems[J]，2012（02）：254-267.

[7]PASSINO K M.Biomimicry of bacterial foraging for distributed optimization and control[J].IEEE Control Systems Magazine， 2002（03）：52-67.

[8]C.-H. Chen and C.-J. Ting， “A hybrid ant colony system for vehicle routing problem with time windows，” J. Eastern Asia Soc. Transp. Stud. ，vol.6，pp.2822-2836，2005.

作者簡(jiǎn)介：孔德福（1987-），男，安徽人，碩士研究生，研究方向：智能控制、群集智能優(yōu)化算法；李明（1977-），男，江蘇人，博士，副教授，研究方向：智能控制、群集智能優(yōu)化算法。

作者單位：西南林業(yè)大學(xué) 機(jī)械與交通學(xué)院，云南昆明 650224；平頂山學(xué)院 電氣信息工程學(xué)院，河南平頂山 467000

基金項(xiàng)目：國(guó)家自然科學(xué)基金項(xiàng)目（31100424）；云南省自然科學(xué)基金項(xiàng)目（2009CD070）；云南省教育廳科學(xué)研究基金項(xiàng)目（2012J047）。