【正文】 很廣泛的智能優(yōu)化算法 ,本文對遺傳算法進行了分析研究 ,針對遺傳算法的一些缺陷提出了相應的改進方法。在上述研究基礎上 ,本文基于遺傳算法 ,研究了物流 系統(tǒng)中的庫存優(yōu)化問題及車輛路徑問題。本文將庫存仿真優(yōu)化問題與車輛路徑問題都看作是組合優(yōu)化問題 ,并應用遺傳算法進行求解。 本文的主要研究工作及貢獻可歸納如下 : (1)對隨機庫存系統(tǒng)建立了基于離散事件系統(tǒng)的計算機仿真模型。用系統(tǒng)仿真方法求解最優(yōu)庫存策略時 ,其難點之一在于仿真的優(yōu)化。為此 ,本文將計算機仿真技術和遺傳算法相結合 ,應用遺傳算法來優(yōu)化模型的控制參數(shù) ,即獲得最優(yōu)的庫存控制策略。針對隨機系統(tǒng)的特點 ,設計了候選解收集器 ,它能夠收集在仿真優(yōu)化過程中產生的 Pareto 解 。提出了 M 精英選擇算子 ,用于保護潛在的最優(yōu)個 體 ,使它們在交叉、變異算子中不被破壞。針對兩種常用的庫存控制策略進行了仿真優(yōu)化的實驗 ,結果表明本文提出的仿真優(yōu)化方法是有效的。 (2)旅行商問題 (TSP)是車輛路徑問題的子問題。為了求解 TSP 問題 ,研究了常用于 TSP 問題的三種交叉算子的優(yōu)化效果 ,提出了一種求解 TSP 問題的高效混合遺傳算法 HGATSP。在該算法中以變形的 OX 算子作為交叉算子 ,以 2opt 算法作為遺傳算法的變異算子 。提出了 K 近鄰點集的概念以縮減搜索空間并提高算法的時間效率。 (3)將單配送中心 ,多輛運輸車且無約束的車輛路徑問題建模成具有總路徑 長度最短、子路徑長度均衡性好這兩個目標的雙目標多旅行商問題 (MTSP),并基于 HGATSP 算法 ,研究了三種求解上述問題的解決方案。 (4)對于帶能力約束的車輛路徑問題 (CVRP),提出了一種新的雙層染色體編碼方案和一種子路徑交換算法。雙層染色體編碼方案不需要預先知道最優(yōu)解所需要的車輛數(shù) ,并能確保染色體不違反能力約束 ,這更適合求解實際物流配送系統(tǒng)中的車輛路徑問題。此外 ,相對于常用的單層染色體編碼方案 ,該編碼方案還能降低搜索空間的大小 ,從 6 而提高搜索效率并降低計算時間。子路徑交換算法可以有效提高遺傳算法的求解精 度?；谏鲜鲭p層染色體編碼方案和子路徑交換算法 ,設計了兩種求解 CVRP問題的混合遺傳算法 ,分別是 HGACVRP 算法和 HGASECVRP 算法。 (5)對于帶時間窗約束的車輛路徑問題 (VRPTW,首先改進了雙層染色體編碼方案 ,以便在編程實現(xiàn)時更方便地進行子路徑的處理。然后研究了遺傳算法與鄰域搜索算法的結合方式 ,在遺傳算法中引入了帶克隆操作的鄰域搜索算子。最后提出了一種求解VRPTW 問題的新型混合遺傳算法 HGAVRPTW。 (6)綜合應用了面向對象分析與設計、多線程、 UML 等先進的軟件開發(fā)方法與技術 ,設計 并開發(fā)了 VRP 仿真實驗室 ,這是一個用于研究車輛路徑問題的軟件包 ,具有使用簡便、界面美觀的特點。 VRP仿真實驗室在本文的研究中發(fā)揮了重要的作用 ,是研究車輛路徑問題的有力工具。本文對大量的基準測試實例 (Benchmark)進行了仿真計算 ,計算結果表明 ,本文所提出的一系列算法能有效求解物流系統(tǒng)中的庫存優(yōu)化問題與車輛路徑問題。 7 3 問題描述 車輛路徑問題定義 車輛路線問題（ VRP）最早是由 Dantzig 和 Ramser 于 1959 年首次提出，它是指一定數(shù)量的客戶，各自有不同數(shù)量的貨物需求， 配送中心 向客戶提供貨物，由一個車隊負責分送貨物， 組織 適當?shù)男熊嚶肪€，目標是使得客戶的 需求 得到滿足，并能在一定的約束下，達到諸如路程最短、 成本 最小、耗費時間最少等目的。 由此定義不難看出， 旅行商問題 （ Traveling Saleman Problem,TSP）是 VRP 的特例，由于 Gaery。 已證明 TSP 問題 是 NP 難題 ，因此， VRP 也屬于 NP 難題。 車輛路線問題自 1959 年提出以來，一直是網(wǎng)絡優(yōu)化問題中最基本的問題之一，由于其應用的廣泛性和 經(jīng)濟 上的重大價值，一直受到國內外學者的廣泛關注。車輛路線問題可以描述如 下（如圖 1）： 圖 1 路徑問題描述 設有一場站（ depot），共有 M 輛貨車，車輛容量為 Q，有 N 位 顧客 （ customer），每位顧客有其需求量 D。車輛從 場站 出發(fā)對客戶進行配送服務最后返回場站，要求所有顧客都被配送 ，每位顧客一次配送完成，且不能違反車輛容量的限制，目的是所有車輛路線的總距離最小。車輛路線的實際問題包括 配送中心配送 、公共汽車路線制定、信件和報紙投遞、航空和鐵路時間表安排、工業(yè)廢品收集等。 車輛路徑問題的類型 一般而言車輛路線問題大致可以分為以下三種類型（ Ballou， 1992） ： 相異的單一起點和單一終點。 相同的單一起點和終點。 8 多個起點和終點。 車輛路線問題研究現(xiàn)狀 經(jīng)過幾十年的研究發(fā)展，車輛路線問題研究取得了大量成果。下面從車輛路線問題的現(xiàn)有研究型態(tài)和求解方法兩個方面介紹車輛路線問題的研究現(xiàn)狀。 車輛路線問題型態(tài) 在基本車輛路線問題（ VRP）的基礎上，車輛路線問題在學術研究和實際應用上產生了許多不同的延伸和變化型態(tài)，包括 時窗限制車輛路線問題 （ vehicle routing problems with time windows， VRPTW）、 追求最佳服務時間的車輛路線問題 （ VRPDT）、 多車種車輛路線問題 （ fleet size and mix vehicle routing problems， FSVRP）、 車輛多次使用的車輛路線問題 （ vehicle routingproblems with multiple use of vehicle， VRPM）、 考慮收集的車輛路線問題 （ vehicle routingproblems with backhauls， VRPB）、 隨機需求車輛路線問題 （ vehicle routing problem with stochastic demand， VRPSD）等。 解決方法 求解方法演進 綜合過去有關車輛路線問題的求解方法，可以分為 精確算法（ exact algorithm）與 啟發(fā)式解法 （ heuristics），其中精密算法有 分支界限法 、 分支切割法 、 集合涵蓋法 等；啟發(fā)式解法有 節(jié)約法 、 模擬退火法 、 確定性退火法 、 禁忌搜尋法 、 基因算法 、 神經(jīng)網(wǎng)絡 、 螞蟻殖民算法 等。 1995 年， Fisher曾將求解車輛路線問題的算法分成三個階段。第一階段是從 1960 年到 1970 年，屬于簡單啟發(fā)式方式，包括有各種局部改善啟發(fā)式算法和貪婪法（ Greedy）等；第二階段是從 1970 年到 1980 年，屬于一種以數(shù)學規(guī)劃為主的啟發(fā)式解法，包括指派法、集合分割法和集合涵蓋法；第三階段是從 1990 開始至今，屬于較新的方法，包括利用嚴謹啟發(fā)式方法、人工智能方法等。 啟發(fā)式算法 由于 VRP 是 NPhard 問題，難以用精確算發(fā)求解，啟發(fā)式算法 9 是求解車輛 運輸問題的主要方法，多年來許多學者對車輛運輸問題進行了研究，提出了各種各樣的啟發(fā)式方法。車輛運輸問題的啟發(fā)式方法可以分為簡單啟發(fā)式算法、兩階段啟發(fā)式算法、人工智能方法建立的啟發(fā)式方法。 簡單啟發(fā)式方法包括節(jié)省法或 插入法 、路線內 /間節(jié)點交換法、貪婪法和局部搜索法等方法。節(jié)省法或插入法（ savings or insertion）是在求解過程中使用節(jié)省 成本最大的可行方式構造路線，直到無法節(jié)省為止。交換法則是依賴其他方法產生一個起始路線，然后以迭代的方式利用交換改善法減少路線距離，直到不能改善為止。 1960 年， Clarke 和 Wrigh 首先提出一種啟發(fā)式節(jié)省法（ savings methods）來建立車隊配送路線。簡單啟發(fā)式方法簡單易懂、求解速度快，但只適合求解小型、簡單的 VRP 問題。 兩階段方法包括先分組后定路線（ clusterfirstroute second）和先定路線后分組（ routefirstcluster second）兩種啟發(fā)式策略。前者是 先將所有需求點大略分為幾個組，然后再對各個組分別進行路線排序；后者則是先將