【正文】 了本文中所提出的方法的有效性，所得到的近似最優(yōu)解能夠?yàn)槲锪髋渌推髽I(yè)提供一個(gè)令人滿意的車輛調(diào)度與路徑規(guī)劃的方案。 物流業(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ā)揮著重要作用。已經(jīng)出臺(tái)的一些政策措施有待進(jìn)一步落實(shí)，一些地方針對(duì)物流企業(yè)的亂收費(fèi)、亂罰款問(wèn)題突出。 因此提升物流經(jīng)濟(jì)效益成為關(guān)鍵。在遺傳算法中，問(wèn)題不同解被 假設(shè)成“種群”中不同個(gè)體（即染色體），各染色體通過(guò)交叉、變異產(chǎn)生下一代染色體（即后代），適應(yīng)值高的染色體具有比較高的選中概率，經(jīng)過(guò)若干代操作將產(chǎn)生最好的染色體。 由于遺傳算法屬于一種基于自然選擇和遺傳變異等生物進(jìn)化機(jī)制而發(fā)展起來(lái)的高度并行、隨機(jī)、自適應(yīng)的智能全局搜索算法，遺傳算法（ GA） 的應(yīng)用范圍非常廣泛 [45]， 用于來(lái)解決傳統(tǒng)搜索方法無(wú)法解決的非線性問(wèn)題。 在送貨過(guò)程中，核心內(nèi)容就是送貨了。即便是同一條線路的短途運(yùn)輸可能會(huì)因?yàn)榫€路復(fù)雜，碳排放量多等問(wèn)題造成總成本 過(guò)高，所以合理規(guī)劃運(yùn)輸路線對(duì)送貨成本的影響要比一般的運(yùn)輸大很多，合理的規(guī)劃配送路線有利于對(duì)送貨速度，成本等實(shí)現(xiàn)有效的控制。（ 3）有利于企業(yè)提高經(jīng)濟(jì)效益。 國(guó)內(nèi)外研究現(xiàn)狀 車輛路徑優(yōu)化問(wèn) 題 （ Vehicle Routing Problem） 是 經(jīng)典的優(yōu)化組合問(wèn)題， 最早 由Dantizing 和 Ramser[6]在 1959 年 提出 。Amico et al [9]在 Montane 和 Galvao 提出的數(shù)學(xué)模型的基礎(chǔ) 上，采用分支定價(jià)方法成功的對(duì)中小規(guī)模的 VRPSPD 問(wèn)題進(jìn)行了求解。 彭春林，梁春華，周泓 [17]研究了 VRPSPD 問(wèn)題 ， 并設(shè)計(jì)了改進(jìn)的遺傳算法 ， 算法采用邊重組的交叉 操作，成功對(duì)該問(wèn)題進(jìn)行了求解；張濤，余綽婭，劉嵐 [18]等人建立了 VRPSPD 問(wèn)題的機(jī)會(huì)約束規(guī)劃模型，并根據(jù)問(wèn)題的特點(diǎn)，設(shè)計(jì)了改進(jìn)的分散搜索算法對(duì)問(wèn)題進(jìn)行了求解；張濤， 田文馨，張杰，劉士新 [19]研究了 VRPSPD 問(wèn)題 ， 考慮了車輛的最大行程約束條件 ，建立了問(wèn)題的混合整數(shù)規(guī)劃數(shù)學(xué)模型 ， 并設(shè)計(jì)了改進(jìn)的蟻群算法 ， 對(duì)該問(wèn)題進(jìn)行了求解 ；張濤，張春梅，張玥杰 [20]針對(duì) VRPSPD 問(wèn)題 ， 建立了問(wèn)題的數(shù)學(xué)模型 ， 設(shè)計(jì)了協(xié)同粒子群 模擬退火算法 ， 成功對(duì)該問(wèn)題進(jìn)行了求解 ；胡大偉，陳誠(chéng)和郭曉汾 [21]研究了多車場(chǎng) VRPSPD問(wèn)題，采用多階段方法得到了最優(yōu)解；龍磊，陳秋雙等 [22]研究了 VRPSPD 問(wèn)題，并建立了數(shù)學(xué)模型，設(shè)計(jì)了改進(jìn)的 GA 算法，算法采用特定的交叉算子和種群更新方法，成功解決了該問(wèn) 題。趙振勇 [31]等人給出了遺傳算法的改進(jìn)方法，并對(duì)系統(tǒng)進(jìn)行了分析和研究。 天津理工大學(xué) 20xx 屆本科畢業(yè)設(shè)計(jì)說(shuō)明書(shū) 6 第二章介紹了實(shí)現(xiàn) 基于改進(jìn)遺傳算法的復(fù)雜網(wǎng)絡(luò)路徑優(yōu)化問(wèn)題 時(shí)所使用的關(guān) 鍵技術(shù)，詳細(xì)地闡述了 在遺傳算法中編碼，生成初始種群，適應(yīng)性值評(píng)估，選擇，交叉，變異，確定最優(yōu)解等 實(shí)現(xiàn)遺傳算法 等技術(shù)的工作原理以及 仿真實(shí)驗(yàn)的介紹 。 第 六 章總結(jié)了在開(kāi)發(fā) 基于改進(jìn)遺傳算法的復(fù)雜網(wǎng)絡(luò)路徑優(yōu)化問(wèn)題時(shí) 所 遇到的各種問(wèn)題，在總結(jié)的過(guò)程中對(duì)這些問(wèn)題進(jìn)行深入的思考，提出了未來(lái)可以進(jìn)一步改進(jìn)的解決方案。 在遺傳（ GA） 算法中，首先通過(guò)一定的編碼方式生成初始群體，然后在每個(gè)染色體上執(zhí)行選擇算子（ Selection Operator）、交叉算子（ Crossover Operator）、變異算子（ Mutation Operator）這些操作，并從中選出適應(yīng)度高的染色體進(jìn)化，從而實(shí)現(xiàn)優(yōu)勝劣汰的進(jìn)化過(guò)程，算法的具體操作過(guò)程如下： （ 1） 染色體編碼： GA 不能對(duì)問(wèn) 題的一些參數(shù)進(jìn)行直接處理，所以需要將問(wèn)題的解通過(guò)一定的編碼方式編碼為染色體，染色體編碼的好壞直接影響計(jì)算消耗的時(shí)間，算法運(yùn)行的快慢，所以一般情況下為節(jié)省算法運(yùn)行時(shí)間采用自然數(shù)直接編碼的方式。 （ 4） 選擇策略：其是為了從當(dāng)前的群體中選出優(yōu)良的染色體復(fù)制到下一代群體中，染色體的適應(yīng)度越高，被復(fù)制到下一代的可能性就大，適應(yīng)度差的染色體被遺傳到下一代的可能性就越小。否則返回步驟（ 3）。 其中 MATLAB仿真技術(shù)在工程上和科學(xué)實(shí)驗(yàn)上起到很大影響，可以用來(lái)完成 系統(tǒng)的設(shè)計(jì)、性能評(píng)估、測(cè)試 、 進(jìn)行數(shù)學(xué)模型、專業(yè)模型的模擬，復(fù)雜數(shù)值計(jì)算等工作。 車輛路徑優(yōu)化 系統(tǒng)仿真具有廣泛的適應(yīng)性和極好的靈活性 ,有助于我們更好地研究 車輛路徑優(yōu)化 系統(tǒng)性能。因此，為便于問(wèn)題的討論，本文對(duì)單輛汽車的送貨路徑優(yōu)化進(jìn)行研究。用圖 ( , , )G V A B? 表示天津理工大學(xué) 20xx 屆本科畢業(yè)設(shè)計(jì)說(shuō)明書(shū) 11 聯(lián)運(yùn)網(wǎng)絡(luò)； V 表示節(jié)點(diǎn)集合， ivV? ? ?1,..., 1in??表示中轉(zhuǎn)節(jié)點(diǎn)、 0v 表示起點(diǎn)、 nv 表示終點(diǎn)；A 表示節(jié)點(diǎn)間的運(yùn)輸方案的集合， ? ?,ijv v m A? 表示節(jié)點(diǎn) iv 、 jv 之間的一個(gè)運(yùn)輸方案，其中 ，,m M M? 表示運(yùn)輸方式集合（同一種運(yùn)輸方式下，若有多個(gè)運(yùn)輸者可選擇， m 可表示不同的運(yùn)輸者）；當(dāng)節(jié)點(diǎn) iv 處發(fā)生轉(zhuǎn)運(yùn)時(shí)，需要一定的中轉(zhuǎn)時(shí)間和中轉(zhuǎn)成本，不同運(yùn)輸方式之間的中轉(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)方案。 （ 4）車場(chǎng)的車輛是同一車型，車輛數(shù)目和車輛最大容量事先知道。 天津理工大學(xué) 20xx 屆本科畢業(yè)設(shè)計(jì)說(shuō)明書(shū) 13 第四章 改進(jìn)遺傳算法設(shè)計(jì) 染色體編碼方式 染色體的編碼對(duì)遺傳算法的實(shí)現(xiàn)尤為重要，不同的染色體編碼決定了算法的運(yùn)行時(shí)間，以及解碼的難易程度。如圖 所示，其染色體編碼包含了運(yùn)輸方式和中轉(zhuǎn)方式的選擇。 （ 3）隨機(jī)生成 3L 條路徑。 天津理工大學(xué) 20xx 屆本科畢業(yè)設(shè)計(jì)說(shuō)明書(shū) 14 設(shè) ()h? 、 ()th、 ()sh 分別表示路徑 h 的運(yùn)輸成本、運(yùn)輸時(shí)間和碳排放量， max? 、 min? 、maxs 、 mins 分別表示 ()h? 、 ()th的上限、下限。 本文采用的交叉算子 ，在進(jìn)行 交叉過(guò)程中 進(jìn)行 互換的最小整體為線路 。在GA 算法中，變異可以擴(kuò)大算法的搜索空間，保持群體中染色體個(gè)體的多樣化，從而避免了局部最優(yōu)解的產(chǎn)生。( , )G V A? 中 0{ , ..., , , , ..., }f g h nh v v v v v? 是 從 0v 到 nv 的一條路徑， 具體的操作 如下： 1. 基因插入：若 ( , )gjvv 、 39。 0{ , ..., , , ..., }f h nh v v v v? ； 3. 基因變換：若 ( , )fjvv、 39。如果一直進(jìn)化，當(dāng)算法運(yùn)行到預(yù)先設(shè)定的最大的進(jìn)化代數(shù)時(shí)，就終止算法，把得到的結(jié)果輸出。 承運(yùn)人 1 2 3 4 5 6 7{ , , , , , , }P p p p p p p p? 。某集團(tuán)采用了表 1給出的 IPCC 國(guó)家溫室氣體清單指南發(fā)布的不同運(yùn)輸方式的 p? 排放因子。 仿真實(shí)驗(yàn) 根據(jù)驗(yàn)證算法的比較結(jié)果得出采用遺傳算法更具有效性，則設(shè)初始種群為 10，進(jìn)化次數(shù)為 50，交叉、變異概率分別為 和 ，在考慮碳排放指標(biāo)（ ? =0）和不考慮碳排放指標(biāo) （ ? =1）情況下進(jìn)行模擬。本文針對(duì)考慮燃油消耗和碳排放的 VRP 問(wèn)題進(jìn)行了研究，主要的研究工作總結(jié)如下： （ 1）首先針對(duì)考慮燃油消耗和碳排放的 VRP 問(wèn)題 ，然后建立了相應(yīng)的數(shù)學(xué)模型，并設(shè)計(jì)了改進(jìn) TS算法，算法中采用有效的解的表示方式、初始解的產(chǎn)生、解的評(píng)價(jià)方法、終止條件以及算法的框架，最后進(jìn)在標(biāo)準(zhǔn)的 VRP 算例上行了仿真實(shí)驗(yàn)，并對(duì)結(jié)果進(jìn)行了分析。 （ 5）仿真實(shí)驗(yàn)結(jié)果表明該方法可以得到一個(gè)令人滿意的車輛調(diào)度與路徑規(guī)劃的方案，此方案可以在不顯著改變物流企業(yè)運(yùn)作成本的情況下使得燃油消耗和碳排放成本得到了明顯的降低，為企業(yè)在進(jìn)行車輛調(diào)度時(shí)提供了有益的參考思路。 在此過(guò)程中，我收獲的不僅僅是一份畢業(yè)設(shè)計(jì)，還從 老師 這里學(xué)到了很多工作 方法與習(xí)慣，我對(duì)技術(shù)的理解也得到了更進(jìn)一步的提升。 。在 大學(xué) 本科四年的 生活與 學(xué)習(xí)中，同學(xué)們 之間有著 良好的 學(xué)習(xí) 氛圍 與融洽的關(guān)系，這 為我 技術(shù)上的進(jìn)步提供了良好的環(huán)境。 Amico, G. Righini, and M. Salani. A branchandprice approach to the vehicle routing problem with simultaneous distribution and collection [J]. Transportation Science, 20xx, 40(2): 235247. [10]J. Dethloff. Vehicle routing and reverse logistics: the vehicle routing problem with simultaneous delivery and pickup [J]. OR spectrum, 200l, 23(1): 7996. [11]G. Nagy and S. Salhi. Heuristic algorithms for single and multiple depot vehicle routing problems with pickups and deliveries [J]. European Journal of Operational Research, 20xx, 162(1): 126141. [12]. Chen and TH. Wu. Vehicle routing problem with simultaneous deliveries and pickups [J]. Journal of the Operational Research Society, 20xx, 57(5): 579587. [13]N. Bianchessi and G. Righini. Heuristic algorithms for the vehicle routing problem with simultaneous [14]肖健梅 , 李軍軍 , 王錫淮 . 求解車輛路徑問(wèn)題的改進(jìn)微粒群優(yōu)化算法 [J]. 計(jì)算機(jī)集成制造系統(tǒng) , 20xx, 11(4): 578581. [15]符桌 . 帶裝載能力約束的 開(kāi)放式車輛路徑問(wèn)題及其禁忌搜索算法研究 [J]. 系統(tǒng)工程理論與實(shí)踐 , 20xx, 3: 123128. [16]馬建華 , 房勇 , 袁杰 . 多車場(chǎng)多車型最快完成車輛路徑問(wèn)題的變異蟻群算法 [J]. 系統(tǒng)工程理論與實(shí)踐 , 20xx, 31(8): 15091516. [17]彭春林 , 梁春華 , 周泓 . 求解同時(shí)取貨和送貨車輛路徑問(wèn)題的改進(jìn)遺傳算法 [J]. 系統(tǒng)仿真學(xué)報(bào) , 20xx, 20(9): 22662270. 天津理工大學(xué) 20xx 屆本科畢業(yè)設(shè)計(jì)說(shuō)明書(shū) 22 [18]張濤 , 余綽婭 , 劉嵐 , 邵志芳 等 . 同時(shí)送取貨的隨機(jī)旅行時(shí)間車輛路徑問(wèn)題方法 [J]. 系統(tǒng)工程理論與實(shí)踐 , 20xx, 31(10): 19131920. [19]張濤 , 田文馨 , 張杰 等 . 帶車輛行程約束的 VRPSPD問(wèn)題的改進(jìn)蟻群算法 [J]. 系統(tǒng)工程理論與實(shí)踐 , 20xx, 1: 133140. [20]張濤 , 張春梅 , 張玥杰 . 協(xié)同粒子群 模擬退火算法求解 VRPSPD問(wèn)題 [J]. 系統(tǒng)管理學(xué)報(bào) , 20xx, 18(6): 682685. [21]胡大偉 , 陳誠(chéng) , 郭曉汾 . 帶集貨和配送的多 VRP優(yōu)化算法研究 ,數(shù)學(xué)的實(shí)踐與認(rèn)識(shí) [J]