【正文】 式之間的中轉(zhuǎn)時(shí)間、成本存在差異， B 表示中轉(zhuǎn)方案集合， ? ?,iv p m B? 表示在節(jié)點(diǎn) iv 的承運(yùn)方式 p 和 m 進(jìn)行轉(zhuǎn)運(yùn)的中轉(zhuǎn)方案。否則返回步驟（ 3）。 天津理工大學(xué) 20xx 屆本科畢業(yè)設(shè)計(jì)說明書 6 第二章介紹了實(shí)現(xiàn) 基于改進(jìn)遺傳算法的復(fù)雜網(wǎng)絡(luò)路徑優(yōu)化問題 時(shí)所使用的關(guān) 鍵技術(shù)，詳細(xì)地闡述了 在遺傳算法中編碼，生成初始種群，適應(yīng)性值評(píng)估，選擇，交叉，變異，確定最優(yōu)解等 實(shí)現(xiàn)遺傳算法 等技術(shù)的工作原理以及 仿真實(shí)驗(yàn)的介紹 。 國(guó)內(nèi)外研究現(xiàn)狀 車輛路徑優(yōu)化問 題 （ Vehicle Routing Problem） 是 經(jīng)典的優(yōu)化組合問題， 最早 由Dantizing 和 Ramser[6]在 1959 年 提出 。 由于遺傳算法屬于一種基于自然選擇和遺傳變異等生物進(jìn)化機(jī)制而發(fā)展起來的高度并行、隨機(jī)、自適應(yīng)的智能全局搜索算法，遺傳算法（ GA） 的應(yīng)用范圍非常廣泛 [45]， 用于來解決傳統(tǒng)搜索方法無法解決的非線性問題。 物流業(yè)融合 多種產(chǎn)業(yè)形成一種 復(fù)合型服務(wù)產(chǎn)業(yè)，是國(guó)民經(jīng)濟(jì)的 重要組成部分，涉及領(lǐng)域廣，吸納就業(yè)人數(shù)多，促進(jìn)生產(chǎn)、拉動(dòng)消費(fèi)作用大，在 經(jīng)濟(jì)方式的轉(zhuǎn)變和加快 產(chǎn)業(yè)結(jié)構(gòu)調(diào)整 等方面 發(fā)揮著重要作用。隨著我國(guó)的集裝箱路徑優(yōu)化日趨國(guó)際化，這些問題導(dǎo)致的影響日益突出，而從定量的角度對(duì)復(fù)雜網(wǎng)絡(luò)下的路徑優(yōu)化問題進(jìn)行研究，對(duì)于提高我國(guó)綜合運(yùn)輸服務(wù)效率和水平，具有很強(qiáng)的理論價(jià)值和廣闊的應(yīng)用前景。同時(shí)，隨著經(jīng)濟(jì)的快速發(fā)展，環(huán)境問題越來越嚴(yán)重，許多國(guó)家開始實(shí)施節(jié) 能減排政策，以減少對(duì)環(huán)境的污染，企業(yè)也更加關(guān)注在進(jìn)行貨物運(yùn)輸過程中車輛的燃油消耗和碳排放，減少車輛在運(yùn)輸過程中的碳排放有助于減少對(duì)環(huán)境的污染，綠色出行的觀念已經(jīng)深入人心，可以為企業(yè)帶來巨大的社會(huì)效益，并且碳排放交易已經(jīng)走進(jìn)中國(guó)市場(chǎng)，減少碳排放就是在節(jié)約金錢。配送運(yùn)輸是屬于短途運(yùn)輸，送貨路線短但較繁雜。 隨著物流業(yè)的高速發(fā)展， 國(guó)內(nèi)越來越多的學(xué)者和專家開始研究 VRP 問題以及其變種問題 ，一些 主要的研究如下 ：肖健梅，李軍軍，王錫淮 [14]研究了 VRP 問題，設(shè)計(jì)了一種新穎的編碼方式，并通過對(duì)微粒群算法進(jìn)行改進(jìn)，成功對(duì)該問題進(jìn)行 了求解；符桌 [15]研究了開放式的 VRP 問題，考慮了車輛的裝載容量的約束，并用禁忌搜索算法對(duì)問題進(jìn)行了求解；馬建華，房勇，袁杰 [16]以最快完成為目標(biāo) 研究了 VRP 問題 ， 考慮了多種車輛型號(hào)和多個(gè)配送中心等約束條件 ， 用變異的蟻群算法對(duì)問題進(jìn)行了求解 。其中 在每一代的群體中，按照每個(gè)染色體的適應(yīng)性優(yōu)劣，選擇出一些良好的染色體復(fù)制到下一代種群中，接著通過染色體之間的交叉、變異生成新的染色體。 車輛路徑優(yōu)化 系統(tǒng)仿真貫穿著 車輛路徑優(yōu)化 系統(tǒng)工程設(shè)計(jì)的全過程 ,對(duì) 車輛路徑優(yōu)化 系統(tǒng)的發(fā)展起著舉足輕重的作用。 問題 的 符號(hào)表示 ijms ：運(yùn)輸方式 m 在節(jié)點(diǎn) iv 、 jv 之間運(yùn)輸?shù)奶寂欧帕浚?g） ； ijmd ：燃油消耗量（ kg）； me ： 運(yùn)輸方式 m 的碳排放因子（ g/kgfuel）； ijmr ：運(yùn)輸方式 iv 、 jv 之間的平均運(yùn)輸速度； ijl ：節(jié)點(diǎn) iv 、 jv 之間的距離； ? ?,BTFT ：運(yùn)輸任務(wù)時(shí)間窗約束，即 貨物運(yùn)達(dá) nv 的時(shí)刻應(yīng)處在時(shí)間窗 ? ?,BTFT 內(nèi)； ipm? ：在節(jié)點(diǎn) iv 處自 p 到 m 的中轉(zhuǎn)成本； ijm? ：運(yùn)輸者 m 針對(duì)節(jié)點(diǎn) iv 、 jv 間的運(yùn)輸成本； ipm? ：在節(jié)點(diǎn) iv 處自 p 到 m 的中轉(zhuǎn)時(shí)間； ijmt ：運(yùn)輸者 m 針對(duì)節(jié)點(diǎn) iv 、 jv 間的運(yùn)輸時(shí)間； ijma ： 01 變量，若經(jīng)營(yíng)者選擇運(yùn)輸方案 ( , , )ijv v m ，則 ijma =1，否則 ijma =0； ipmb ： 01 變量，若在 iv 處 p 和 m 之間存在中轉(zhuǎn)，則 ipmb =1，否則， ipmb =0； 問題的 數(shù)學(xué)模型 （ 1）碳排放計(jì)量為： ijm ijm ms d e??， ( , , )ijv v m A? ， mM? （ ） （ 2）對(duì)于一種 給定的運(yùn)輸方式，其單位距離下的燃油消耗量和速度的二次方成正比 [3233]，所以燃油消耗和運(yùn)輸速度之間的非線性關(guān)系為： 2ijm m ijm ijd r l?? ? ? （ ） 則目標(biāo) 函數(shù)為：? ?1 ( , , ) , ,m i n i j iijm ijm ip m ip mv v m A v p m Bf a b???????? （ ） 天津理工大學(xué) 20xx 屆本科畢業(yè)設(shè)計(jì)說明書 12 2 ( , , )m i n ij ijm ijmv v m Af s a?? ? （ ） . ( , , ) ( , , )()i j iijm ijm ip m ip mv v m A v p m BB T t a b F T???? ? ???； （ ） j V j Vjim ijmv m M v m Maa??????? ? ? ?001,1,0, \ { , }iinvvvvv V v v?????????； （ ） 1ipmp M m M b?? ??? ， 0\{ , }inv V v v? ； （ ） ipmp Mm Mb????=jV ijmv m Ma? ???， 0\{ , }inv V v v? ； （ ） 0 0b? ， 0nb? ； （ ） {0,1}ijma ? ， ( , , )ijv v m A??； （ ） {0,1}ipmb ? ， ( , , )ipv v m B??； （ ） 其中：模型包含兩個(gè)指標(biāo)，式（ ）表示考慮成本指標(biāo)，式（ ）表示考慮碳排放指標(biāo)；式（ ）表示關(guān)于時(shí)間窗的約束；式（ ）表示節(jié)點(diǎn)流量平衡約束；式（ ）、（ ）表示每個(gè)節(jié)點(diǎn)至多被訪問一次；式（ ）表示在起點(diǎn)、終點(diǎn)處不計(jì)時(shí)間和成本；式（ ）、（ ）表示決策變量的取值約束 。當(dāng)有 2 個(gè)以上的公共節(jié)點(diǎn)時(shí)，按照等概率選擇其中之一作為交叉點(diǎn)。 終止條件 本文設(shè)計(jì)的算法終止條件如下： 當(dāng)某一解連續(xù)進(jìn)化一定的代數(shù)后，其適應(yīng)度值仍然沒有變化，就終止算法，把得到的天津理工大學(xué) 20xx 屆本科畢業(yè)設(shè)計(jì)說明書 15 結(jié)果輸出。 天津理工大學(xué) 20xx 屆本科畢業(yè)設(shè)計(jì)說明書 20 第六章 總結(jié) 隨著 經(jīng)濟(jì)的發(fā)展 ， 環(huán)境問題嚴(yán)峻 ， 全球各國(guó)日益 重視碳排放，車輛在運(yùn)輸過程中碳排放量被更多消費(fèi)者和物流企業(yè)所關(guān)注，如何合理安排車輛的路徑，在不顯著改變物流企業(yè)運(yùn)作成本的情況下，使得燃油消耗和碳排放成本得到明顯的降低，已經(jīng)成為多數(shù)企 業(yè)的選擇。 最后，我要感謝我的父母 ， 你們對(duì)我的關(guān)心 與 支持是我 前進(jìn) 的動(dòng)力，謝謝你們 。 本文為驗(yàn)證算法的有效性，采用貪婪算法和遺傳算法，利用適應(yīng)度函數(shù)公式 （ ）、（ ）來進(jìn)行驗(yàn)證， 當(dāng) ? =0 時(shí)，即 不考慮碳排放量，比較貪婪算法和遺傳算法的求解時(shí)間和方案成本， time 表示求解時(shí)間， cost 表示方案成本，則驗(yàn)證算法如表 2： 天津理工大學(xué) 20xx 屆本科畢業(yè)設(shè)計(jì)說明書 18 表 2 貪婪算法與遺傳算法相比較 實(shí)例 貪婪算法 遺傳算法 time cost time cost 1 2 3 4 5 6 7 8 9 10 從表 2 可以看出，在求解時(shí)間方面，貪婪算法和遺傳算法求解時(shí)間相接近，但在方案成本方面，相比采用貪婪算法，采用遺傳算法的方案成本明顯較低。( , )fhv v A? ，則 39。而本問題中，目標(biāo)函數(shù)是最小化總成本，即適應(yīng)度函數(shù)值越小，對(duì)應(yīng)的染色體的適應(yīng)度就越大，所以直接采用目標(biāo)函數(shù)值的倒數(shù)作為適應(yīng)度函數(shù)。 （ 3）每輛車在進(jìn)行送貨時(shí)，其裝載量不能超過其最大容量。 MATLAB 已經(jīng)成為線性代數(shù)、自動(dòng)控制理論、概率論及數(shù)理統(tǒng)計(jì)、數(shù)字信號(hào)處理、時(shí)間序列分析、動(dòng)態(tài)系統(tǒng)仿真等課程的基本教學(xué)工具。 第五章通過算例分析進(jìn)行仿真實(shí)驗(yàn) ，通過詳細(xì)的測(cè)試對(duì)該 問題 進(jìn)行了可行性驗(yàn)證 以及對(duì)結(jié)果的分析 。 Montane 和 Galvao[8]研究了 VRPSPD 問題，提出了一個(gè)基于 VRPSPD 的貨物流模型； Dell39。 本課題的研究目的是對(duì)車輛路徑的選擇與規(guī)劃問題進(jìn)行研究，以車輛的最短路徑為研究對(duì)象，以車輛的碳排放量費(fèi)用和成本為約束條件來確定最短路徑，從而降低成本。 其物流成本較高、效率較低， 條塊分割嚴(yán)重，阻礙物流業(yè)發(fā)展的體制機(jī)制障礙仍未打破 且 政策法規(guī)體系還不夠完善，市場(chǎng)秩序不夠規(guī)范。 基于改進(jìn)遺傳算法的復(fù)雜網(wǎng)絡(luò)路徑優(yōu)化問題 摘要 隨著全球化進(jìn)程的不斷加快，各類型跨國(guó)企業(yè)在世界范圍內(nèi)的生產(chǎn)、銷售及售后服務(wù)推動(dòng)了原材料、產(chǎn)品及配件在全球的有序流動(dòng)，在這種全球供應(yīng)鏈的大背景下，大型國(guó)際物流公司紛紛依托其覆蓋全球的綜合運(yùn)輸服務(wù)網(wǎng)絡(luò)為貨主提供“門到門”的物流服務(wù)，而各個(gè)中小型物流公司也依托該網(wǎng)絡(luò)開展自己的業(yè)務(wù)。已經(jīng)出臺(tái)的一些政策措施有待進(jìn)一步落實(shí)，一些地方針對(duì)物流企業(yè)的亂收費(fèi)、亂罰款問題突出。 在送貨過程中，核心內(nèi)容就是送貨了。Amico et al [9]在 Montane 和 Galvao 提出的數(shù)學(xué)模型的基礎(chǔ) 上，采用分支定價(jià)方法成功的對(duì)中小規(guī)模的 VRPSPD 問題進(jìn)行了求解。 第 六 章總結(jié)了在開發(fā) 基于改進(jìn)遺傳算法的復(fù)雜網(wǎng)絡(luò)路徑優(yōu)化問題時(shí) 所 遇到的各種問題，在總結(jié)的過程中對(duì)這些問題進(jìn)行深入的思考，提出了未來可以進(jìn)一步改進(jìn)的解決方案。 其中 MATLAB仿真技術(shù)在工程上和科學(xué)實(shí)驗(yàn)上起到很大影響，可以用來完成 系統(tǒng)的設(shè)計(jì)、性能評(píng)估、測(cè)試 、 進(jìn)行數(shù)學(xué)模型、專業(yè)模型的模擬，復(fù)雜數(shù)值計(jì)算等工作。 （ 4）車場(chǎng)的車輛是同一車型，車輛數(shù)目和車輛最大容量事先知道。 天津理工大學(xué) 20xx 屆本科畢業(yè)設(shè)計(jì)說明書 14 設(shè) ()h? 、 ()th、 ()sh 分別表示路徑 h 的運(yùn)輸成本、運(yùn)輸時(shí)間和碳排放量， max? 、 min? 、maxs 、 mins 分別表示 ()h? 、 ()th的上限、下限。 0{ , ..., , , ..., }f h nh v v v v? ； 3. 基因變換：若 ( , )fjvv、 39。 仿真實(shí)驗(yàn) 根據(jù)驗(yàn)證算法的比較結(jié)果得出采用遺傳算法更具有效性，則設(shè)初始種群為 10，進(jìn)化次數(shù)為 50，交叉、變異概率分別為 和 ，在考慮碳排放指標(biāo)（ ? =0）和不考慮碳排放指標(biāo) （ ? =1）情況下進(jìn)行模擬。 。結(jié)果如表 3 所示： 表 3 求解質(zhì)量 實(shí)例 考慮碳排放指標(biāo) 不考慮碳排放指標(biāo) M_C M_S M_C M_S 1 2 3 4 5 6 7 8 9 10 天津理工大學(xué) 20xx 屆本科畢業(yè)設(shè)計(jì)說明書 19 4905005105205305405505605701 2 3