1、車輛路徑問題的離散細菌菌落算法摘 要：為了豐富解決車輛路徑優化問題的方 式，提出一種融入了局部搜索的離散型細菌菌落優化 算法。首先設計了算法的個體編碼方式和進化模式； 然后融入局部搜索方式來加速算法尋優的效率；最后 將該算法應用于帶時間窗的車輛路徑問題，并采用solomon 數據驗證，通過與其他算法進行比較，驗證 算法的可行性。關鍵詞：細菌菌落算法；車輛路徑問題；離散型 優化；局部搜索中圖分類號： TP312 隨著物流業在現代經濟中地位的上升，物流配送 系統的完善與發展已經成為眾多國內外學者研究的熱 點。車輛路徑優化問題是影響物流配送水平的重要因 素，合理的車輛行駛路徑可以在提高服務質量的同時

2、， 降低企業的運營成本。為此'Dantzig和Ramser于1959 年首次提出車輛路徑優化問題( Vehicle Routine Problem,簡稱VRP)。VRP問題已被證明是np難題， 經過廣大學者的多年研究，求 VRP 問題1 問題描述與數學模型車輛路徑中的客戶點作為細菌位置矢量的編碼，去除中間的編碼轉換，使得細菌可以直接在路徑問題 的解空間中對最優解進行優化搜索。所以，要用細菌 算法來解絕問題，就必須設計出合適的個體表達方式。 在文獻 6-8 中采用了 LOV 編碼方式，該規則先根據個 體位置分量在連續空間中的大小進行排序，并將排序 后的序列作為問題的一個可行解，因此算法本

3、質上還 是在連續空間中對最優解進行搜索。由于算法搜索空 間和實際排序問題的離散解空間之間不存在嚴格的對 應關系，所以個體在連續空間中所得到解的優劣性無 法通過 LOV 編碼直接反映到排序問題的解空間中。 車 輛路徑問題本質上也是一種排序問題，顯然這些算法 還是利用連續函數優化的方法解決這類問題，不可避 免地存在一定程度的不足。根據群集優化算法的基本原理，個體會向群體或 個體歷史最優位置移動，在連續空間中，可以通過簡 單的向量加減來實現優化，但無法直接將其運用到離 散空間中。因此，本文需要對離散個體的這種移動方 式重新定義。圖 1 反應的是適應值 fitness 與迭代次數的關系。 由圖可看出，

4、迭代初始時適應值隨迭代次數的增加有 所減小在 200 次時趨于平穩，此時算法有陷入局部最 優的可能，通過設置最大迭代數可突破這種狀態，跳 出局部最優進而找到更好的解。本文的迭代進程除了 可以設置精度要求和最大迭代次數來結束外，還可以 通過設置細菌壽命自然結束算法。圖 2 反應的是最大種群規模數 SN 與 k 之間的關 系。由圖可看出，種群數量的變化基本與培養基中細 菌菌落規模的變化一致。4 結束語 本文的離散細菌聚落優化算法，可以在解空間中 直接對最優解進行優化，并且具有一定的搜索能力和 穩定性。通過Solomon數據對算法進行驗證，與S-PSO 和 I-PSO 算法的對比中可以看出算法具有一

5、定的優越 性。但算法的各參數還有待進一步調試，算法的進化 機制有一定的進步空間，各種算法的間優點的融合必 然會提高解決問題的效率和精度。參考文獻：1 李琳，劉士新， 唐加福 .改進的蟻群算法求解帶 時間窗的車輛路徑問題J.控制與決策.2010 (09): 1379-1383.2 徐杰，黃德先 .基于混合粒子群算法的多目標車 輛路徑研究J.計算機集成制造系統，2007( 03): 573-584.3 蔣忠中，汪定偉 .物流配送車輛路徑優化的模糊規劃模型與算法J.系統仿真學報，2006 (11): 3301-3304.4 李明，楊成梧 .細菌菌落優化算法 J .控制理論 與應用， 2011( 02

6、)： 223-228.5 宋德羅，孔德福等 .一種離散細菌菌落優化算法 研究J.軟件導刊，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 SystemsJ， 20 1 2 ( 02): 254-267.7 PASSINO K M.Biomimicry of bacter

7、ial foraging for distributed optimization and controlJ.IEEE Control Systems Magazine， 2002( 03): 52-67.8 C.-H. Chen and C.-J. Ting，“A hybrid antcolony system for vehicle routing problem with time windows ， ” J. Eastern Asia Soc. Transp. Stud.， vol.6， pp.2822-2836， 2005.作者簡介:孔德福( 1987-)，男，安徽人，碩士 研究生，研究方向:智能控制、群集智能優化算法； 李明( 1977-)，男，江蘇人，博士，副教授，研究方向：智能控制、群集智能優化算法作者單位： 西南林業大學 機械與交通學院， 云南 昆