帶時(shí)間約束條件的弧路徑問(wèn)題研究.pdf

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

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

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

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

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