帶時間約束條件的弧路徑問題研究.pdf

1、帶時間約束條件的弧路徑問題屬于帶容量限制弧路徑優(yōu)化問題（CARP）的一個擴(kuò)展，在CARP的基礎(chǔ)上對某些關(guān)鍵路徑做出了時間限制，這種擴(kuò)展有著實際的應(yīng)用意義，比如在某些城市主干道中只能在某些時間段內(nèi)才允許對其進(jìn)行服務(wù)，這就要求在完成全部路徑規(guī)劃的同時，優(yōu)先保證這些路徑的服務(wù)時間。在不能滿足每條路徑都能按照其約束時間進(jìn)行服務(wù)時，優(yōu)先選擇具有最小時間延誤代價的路徑規(guī)劃方案來進(jìn)行，具體延誤懲罰代價可以依據(jù)路徑重要程度不同來判定，總之可以根據(jù)我們實

2、際的需求進(jìn)行約束。
　　 本文以車輛路徑問題為研究對象，綜合研究了車輛路徑問題的各種常用解決方法。在較大規(guī)模的路徑問題中主要是以啟發(fā)式算法為主，其中以遺傳算法為研究重點(diǎn)，遺傳算法因其全局的收斂性在解決多目標(biāo)優(yōu)化組合問題時有著優(yōu)良的效果，其具有極強(qiáng)的魯棒性和內(nèi)在的并行計算機(jī)制，特別適合于空間中復(fù)雜的多極值優(yōu)化和組合優(yōu)化問題，但基本遺傳算法在求解過程中容易出現(xiàn)早熟收斂，以及陷入局部最優(yōu)解的情況。本文通過構(gòu)造種群結(jié)構(gòu)，改善進(jìn)化算子來避

3、免基本遺傳算法所帶來的缺陷，通過提出實際規(guī)劃方案拓展了車輛路徑問題和優(yōu)化組合的研究領(lǐng)域，豐富了路徑規(guī)劃的理論研究成果，為車輛路徑應(yīng)用領(lǐng)域提供了規(guī)劃方案設(shè)計的借鑒與參考。
　　 本研究主要內(nèi)容及成果包括：⑴對CARP問題進(jìn)行了描述并引入了帶時間約束的CARP問題(CARPTC)，建立其數(shù)學(xué)模型，在對各種求解方法的歸納與總結(jié)基礎(chǔ)上明確了本文以遺傳算法為工具，通過對基本遺傳算法的改進(jìn)，解決帶時間約束的CARP問題(CARPTC)。⑵根

4、據(jù)CARPTC問題的特性，提出了一種混合遺傳算法HGA-TC，該算法采用了適合其問題的染色體編碼和種群初始化方法，改進(jìn)了進(jìn)化算子、變異算子、適應(yīng)值計算以及適應(yīng)度函數(shù)。對于帶有時間限制的關(guān)鍵路徑，采用在算法中加入時間懲罰函數(shù)，對于沒有達(dá)到時間要求的規(guī)劃方案加入懲罰成本，通過遺傳算法的優(yōu)勝劣汰原則來選擇出具有最優(yōu)適應(yīng)值和最小懲罰成本的規(guī)劃方案，以此來滿足帶有時間約束的路徑規(guī)劃。⑶引入了一些復(fù)雜限制條件，如單行道、雙邊同時被服務(wù)以及有坡度的路

5、徑等，設(shè)計了一種分層遺傳算法，其思想先按照某種要求或約束限制條件將整個初始種群劃分為一些子群體，在每個子群體內(nèi)部分別進(jìn)行獨(dú)立的遺傳進(jìn)化操作，在適當(dāng)?shù)臅r候進(jìn)行子群體之間的信息交換，這樣不僅可以使子種群因約束限制的減少而能以更快的效率進(jìn)化收斂迭代，還能維持種群的多樣性，使其不趨于一致，達(dá)到抑制早熟現(xiàn)象的效果，同時又可因種群規(guī)模有所減小而增加算法的效率。⑷根據(jù)真實道路圖為CARPTC問題建立了數(shù)據(jù)集，設(shè)定一些重要道路的時間約束，通過道路模擬系