遺傳算法在物流系統最佳化中的套用研究

中文摘要

物流已被認為是繼降低原材料消耗和提高勞動生產率之後的“第三利潤源”。通過最佳化物流系統，可以降低物流成本，從而增強企業的市場競爭能力。因此，研究物流系統中的最佳化問題，具有十分重要的意義，是國內外研究的一個熱點。庫存成本與配送成本是物流系統的核心成本，在物流總成本中占據了很大的比例。如果能降低庫存成本與配送成本，就能有效地降低物流成本。遺傳算法是一種套用很廣泛的智慧型最佳化算法，本文對遺傳算法進行了分析研究，針對遺傳算法的一些缺陷提出了相應的改進方法。在上述研究基礎上，本文基於遺傳算法，研究了物流系統中的庫存最佳化問題及車輛路徑問題。本文將庫存仿真最佳化問題與車輛路徑問題都看作是組合最佳化問題，並套用遺傳算法進行求解。本文的主要研究工作及貢獻可歸納如下：

(1)對隨機庫存系統建立了基於離散事件系統的計算機仿真模型。用系統仿真方法求解最優庫存策略時，其難點之一在於仿真的最佳化。為此，本文將計算機仿真技術和遺傳算法相結合，套用遺傳算法來最佳化模型的控制參數，即獲得最優的庫存控制策略。針對隨機系統的特點，設計了候選解收集器，它能夠收集在仿真最佳化過程中產生的Pareto解；提出了M精英選擇運算元，用於保護潛在的最優個體，使它們在交叉、變異運算元中不被破壞。針對兩種常用的庫存控制策略進行了仿真最佳化的實驗，結果表明本文提出的仿真最佳化方法是有效的。

(2)旅行商問題(TSP)是車輛路徑問題的子問題。為了求解TSP問題，研究了常用於TSP問題的三種交叉運算元的最佳化效果，提出了一種求解TSP問題的高效混合遺傳算法HGA-TSP。在該算法中以變形的OX運算元作為交叉運算元，以2-opt算法作為遺傳算法的變異運算元：提出了K近鄰點集的概念以縮減搜尋空間並提高算法的時間效率。

(3)將單配送中心，多輛運輸車且無約束的車輛路徑問題建模成具有總路徑長度最短、子路徑長度均衡性好這兩個目標的雙目標多旅行商問題(MTSP)，並基於HGA-TSP算法，研究了三種求解上述問題的解決方案。

(4)對於帶能力約束的車輛路徑問題(CVRP)，提出了一種新的雙層染色體編碼方案和一種子路徑交換算法。雙層染色體編碼方案不需要預先知道最優解所需要的車輛數，並能確保染色體不違反能力約束，這更適合求解實際物流配送系統中的車輛路徑問題。此外，相對於常用的單層染色體編碼方案，該編碼方案還能降低搜尋空間的大小，從而提高搜尋效率並降低計算時間。子路徑交換算法可以有效提高遺傳算法的求解精度。基於上述雙層染色體編碼方案和子路徑交換算法，設計了兩種求解CVRP問題的混合遺傳算法，分別是HGA-CVRP算法和HGA-SE-CVRP算法。

(5)對於帶時間窗約束的車輛路徑問題(VRPTW)，首先改進了雙層染色體編碼方案，以便在編程實現時更方便地進行子路徑的處理。然後研究了遺傳算法與鄰域搜尋算法的結合方式，在遺傳算法中引入了帶克隆操作的鄰域搜尋運算元。最後提出了一種求解VRPTW問題的新型混合遺傳算法HGA-VRPTW。

(6)綜合套用了面向對象分析與設計、多執行緒、UML等先進的軟體開發方法與技術，設計並開發了VRP仿真實驗室，這是一個用於研究車輛路徑問題的軟體包，具有使用簡便、界面美觀的特點。VRP仿真實驗室在本文的研究中發揮了重要的作用，是研究車輛路徑問題的有力工具。本文對大量的基準測試實例(Benchmark)進行了仿真計算，計算結果表明，本文所提出的一系列算法能有效求解物流系統中的庫存最佳化問題與車輛路徑問題。

遺傳算法在物流系統最佳化中的套用研究

基本介紹

相關詞條

熱門詞條