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

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

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

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

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