【文章內(nèi)容簡介】 對象，建立了考慮環(huán)境指標(biāo)和經(jīng)濟指標(biāo)的車輛路徑優(yōu)化問題的多目標(biāo)數(shù)學(xué)模型，以車輛的運輸時間和中轉(zhuǎn)時間為約束條件來確定最短路徑降低成本，之后設(shè)計了求解該問題的改進(jìn)遺傳算法，最后用標(biāo)準(zhǔn)的車輛路 徑優(yōu)化問題算例做了仿真實驗，通過對實驗結(jié)果的分析驗證了算法的正確性。 本文結(jié)構(gòu)路線圖如圖 所示： 天津理工大學(xué) 20xx 屆本科畢業(yè)設(shè)計說明書 5 V R P 問 題 優(yōu) 化 研 究研 究 背 景 、 意 義 和現(xiàn) 狀V R P 求 解 方 法V R P 問 題 概 述 V R P 模 型 構(gòu) 建V R P 描 述 組 成 、 模型 、 分 類求 解 算 法 設(shè) 計遺 傳 算 法 介 紹遺 傳 算 法 原 理 、 工作 過 程 、 特 點G A 具 體 方 案 ： 染 色體 、 種 群 、 適 應(yīng)度 、 遺 傳 算 子 等算 例 分 析時 間 窗 描 述 、 分 類總 結(jié) 及 展 望 圖 結(jié)構(gòu)路線圖 本文的 結(jié)構(gòu)安排 本文共分為五章，各章的主要內(nèi)容安排如下： 第一章介紹了 復(fù)雜網(wǎng)絡(luò)下的路徑優(yōu)化問題 的研究背景，相關(guān)技術(shù)的發(fā)展概況 、研究的目的和意義 以及國內(nèi)外在 遺傳算法進(jìn)化過程中 等領(lǐng)域的研究現(xiàn)狀。并分析了在這些前提下，基于改進(jìn)遺傳算法的復(fù)雜路徑優(yōu)化問題 的優(yōu)勢。 天津理工大學(xué) 20xx 屆本科畢業(yè)設(shè)計說明書 6 第二章介紹了實現(xiàn) 基于改進(jìn)遺傳算法的復(fù)雜網(wǎng)絡(luò)路徑優(yōu)化問題 時所使用的關(guān) 鍵技術(shù)，詳細(xì)地闡述了 在遺傳算法中編碼，生成初始種群，適應(yīng)性值評估，選擇，交叉，變異，確定最優(yōu)解等 實現(xiàn)遺傳算法 等技術(shù)的工作原理以及 仿真實驗的介紹 。 第三章 復(fù)雜網(wǎng)絡(luò)路徑優(yōu)化問題的 描述了該 優(yōu)化問題的符號含義 ，并設(shè)計了該 優(yōu)化問題所使用的數(shù)據(jù) 模型 ，并深入地描述了 該優(yōu)化問題的求解方法 。 第四章具體地說明了對基于 改進(jìn)遺傳算法的復(fù)雜網(wǎng)絡(luò)路徑優(yōu)化問題 進(jìn)行了 改進(jìn)遺傳算法的設(shè)計 。 第五章通過算例分析進(jìn)行仿真實驗 ，通過詳細(xì)的測試對該 問題 進(jìn)行了可行性驗證 以及對結(jié)果的分析 。 第 六 章總結(jié)了在開發(fā) 基于改進(jìn)遺傳算法的復(fù)雜網(wǎng)絡(luò)路徑優(yōu)化問題時 所 遇到的各種問題，在總結(jié)的過程中對這些問題進(jìn)行深入的思考，提出了未來可以進(jìn)一步改進(jìn)的解決方案。 天津理工大學(xué) 20xx 屆本科畢業(yè)設(shè)計說明書 7 第二章 系統(tǒng)關(guān)鍵技術(shù)介紹 遺傳算法 遺傳算法（ Geic Algorithm， GA）是 Holland 和 Bagley 于 1975 年提出，它是一種借鑒生物進(jìn)化機制演化而來的自適應(yīng)隨機搜索算法。遺傳算法從一定的初始群體開始進(jìn)化，從中篩選出優(yōu)良的染色體，通過一代一代的進(jìn)化，使整個群體適應(yīng)性更好，經(jīng)過一定代數(shù)的進(jìn)化之后，最終找到最優(yōu)的個體。其中 在每一代的群體中，按照每個染色體的適應(yīng)性優(yōu)劣，選擇出一些良好的染色體復(fù)制到下一代種群中，接著通過染色體之間的交叉、變異生成新的染色體。 在遺傳（ GA） 算法中，首先通過一定的編碼方式生成初始群體，然后在每個染色體上執(zhí)行選擇算子（ Selection Operator）、交叉算子（ Crossover Operator）、變異算子（ Mutation Operator）這些操作，并從中選出適應(yīng)度高的染色體進(jìn)化，從而實現(xiàn)優(yōu)勝劣汰的進(jìn)化過程，算法的具體操作過程如下： （ 1） 染色體編碼： GA 不能對問 題的一些參數(shù)進(jìn)行直接處理，所以需要將問題的解通過一定的編碼方式編碼為染色體，染色體編碼的好壞直接影響計算消耗的時間，算法運行的快慢，所以一般情況下為節(jié)省算法運行時間采用自然數(shù)直接編碼的方式。 （ 2） 初始化：對問題的參數(shù)進(jìn)行初始化，并按照一定的方法生成初始的染色體群體，一個染色體對應(yīng)著一個配送方案。 （ 3） 計算適應(yīng)度值：適應(yīng)度函數(shù)用來判定染色體的優(yōu)良程度，常常根據(jù)問題的特點，選取一定的函數(shù)作為適應(yīng)度函數(shù)。為了能迅速判定染色體的優(yōu)良程度，就要拉大優(yōu)良個體的適應(yīng)度值，基于序的評價函數(shù)就有利于拉大個體之間的適應(yīng)度值，基于序的評 價函數(shù)首先就是對種群中所有的個體按照總距離的大小進(jìn)行排序，每一個個體要給與一個隊列序號，總的距離越小，序號越靠前。 （ 4） 選擇策略：其是為了從當(dāng)前的群體中選出優(yōu)良的染色體復(fù)制到下一代群體中，染色體的適應(yīng)度越高，被復(fù)制到下一代的可能性就大，適應(yīng)度差的染色體被遺傳到下一代的可能性就越小。 （ 5） 交叉算子：根據(jù)選擇操作得到的兩個染色體個體，以一定的概率按照某種方式互換一些基因，從而得到子代染色體的過程即形成新的子代種群。 （ 6） 變異算子：對染色體個體的某些基因按照一定的概率進(jìn)行變換即改變自身染色體的基因位。 （ 7） 終止條件：染色體群體經(jīng) 過選擇、交叉、變異，在進(jìn)化一定的代數(shù)后，滿足終止的條件就停止計算，并輸出所得到的結(jié)果。否則返回步驟（ 3）。 GA 算法的流程圖如圖 所示： 天津理工大學(xué) 20xx 屆本科畢業(yè)設(shè)計說明書 8 開 始產(chǎn) 生 初 始 種 群計 算 個 體 適 應(yīng) 度 值選 擇交 叉變 異滿 足 終 止 條件 ？輸 出 最 優(yōu) 解結(jié) 束否是 圖 遺傳算法流程圖 MATLAB 仿真技術(shù) MATLAB 是一種以矩陣作為基本數(shù)據(jù)單遠(yuǎn)的程序設(shè)計語言，其具備數(shù)據(jù)分析、算法實現(xiàn)以及應(yīng)用開發(fā)的交互式開發(fā)環(huán)境。 MATLAB 分為總包和若干個工具箱，具有強大的數(shù)值計算天津理工大學(xué) 20xx 屆本科畢業(yè)設(shè)計說明書 9 能力、數(shù)據(jù)可視化能力與符號計算能力，逐步發(fā)展成為各種學(xué)科、多種工作平臺下功能強大的大型 軟件，可以方便實現(xiàn)數(shù)值分析、優(yōu)化分析、數(shù)據(jù)處理、自動控制、信號處理等領(lǐng)域的數(shù)學(xué)計算，也可以快捷實現(xiàn)計算可視化、圖形控制、場景創(chuàng)建和渲染、圖像處理、虛擬現(xiàn)實和地圖制作等分析處理工作。 MATLAB 已經(jīng)成為線性代數(shù)、自動控制理論、概率論及數(shù)理統(tǒng)計、數(shù)字信號處理、時間序列分析、動態(tài)系統(tǒng)仿真等課程的基本教學(xué)工具。 其中 MATLAB仿真技術(shù)在工程上和科學(xué)實驗上起到很大影響，可以用來完成 系統(tǒng)的設(shè)計、性能評估、測試 、 進(jìn)行數(shù)學(xué)模型、專業(yè)模型的模擬，復(fù)雜數(shù)值計算等工作。 同時 在經(jīng)濟領(lǐng)域，可以進(jìn)行數(shù)據(jù)評價， 高等數(shù)值計算、 數(shù)值分析和 預(yù)測等。 這些功能強大的仿真軟件 ,使得 物流系統(tǒng) 仿真的設(shè)計和分析過程變得相對直觀和便捷 ,由此也使得 車輛路徑優(yōu)化 系統(tǒng)仿真技術(shù)得到了更快的發(fā)展。 車輛路徑優(yōu)化 系統(tǒng)仿真貫穿著 車輛路徑優(yōu)化 系統(tǒng)工程設(shè)計的全過程 ,對 車輛路徑優(yōu)化 系統(tǒng)的發(fā)展起著舉足輕重的作用。 車輛路徑優(yōu)化 系統(tǒng)仿真具有廣泛的適應(yīng)性和極好的靈活性 ,有助于我們更好地研究 車輛路徑優(yōu)化 系統(tǒng)性能。 天津理工大學(xué) 20xx 屆本科畢業(yè)設(shè)計說明書 10 第三章 復(fù)雜路徑優(yōu)化問題 問題的描述 車輛路徑優(yōu)化問題可以描述為：從發(fā)貨中心用一輛汽車向一個收貨點送貨，這個收貨點的位置和需求量一定 ，這輛汽車的負(fù)載重量一定，運輸方式有三種車 1 運輸，車 2 運輸，車三運輸，合理安排汽車路線，使總運距最短，并滿足一下條件：每天送貨路徑上只有一個收貨點和送貨點，且只能由一輛汽車送貨。 通過分析上述車輛路徑優(yōu)化問題的約束條件和優(yōu)化目標(biāo)可知，車輛路徑優(yōu)化問題可以歸結(jié)為最短路徑問題。本問題為單量汽車的送貨路徑優(yōu)化，求得滿足經(jīng)濟指標(biāo)和環(huán)境指標(biāo)的單輛汽車的最優(yōu)送貨路徑后。因此，為便于問題的討論，本文對單輛汽車的送貨路徑優(yōu)化進(jìn)行研究。其模型如圖 所示： v 0v 2v 1v 3v 4v 5v 6v 7cbcbcbaabcbaaaabcbc6553432363224242314 — a— ：車 1 運輸 — b— ：車 2 運輸 — c— ：車 3 運輸 圖 車輛路徑優(yōu)化 VRP 模型 為了更清楚地描述車輛路徑問題，我們可以用 ( , , )G V A B? 來表示聯(lián)運網(wǎng)絡(luò)結(jié)合圖 的 VRP 模型，其中 V 表示各個節(jié)點的集合，而 A 表示節(jié)點之間的運輸方案集合， B 表示節(jié)點之間的中轉(zhuǎn)方案集合，以圖 為例，節(jié)點有 0V 、 1V 、 2V 3V 、 4V 、 5V 、 6V 以及 7V ，運輸方式有車 1 運輸，車 2 運輸和車 3 運輸，中轉(zhuǎn)方案包括中轉(zhuǎn)時間和中轉(zhuǎn)成本，每條路徑上的數(shù)字 表示各運輸方式所需要花費的運輸成本，如 0V → 1V 車 1 運輸成本 1（萬元），車 2運輸成本 4（萬元），車 3運輸成本 6（萬元）。 而本文研究的是將運輸任務(wù)分解成一系列的有順序的分段運輸任務(wù)，每個分段運輸任務(wù)有多個運輸者。相鄰的分段運輸任務(wù)之間存在任務(wù)的中轉(zhuǎn)和銜接。用圖 ( , , )G V A B? 表示天津理工大學(xué) 20xx 屆本科畢業(yè)設(shè)計說明書 11 聯(lián)運網(wǎng)絡(luò)； V 表示節(jié)點集合， ivV? ? ?1,..., 1in??表示中轉(zhuǎn)節(jié)點、 0v 表示起點、 nv 表示終點；A 表示節(jié)點間的運輸方案的集合， ? ?,ijv v m A? 表示節(jié)點 iv 、 jv 之間的一個運輸方案，其中 ，,m M M? 表示運輸方式集合（同一種運輸方式下，若有多個運輸者可選擇， m 可表示不同的運輸者）；當(dāng)節(jié)點 iv 處發(fā)生轉(zhuǎn)運時，需要一定的中轉(zhuǎn)時間和中轉(zhuǎn)成本，不同運輸方式之間的中轉(zhuǎn)時間、成本存在差異， B 表示中轉(zhuǎn)方案集合， ? ?,iv p m B? 表示在節(jié)點 iv 的承運方式 p 和 m 進(jìn)行轉(zhuǎn)運的中轉(zhuǎn)方案。 在對問題進(jìn)行進(jìn)一步研究之前，根據(jù)問題的特點，作以下假設(shè)： （ 1）只有一個車場且車場與收貨點的位置是確定的。 （ 2）收貨點的需求量己知。 （ 3）每輛車在進(jìn)行送貨時，其裝載量不能超過其最大容量。 （ 4）車場的車輛是同一車型，車輛數(shù)目和車輛最大容量事先知道。 （ 5）忽略不確定性因素的影響，認(rèn)為運輸方案和中轉(zhuǎn)方案是已知的、確定性的。 （ 6）不考慮由于受天氣狀況、 交通狀況、路況、節(jié)點能力等因素的影響。 問題 的 符號表示 ijms ：運輸方式 m 在節(jié)點 iv 、 jv 之間運輸?shù)奶寂欧帕浚?g） ； ijmd ：燃油消耗量（ kg）； me ： 運輸方式 m 的碳排放因子（ g/kgfuel）； ijmr ：運輸方式 iv 、 jv 之間的平均運輸速度； ijl ：節(jié)點 iv 、 jv 之間的距離； ? ?,BTFT ：運輸任務(wù)時間窗約束，即 貨物運達(dá) nv 的時刻應(yīng)處在時間窗 ? ?,BTFT 內(nèi)； ipm? ：在節(jié)點 iv 處自 p 到 m 的中轉(zhuǎn)成本； ijm? ：運輸者 m 針對節(jié)點 iv 、 jv 間的運輸成本； ipm? ：在節(jié)點 iv 處自 p 到 m 的中轉(zhuǎn)時間； ijmt ：運輸者 m 針對節(jié)點 iv 、 jv 間的運輸時間； ijma ： 01 變量，若經(jīng)營者選擇運輸方案 ( , , )ijv v m ，則 ijma =1，否則 ijma =0； ipmb ： 01 變量，若在 iv 處 p 和 m 之間存在中轉(zhuǎn)，則 ipmb =1，否則， ipmb =0； 問題的 數(shù)學(xué)模型 （ 1）碳排放計量為： ijm ijm ms d e??， ( , , )ijv v m A? ， mM? （ ） （ 2）對于一種 給定的運輸方式，其單位距離下的燃油消耗量和速度的二次方成正比 [3233]，所以燃油消耗和運輸速度之間