蟻群粒子群混合優(yōu)化算法研究與應(yīng)用.pdf

1、物流配送管理中的關(guān)鍵問題之一是車輛配送調(diào)度問題，對其進(jìn)行抽象建模即為帶時間窗的車輛路徑問題(Vehicle Routing Problem with Time Windows，VRPTW)。VRPTW與基本車輛路徑問題(VRP)相比，多了一個時間窗約束，VRPTW的描述如下:所有車輛均從配送中心出發(fā)，在完成對客戶的服務(wù)后，需要返回配送中心，而且每個客戶有且只能被服務(wù)一次，在服務(wù)客戶時，車輛必須處于客戶指定的時間窗內(nèi)，VRPTW的優(yōu)化目標(biāo)

2、是在滿足約束條件的情況下找到一條合理的路徑，使得完成全部需求所花費的總成本最小（總利潤最大）。在現(xiàn)實生活中，JIT生產(chǎn)調(diào)度、校車問題、工廠廢棄物回收問題、郵政配送問題、銀行運鈔車調(diào)度等許多物流配送管理問題均可抽象為VRPTW。
　　蟻群算法和粒子群算法都是最近十幾年研究出的基于群體智能的隨機化算法，蟻群算法作為一種啟發(fā)式算法，具有分布式計算、信息素正反饋機制、啟發(fā)式搜索等優(yōu)點。但是，當(dāng)求解組合優(yōu)化問題時，基本蟻群算法很容易產(chǎn)生過早

3、收斂或停滯現(xiàn)象。粒子群算法具有全局搜索機制，對于解決類似車輛調(diào)度問題和其他NP難問題等復(fù)雜數(shù)學(xué)問題，能在合理時間內(nèi)找到較優(yōu)解。但粒子群算法的傳統(tǒng)設(shè)計也經(jīng)常面臨早熟、局部搜索能力較差等問題，導(dǎo)致單純的粒子群算法耗費時間過長，在進(jìn)化后期搜索效率偏低。從上述對兩種算法的優(yōu)缺點分析可知，如果可以充分利用蟻群算法的信息素正反饋機制和粒子群算法的快速、全局收斂性，將兩種算法相結(jié)合，則能達(dá)到優(yōu)勢互補的效果。本文在此基礎(chǔ)上提出一種蟻群粒子群混合優(yōu)化算法

4、(Hybrid of Ant Colony and Particle Swarm OptimizationAlgorithm，HACPSO)，利用兩個隔離的種群Ⅰ和Ⅱ同時進(jìn)化的方式，有效避免了兩種算法的缺點，種群Ⅰ應(yīng)用蟻群算法豐富了解的多樣性，種群Ⅱ則應(yīng)用粒子群算法來強化進(jìn)化過程。種群Ⅰ還利用局部搜索、復(fù)制、重組和選擇等操作來保持種群廣泛搜索的能力，種群Ⅱ則依靠復(fù)制、局部優(yōu)化、交叉和選擇等操作以快速獲得高質(zhì)量解并頻繁更新得到的解。此外，