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

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

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

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

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