【正文】 在設(shè)計(jì)過程中，我通過查閱大量有關(guān)資料，與同學(xué)交流經(jīng)驗(yàn)和自學(xué)，并向老師請(qǐng)教等方式，使自己學(xué)到了不少知識(shí)，也經(jīng)歷了不少艱辛，但收獲同樣巨大。通過這次畢業(yè)設(shè)計(jì)使我明白了自己原來知識(shí)還比較欠缺。此實(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è)新的布爾矩陣。對(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)解。根據(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ī)則。 4 遺傳算法介紹遺傳算法簡稱 GA(Genetic 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ī)仿真模型。2選題的目的物流已被認(rèn)為是繼降低原材料消耗和提高勞動(dòng)生產(chǎn)率之后的“第三利潤源”。采用多組通用算例測(cè)算，將多策略分組編碼遺傳算法與其它算法進(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ù)中心（或車場(chǎng)）的若干車輛向多個(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ì)于常用的單層染色體編碼方案,該編碼方案還能降低搜索空間的大小,從而提高搜索效率并降低計(jì)算時(shí)間。本文對(duì)大量的基準(zhǔn)測(cè)試實(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?？梢圆捎眠z傳算法的思想作為總體框架對(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條染色體。本文中，取,（）采用反順序變異法改變布爾矩陣中的某些位（1變成0,0變成1），產(chǎn)生新的布爾矩陣。表1客戶間距離表設(shè)置車輛數(shù)為 3，最大負(fù)載10，車輛容積30，最大行駛距離為200，運(yùn)輸成本系數(shù)4，平均時(shí)速為40，不考慮裝卸及休息時(shí)間。經(jīng)過幾周的奮戰(zhàn)我的畢業(yè)設(shè)計(jì)終于完成了。最后