【正文】 在設(shè)計(jì)過程中，我通過查閱大量有關(guān)資料，與同學(xué)交流經(jīng)驗(yàn)和自學(xué)，并向老師請(qǐng)教等方式，使自己學(xué)到了不少知識(shí)，也經(jīng)歷了不少艱辛，但收獲同樣巨大 。通過這次畢業(yè)設(shè)計(jì)使我明白了自己原來知識(shí)還比較欠缺。 24 此實(shí)例引用了參考文獻(xiàn) 2 中的經(jīng)典案例，通過上面的具體實(shí)例，可以讓我們對(duì)遺傳算法在物流配送中的具體應(yīng)用有了更深的理解。 由于該算法屬于種群非重疊 amp。 以概率 對(duì)染色體群隨機(jī)地交換兩個(gè)個(gè)體的某些片段產(chǎn)生新的個(gè)體染色體 ， 即對(duì)選定的需進(jìn)行交叉運(yùn)算的每一組布爾矩陣隨機(jī)設(shè)定交叉位置 $通過交換布爾矩陣中的某些行或列的部分信息 （ 二進(jìn)制位 ）， 其他位不變 ， 從而生成兩個(gè)新的布爾矩陣 。 用啟發(fā)式算法求解單一車輛排序問題 對(duì)變量 的求解實(shí)質(zhì)上是一個(gè)帶時(shí)間約束的單一車輛排序問題 ， 即對(duì)中的元素進(jìn)行排序 ， 求解最小的 ， 以滿足約束條件 。 對(duì)于 m 輛車 、 n 個(gè)客戶的車輛分配 ,可表示成 mn 矩陣 。 函數(shù)控制的終止條件 優(yōu)化算法的結(jié)束條件是系統(tǒng)設(shè)定的最大遺傳代數(shù)。在此引入新的 CX 交叉算子。 適應(yīng)度分析 初始種群形成以后，需要通過種群的適應(yīng)度函數(shù)，對(duì)種群中的每個(gè)染色體進(jìn)評(píng)價(jià)，并以此為標(biāo)準(zhǔn)選擇最優(yōu)解。 帶時(shí)間窗的物流配送路徑問題的遺傳算法 染色體結(jié)構(gòu)編碼 根據(jù)物流配送路徑優(yōu)化問題的特點(diǎn)，本文采用了簡單直觀的自然數(shù)編碼方法，用 0 表示配送中心，用 … 、 L 表示各需求點(diǎn)。 其中 ，為客戶所要求的送貨時(shí)區(qū) ， 為時(shí)間窗 ， 超過該范圍客戶將拒絕收貨 ， 因此設(shè)定一個(gè)極大的懲罰成本 以避免此情況的發(fā)生 。遺傳算法作為一種全局優(yōu)化搜索方法，具有簡單、通用普適性強(qiáng)，適用于并行處理和應(yīng)用范圍廣等優(yōu)點(diǎn)。具有如下特點(diǎn)： (1) 遺傳算法運(yùn)算的是解集的編碼，而不是解集本身； (2) 遺傳算法的搜索始于解的一個(gè)種群，而不是單個(gè)解； (3) 遺傳算法只使用報(bào)酬信息（適值函數(shù)），不使用導(dǎo)數(shù)或其他輔助知識(shí)； (4) 遺傳算法采用概率的，而不是確定的狀態(tài)轉(zhuǎn)移規(guī)則。 11 4 遺傳算法介紹 遺傳算法簡稱 GA(Geic Algorithm)，在本質(zhì)上是一種不依賴具體問題的直接搜索方法。 禁忌搜索法 （ TS）基本上是屬于一種人工智能型（ AI）的局部搜尋方法， Willard 首先將此算法用來求解 VRP ，隨后亦有許多位學(xué)者也發(fā)表了求解 VRP 的 TS 算法。 簡單啟發(fā)式方法包括節(jié)省法或 插入法 、路線內(nèi) /間節(jié)點(diǎn)交換法、貪婪法和局部搜索法等方法。 車輛路線問題研究現(xiàn)狀 經(jīng)過幾十年的研究發(fā)展，車輛路線問題研究取得了大量成果。 已證明 TSP 問題 是 NP 難題 ，因此， VRP 也屬于 NP 難題。 (5)對(duì)于帶時(shí)間窗約束的車輛路徑問題 (VRPTW,首先改進(jìn)了雙層染色體編碼方案 ,以便在編程實(shí)現(xiàn)時(shí)更方便地進(jìn)行子路徑的處理。在該算法中以變形的 OX 算子作為交叉算子 ,以 2opt 算法作為遺傳算法的變異算子 。 本文的主要研究工作及貢獻(xiàn)可歸納如下 : (1)對(duì)隨機(jī)庫存系統(tǒng)建立了基于離散事件系統(tǒng)的計(jì)算機(jī)仿真模型。 5 2 選題的目的 物流已被認(rèn)為是繼降低原材料消耗和提高勞動(dòng)生產(chǎn)率之后的 “ 第三利潤源 ” 。采用多組通用算例測算，將多策略分組編碼遺傳算法與其它算法進(jìn)行比較，其求解結(jié)果和計(jì)算時(shí)間都有明顯改進(jìn)，驗(yàn)證了多策略分組編碼遺傳算法能夠有效穩(wěn)定地收斂到所求問題的解。 關(guān)鍵詞 ： 物流車輛路徑問題 。對(duì)配送車輛進(jìn)行優(yōu)化調(diào)度 ,有利于提高物流經(jīng)濟(jì)效益、實(shí)現(xiàn)物流科學(xué)化。配送作為物流中一種特殊的、綜合的活動(dòng)形式 ,在當(dāng)今社會(huì)經(jīng)濟(jì)發(fā)展中發(fā)揮著越來越重要的作用。應(yīng)用 C 語言編程進(jìn)行實(shí)例計(jì)算 ,結(jié)果表明改進(jìn)的遺傳算法明顯增強(qiáng)了群體演化的質(zhì)量 ,提高了算法的收斂速度 ,得到了問題的滿意解。 本文首先介紹了遺傳算法在解決簡單約束車輛路徑問題上的應(yīng)用，改進(jìn)了交叉算子，為研究有時(shí)間窗裝卸問題的遺傳算法作了充分準(zhǔn)備。有容量約束的車輛路徑問題（ Capacitated Vehicle routing problem， CVRP）是由一個(gè)服務(wù)中心（或車場）的若干車輛向多個(gè)客戶點(diǎn)進(jìn)行配送服務(wù)，在已知待服務(wù)客戶點(diǎn)和出發(fā)點(diǎn) 的位置、客戶需求及車輛最大負(fù)載的前提下，設(shè)計(jì)車輛配送路徑，規(guī)劃設(shè)計(jì)方案，使運(yùn)輸成本最小化，即總代價(jià)最?。ㄊ褂密囕v盡量少，行車總距離盡量短）。 遺傳算法是一種應(yīng)用很廣泛的智能優(yōu)化算法 ,本文對(duì)遺傳算法進(jìn)行了分析研究 ,針對(duì)遺傳算法的一些缺陷提出了相應(yīng)的改進(jìn)方法。針對(duì)兩種常用的庫存控制策略進(jìn)行了仿真優(yōu)化的實(shí)驗(yàn) ,結(jié)果表明本文提出的仿真優(yōu)化方法是有效的。此外 ,相對(duì)于常用的單層染色體編碼方案 ,該編碼方案還能降低搜索空間的大小 ,從 6 而提高搜索效率并降低計(jì)算時(shí)間。本文對(duì)大量的基準(zhǔn)測試實(shí)例 (Benchmark)進(jìn)行了仿真計(jì)算 ,計(jì)算結(jié)果表明 ,本文所提出的一系列算法能有效求解物流系統(tǒng)中的庫存優(yōu)化問題與車輛路徑問題。 車輛路徑問題的類型 一般而言車輛路線問題大致可以分為以下三種類型（ Ballou， 1992） ： 相異的單一起點(diǎn)和單一終點(diǎn)。第一階段是從 1960 年到 1970 年，屬于簡單啟發(fā)式方式，包括有各種局部改善啟發(fā)式算法和貪婪法（ Greedy）等；第二階段是從 1970 年到 1980 年，屬于一種以數(shù)學(xué)規(guī)劃為主的啟發(fā)式解法，包括指派法、集合分割法和集合涵蓋法；第三階段是從 1990 開始至今，屬于較新的方法，包括利用嚴(yán)謹(jǐn)啟發(fā)式方法、人工智能方法等。 兩階段方法包括先分組后定路線（ clusterfirstroute second）和先定路線后分組（ routefirstcluster second）兩種啟發(fā)式策略。 Ombuk 提出了用 遺傳算法 進(jìn)行路線分組，然后用禁忌搜索方法進(jìn)行路線優(yōu)化的混合算法。利用遺傳算法進(jìn)行尋優(yōu)時(shí)，編碼、選擇、交叉、變異是四個(gè)重要步驟。 這 5 個(gè)要素構(gòu)成了遺傳算法的核心內(nèi)容。 若車輛 k 為客戶 i 服務(wù) ， 則 1， 否則為 0， 即 ： 此變量表示車輛分配方案 ， 可用布爾矩陣表示 ； 若車輛 k 經(jīng)由客戶 i 到客戶 j， 則 為 1， 否則為 0， 即 ：， 表示車輛路線安排 。硬時(shí)間窗 (Hard Time Windows)：指配送車輛必須在特定時(shí)間區(qū)段，將貨物送達(dá)顧客手中，不論是遲到或早到都完全不予接受；軟時(shí)間窗 (Soft Time Windows)：允許服務(wù)的開始時(shí)間有所偏離時(shí)間窗，則必須按照違反時(shí)間的長短施以一定的罰金或其他懲罰法則；混合型時(shí)間窗（ Mixed Time Windows）：是指系統(tǒng)中有些客戶 只接受硬時(shí)間窗服務(wù)，有些客戶接受軟時(shí)間窗服務(wù)，或者同一客戶，往往軟、硬兩種時(shí)間窗服務(wù)混合使用。如個(gè)體 0l26354 表示的配送路徑方案為：路徑 1： 0126，路徑 2： 354共有 2 條配送路徑； 種群的初始化 群體初始化時(shí)，采用兩種機(jī)制，一種是隨機(jī)生成個(gè)體，一種是按 前相插入啟發(fā)式算法。簡 單的說就是人為選取較好的一對(duì)染色體作為新染色體的父母，按染色體按長度分為前后兩段，取其中一個(gè)染色體的前半部分放在另一個(gè)染色體的前邊，再順序遍歷新染色體的基因并剔除重復(fù)基因，從而得到新的染色體 child1。A， 39。 可以采用遺傳算法的思想作為總體框架對(duì)該問題進(jìn)行求解 ， 用遺傳算法求解變量 ， 而變量 則用啟發(fā)式算法求解 。 N 的取值不宜過大或過小 。 首先根據(jù)前面計(jì)算的 計(jì)算個(gè)體 i 在下一代中應(yīng)復(fù)制自 身的比例 ； 定義選擇概率 為個(gè)體適配值所占比例的反向排序 $即適配值最小的車輛分配方案其選擇概率最大 ； 依據(jù)選擇概率對(duì)種群中的個(gè)體進(jìn)行復(fù)制 ， 選擇概率大的個(gè)體被重復(fù)復(fù)制的機(jī)會(huì)大 ， 而選擇概率小的個(gè)體則趨向于減少或淘汰 ， 直到復(fù)制 N 22 條染色體 。 本文中 ， 取 , 變異操作 mutation（） 采用反順序變異法改變布爾矩陣中的某些位 （ 1 變成 0,0 變成 1）， 產(chǎn)生新的布爾矩陣 。 表 1 客戶間距離表