帶有隨機需求的容量約束弧路徑問題的算法研究.pdf

1、容量約束弧路徑問題(CapacitatedArcRoutingProblem,CARP)源于垃圾回收、掃雪、郵件投遞等實際問題,是弧路徑問題(ArcRoutingProblem,ARP)的一種擴展類型,在現(xiàn)實中具有非常重要的應(yīng)用價值,故近年來越來越受到研究者的關(guān)注。本文所研究的帶有隨機需求的容量約束弧路徑問題(CapacitatedArcRoutingProblemwithStochasticDemands,CARPSD),由于考慮每條

2、任務(wù)邊的需求是隨機的,因此屬于容量約束弧路徑問題的一種推廣形式。該類問題是NP-hard問題,傳統(tǒng)的算法如分支定界方法等無法求解實際中出現(xiàn)的大規(guī)模例子,而元啟發(fā)式算法因其內(nèi)在的自適應(yīng)性、并行性、穩(wěn)定性等強大優(yōu)點有望能解決大型的容量約束弧路徑問題。
　　本文以CARPSD為研究對象,在廣泛查閱國內(nèi)外文獻的基礎(chǔ)上,深入探索該問題的求解方法,提出了求解CARPSD問題的分割算法、自適應(yīng)局部搜索算法和自適應(yīng)領(lǐng)域搜索算法,有效地解決CARP

3、SD問題,主要研究工作和成果如下:
　　首先,對基本CARP問題進行了描述,并引入了帶有隨機需求的CARP問題(CARPSD),給出該問題的數(shù)學(xué)模型,進行了相關(guān)的理論證明,完成對問題可行性的基本假設(shè)。
　　其次,根據(jù)CARPSD問題的特性,提出一種隨機路徑掃描(StochasticPathScanning,SPS)與分割算法來建立隨機條件下的可行解及最短路徑,其中設(shè)計的分割算法對可行解進行重新排序分割,計算所有可能情況下的最

4、小費用。以最小費用的期望作為最終的判斷指標,記錄并保存從車場到當(dāng)前弧的最小期望費用,直到所有需求弧服務(wù)完畢。
　　最后,基于算法的自適應(yīng),利用啟發(fā)式算法極強的魯棒性和內(nèi)在并行機制等優(yōu)點進一步求得問題的近似最優(yōu)解。但由于基本啟發(fā)式算法例如遺傳算法,模擬退火算法、禁忌搜索算法在求解過程中易限于局部最優(yōu),因此設(shè)計出兩種相對有效的啟發(fā)式算法:自適應(yīng)局部搜索算法、自適應(yīng)領(lǐng)域搜索算法。數(shù)值試驗結(jié)果表明,兩種算法在該類問題的表現(xiàn)優(yōu)于以往所設(shè)計的