【正文】 然后 要感謝的是我的同學(xué)們。 （ 2）接著在前人的工作基礎(chǔ)上，著重研究了帶時(shí)間窗的同時(shí)取送貨綠色車輛調(diào)度與路徑規(guī)劃問題，重點(diǎn)關(guān)注了燃油消耗和碳排放成本。（ p? 單位為 g/kgfuel） 表 1 各種運(yùn)輸方式的碳排放因子 IPCC 運(yùn)輸方式 車 1 車 2 車 3 p? 3110 3147 3185 根據(jù)上述情景進(jìn)行仿真實(shí)驗(yàn)，在 [BT,FT]=[500,560]的情況下，按照均勻分布在指定參數(shù)區(qū)間內(nèi)隨機(jī)生成 10 實(shí)例 1M 、 2M 、??、 10M ， iM 表示隨機(jī)生成的一組 ipm? 、 ijm? 、 ipm? 、ijmt ，即聯(lián)運(yùn)網(wǎng)絡(luò)。 算法步驟 改進(jìn)遺傳算法的步驟如下：（ gen 表示當(dāng)前 代數(shù)， i 表示個(gè)體計(jì)數(shù)器 ） Step 1：把車輛的可行的路徑按照本文的編碼方式編碼為染色體； Step 2：初始化算法的參數(shù)； Step 3：生成初始的染色體種群； Step 4： gen ： = 0； Step 5： i = 0； Step 6：計(jì)算群體中第 i 個(gè)染色體個(gè)體的適應(yīng)度； Step 7： i ： = i + 1； Step 8：若 i = n，回到 Step 6，否則跳轉(zhuǎn)到 Step 9； Step 9：根據(jù)適應(yīng)度選擇父代； Step 10：進(jìn)行交叉和變異操作； Step 11： gen ： =gen + 1； Step 12：如果滿足算法的終止條件，則停止，否則跳轉(zhuǎn)到 Step 5。( , )jhv v A? ，則 39。如： 父染色體為： 1 1 2 3 5 6 1 0{ , , , , , }h v v v v v v? ； 2 1 3 4 7 1 0{ , , , , }h v v v v v? ； 交叉點(diǎn)為 3v ，子染色體為： 39。 （ 4）初始種群的染色體數(shù)量 1 2 3L L L L? ? ? 。常用的編碼方式有兩種：用二進(jìn)制數(shù)表示和用自然數(shù)表示。 在對(duì)問題進(jìn)行進(jìn)一步研究之前，根據(jù)問題的特點(diǎn)，作以下假設(shè)： （ 1）只有一個(gè)車場且車場與收貨點(diǎn)的位置是確定的。 天津理工大學(xué) 20xx 屆本科畢業(yè)設(shè)計(jì)說明書 10 第三章 復(fù)雜路徑優(yōu)化問題 問題的描述 車輛路徑優(yōu)化問題可以描述為：從發(fā)貨中心用一輛汽車向一個(gè)收貨點(diǎn)送貨，這個(gè)收貨點(diǎn)的位置和需求量一定 ，這輛汽車的負(fù)載重量一定，運(yùn)輸方式有三種車 1 運(yùn)輸，車 2 運(yùn)輸，車三運(yùn)輸，合理安排汽車路線，使總運(yùn)距最短，并滿足一下條件：每天送貨路徑上只有一個(gè)收貨點(diǎn)和送貨點(diǎn)，且只能由一輛汽車送貨。 GA 算法的流程圖如圖 所示： 天津理工大學(xué) 20xx 屆本科畢業(yè)設(shè)計(jì)說明書 8 開 始產(chǎn) 生 初 始 種 群計(jì) 算 個(gè) 體 適 應(yīng) 度 值選 擇交 叉變 異滿 足 終 止 條件 ？輸 出 最 優(yōu) 解結(jié) 束否是 圖 遺傳算法流程圖 MATLAB 仿真技術(shù) MATLAB 是一種以矩陣作為基本數(shù)據(jù)單遠(yuǎn)的程序設(shè)計(jì)語言，其具備數(shù)據(jù)分析、算法實(shí)現(xiàn)以及應(yīng)用開發(fā)的交互式開發(fā)環(huán)境。 （ 2） 初始化：對(duì)問題的參數(shù)進(jìn)行初始化，并按照一定的方法生成初始的染色體群體，一個(gè)染色體對(duì)應(yīng)著一個(gè)配送方案。 第三章 復(fù)雜網(wǎng)絡(luò)路徑優(yōu)化問題的 描述了該 優(yōu)化問題的符號(hào)含義 ，并設(shè)計(jì)了該 優(yōu)化問題所使用的數(shù)據(jù) 模型 ，并深入地描述了 該優(yōu)化問題的求解方法 。 曹二保 [23]研究了 VRPSPDTW 問題，建立了問題的模型，對(duì) GA 算法進(jìn)行了改進(jìn)，算法采用特殊的交叉變異操作；藍(lán)伯雄 [24]等人研究了 VRPSPDTW 問題，并設(shè)計(jì)了一種改進(jìn)的 TS 算法；殷佳林 [25]等人在蟻群算法的基礎(chǔ)上進(jìn)行了改進(jìn)，研究了 VRPSPDTW 問題，最后進(jìn)行了仿真實(shí)驗(yàn)，結(jié)果證明了算法可以成功的解決此類問題；段鳳華 [26]針對(duì) VRPSPDTW 問題 ，考慮了硬時(shí)間窗約束條件，設(shè)計(jì)了改進(jìn) TS 算法；郎茂祥 [27]采用了 TS 算法和模擬退火算法對(duì)VRPSPDTW 問題進(jìn)行了研究，研究中考慮的是軟時(shí)間窗 約束；郭耀煌和李軍 [28]研究了車輛滿載情況下， VRPSPDTW 問題，并用啟發(fā)式方法得到了車輛路線；張燕，周支力和翟斌 [29]對(duì)傳天津理工大學(xué) 20xx 屆本科畢業(yè)設(shè)計(jì)說明書 4 統(tǒng)標(biāo)號(hào)算法進(jìn)行了改進(jìn)，研究了 VRPSPDTW 問題。 涉及到很多領(lǐng)域和應(yīng)用 ，而且 VRP 及其變種已經(jīng)被廣泛的研究，直到 Min[7]意識(shí)到在實(shí)際情況中同一結(jié)點(diǎn)同時(shí)取送貨的可能性，介紹了同時(shí)取送貨車輛路徑問題（ vehicle routing problem with simultaneous pickups and deliveries，VRPSPD）。因此，設(shè)計(jì)合理有效的路徑方案對(duì)企業(yè)和社會(huì)具有十分重要的意義。由于遺傳算法能在解決組合優(yōu)化問題上展現(xiàn)出良好的特性 ，將遺傳算法應(yīng)用到車輛調(diào)度與路徑優(yōu)化問題中去，有助于解決其車輛路徑的復(fù)雜度， 使得求解車輛最短路徑問題得到很大進(jìn)步。 遺傳算法是由美國 Michigan 大學(xué)的 教授于 1975 年首先提出的一種模擬自然界生物進(jìn)化過程的全局隨 機(jī)優(yōu)化算法。我國物流業(yè)已 進(jìn)入 轉(zhuǎn)型升級(jí)的新階段。數(shù)據(jù)實(shí)例的實(shí)驗(yàn)計(jì)算結(jié)果分析表明，應(yīng)用本文中的模型及其求解算法，可以得到環(huán)境友好的路徑規(guī)劃方案，有效降低運(yùn)輸過程中的碳排放量。而我國雖然在交通網(wǎng)的基礎(chǔ)設(shè)施建設(shè)方面取得了一定進(jìn)展，但是管理體制和信息化程度的落后嚴(yán)重 制約著綜合運(yùn)輸服務(wù)的進(jìn)一步發(fā)展。 According to the characteristics of the problem, the improved geic algorithm is designed to solve the problem. Data instance analysis of the experiment results show that application model and its algorithm in this paper, can be environment friendly path planning scheme, effectively reduce carbon emissions in the process of transportation. This model mainly consider the influence of the transportation time and transit time, involved in the delivery of the vehicle routing optimization, so as to choose the shortest path. Designed a kind of improved geic algorithm based on variablelength chromosomes to solve the problem, the algorithm adopts effective encoding and specific crossover operator, to successfully implement the solution of the problem. In addition, the application experiment of simulation data instance calculation to verify the effectiveness of the method proposed in this paper, the approximate optimal solution can be got by for logistics enterprise to provide a satisfactory vehicle scheduling scheme with path planning. Key Words: Carbon emission Fuel consumption Path optimization Geic algorithm I 目 錄 第一章 緒論 ................................................1 研究背景及發(fā)展概況 ....................................................... 1 研究目的和意義 ........................................................... 2 研究目的 ............................................................. 2 研究意義 ............................................................. 2 國內(nèi)外研究現(xiàn)狀 ........................................................... 2 本文的研究內(nèi)容 ........................................................... 4 本文的結(jié)構(gòu)安排 ........................................................... 5 第二章 系統(tǒng)關(guān)鍵技術(shù)介紹 .....................................7 遺傳算法 ................................................................. 7 遺傳算法的基本原理 ................................................... 7 遺傳算法的基本步驟 ................................................... 7 MATLAB 仿真技術(shù) .......................................................... 8 第三章 復(fù)雜路徑優(yōu) 化問題 ....................................10 問題的描述 .............................................................. 10 問題的符號(hào)表示 .......................................................... 11 問題的數(shù)學(xué)模型 .......................................................... 11 第四章 改進(jìn)遺傳算法設(shè)計(jì) ....................................13 染色體編碼方式 .......................................................... 13 初始種群的生成 .......................................................... 13 適應(yīng)度函數(shù)的建立 ........................................................ 13 選擇策略 ...........................................................