帶有隨機(jī)需求的容量約束弧路徑問(wèn)題的算法研究.pdf

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

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

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

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