《基于遺傳算法的物流車輛路徑規(guī)劃探究》15000字

PAGE3基于遺傳算法的物流車輛路徑規(guī)劃研究TOC\o"1-2"\h\u15193第一章緒論 191291.1研究背景與意義 1180741.2國內(nèi)外研究發(fā)展現(xiàn)狀 396241.3本文主要內(nèi)容 5242861.4本文組織結(jié)構(gòu) 5264251.5本章小結(jié) 619666第二章相關(guān)技術(shù)介紹 737072.1車輛路徑問題描述 7263192.2車輛路徑規(guī)劃常用算法 8265802.3遺傳算法 10248202.4本章小結(jié) 1429308第三章總體設(shè)計(jì)與建模 15130233.1總體架構(gòu) 1540213.2CVPR數(shù)學(xué)模型 16267223.3基于遺傳算法的CVPR設(shè)計(jì)流程 17300163.4本章小結(jié) 187334第四章算法實(shí)現(xiàn) 19175074.1編碼設(shè)計(jì) 1970634.2初始種群生成 20292254.3評價(jià)種群 21173014.4遺傳算子設(shè)計(jì) 22212054.5本章小結(jié) 2420922第五章仿真 25270245.1實(shí)驗(yàn)數(shù)據(jù) 25218075.2實(shí)驗(yàn)結(jié)果 2626330第六章總結(jié) 28108666.1完成的工作 28213276.2存在的問題及下一步工作 289590參考文獻(xiàn) 29第一章緒論1.1研究背景與意義由于經(jīng)濟(jì)社會(huì)的不斷發(fā)展，物流已經(jīng)成為在勞動(dòng)力和資源以后的“第三利潤源泉”，物流配送是對利潤源泉進(jìn)行挖掘的重要突破口，也引起了物流行業(yè)的高度關(guān)注。當(dāng)前世界各國的物流配送都呈現(xiàn)出迅猛的發(fā)展態(tài)勢，物流配送數(shù)量迅猛增加，配送規(guī)模不斷擴(kuò)大，出現(xiàn)了一些先進(jìn)的配送方式，比如即時(shí)配送（JIT）等[1]，同時(shí)物流配送的水平也在不斷提升。當(dāng)前我國企業(yè)結(jié)合政府部門對于物流配送的發(fā)展都非常關(guān)注，并且我國政府專門針對物流配送出臺了一系列的扶持和鼓勵(lì)政策，由于我國對物流業(yè)的發(fā)展高度關(guān)注，近幾年國內(nèi)物流配送服務(wù)迅猛發(fā)展，并且成為很多企業(yè)強(qiáng)化自身競爭力和加強(qiáng)成本控制的有力手段。當(dāng)前物流的高速發(fā)展，為城市的建設(shè)帶來了非常有利的機(jī)會(huì)，要實(shí)現(xiàn)城市的信息化，離不開物流的現(xiàn)代化，城市的建設(shè)和發(fā)展也需要完善的物流配送體系，為其提供支撐[2]。由于我國城市化進(jìn)程的逐步推進(jìn)，不管是經(jīng)濟(jì)發(fā)展，還是城市的基礎(chǔ)設(shè)施建設(shè)與交通運(yùn)輸布局亦或是城市的空間結(jié)構(gòu)，都需要對原來的物流體系升級改進(jìn)。我國自21世紀(jì)初以來面向物流業(yè)推出了一系列的扶持政策，表示對物流行業(yè)發(fā)展的關(guān)注與支持，同時(shí)很多城市也意識到物流發(fā)展對城市建設(shè)與發(fā)展的重要意義，我國物流產(chǎn)業(yè)也逐漸步入良性發(fā)展時(shí)期。對于城市來說物流的發(fā)展能夠?qū)?jīng)濟(jì)建設(shè)產(chǎn)生非常重要的拉動(dòng)作用，夠使城市在經(jīng)濟(jì)和物流領(lǐng)域的中心地位得到有效提升，并且當(dāng)前物流業(yè)已經(jīng)不單純是某個(gè)行業(yè)，而是成為經(jīng)濟(jì)競爭力提升的重要條件。在物流活動(dòng)中配送是非常重要的業(yè)務(wù)方式，并且和資金流與物流以及商流有非常密切的聯(lián)系，涉及資金流與物流以及商流等各種活動(dòng)，所以也可以將配送理解為一種包括各種物流活動(dòng)的業(yè)務(wù)形式。配送涵蓋了物流功能的全部要素，可以將其看作是物流的一個(gè)縮影，也可以將其看作是物流中各種活動(dòng)在一定小范圍的表現(xiàn)。一般的配送包括運(yùn)輸與保管，以及包裝和裝卸等環(huán)節(jié)，通過這些活動(dòng)共同完成配送。配送系統(tǒng)的運(yùn)行會(huì)影響整個(gè)物流系統(tǒng)的運(yùn)行，要確保物流系統(tǒng)的良好發(fā)展，需要制定科學(xué)的規(guī)劃策略。若是依然采用傳統(tǒng)的規(guī)劃方式進(jìn)行組織配送，那么很可能會(huì)帶來一系列問題，主要包括：(1)服務(wù)量的下降。在城市中物流配送的目的是服務(wù)于民眾的基本生活，同時(shí)還需要為工業(yè)企業(yè)進(jìn)行產(chǎn)成品與零部件以及原材料等的配送，所以城市物流配送的商品與貨物呈現(xiàn)出流向多變，并且流量大和批次多的特征。但是傳統(tǒng)物流配送主要是依賴人工進(jìn)行調(diào)度，因?yàn)檎{(diào)度規(guī)模比較大，很難快速完成處理，所以會(huì)影響配送服務(wù)的及時(shí)性，同時(shí)也會(huì)消耗比較長的時(shí)間。由于物流配送的業(yè)務(wù)規(guī)模不斷擴(kuò)大，傳統(tǒng)的物流配送服務(wù)模式已經(jīng)無法使配送質(zhì)量得到保證。(2)物流成本控制困難。在傳統(tǒng)的物流配送中，我交一輛比較小，那么就能夠?qū)ε渌瓦M(jìn)行比較科學(xué)的安排，可以有效降低成本，然而當(dāng)交易速度加快、交易規(guī)模擴(kuò)大之后，僅僅依賴人工已經(jīng)無法完成配送調(diào)度的任務(wù)，會(huì)造成大量的不合理調(diào)度，嚴(yán)重影響物流成本的管控。(3)加大城市的負(fù)擔(dān)。現(xiàn)階段，城市經(jīng)濟(jì)社會(huì)活動(dòng)面臨的最突出的問題就是環(huán)境惡化以及交通資源短缺。如果不能合理調(diào)度物流配送，會(huì)導(dǎo)致配送成本大幅增加，并且增加交通事故發(fā)生的概率，會(huì)進(jìn)一步加重原本就已經(jīng)非常沉重的交通負(fù)擔(dān)，同時(shí)配送調(diào)度不合理還會(huì)造成大量廢氣的排放。所以基于現(xiàn)階段的技術(shù)和經(jīng)濟(jì)社會(huì)條件，對物流配送進(jìn)行研究有非常重要的現(xiàn)實(shí)意義，并且非常迫切。1.2國內(nèi)外研究發(fā)展現(xiàn)狀車輛路徑問題（VehicleRoutingProblem,VRP）本質(zhì)上可以理解為優(yōu)化組合問題，在日常的生活中和理論研究中都具有意義。VRP屬于NP難題。VRP在文獻(xiàn)中也也被稱為車輛調(diào)度或者派遣問題。Dantzig和Ramse在上世紀(jì)50年代末首次提出這一概念，引起了很多研究者的關(guān)注，基于經(jīng)典或創(chuàng)新的優(yōu)化算法對其進(jìn)行研究。車輛路徑問題涉及的因素眾多，在研究中需要考慮的層面眾多，不同的角度研究的結(jié)果之間差異較大，所以本文重點(diǎn)是從帶能力約束的車輛路徑問題展開研究，通過對車輛能力的約束，保證車輛路徑規(guī)劃問題在解決的過程中各項(xiàng)數(shù)據(jù)信息的完整性和科學(xué)性。車輛的載貨量達(dá)到設(shè)計(jì)要求。Clarke和Wright[3]在上世紀(jì)60年代初針對車隊(duì)配送問題進(jìn)行分析，指出啟發(fā)式節(jié)省法在車輛路線的規(guī)劃和成本的控制上具有很好的效果，隨后引起了計(jì)算機(jī)應(yīng)用以及運(yùn)籌學(xué)等領(lǐng)域?qū)＜业年P(guān)注，該算法能夠快速完成求解并且簡單易懂，但是主要適用于較為簡單、小規(guī)模車輛路徑問題的求解。上世紀(jì)90年代早期，ElhassaniaM[4]等主要對動(dòng)態(tài)車輛路徑問題的求解進(jìn)行分析，提出可以應(yīng)用遺傳算法進(jìn)行求解，在研究過程中應(yīng)用了交叉算子以及啟發(fā)式算法，通過研究對該算法的有效性進(jìn)行了驗(yàn)證。Karakati?S[5]等學(xué)者在對多中心的車輛路徑問題進(jìn)行分析時(shí)，提出可通過遺傳算法進(jìn)行求解，并且對各種遺傳方法的效率進(jìn)行了評估。MungwattanaA[6]等學(xué)者在對VRPTW進(jìn)行研究時(shí)提出，可以通過遺傳算法以及局部搜索下降法的方式進(jìn)行求解，通過實(shí)驗(yàn)對方法的可行性進(jìn)行驗(yàn)證，并證明了該方法求解的高效性。相比較而言，我國到90年代才開始興起關(guān)于車輛路徑問題的研究，比國外起步要晚，并且研究成果相對較少，目前的研究主要是通過遺傳算法進(jìn)行求解，有的學(xué)者覺得遺傳算法的收斂效果不高，算法的科學(xué)性和精準(zhǔn)性不高，以及計(jì)算時(shí)間長等問題提出了改進(jìn)方法，主要是單親遺傳算法，以及優(yōu)化遺傳算子和改進(jìn)編碼方式等等。上世紀(jì)90年代末，李大衛(wèi)和王莉[7]等學(xué)者通過研究改進(jìn)了遺傳算法的交叉算子以及編碼方式，能夠通過更加直觀的方式進(jìn)行編碼，同時(shí)提出了以優(yōu)先關(guān)系為基礎(chǔ)的交叉算子，在對算法改善之后可以有效的解決車輛路徑規(guī)劃上的問題。宋偉剛等[8]學(xué)者在2005年對遺傳算法進(jìn)行了改進(jìn)，主要是對其中的交叉算子進(jìn)行優(yōu)化，使得算法的尋優(yōu)能力得到有效提升，并且能夠有效避免出現(xiàn)早熟的情況。2006年姜靈敏[9]在對此類問題進(jìn)行研究時(shí)提出，綜合應(yīng)用爬山法和遺傳算法可以有效提高求解效率，同時(shí)還能夠?qū)獾馁|(zhì)量進(jìn)行優(yōu)化。2009年龍磊[10]等學(xué)者針對存在同時(shí)急送或需求的車輛路徑問題進(jìn)行探究，指出通過B型算法能夠使求解速度得到有效提升，能夠獨(dú)立進(jìn)行不同子群體的遺傳操作。詹孝龍[11]對車輛路徑問題情況進(jìn)行分析時(shí)，提出了一種新的改進(jìn)遺傳算法，主要是應(yīng)用交叉算子進(jìn)行遺傳算法的構(gòu)建。姚衛(wèi)粉[12]等學(xué)者主要針對遺傳算法存在的早熟現(xiàn)象進(jìn)行分析，通過研究指出，動(dòng)態(tài)小生境協(xié)同進(jìn)化遺傳算法的應(yīng)用能夠有效解決這種早熟現(xiàn)象帶來的問題，同時(shí)也可以使調(diào)節(jié)效率得到提升。黃務(wù)蘭和張濤[13]在對帶時(shí)間窗的車輛路徑問題進(jìn)行探究時(shí)，提出可以將段和點(diǎn)交叉段子結(jié)合起來對遺傳算法進(jìn)行改進(jìn)，對該算法的效果進(jìn)行驗(yàn)證，指出該算法的收斂速度更快，并且在全局尋優(yōu)能力方面也具有一定的優(yōu)勢。1.3本文主要內(nèi)容文章的研究主要是為了給物流配送作業(yè)的決策提供支持，重點(diǎn)對CVRP問題進(jìn)行分析和探究，并且通過建立數(shù)學(xué)模型，以遺傳算法為基礎(chǔ)，制定路徑規(guī)劃策略，滿足物流運(yùn)輸成本最小化。本文的主要研究內(nèi)容為：(1)建立帶能力約束的車輛路徑問題模型，將車輛行駛的總油耗成本最少作為目標(biāo)函數(shù)。(2)改進(jìn)優(yōu)化遺傳算法中的遺傳算子與適應(yīng)度函數(shù)，以及染色體編碼等，用遺傳算法解決物流配送路徑規(guī)劃問題。(3)完成模型創(chuàng)建和數(shù)據(jù)分析，實(shí)現(xiàn)對物流配送問題的仿真實(shí)驗(yàn)。1.4本文組織結(jié)構(gòu)本文共分為六章，各章內(nèi)容如下：第1章，緒論。首先闡述物流配送的背景及意義，簡要介紹車輛路徑問題的研究和發(fā)展現(xiàn)狀，說明了本文的研究意義與結(jié)構(gòu)安排。第2章，相關(guān)技術(shù)介紹。介紹了經(jīng)典VRP問題的定義與描述，分析對比了車輛路徑問題（VRP）的幾種常見求解算法。并重點(diǎn)闡述了遺傳算法的基本概念與原理，及其特點(diǎn)。第3章，總體設(shè)計(jì)與建模。介紹了設(shè)計(jì)車輛路徑規(guī)劃程序的整體架構(gòu)，建立帶能力約束的車輛路徑問題（CVRP）數(shù)學(xué)模型，設(shè)計(jì)基于遺傳算法的CVPR工作流程。第4章，算法實(shí)現(xiàn)。闡述了算法實(shí)現(xiàn)的各個(gè)模塊，將建立的CVPR數(shù)學(xué)模型與算法術(shù)語具體結(jié)合，以此設(shè)計(jì)出獨(dú)特的編碼方式，并對初代種群、適應(yīng)度函數(shù)以及遺傳算子進(jìn)行了改進(jìn)優(yōu)化。第5章，仿真實(shí)例。通過對一個(gè)常見路網(wǎng)模型進(jìn)行仿真模擬。根據(jù)實(shí)驗(yàn)的數(shù)據(jù)進(jìn)行實(shí)驗(yàn)驗(yàn)證分析，找出最佳方案，為車輛路徑規(guī)劃問題的解決提供保障。最后，總結(jié)與展望。對本文研究內(nèi)容的總結(jié)以及未來發(fā)展目標(biāo)的規(guī)劃，為接下來的工作指明方向1.5本章小結(jié)本章簡要分析物流配送的意義研究背景、以及國內(nèi)外相關(guān)領(lǐng)域的研究和發(fā)展現(xiàn)狀。最后，陳述了本文的主要工作及本文的組織結(jié)構(gòu)。第二章相關(guān)技術(shù)介紹2.1車輛路徑問題描述隨著經(jīng)濟(jì)的發(fā)展和技術(shù)的進(jìn)步車輛路徑問題開始成為社會(huì)關(guān)注的焦點(diǎn)，特別是在融入運(yùn)籌學(xué)、數(shù)學(xué)、圖論、計(jì)算機(jī)應(yīng)用及交通運(yùn)輸?shù)葘W(xué)科之后，公路交通運(yùn)輸以及車輛路徑管理成為人們經(jīng)濟(jì)發(fā)展的重要考慮層面，對于改善人們生產(chǎn)效率起到極大的幫助。郭耀煌、李軍在對物流行業(yè)的研究中將VRP定義為：運(yùn)輸車隊(duì)在物流配送中心的監(jiān)管下，實(shí)現(xiàn)對多個(gè)城市運(yùn)輸過程中的路線優(yōu)化，創(chuàng)建的最佳路線運(yùn)輸方案，并結(jié)合運(yùn)輸過程中的各個(gè)約束要求，例如運(yùn)輸?shù)臅r(shí)間、距離、重量以及成本控制等，最終實(shí)現(xiàn)用最低的成本達(dá)到運(yùn)輸?shù)哪康?。在對車輛路徑問題的研究中經(jīng)常被描述為；假設(shè)存在一個(gè)配送中心存在n輛車,此時(shí)需要m個(gè)結(jié)點(diǎn)對其進(jìn)行運(yùn)輸服務(wù),節(jié)點(diǎn)的運(yùn)輸量為gi(i=1,2,...,m)<(i=1,2,…,C),每輛車最大的貨物裝載量為Q.設(shè)Cij就是在運(yùn)輸過程中需要付出的成本,也就是約束能力的條件.此時(shí)的配送中心編號為0,節(jié)點(diǎn)的信息數(shù)據(jù)為i(i=1,2,...,m),可以將其定義為：(2-1)(2-2)VRP問題的數(shù)學(xué)模型：(2-3)(2-4)(2-5)(2-6)(2-7)2.2車輛路徑規(guī)劃常用算法2.2.1精確算法精確算法指的是能夠計(jì)算得到最優(yōu)解的一種算法，對于VRP問題的求解而言，常用的精確算法包括網(wǎng)絡(luò)流算法與動(dòng)態(tài)規(guī)劃法，以及割平面法和分枝定界法、等。(1)分枝定界法[14]。該方法在對VRP問題進(jìn)行求解時(shí)，主要的思路是先求解與原VRP問題(A)對應(yīng)的不含整數(shù)約束的VRP問題(B)的最優(yōu)解，若是得到整數(shù)解，那么該解就是原問題的最優(yōu)解。就是得到的解不是整數(shù)，那么就需要將非整數(shù)解的相鄰整數(shù)作為一種附加條件，然后得到兩個(gè)分枝,這就是形成的兩個(gè)子問題，在此基礎(chǔ)上對此問題進(jìn)行求解。(2)割平面法。用該方法對問題進(jìn)行求解的思路主要是，對問題(B)進(jìn)行求解時(shí)增加了線性約束條件，也就是割平面，主要是割掉問題B的一部分可行域，以此保留保留整數(shù)解而舍棄非整數(shù)解，最終剛好有一個(gè)整數(shù)坐標(biāo)點(diǎn)為問題A的最優(yōu)解。因?yàn)樵摲椒ㄐ枰^長的時(shí)間才能完成求解，因此對于大規(guī)模問題同樣不適用。(3)動(dòng)態(tài)規(guī)劃法[15-16]。Eilon等人最早通過研究提出動(dòng)態(tài)規(guī)劃法，該方法主要是通過遞歸方法求解固定車輛數(shù)的VRP問題。將問題分解為多階段其策略求解，然后分別對不同階段的問題進(jìn)行求解，這些階段彼此之間存在遞推關(guān)系，通過該方法能夠得到問題的最優(yōu)解，但是同樣只適用于小規(guī)模問題的求解。(4)網(wǎng)絡(luò)流算法[17]。該算法在對問題進(jìn)行求解時(shí)的思路主要是，先完成VRP問題網(wǎng)絡(luò)模型的構(gòu)建，然后從中發(fā)現(xiàn)需調(diào)量最大的弧，在此基礎(chǔ)上對弧兩端節(jié)點(diǎn)以及弧流量的位勢進(jìn)行調(diào)節(jié)，從而使弧上的虛調(diào)量得到減少，最終讓全部弧的需調(diào)量都為零。因?yàn)檫叺臄?shù)目和頂點(diǎn)的數(shù)目會(huì)對算法的執(zhí)行效率產(chǎn)生直接影響，因此只適用于小規(guī)模VRP問題應(yīng)用中。精確算法在能夠求解的條件下與啟發(fā)式算法相比，精確算法得到的解往往更優(yōu)，主要適用于一些小規(guī)模問題的求解，特別是對于一些邊界和結(jié)構(gòu)都比較清晰的良性結(jié)構(gòu)問題是很好的解決辦法。因?yàn)槿绻麊栴}有比較清晰的邊界與結(jié)構(gòu)，那么就有對解進(jìn)行判定的明確準(zhǔn)則，同時(shí)得到的解也可以很好的反映解決問題的方案，不需要耗費(fèi)太大的工作量就可以完成求解。然而在實(shí)踐中，由于問題自身結(jié)構(gòu)以及問題規(guī)模，如果應(yīng)用精確算法進(jìn)行求解，可能會(huì)出現(xiàn)指數(shù)爆炸問題，所以精確算法的應(yīng)用范圍較為有限，只是用于小規(guī)模和中等規(guī)模確定性VRP問題的求解?；谏鲜龇治瞿軌虬l(fā)現(xiàn)，在求解VRP問題方面，沒有可能的高效的精確算法，因此需要找到能夠?qū)ζ溥M(jìn)行求解的近似算法，基于這種環(huán)境，有研究者提出啟發(fā)式算法，并且啟發(fā)式算法也成為解決VRP問題的重要方式。對2.2.2啟發(fā)式算法(1)線路構(gòu)造算法(TourConstructiveAlgorithm)。主要是基于特定的準(zhǔn)則，每一次都需要在線路中增加一個(gè)不在其上的點(diǎn)，直到線路中安排全部的點(diǎn)。構(gòu)造算法是最早應(yīng)用于VSP問題以及TSP問題的求解，其特點(diǎn)在于具有較強(qiáng)的靈活性，并且求解速度比較快，但是找到的解可能同最優(yōu)解之間有很遠(yuǎn)的距離。(2)節(jié)約法[18]。ClarkeandWright在上世紀(jì)60年代早期，通過研究提出這一算法，所以該算法也被稱為ClarkeandWright算法。其特點(diǎn)在于對容量車輛路徑問題能夠很好的解決，并且不限制車輛的數(shù)目。該方法的思路主要是先假設(shè)，所有的線路中都有一個(gè)車庫和顧客，遵循最大節(jié)省費(fèi)用原則對兩條路線進(jìn)行合并，該方法相對較為復(fù)雜。(3)禁忌搜索(簡稱TS)[19]。Glover最早提出禁忌搜索，是在局部領(lǐng)域搜索的基礎(chǔ)上進(jìn)行的一種擴(kuò)展，其本質(zhì)屬于全局迭代尋優(yōu)算法，能夠通過禁忌準(zhǔn)則和靈活的存儲結(jié)構(gòu)對迂回搜索進(jìn)行規(guī)避，同時(shí)可以利用特赦規(guī)則對被禁忌的優(yōu)良狀態(tài)進(jìn)行赦免，一方面可以保證搜索的多樣性和有效性，另一方面也可以實(shí)現(xiàn)全局的優(yōu)化。競技搜索主要是對已經(jīng)搜索到的局部最優(yōu)解進(jìn)行標(biāo)記，然后通過迭代搜索對這些對象進(jìn)行避開，但是并非絕對禁止循環(huán)，通過這種方式確保對各個(gè)區(qū)域進(jìn)行有效搜索，并不斷對其進(jìn)行改進(jìn)，在此過程中產(chǎn)生的一些車輛路線不一定可行，所以需要通過目標(biāo)罰函數(shù)對這些不可行的路線進(jìn)行測量，并對其進(jìn)行改正。Tabu搜索法對目標(biāo)函數(shù)并沒有太多的要求，在理論上能夠找到全局的最優(yōu)解，并且能夠快速完成。但禁忌搜索在搜索效率方面，可能會(huì)對初始解有較強(qiáng)的依賴性，需要精心構(gòu)造禁忌表結(jié)構(gòu)以及搜索領(lǐng)域結(jié)構(gòu)。(4)模擬退火算法(SimulatedAnnealing，SA)[20]。模擬退火算法主要是在熱力學(xué)退火原理基礎(chǔ)上進(jìn)行隨機(jī)搜索的一種算法，最早出現(xiàn)在上世紀(jì)中期，直到上世紀(jì)80年代才在組合優(yōu)化領(lǐng)域得到應(yīng)用。模擬退火算法的思路主要是將目標(biāo)函數(shù)作為能量函數(shù)，對物理學(xué)中的固體物質(zhì)退火處理進(jìn)行模擬，如果能夠應(yīng)用適當(dāng)?shù)耐嘶鸩襟E，就可以形成能量最低的基態(tài)。應(yīng)用模擬退火算法進(jìn)行問題求解時(shí)，需要接受目標(biāo)函數(shù)有改進(jìn)的狀態(tài)。模擬退火算法算較于其他算法來說對目標(biāo)函數(shù)沒有特殊的要求，在理論上能夠找到全局最優(yōu)解，并且在大多數(shù)情況下都能得到質(zhì)量較好的解。然而模擬退火算法也有一定的缺陷，主要是很難控制冷卻溫度，在實(shí)踐中往往只能得到近似解，并且有非常龐大的算量，耗時(shí)比較長，這一點(diǎn)對模擬退火算法的實(shí)用性產(chǎn)生了一定的影響。(5)蟻群優(yōu)化算法(AntColonyOptimization，ACO)[21]。M.Dorigo等人通過蟻群覓食受到了啟發(fā)，進(jìn)而提出蟻群優(yōu)化算法，是一種在組合優(yōu)化問題進(jìn)行求解的基礎(chǔ)上進(jìn)行仿生進(jìn)化的算法，最初被稱為蟻群系統(tǒng)(AntSystem,AS)。該算法在求解一些較為復(fù)雜的組合優(yōu)化問題時(shí)，表現(xiàn)出了比較好的性質(zhì)以及比較強(qiáng)的尋優(yōu)能力。2.3遺傳算法2.3.1基本概念與原理遺傳算法[22-24]最早是在西方出現(xiàn)，是在達(dá)爾文生物進(jìn)化論基礎(chǔ)上發(fā)展而來，隨后被美國學(xué)者進(jìn)行深入研究并成為主流的算法，它以優(yōu)異的全局尋優(yōu)能力、自適性的搜索能力以及內(nèi)在的隱并行性滲透到了人工生命、組合優(yōu)化、自適應(yīng)控制、信號處理以及機(jī)器學(xué)習(xí)等領(lǐng)域，并取得了較好的成果。遺傳算法是一種啟發(fā)式迭代搜索技術(shù)。問題的潛在解決方案被編碼為染色體，這些染色體形成群體。適應(yīng)度函數(shù)使用在群體中的評價(jià)分析。在此基礎(chǔ)上選擇研究對應(yīng)的群體，適者生存。通過遺傳操作，例如交叉和突變，優(yōu)勝者有更好的機(jī)會(huì)被選擇和復(fù)制后代。重復(fù)該過程，群體通過代代進(jìn)化。經(jīng)過多代，種群收斂于質(zhì)量好的解決方案，最好的個(gè)體有很好的機(jī)會(huì)成為最優(yōu)或接近最優(yōu)的解決方案[25-26]。一個(gè)典型遺傳算法有如下要求：（1）解決方案域基因的表示。（2）一個(gè)適應(yīng)度函數(shù)來評估解決方案域。當(dāng)編碼和適應(yīng)度函數(shù)確定后，遺傳算法就會(huì)對解進(jìn)行初始化操作，然后通過重復(fù)應(yīng)用突變，交叉，倒置和選擇算子來改進(jìn)。遺傳算法的求解過程如圖2-1所示：圖2SEQ圖\*ARABIC\s11遺傳算法發(fā)的求解步驟(1)個(gè)體(individual)與種群(population)在遺傳算法中，問題可能潛在的解集形成一個(gè)集合，集合中的元素，即問題的一個(gè)潛在解決方案稱為個(gè)體，這個(gè)集合就叫種群。遺傳算法是從這個(gè)初代種群開始搜索解的。在不斷地進(jìn)化過程中，種群中的個(gè)體是不斷變化的，同時(shí)種群的規(guī)模保持不變，最終得到最優(yōu)的個(gè)體。(2)基因(Gene)與染色體(chromosome)基因是染色體特征的表達(dá)，是個(gè)體各項(xiàng)特征的基礎(chǔ)。染色體往往都是按照編碼的形式存在，是重要的遺傳物質(zhì)載體，基因組合組合在一起就是構(gòu)成個(gè)體行為特征的主要基礎(chǔ)，通過在個(gè)體內(nèi)部的組合，實(shí)現(xiàn)對個(gè)體特征的表達(dá)。(3)基因位點(diǎn)(Locus)基因位點(diǎn)就是基因位，通過對基因位的研究可以找出其在基因中的位置信息。一般在計(jì)算的過程都是按照從左向右的方式完成編號。(4)適應(yīng)度(Fitness)適應(yīng)度表示個(gè)體在環(huán)境中的生存能力。為更好的實(shí)現(xiàn)對種群的評價(jià)，這里會(huì)引入一個(gè)遺傳算法的概念，通過函數(shù)對種群中的個(gè)體進(jìn)行評價(jià)分析，即適應(yīng)度函數(shù)，已實(shí)現(xiàn)對數(shù)據(jù)的收集整理，確保對特征信息的準(zhǔn)確采集。但是適應(yīng)度函數(shù)的研究在很多時(shí)候存在不足，這就需要借助模擬方案實(shí)現(xiàn)對特征的掌握收集，確立自適應(yīng)函數(shù)，交互式遺傳算法也是很好的計(jì)算方式。(5)編碼（Coding）遺傳算法的編碼就是將研究對象按照一定的方式進(jìn)行編碼轉(zhuǎn)化為遺傳空間中可被識別的染色體信息。編碼的方式很多，常見的為二進(jìn)制編碼，實(shí)數(shù)編碼，整數(shù)編碼等。完備性、健全性和非冗余性是判斷編碼好壞的主要依據(jù)。不同的編碼方式造成的計(jì)算成本也是不同。在實(shí)際的問題中，應(yīng)根據(jù)問題的特點(diǎn)和復(fù)雜程度，設(shè)計(jì)較好的編碼方式。(6)遺傳算子（geneticoperator）（a）選擇算子（SelectOperator）遺傳算法在對群體中的個(gè)體特征進(jìn)行研究分析的過程中主要是借助遺傳算子完成。因此研究對象是下一代的主要遺傳載體，所以這一過程中也叫做再生(Reproduction)。個(gè)體在自適應(yīng)評價(jià)的過程中可以優(yōu)化自己的選擇方案。（b）交叉算子（CrossoverOperator）交叉算子可以對不同染色體上的基因位置進(jìn)行兩兩交換。這些過程最終產(chǎn)生與第一代不同的下一代染色體群體。選擇來自第一代的最佳個(gè)體以及小比例的適應(yīng)度低的個(gè)體，通過交叉處理，群體平均適合度將增加。這些適應(yīng)度低的個(gè)體確保了父一代遺傳庫內(nèi)的遺傳多樣性，并因此確保隨后一代種群的遺傳多樣性。（c）變異算子（MutationOperator）變異算子表示對目標(biāo)個(gè)體的特征進(jìn)行異化轉(zhuǎn)向。變異是隨機(jī)的無序的，因此無法判斷變異的好壞。但是變異的過程就是一個(gè)進(jìn)化的過程這一點(diǎn)可以通過算子進(jìn)行研究。當(dāng)所有的個(gè)體保持一致性時(shí)，新個(gè)體的出現(xiàn)就必須在變異的基礎(chǔ)上完成。也可以理解為變異就是對全局多樣性的維護(hù)，是保證個(gè)體差異化特征的基礎(chǔ)，正是在變異的基礎(chǔ)上才能實(shí)現(xiàn)全局優(yōu)化。2.3.2算法特點(diǎn)（1）自適應(yīng)性:遺傳算法在自適應(yīng)調(diào)節(jié)的過程中需要結(jié)合各項(xiàng)數(shù)據(jù)信息對自適應(yīng)的環(huán)境進(jìn)行調(diào)節(jié)，在此過程中適應(yīng)度高的個(gè)體將會(huì)存活下來，而自適應(yīng)低就會(huì)被自然淘汰。因此在對種群的規(guī)模進(jìn)行評價(jià)的過程中需要結(jié)合客觀的優(yōu)化評價(jià)體系進(jìn)行，創(chuàng)建函數(shù)完成評價(jià)。（2）全局最優(yōu)性:遺傳算法最優(yōu)解的求解是從全局出發(fā)，所以其搜索的范圍更加廣泛，是在整體的基礎(chǔ)上完成對最佳數(shù)據(jù)的分析，找出最佳問題解決方案。算法執(zhí)行交叉和變異就是對全局最佳方案的選擇，避免出現(xiàn)算法上的混亂。（3）并行性:遺傳算法在搜索的過程中其目標(biāo)的選擇對象可以是多個(gè)，也就是在多個(gè)個(gè)體特征上進(jìn)行處理，實(shí)現(xiàn)對不同自適應(yīng)度的評價(jià)分析，提高算法的計(jì)算效率，降低計(jì)算成本。（4）不確定性:遺傳算法的選擇、交叉和變異操作算子都是在一定概率的基礎(chǔ)上完成，對計(jì)算的方式方法進(jìn)行指導(dǎo)，因此可以理解為遺傳算法具有隨機(jī)性和不確定性。（5）通用性:遺傳算法在求解的過程中可以在單一信息的支持下完成對問題的分析，將問題解決方案轉(zhuǎn)化為潛在的染色體，通過染色體完成對自適應(yīng)的調(diào)節(jié)和使用，完成個(gè)體的評價(jià)。遺傳算法在問題的解決處理上具有通用性，適應(yīng)能力強(qiáng)。2.4本章小結(jié)本章對車輛路徑規(guī)劃問題展開介紹分析，通過對NP-hard難題的分析指出本文的研究思路，結(jié)合本文研究問題創(chuàng)建相關(guān)模型，列舉了VRP問題各類算法，重點(diǎn)對遺傳算法的路徑規(guī)劃思想展開介紹分析。第三章總體設(shè)計(jì)與建模3.1總體架構(gòu)根據(jù)路徑規(guī)劃算法的實(shí)際應(yīng)用場景，物流配送車路徑規(guī)劃程序的總體架構(gòu)分為三層，從左到右分別為：數(shù)據(jù)采集匯聚層、算法規(guī)劃層、表現(xiàn)層。系統(tǒng)總體架構(gòu)如圖3-1所示。圖3SEQ圖\*ARABIC\s11系統(tǒng)架構(gòu)圖數(shù)據(jù)采集匯聚層：主要通過RFID智能標(biāo)簽與車載GPS對路網(wǎng)信息，車輛運(yùn)輸及分布特點(diǎn)，客戶貨物需求量等數(shù)據(jù)進(jìn)行采集。對采集到的數(shù)據(jù)進(jìn)行預(yù)處理，構(gòu)建CVRP數(shù)學(xué)模型，確定車輛的數(shù)量等。算法規(guī)劃層：把車輛路線規(guī)劃的潛在解決方案編碼成染色體，生成初始種群。評價(jià)種群，遺傳進(jìn)化操作，直到得到適應(yīng)度最好的個(gè)體。通過遺傳算法的處理來實(shí)現(xiàn)物流配送車最優(yōu)路線方案的輸出，是系統(tǒng)處理中最重要一環(huán)表現(xiàn)層：由適應(yīng)度最高的個(gè)體映射出車輛最優(yōu)派遣方案，為相關(guān)物流配送作業(yè)提供決策支持。3.2CVPR數(shù)學(xué)模型定義如下：假設(shè)有運(yùn)輸車輛為m輛，每輛車的載貨量都是Q；面向的服務(wù)客戶數(shù)量為n，對客戶進(jìn)行編號i(i=2,Lni=0表示為配送中心，客戶i對貨物的需求數(shù)量為qi(i=2,Lnq0=0，并且任意客戶的貨物需求量qi要小于每輛車的額定載貨量Q；客戶i與客戶j之間的路程為dij，若客戶i、j之間不能連通則dij=0；車輛k從客戶i駛向客戶j到達(dá)之前車上配送物品的重量為wijk，若客戶i1j&j=0wijk=1。若車輛k訪問客戶i后訪問客戶j(i1jxijk=xijk=0；若客戶i的需求可以由車輛k滿足則yik=1yik=0。(3-1)約束條件為：(3-2)(3-3)(3-4)(3-5)(3-6)(3-7)其中，式（3-1）代表車輛運(yùn)輸過程中付出的油耗最小，式（3-2）表示客戶需要運(yùn)輸?shù)呢浳锊坏贸^車輛的最大承載量，式（3-3）表示可以運(yùn)輸?shù)能囕v為m輛，客戶的運(yùn)輸要求只能由一輛車服務(wù)，也即是客戶的貨物通過一輛車運(yùn)輸，式（3-4）和式（3-5）表示在運(yùn)輸?shù)倪^程中中間只能停靠一次，式（3-6）和（3-7）表示對變量的約束。3.3基于遺傳算法的CVPR設(shè)計(jì)流程車輛路徑問題需要考慮到車輛的數(shù)量和路線的選擇，在方案的確定上充滿隨機(jī)性和不確定性。遺傳算法（GA）屬于自然選擇的原啟發(fā)式方法，可以生成一些質(zhì)量比較高的解決方案，通過選擇、交叉以及突變等生物啟發(fā)運(yùn)算操作對問題進(jìn)行搜索和優(yōu)化，在對CVRP問題進(jìn)行求解時(shí)，遺傳算法的運(yùn)算流程詳見下圖4-2。圖3SEQ圖\*ARABIC\s12基于遺傳算法的車輛路徑規(guī)劃流程圖第一步：信息收集，對路網(wǎng)信息和貨物量數(shù)據(jù)進(jìn)行采集。第二步：要解決問題的特征以及信息完成相應(yīng)數(shù)學(xué)模型的構(gòu)建，也就是目標(biāo)函數(shù)的構(gòu)造。第三步：明確編碼方式，明確遺傳算子、最大遺傳代數(shù)，以及種群個(gè)體數(shù)量等相關(guān)參數(shù)之后，對潛在解決方案進(jìn)行編碼，形成各種基因的染色體。第四步：獲取研究初期的種群，按照研究的要求和設(shè)計(jì)的標(biāo)準(zhǔn)，獲取最大容量的種群染色體，作為研究的初始種群。第五步：評價(jià)種群，由目標(biāo)函數(shù)以及懲罰函數(shù)對研究的群體特征進(jìn)行評價(jià)，然后在自適應(yīng)的基礎(chǔ)上完成對個(gè)體特征的分析，結(jié)合適應(yīng)度值完成對個(gè)體的分析研究。第六步：遺傳操作，主要是對交叉、選擇和變異的分析研究。其中選擇算子能夠提高選擇適應(yīng)度值更大的個(gè)體的概率，能夠提高淘汰數(shù)值較小的個(gè)體的概率。交叉算子的存在可以按照確定的交叉概率對兩個(gè)個(gè)體進(jìn)行交叉操作。變異算子能夠按照變異概率進(jìn)行變異操作。第七步：終止條件判斷，通過不斷的進(jìn)化，最終符合終止條件，找到了適應(yīng)值最大的個(gè)體，若是沒有，則繼續(xù)執(zhí)行第五步。第八步：基于運(yùn)算結(jié)果對問題的最優(yōu)路徑進(jìn)行求解。3.4本章小結(jié)本章首先根據(jù)VRP問題的實(shí)際應(yīng)用場景介紹了設(shè)計(jì)車輛路徑規(guī)劃程序的總體架構(gòu)，然后根據(jù)第二章的相關(guān)技術(shù)的介紹和構(gòu)建了基于遺傳算法的路徑規(guī)劃原理和工作流程，結(jié)合研究對象特征，依據(jù)帶約束能力的要求創(chuàng)建研究模型。第四章算法實(shí)現(xiàn)4.1編碼設(shè)計(jì)遺傳搜索的基礎(chǔ)就是編碼，通過科學(xué)的編碼可以實(shí)現(xiàn)對遺傳搜索的科學(xué)性和完整性。針對車輛路徑優(yōu)化組合的研究中，能夠完成編碼的方式有很多，這里經(jīng)常使用到的就是二進(jìn)制編碼。整數(shù)編碼就是在整個(gè)基因值的基礎(chǔ)上通過整數(shù)進(jìn)行表達(dá)，整數(shù)的數(shù)值對應(yīng)個(gè)體的數(shù)量。本文使用的是整數(shù)編碼實(shí)現(xiàn)對車輛整體信息的表達(dá)。對于物流配送車路徑問題，用整數(shù)編碼，染色體的長度與車輛數(shù)和客戶數(shù)有關(guān)，當(dāng)有客戶數(shù)量為n，各客戶編號用i(i=1,2,...,n)表示。車輛數(shù)為m，則存在m條運(yùn)輸配送路徑。每條路徑都是從配送中心開始直到貨物配送目的地結(jié)束。這里使用0表示配送中心，整數(shù)編碼染色體的開始和最后都是0，為實(shí)現(xiàn)染色體在車輛信息的表達(dá)上更加科學(xué)準(zhǔn)確，在第1,2,3,...,n客戶中間插入m1個(gè)虛擬配送中心，這里也使用0表示，那么就可以得出：i12,Li1p,i21,i22,L,i2v,0,L,0,im1,im2,L,imw,0)，其中p+v+w=n，染色體的長度為n+m+1。這n個(gè)相互獨(dú)立的自然數(shù)彼此相加，m+1個(gè)0組成的n+m+1在整數(shù)編碼基礎(chǔ)上隨機(jī)排列就可以構(gòu)成一條染色體，也就是配送路徑的選擇依據(jù)。在對任意路徑的研究過程中，也就是在有效染色體的研究過程中需要滿足下面的條件：1）任意一條染色體的首尾必須為0。2）任意一條染色體中的兩個(gè)0不得相鄰。實(shí)例：在對物流配送的研究過程中，假設(shè)這里的車輛數(shù)為2，客戶數(shù)為7，設(shè)其隨機(jī)構(gòu)造的染色體為0215307640，那么對應(yīng)的長度為7+2+1=10，此時(shí)總路徑在2輛車的選擇上為：第一輛車路線：0→2→1→5→3→0；第二輛車路線：0→7→6→4→0；染色體中子路線之間可以是無序的，但是在每條子路線上訪問客戶點(diǎn)是有序的，改變子路線上客戶節(jié)點(diǎn)的訪問順序會(huì)導(dǎo)致目標(biāo)函數(shù)發(fā)生變化。針對路徑的規(guī)劃過程中，首先需要明確車輛的數(shù)量為m。車輛的約束條件也是研究的重點(diǎn)，為提高效率就需要降低車輛的運(yùn)輸成本。在對車輛數(shù)量的研究中公式如下所示：(4-1)其中，m表示當(dāng)前的車輛數(shù)量，qi代表客戶i需要運(yùn)輸?shù)呢浳锟偭?，Q表示車輛的最大載貨量，a(0<a<1)的值結(jié)合約束條件的限制得出，在約束條件減小的情況下，a取值增加，反之變小，這里的數(shù)值設(shè)置0.85，本文a=0.85。?表示數(shù)值下調(diào)。4.2初始種群生成本文研究中使用的是隨機(jī)但是具有約束的研究方式，這樣可以最大程度的保證收斂效果，提高種群的豐富性和多樣性，增加樣本中有效個(gè)體的數(shù)量。路徑規(guī)劃中的初始種群在最初的研究中都是建立在節(jié)點(diǎn)的基礎(chǔ)上，通過對車輛路徑的分析完成整體路徑的規(guī)劃。結(jié)合本文的研究完成編碼整理信息，詳細(xì)的操作方式如下所示：第一步：對客戶信息進(jìn)行編碼，用i(i=1,2,…,n)表示；第二步：根據(jù)客戶編號隨機(jī)產(chǎn)生一次客戶的排列，排列后重新編號e(e=1,2,…,n)，其對應(yīng)的貨物量為；第三步：從客戶對應(yīng)的第一個(gè)編號元素開始計(jì)算客戶點(diǎn)對應(yīng)的貨物累計(jì)需求量，若h滿足則針對客戶的排序進(jìn)行到h后就可以插入虛擬中心，以此內(nèi)推，直至插入(m-1)個(gè)0為止，然后在排列的開始和結(jié)束設(shè)置為0，這就是染色體形成的過程；第四步：重復(fù)上述步驟，直到滿足種群規(guī)模。4.3評價(jià)種群4.3.1定義懲罰函數(shù)以遺傳算法編碼為基礎(chǔ)設(shè)計(jì)的染色體，在進(jìn)行選擇、交叉和變異的過程之后，染色體的構(gòu)造形式就會(huì)發(fā)生變化，在實(shí)際的研究中每輛車的載貨量可能不滿足設(shè)計(jì)要求，這就需要使用到懲罰函數(shù)對系統(tǒng)進(jìn)行調(diào)整，懲罰函數(shù)的定義如下所示：(4-2)其中，T表示達(dá)不到約束條件車輛的懲罰值。這里為便于對懲罰函數(shù)進(jìn)行研究，在數(shù)值的選擇上往往較大。當(dāng)車輛的承載最大時(shí)，懲罰值為0；隨著車輛的載貨量提高，懲罰數(shù)值也會(huì)相應(yīng)的增加。4.3.2適應(yīng)度計(jì)算通過對種群中個(gè)體適應(yīng)度的計(jì)算分析，可以完成遺傳算法中的種群評價(jià)。針對本文的研究對象，為在最短時(shí)間內(nèi)將貨物送達(dá)制定地點(diǎn)，降低運(yùn)輸成本，需要對車輛的使用進(jìn)行合理的安排，設(shè)計(jì)出全局最優(yōu)規(guī)劃路徑，在車輛運(yùn)輸距離基礎(chǔ)上，對載貨量也要科學(xué)分析，實(shí)現(xiàn)成本的降低。因此本文的研究是在（3-1）式和（4-2）式組成得：(4-3)(4-4)其中，目標(biāo)函數(shù)為F，研究個(gè)體的適應(yīng)度值為f，在符合約束模型條件的基礎(chǔ)上，隨著f數(shù)值的增加，表示個(gè)體的適應(yīng)度也在不斷提高，個(gè)體在進(jìn)化的過程中具有更強(qiáng)的適應(yīng)能力，反之則在進(jìn)化的過程中更容易被自然淘汰。4.4遺傳算子設(shè)計(jì)4.4.1選擇算子選擇操作是在個(gè)體自適應(yīng)研究基礎(chǔ)上得出。這對于優(yōu)秀個(gè)體的遺傳和保留具有重要的作用，只有優(yōu)秀的個(gè)體才會(huì)被最大程度的保留下來。算子的選擇眾多，輪盤賭選擇、精英保留策略和確定式采樣等都是常見的方式。輪盤賭是在概率的基礎(chǔ)上將概率最大的個(gè)體保留下來，在算子的設(shè)計(jì)研究中扮演著重要的角色。精英保留策略是在遺傳個(gè)體中找出最佳的個(gè)體，并將其直接保留下來，然后和選擇之后的個(gè)體進(jìn)行比較，將表現(xiàn)優(yōu)異的個(gè)體保留下來，也就是不斷的用最好的替代最差的。確定式采樣就是在人為因素的干擾下對選擇的方式方法進(jìn)行設(shè)計(jì)明確。本文采用輪盤賭和精英保留策略組合的方式。相比其他方法具有高效、實(shí)用的特點(diǎn)。個(gè)體被選中的概率公式為：(4-5)其中，表示第i個(gè)個(gè)體被選擇的幾率，表示第i個(gè)個(gè)體適應(yīng)度數(shù)值。4.4.2交叉算子交叉算子，表示遺傳中的精子和卵子相互結(jié)合產(chǎn)生受精卵的過程，在生物遺傳上具有重要的研究價(jià)值，是分析生命起源的重要途徑。交叉算子在研究的過程中需要考慮雙方的聯(lián)系，就像是孩子出生之后，有的地方像父親，有的地方像母親，但是在個(gè)體的選擇上都是隨機(jī)的。本文算法中交叉概率pc=0.85。由于染色體中車輛的信息都是按照一定的順序排列，但是車輛的路徑都是隨機(jī)的。車輛的數(shù)量在染色體群定的情況下也是明確的，也就是當(dāng)染色體的數(shù)量為0時(shí)不得改變。所以這里介紹一種新的兩點(diǎn)交叉法。詳細(xì)的研究思路為：交叉點(diǎn)的出現(xiàn)是隨機(jī)的，如果此時(shí)出現(xiàn)的兩點(diǎn)交叉在數(shù)值上滿足，那么在此情況下出現(xiàn)的交叉點(diǎn)是有效的，反之則是無效的，那么就需要重新對兩點(diǎn)交叉點(diǎn)進(jìn)行生成；在交叉點(diǎn)出現(xiàn)的過程中子串的數(shù)值不得為0，如果存在0，就需要對子串的位置進(jìn)行移動(dòng)，直到該0消失為止；然后對子串的位置進(jìn)行交換；完成交換之后的基因必然會(huì)存在重復(fù)的信息，這里需要對其進(jìn)行清除。如果不存在子串0，就可以進(jìn)行交叉操作。例如：P1：（06830|521|0740）P1：（01680|273|0450）其中“|”表示交叉點(diǎn)，若交叉點(diǎn)的子串不含0，則可進(jìn)行交叉操作得到如下字串：Q1：（06830|273|0740）Q2：（01680|521|0450）交叉后發(fā)現(xiàn)Q1有重復(fù)的基因點(diǎn)3,7，Q2的重復(fù)基因點(diǎn)為1,5，保持兩個(gè)交叉點(diǎn)之間的基因不變，對其他重復(fù)位置的基因進(jìn)行操作，將基因點(diǎn)兩兩反向交換，得到：Q1：（06850|273|0140）Q2：（07680|521|0430）如果染色體交叉點(diǎn)子串中存在0，就需要對子串的位置進(jìn)行移動(dòng)，直到該0消失為止；然后進(jìn)行交叉操作。例如：P1：（06803|520|1740）P2：（01680|273|0450）將染色體P1中的交叉點(diǎn)向左移動(dòng)一位，得到：P1：（0680|352|01740）P2：（01680|273|0450）用上述方法進(jìn)行交叉運(yùn)算后得到：Q1：（0680|273|01540）Q2：（01680|352|0470）4.4.3變異算子變異是隨機(jī)的，變異的過程會(huì)產(chǎn)生節(jié)點(diǎn)用來替代之前的節(jié)點(diǎn)，在變異的過程中往往會(huì)出現(xiàn)更多的方案，對問題的解決提供研究思路，因?yàn)檫@也是解決方案的有效途徑。在突變的過程中觀察染色體的變化，選擇更好的對象，每個(gè)基因的突變概率為pm（通常在0.001?0.3內(nèi)），這里研究中設(shè)置pm=0.25。突變和交叉是相互作用的，其目的是保證重要信息的完整性和科學(xué)性。但是突變的信息保留非常短暫，這樣可以避免對下一代遺傳的破壞。在對染色體結(jié)構(gòu)的分析過程中，本文使用的是互換變異算子完成對路徑的分析研究?；Q變異算子的本質(zhì)就是在隨機(jī)變異基礎(chǔ)上完成對基因的分析和研究，為了提高變異效率，兩個(gè)基因需為非零且基因位置在不同子路徑實(shí)現(xiàn)。例如：P1：（06|8035201|740）其中“|”表示變異位，子路徑0680對應(yīng)的變異位為6，子路徑01740對應(yīng)的變異位為7，將兩者進(jìn)行交換變異得到：Q1：（078035201640）4.5本章小結(jié)整合現(xiàn)有第五章本章重點(diǎn)闡述了遺傳算法在求解該問題的幾個(gè)關(guān)鍵步驟，設(shè)計(jì)整數(shù)編碼的方式對染色體進(jìn)行編碼；本文研究中使用的是隨機(jī)但具有約束的研究方式，這樣可以最大程度的保證收斂效果，提高種群的豐富性和多樣性，增加樣本中有效個(gè)體的數(shù)量；算法在函數(shù)評價(jià)的過程中需要關(guān)注兩點(diǎn)：運(yùn)輸?shù)目偮烦毯蛙囕v的運(yùn)輸能力，目的是降低成本；對遺傳算子進(jìn)行優(yōu)化，保證收斂效果。第五章仿真5.1實(shí)驗(yàn)數(shù)據(jù)本次實(shí)驗(yàn)的數(shù)據(jù)來源于某大型連鎖物流中心，配送中心周邊分布著12個(gè)客戶節(jié)點(diǎn)，根據(jù)這12個(gè)客戶點(diǎn)的貨物需求量，由公式（4-8）可確定完成這些任務(wù)需要車輛數(shù)目m=4，其中每輛車的最大載重為70。客戶貨物需求量如表5-1所示。其中算法的控制參數(shù)設(shè)置：交叉概率為Pc=0.25，變異概率為Pm=0.25，種群規(guī)模N為600，進(jìn)化代數(shù)Gen為400。表5SEQ表\*ARABIC\s11客戶貨物需求量客戶編號i123456789101112貨物需求量qi121816291517112325211927路網(wǎng)信息記錄著任意兩個(gè)不同節(jié)點(diǎn)的連通性以及路程，如果兩個(gè)節(jié)點(diǎn)不能連通，則用路程0表示，如表5-2所示。表5SEQ表\*ARABIC\s12配送中心（i=0）及各客戶之間的路程客戶編號012345678910111200151317167.18.310.212.37.913.814.615.211509.1218.613.61016.825.52128.62730.12139.1012.4177.31419.719.22123.927.227.13172112.402810.82327.214.32520.730.5264168.616.528018.27.812.128.21929.423.429.257.1147.310.81801216.512.21516.621.52068.31013.522.87.812.206.920.61121.617.121.67101719.727.21216.56.9021.37.420.111.318.38122619.214.32812.22121.30156.519.212.297.92120.524.51914.9117.415.20136.710.910142923.920.72916.62220.16.513014.8611152727.230.52321.51711.319.26.714.801012153027.12629202118.312.2116100配送中心和客戶點(diǎn)的分布圖如圖5-7所示，用黑色的三角形表示配送中心，用黑色的圓點(diǎn)表示客戶點(diǎn)。圖5SEQ圖\*ARABIC\s11配送中心和客戶點(diǎn)的分布圖5.2實(shí)驗(yàn)結(jié)果為了確定所得到的解科學(xué)有效，對以上數(shù)據(jù)集進(jìn)行多次測試得到最優(yōu)的實(shí)驗(yàn)結(jié)果如圖5-8和如表5-3所示：圖5SEQ圖\*ARABIC\s12最優(yōu)路徑軌跡圖表5SEQ表\*ARABIC\s13車輛派遣方案路徑編號車輛停靠順序10 7 4 6 020 8 3 5 030 2 11 9 040 1 10 12 0車輛派遣方案具體如下：第一輛車的配送路線：配送中心→客戶節(jié)點(diǎn)7→客戶節(jié)點(diǎn)4→客戶節(jié)點(diǎn)6→配送中心第二輛車的配送路線：配送中心→客戶節(jié)點(diǎn)8→客戶節(jié)點(diǎn)3→客戶節(jié)點(diǎn)5→配送中心第三輛車的配送路線：配送中心→客戶節(jié)點(diǎn)2→客戶節(jié)點(diǎn)11→客戶節(jié)點(diǎn)9→配送中心第四輛車的配送路線：配送中心→客戶節(jié)點(diǎn)1→客戶節(jié)點(diǎn)10→客戶節(jié)點(diǎn)12→配送中心第六章總結(jié)6.1完成的工作本文圍繞物流配送車在路徑選擇規(guī)劃上存在的各類問題展開分析。首先對本文的研究背景進(jìn)行介紹，通過查找大量資料文獻(xiàn)，對比國內(nèi)在現(xiàn)階段的發(fā)展現(xiàn)狀，深入剖析物流配送方面的知識，對車輛路徑規(guī)劃上常見的各類算法進(jìn)行介紹分析，通過對各種優(yōu)化算法的分析和比較，并根據(jù)車輛路徑問題的特點(diǎn)，明確提出遺傳算法在本次研究中的重要性和意義，然后對該算法的相關(guān)理論和特征展開論述。通過建立數(shù)學(xué)模型，使用遺傳算法規(guī)劃物流路徑，滿足物流運(yùn)輸成本最小化。本文的主要研究內(nèi)容：(1)建立帶能力約束的車輛路徑問題模型，確定了以車輛行駛的總油耗成本最少作為目標(biāo)函數(shù)。(2)改進(jìn)優(yōu)化遺傳算法中的遺傳算子與適應(yīng)度函數(shù)，以及染色體編碼等，用遺傳算法解決物流配送路徑規(guī)劃問題。(3)完成模型創(chuàng)建和數(shù)據(jù)分析，實(shí)現(xiàn)對物流配送問題的仿真實(shí)驗(yàn)。6.2存在的問題及下一步工作文章主要對車輛路徑規(guī)劃問題進(jìn)行了簡單的研究，在實(shí)踐中可能會(huì)存在約束條件或者需求增加等一些不確定性因素，所以今后的研究可以從以下幾方面進(jìn)行：（1）文章主要是對CVRP模型中的靜態(tài)因素進(jìn)行分析，在實(shí)踐中，配送中心和客戶數(shù)量往往是變化的，在今后的研究中需要考慮這些動(dòng)態(tài)因素。（2）雖然對算法的遺傳算子進(jìn)行了優(yōu)化，但在算法遺傳進(jìn)化過程中，具體的交叉概率、變異概率是固定的，而不是自適應(yīng)，不會(huì)動(dòng)態(tài)調(diào)整。所以在下一步中應(yīng)該建立更加智能的算法改進(jìn)。（3）文章構(gòu)建CVRP模型過程中進(jìn)行了理想化處理，沒有考慮復(fù)雜的約束條件。在實(shí)際的應(yīng)用中還需要更多研究。（4）本文圍繞物流配送問題展開研究，首先設(shè)置物流配送中心，企業(yè)規(guī)模壯大之后，其物流配送中心的數(shù)量也會(huì)增加，如何將這些配送中心有效的聯(lián)合在一起，結(jié)合VRP問題成為當(dāng)前研究的重點(diǎn)。參考文獻(xiàn)崔滬.“大和”的秘密武器—解讀日本大和運(yùn)輸公司配送模式及其特點(diǎn)[J],中國物流與采購,2003,3:26-27劉有鵬.我國城市信息化與物流現(xiàn)代化的關(guān)系及發(fā)展道路[J],上海經(jīng)濟(jì)研究,2006,8:72-76ClarkeG,WrightJ.W..Schedulingofvehiclesfromacentraldepottoanumberofdeliverypoints[J].OperationalResearch,1964,12:568-581.ElhassaniaM,JaouadB,AhmedEA.Solvingthedynamicvehicleroutingproblemusinggeneticalgorithms[C]//LogisticsandOperationsManagement(GOL),2014InternationalConferenceon.IEEE,2014:62-69.Karakati?S,PodgorelecV.Asurveyofgeneticalgorithmsforsolvingmultidepotvehiclerouting