基于元啟發(fā)式方法對限量弧路由問題的求解.pdf

1、本文所研究的限量弧路由問題(Capacitated Arc Routing Problem，CARP)是一個經(jīng)典的組合優(yōu)化問題。它在現(xiàn)實中具有非常廣泛的應用，如冬季撒鹽路由、城市垃圾清理、信件投遞等現(xiàn)實應用均能夠抽象為限量弧路由問題?；谏鲜鲈?，該問題在近年來越來越受到研究者的關(guān)注。然而，由于其問題本身的復雜性，現(xiàn)有的解決方法均無法在對問題規(guī)模的多項式時間內(nèi)找到全局最優(yōu)解。因此，我們考慮利用近似算法中的元啟發(fā)式方法(Meta-heur

2、istics)來對問題進行求解以得到盡可能逼近最優(yōu)解的次優(yōu)解。由限量弧路由問題的基本模型開始，我們設計了一個問題相關(guān)的全局修復算子。該全局修復算子能夠很好地嵌入任意基于搜索的限量弧路由問題優(yōu)化算法并提高其搜索效率。
　　 由整個算法框架角度出發(fā)，模因演算法(Memetic Algorithms)在許多從實際出發(fā)的離散問題與組合優(yōu)化問題上均得到了成功。它可看作是傳統(tǒng)演化算法與局部搜索相結(jié)合而構(gòu)成的混合算法框架。模因演算法中包含的局

3、部搜索所帶來的高選擇壓力使其能夠比傳統(tǒng)的演化算法更快地找到質(zhì)量更好的解。當應用于限量弧路由問題時，我們發(fā)現(xiàn)傳統(tǒng)的局部搜索(基于傳統(tǒng)的小步長搜索算子的局部搜索)依舊難以對具有搜索吸引力的區(qū)域有效地進行開發(fā)，因而面臨解無法跳出局部最優(yōu)的風險?；谏鲜鲈?，我們提出了一個基于擴展鄰域搜索的模因演算法以幫助這樣的解跳出當前局部最優(yōu)從而到達新的更好的局部最優(yōu)解。經(jīng)驗證該算法能夠得到質(zhì)量遠高于當前性能最優(yōu)算法的解，盡管其所需計算消耗更大。
　

4、　 接下來，我們進一步研究了限量弧路由問題的兩種更為復雜的模型：周期性限量弧路由問題與多目標限量弧路由問題。周期性限量弧路由問題為基本限量弧路由問題從單時期至多時期的一個擴展模型。該問題引入了最小化整個周期內(nèi)所需車輛數(shù)目這一主要優(yōu)化目標，而在基本限量弧路由問題中的唯一優(yōu)化目標，即最小化回路總消耗，則變?yōu)榇我獌?yōu)化目標。基于問題主要優(yōu)化目標對傳統(tǒng)搜索算子的敏感性較低這一現(xiàn)象，我們提出了一個將主要目標與次要目標分離進行優(yōu)化的算法。具體來說，

5、我們設計了一個專門優(yōu)化主要目標的特定算子并將其在算法中的局部搜索之前進行調(diào)用。通過實驗我們得出，在解決具有對傳統(tǒng)搜索算子敏感性較低目標的問題時，將其與其余敏感性較高的目標分離進行優(yōu)化將能夠得到更好的結(jié)果。
　　 多目標限量弧路由問題同時具有多目標優(yōu)化問題與組合優(yōu)化問題所導致的難度，這使其成為一個極具挑戰(zhàn)性的問題。基于在多目標限量弧路由問題環(huán)境下對現(xiàn)有演化多目標優(yōu)化策略的性能評估結(jié)果，我們將單目標限量弧路由優(yōu)化方法與演化多目標優(yōu)化

6、策略的優(yōu)勢進行了有機地結(jié)合，并通過實驗驗證了這樣的組合方式在性能上能夠同時超越簡單地擴展單目標限量弧路由算法與直接應用現(xiàn)有多目標演化算法框架這兩種對于多目標限量弧路由問題的解決方法。
　　 最后，我們對非確定限量弧路由問題進行了研究。至今為止，關(guān)于限量弧路由問題的大部分研究工作均集中于關(guān)注確定環(huán)境下的限量弧路由問題。在確定性限量弧路由問題中，包括任務需求量與頂點之間經(jīng)過消耗等問題參數(shù)均為已知常數(shù)。然而，在許多現(xiàn)實應用問題中，這些