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

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

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

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

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

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

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