【正文】 機(jī)仿真模型。提出了 M 精英選擇算子 ,用于保護(hù)潛在的最優(yōu)個(gè) 體 ,使它們?cè)诮徊妗⒆儺愃阕又胁槐黄茐?。在該算法中以變形?OX 算子作為交叉算子 ,以 2opt 算法作為遺傳算法的變異算子 。雙層染色體編碼方案不需要預(yù)先知道最優(yōu)解所需要的車輛數(shù) ,并能確保染色體不違反能力約束 ,這更適合求解實(shí)際物流配送系統(tǒng)中的車輛路徑問題。 (5)對(duì)于帶時(shí)間窗約束的車輛路徑問題 (VRPTW,首先改進(jìn)了雙層染色體編碼方案 ,以便在編程實(shí)現(xiàn)時(shí)更方便地進(jìn)行子路徑的處理。 VRP仿真實(shí)驗(yàn)室在本文的研究中發(fā)揮了重要的作用 ,是研究車輛路徑問題的有力工具。 已證明 TSP 問題 是 NP 難題 ，因此， VRP 也屬于 NP 難題。車輛路線的實(shí)際問題包括 配送中心配送 、公共汽車路線制定、信件和報(bào)紙投遞、航空和鐵路時(shí)間表安排、工業(yè)廢品收集等。 車輛路線問題研究現(xiàn)狀 經(jīng)過幾十年的研究發(fā)展，車輛路線問題研究取得了大量成果。 1995 年， Fisher曾將求解車輛路線問題的算法分成三個(gè)階段。 簡單啟發(fā)式方法包括節(jié)省法或 插入法 、路線內(nèi) /間節(jié)點(diǎn)交換法、貪婪法和局部搜索法等方法。簡單啟發(fā)式方法簡單易懂、求解速度快，但只適合求解小型、簡單的 VRP 問題。 禁忌搜索法 （ TS）基本上是屬于一種人工智能型（ AI）的局部搜尋方法， Willard 首先將此算法用來求解 VRP ，隨后亦有許多位學(xué)者也發(fā)表了求解 VRP 的 TS 算法?，F(xiàn)在多數(shù)學(xué)者采用混合策略，分別采用兩種人工智能方法進(jìn)行路線分組和路線優(yōu)化。 11 4 遺傳算法介紹 遺傳算法簡稱 GA(Geic Algorithm)，在本質(zhì)上是一種不依賴具體問題的直接搜索方法。 遺傳算法是受生物進(jìn)化學(xué)說和遺傳學(xué)說啟發(fā)而發(fā)展起來的，基于適者生存思想的一種較通用的問題求解方法。具有如下特點(diǎn)： (1) 遺傳算法運(yùn)算的是解集的編碼，而不是解集本身； (2) 遺傳算法的搜索始于解的一個(gè)種群，而不是單個(gè)解； (3) 遺傳算法只使用報(bào)酬信息（適值函數(shù)），不使用導(dǎo)數(shù)或其他輔助知識(shí)； (4) 遺傳算法采用概率的，而不是確定的狀態(tài)轉(zhuǎn)移規(guī)則。遺傳算法中包含了如下 5 個(gè)基本要素： 1)參數(shù)編碼； 2)初始群體的設(shè)定； 3)適應(yīng)度函數(shù)的設(shè)計(jì)； 4)遺傳操作設(shè)計(jì)； 12 5） 控制參數(shù)設(shè)定 (主要是指群體大小和使用遺傳操作的概率等 )。遺傳算法作為一種全局優(yōu)化搜索方法，具有簡單、通用普適性強(qiáng)，適用于并行處理和應(yīng)用范圍廣等優(yōu)點(diǎn)。 另外 ， 變量 和 的值為 0 或 1。 其中 ，為客戶所要求的送貨時(shí)區(qū) ， 為時(shí)間窗 ， 超過該范圍客戶將拒絕收貨 ， 因此設(shè)定一個(gè)極大的懲罰成本 以避免此情況的發(fā)生 。按客戶對(duì)物流中心違反時(shí)間窗約束規(guī)定時(shí)的接受程度，可分為硬時(shí)間窗、軟時(shí)間窗和混合型時(shí)間窗。 帶時(shí)間窗的物流配送路徑問題的遺傳算法 染色體結(jié)構(gòu)編碼 根據(jù)物流配送路徑優(yōu)化問題的特點(diǎn)，本文采用了簡單直觀的自然數(shù)編碼方法，用 0 表示配送中心，用 … 、 L 表示各需求點(diǎn)。例如，對(duì)于一個(gè)有 6 個(gè)需求點(diǎn)，用 2 輛汽車完成配送任務(wù)的問題， 則可用 0、 … 、 6 (0 表示配送中心 )這 7 個(gè)自然數(shù)的隨機(jī)排列表示物流配送路徑方案。 適應(yīng)度分析 初始種群形成以后，需要通過種群的適應(yīng)度函數(shù)，對(duì)種群中的每個(gè)染色體進(jìn)評(píng)價(jià)，并以此為標(biāo)準(zhǔn)選擇最優(yōu)解。 2. 遺傳基因的交叉 對(duì)通過選擇操作產(chǎn)生的新群體，需要進(jìn)行配對(duì)交叉重組。在此引入新的 CX 交叉算子。B=6 2 9 8|8 3 2 9 5 4 1 6 7 最后在 39。 函數(shù)控制的終止條件 優(yōu)化算法的結(jié)束條件是系統(tǒng)設(shè)定的最大遺傳代數(shù)。 一旦車輛分配方案確定 ，那么路線安排問題也就比較容易求解 （ 即求解變量 ）。 對(duì)于 m 輛車 、 n 個(gè)客戶的車輛分配 ,可表示成 mn 矩陣 。 隨機(jī)產(chǎn)生初始車輛分配方案 ， 并淘汰不符合約束條件的染色體 ,直到染色體群的種群數(shù)達(dá) N 條 。 用啟發(fā)式算法求解單一車輛排序問題 對(duì)變量 的求解實(shí)質(zhì)上是一個(gè)帶時(shí)間約束的單一車輛排序問題 ， 即對(duì)中的元素進(jìn)行排序 ， 求解最小的 ， 以滿足約束條件 。 對(duì)每一條染色體 ， 求解變量 ， 并計(jì)算每一條染色體的適配值 ： ! 種群的選擇與復(fù)制 本算法采用與適配值成比例的概率方法 ， 對(duì)種群的個(gè)體進(jìn)行選擇與復(fù)制 。 以概率 對(duì)染色體群隨機(jī)地交換兩個(gè)個(gè)體的某些片段產(chǎn)生新的個(gè)體染色體 ， 即對(duì)選定的需進(jìn)行交叉運(yùn)算的每一組布爾矩陣隨機(jī)設(shè)定交叉位置 $通過交換布爾矩陣中的某些行或列的部分信息 （ 二進(jìn)制位 ）， 其他位不變 ， 從而生成兩個(gè)新的布爾矩陣 。 變異概率取不同的值對(duì)算法性能的影響很大 ； 過大 ， 求解時(shí)間明顯增加 $但算法收斂于局部最優(yōu)的可能性減少 。 由于該算法屬于種群非重疊 amp。已知各客戶的需求和各客戶之間的距離如表 1(其中 0 表示配送中心 )，要求合理安排車輛的行駛路線，使總的運(yùn)距最短。 24 此實(shí)例引用了參考文獻(xiàn) 2 中的經(jīng)典案例，通過上面的具體實(shí)例，可以讓我們對(duì)遺傳算法在物流配送中的具體應(yīng)用有了更深的理解。 25 7 結(jié)束語 隨著畢業(yè)日子的到來，畢業(yè)設(shè)計(jì)也接近了尾聲。通過這次畢業(yè)設(shè)計(jì)使我明白了自己原來知識(shí)還比較欠缺。 我的心得也就這么多了，總之，不管學(xué)會(huì)的還是學(xué)不會(huì)的的確覺得困難比較多，真是萬事開頭難，不知道如何入手。在設(shè)計(jì)過程中，我通過查閱大量有關(guān)資料，與同學(xué)交流經(jīng)驗(yàn)和自學(xué)，并向老師請(qǐng)教等方式，使自己學(xué)到了不少知識(shí)，也經(jīng)歷了不少艱辛，但收獲同樣巨大 。 26 8 參考文獻(xiàn) [1] 鐘石泉，賀國光 . 單車場復(fù)雜情況下的車輛調(diào)度 [J]. 系統(tǒng)工程，2020,23(5):2932. [2] 肖健梅，黃有方，李軍軍 ,等 . 基于離散微粒群優(yōu)化的物流配送車 輛路徑問題 [J]. 系統(tǒng)工程， 2020,23(4):97100. [3] 張建勇，郭耀煌，李軍 . 基于顧客滿意度的多目標(biāo)模糊車輛優(yōu)化調(diào)度問題研究 [J]. 鐵道學(xué)報(bào)， 2020,25(2):1517. [4] 李軍，郭耀煌 . 物流配送車輛優(yōu)化調(diào)度理論與方法 [M]. 北京：中國物資出版社， 2020. [5] 郭惠昕，車曉毅，肖偉躍 . 混沌遺傳優(yōu)化算法及其在機(jī)械優(yōu)化設(shè)計(jì)中的應(yīng)用 [J]. 機(jī)械設(shè)計(jì)， 2020,20(10):2325. [6] YungChien Lin, FengSheng Wang, KaoShing Hwang. A hybrid method of evolutionary algorithms for mixedinteger nonlinear optimization problems[C] // Proceedings of the 1999 Congress on Evolutionary Computation, 1999:21602166. [7] 李愛國 . 多粒子群協(xié)同優(yōu)化算法 [J]. 復(fù)旦大學(xué)學(xué)報(bào)， 2020(6):8790. [8] 陳一永，韓紅，龔延成 . 帶時(shí) 間約束的配載車輛調(diào)度問題研究 [J]. 物流技術(shù)， 2020,25(3):4850. [9] Savelsbergh search for routing problem with time windows. Annals of OperationsResearch,1985,16(4): 285305. [10] 曾凡超 . 車輛路徑問題的改進(jìn)遺傳算法 [J]，重慶大學(xué) , 2020. [11] 徐天亮 . 運(yùn)輸與配送 [M]，北京：中國物資出版社 , 2020. [12] 晏夢君 . 遺傳算法在配送線 路優(yōu)化系統(tǒng)中的應(yīng)用 [J], 吉林大學(xué) , . [13]:Anovevriewofexactandapproximatealgorithms[J].EuroPeanJounralofOPerationalReseareh，:345358.