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

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

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

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

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

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