離散粒子群算法在車輛路徑問題中的應(yīng)用畢業(yè)設(shè)計(jì)(論文)

1、計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院畢業(yè)設(shè)計(jì)(論文)論文題目離散粒子群算法在車輛路徑問題中的應(yīng)用 指導(dǎo)教師職 稱講師學(xué)生姓名學(xué) 號專 業(yè)班 級系 主 任院 長起止時(shí)間目錄摘要iabstract.ii第一章 緒論11.1 課題背景11.2 課題意義11.3 國內(nèi)外研究現(xiàn)狀21.3.1國外的研究現(xiàn)狀21.3.2國外的研究現(xiàn)狀31.4 論文的結(jié)構(gòu)4第二章 離散粒子群算法62.1粒子群優(yōu)化算法62.1.1算法介紹62.1.2 算法原理62.1.3 算法流程82.1.4 本節(jié)小結(jié)92.2 離散粒子群算法102.2.1 算法引入102.2.2 算法原理112.2.3 算法應(yīng)用122.2.4 本節(jié)小結(jié)15第三章 車輛路徑問

2、題分析163.1 物流配送163.2 車輛路徑問題的概述173.3 車輛路徑問題的分析173.3.1 vrp的研究要素183.3.2 vrp的優(yōu)化目標(biāo)183.3.3 vrp的實(shí)現(xiàn)算法193.4 本章小結(jié)19第四章 車輛路徑問題的建模與實(shí)現(xiàn)214.1 車輛路徑問題的建模214.2 算法實(shí)現(xiàn)214.3 實(shí)現(xiàn)代碼224.4 演示結(jié)果254.5 dpso算法與其他算法的比較254.5.1 dpso算法與免疫算法的比較254.5.2 dpso算法與最小生成樹的比較284.5.3 dpso算法與遺傳算法的比較284.6 本章小結(jié)29第五章 結(jié)論和展望30參考文獻(xiàn)31謝辭34離散粒子群算法在車輛路徑問題中的

3、應(yīng)用摘要：在這個(gè)高速發(fā)展的經(jīng)濟(jì)社會(huì)，各行各業(yè)對科學(xué)技術(shù)的革新的要求愈發(fā)的強(qiáng)烈，同時(shí)對人們的日常生活產(chǎn)生愈來愈廣的影響。其中物流企業(yè)也逐漸凸顯期重要性，然而物流配送則是物流企業(yè)日常生產(chǎn)中一個(gè)最為重要的環(huán)節(jié)，物流配送效率的高低直接將會(huì)影響到整個(gè)物流企業(yè)的運(yùn)作效益，同時(shí)對于電子商務(wù)活動(dòng)物流配送也必不可少。物流配送中亟待解決的問題是怎樣得到一條費(fèi)用最小的車輛路徑并將貨物配送給每個(gè)客戶，即車輛路徑問題(vrp)33。優(yōu)化車輛路徑問題(vrp)則需要優(yōu)化配送速度、服務(wù)質(zhì)量、配送成本等決定性因素，因此在這些問題中涉及到多種多樣優(yōu)化方案。應(yīng)用離散粒子群算法(dpso)22這種群體智能算法能更好更快地解決這些多

4、樣化的問題，該算法以快速收斂性而獲取最佳是通過模擬鳥群覓食得到的。應(yīng)用于車輛路徑問題中的離散粒子群算法同時(shí)也克服了其他算法的不足和缺點(diǎn)，離散粒子群算法編碼比較簡單克服遺傳算法實(shí)現(xiàn)的復(fù)雜性，并且該算法具有一般的特性，適用于絕大多數(shù)的目標(biāo)優(yōu)化問題。粒子依據(jù)自身和群體經(jīng)驗(yàn)進(jìn)行優(yōu)化更新，具有記憶和學(xué)習(xí)能力，克服其他算法的眾多參數(shù)的問題。因此離散粒子群算法適合應(yīng)用在車輛路徑問題。關(guān)鍵詞：粒子群算法、離散粒子群算法、車輛路徑問題、物流配送、路徑優(yōu)化問題、免疫算法discrete particle swarm optimization for vehicle routing problemabstract:

5、 in this high-speed economic and social development, science and technology sectors of innovation requires increasingly strong, while producing increasingly broad impact on peoples daily lives. which of logistics enterprises have gradually highlights the importance is the logistics and distribution

6、logistics companies daily production one of the most important aspects, however the level will directly affect the efficiency of logistics and distribution to the operational efficiency of the entire logistics enterprises, but for e-commerce logistics and distribution also essential.logistics and di

7、stribution problems to be solved is how to get a minimum cost of vehicle routing and distribution of goods to each customer, namely vehicle routing problem (vrp). optimizing vehicle routing problem (vrp) is required to optimize the speed of delivery, quality of service, distribution costs and other

8、decisive factors, involved in these issues to a wide variety optimization. discrete particle swarm optimization (pso) algorithm which swarm intelligence to better address these diverse problems faster, rapid convergence of the algorithm is to acquire the best is obtained by simulating the foraging b

9、irds.applied to the vehicle routing problem discrete particle swarm algorithm also overcomes the deficiencies and shortcomings of other algorithms, discrete particle swarm algorithm coded genetic algorithm is relatively simple to overcome the complexity and the algorithm has the general characterist

10、ics for the vast majority of objective optimization problem. and groups of particles based on their own experience to optimize the update, with memory and learning ability, to overcome the problems of many other parameters of the algorithm. therefore discrete particle swarm algorithm suitable for ap

11、plications in vehicle routing problem.keywords: particle swarm optimization; discrete particle swarm optimization; vehicle routing problem; logistics problem; path optimization problem第一章 緒論1.1 課題背景根據(jù)中國入世承諾，使得物流行業(yè)和服務(wù)行業(yè)成為中國最早的開放的行業(yè)其中之一。從而在經(jīng)濟(jì)全球化的趨勢下，我國的經(jīng)濟(jì)得到了迅猛的發(fā)展，在高水平經(jīng)濟(jì)的平臺上科學(xué)技術(shù)同時(shí)也得到了進(jìn)步。因此物流產(chǎn)業(yè)也得到了發(fā)展并成為

12、了國家經(jīng)濟(jì)發(fā)展中一個(gè)重要的行業(yè)，同時(shí)在全球飛速發(fā)展延伸，成為象征一個(gè)國家綜合國力的標(biāo)志之一,并在我國開始慢慢成為國家經(jīng)濟(jì)的基礎(chǔ)產(chǎn)業(yè)和主力軍。對于物流產(chǎn)業(yè)而言，物流配送是其中重要的環(huán)節(jié)，然而在這個(gè)環(huán)節(jié)中車輛路徑的選擇則會(huì)起著關(guān)鍵性的作用。現(xiàn)實(shí)生活的交通中，對于車輛的行駛會(huì)有著各種的影響因素，比如天氣的變化、突發(fā)的交通事故、交通流量等等各種的非主觀的因素，因此配送的時(shí)間也會(huì)相應(yīng)的被改變，于是研究在諸多的不確定的因素下得出一條最優(yōu)的或者最優(yōu)的路徑是非常具有意義的。該問題自1959年被首先提出，到現(xiàn)在目前已經(jīng)有將近五十多年的的研究歷史，它已經(jīng)是組合優(yōu)化問題領(lǐng)域和運(yùn)籌學(xué)研究的熱點(diǎn)和重點(diǎn)。在互聯(lián)網(wǎng)和電子商

13、務(wù)發(fā)展的帶動(dòng)下，物流產(chǎn)業(yè)得到了飛速的發(fā)展，vrp問題模型已經(jīng)建立在現(xiàn)實(shí)生活和生產(chǎn)的各個(gè)方面，比如水運(yùn)的船舶、公共汽車、火車和飛機(jī)等的調(diào)度問題以及郵政投遞的問題，還有電力的調(diào)度問題也同樣能抽象為車輛路徑問題。簡而言之，深入對車輛路徑問題的研究，很具有工程和科學(xué)的應(yīng)用價(jià)值。1.2 課題意義隨著物流產(chǎn)業(yè)的發(fā)展，產(chǎn)業(yè)中同時(shí)也產(chǎn)生了諸多的問題引人注目，其中運(yùn)輸配送的成本占物流配送總成本中的60%，所以對于物流行業(yè)最急需解決的問題便是運(yùn)輸配送的成本的問題。然而影響運(yùn)輸配送的成本的最主要的問題便是車輛路徑問題(vrp)，以現(xiàn)代的物流產(chǎn)業(yè)的發(fā)展的重要性可見的車輛路徑問題的顯著，因此成功地合理地規(guī)劃處理車輛路徑

14、問題會(huì)帶來可喜可贊的經(jīng)濟(jì)的效益和科學(xué)的效益。車輛路徑問題(vrp)屬于一個(gè)np難題，離散粒子算法能較好的解決這一類問題，特別地適合于應(yīng)用在處理那些復(fù)雜的和線性的傳統(tǒng)的搜索方法卻又很難以解決的疑難問題上，pso算法（粒子群優(yōu)化算法）1可以提高配送中的物流配送的效率質(zhì)量等關(guān)鍵問題。應(yīng)用于車輛路徑問題中離散粒子群算法同時(shí)也克服了其他算法的不足和缺點(diǎn)，離散粒子群算法編碼比較簡單克服遺傳算法實(shí)現(xiàn)的復(fù)雜性，并且該算法具有一般的特性，適用于絕大多數(shù)的目標(biāo)優(yōu)化問題。粒子依據(jù)自身和群體經(jīng)驗(yàn)進(jìn)行優(yōu)化更新，具有記憶和學(xué)習(xí)能力，克服其他算法的眾多參數(shù)的問題，因此離散粒子群算法適合應(yīng)用在車輛路徑問題。1.3 國內(nèi)外研究

15、現(xiàn)狀1.3.1國外的研究現(xiàn)狀1959年的時(shí)候有學(xué)者dantzig與ramser二人第一次提出了車輛問題(vechicle routing problem，vrp)33,當(dāng)時(shí)提出該問題的背景是運(yùn)輸汽油，然后給出了出數(shù)學(xué)模型和求解的具體方法。到目前為止已經(jīng)提出了很多的只能算法和啟發(fā)式算法應(yīng)用在輛路徑問題中,從提出到現(xiàn)在vrp的研究經(jīng)過了近50年的發(fā)展，在此過程中已經(jīng)出現(xiàn)眾多的模型和求解算法。從提出的改進(jìn)版的模擬的退火算法到動(dòng)態(tài)的蟻群算法再到改進(jìn)的粒子群算法等算法來解決車輛路徑問題。由于研究重點(diǎn)的不同模型存在不同的方式。標(biāo)準(zhǔn)的車輛路徑問題其實(shí)是指帶裝載限制的車輛路徑問題(capacitatied v

16、rp，cvrp)，其他的各類型的問題都是從此問題延伸展開。一個(gè)典型的vrp的基本特征包括：目標(biāo)、派送點(diǎn)、用戶點(diǎn)、道路和車輛。同時(shí)vrp也可以如此分類：在研究目標(biāo)方面，可以最小化總的運(yùn)輸成本；可以將顧客的等待時(shí)間最小化；可以最小化行駛的路程和將服務(wù)的效率最大化等。在限定的條件方面，單一的配送點(diǎn)；多個(gè)配送點(diǎn)；帶有時(shí)間窗口的和沒有時(shí)間窗口的；開放型的和封閉型的；單一車型配送的和多個(gè)車型配送的等。按任務(wù)的性質(zhì)，有確定信息的和不確定的；需求的動(dòng)態(tài)性和靜態(tài)性等等。隨著生活和生產(chǎn)不斷地在進(jìn)步和發(fā)展，為了滿足這其中的各種的需求，車輛路徑問題(vrp)需要不斷地進(jìn)行擴(kuò)展和完善。通過調(diào)整標(biāo)準(zhǔn)的vrp的不同的建設(shè)條

17、件，從而來擴(kuò)寬vrp的研究。當(dāng)前最普遍的車輛路徑問題是帶有時(shí)間窗的靜態(tài)車輛問題，世界各國的研究學(xué)者通過對基本的vrp的研究得出了基本的模型，使用得出的基本的模型做出各種類型的題庫，比如fisher題庫等。將不同的擴(kuò)寬元素再與標(biāo)準(zhǔn)的vrp相結(jié)合,然后可以構(gòu)造出不同的車輛路徑問題,比如：有能力約束的vrp(cvr)、有時(shí)間窗的約束的vrp(vrptw)、帶取送貨的vrp(vrppd)、周期性的vrp(pvrp)、分散配送vrp(sdvri)和帶回程載貨的vrp(vrpb)等3-16。同時(shí)針對不同的主要的約束條件，針對不同實(shí)際公司和企業(yè)中的不通風(fēng)情況又能衍生出一些衍生模型：多倉庫型的車輛路徑問題(m

18、vrp)、多車型的車輛路徑問題（hvrp)、隨機(jī)的車輛路徑問題(svrp）、模糊的車輛路徑問題(fvrp)?？偨Y(jié)得出vrp擴(kuò)展問題及關(guān)系圖如圖1.1所示。圖 1.1 vrp擴(kuò)展問題以及關(guān)系1.3.2國外的研究現(xiàn)狀從上個(gè)世紀(jì)的90年代開始，國內(nèi)也開始對vrp進(jìn)行研究。到目前為止，可以在國內(nèi)的各大期刊網(wǎng)站上都能搜索到有關(guān)vrp的研究成果近千篇，同時(shí)著也說明了vrp這個(gè)問題的研究價(jià)值和重要性，同時(shí)還說明了國內(nèi)學(xué)者對不同類型的vrp的研究做出了不可磨滅的貢獻(xiàn)。其中這些研究主要有取送貨問題17，多需求點(diǎn)調(diào)度問題18，裝卸一體化問題19等。同時(shí)為了解決vrp的各種確定性問題用了各類型的不同算法，如遺傳算法

19、20、混合算法21等。對vrp的研究國內(nèi)已經(jīng)達(dá)到了相當(dāng)?shù)囊?guī)模，雖然如此，但是vrp仍然存在很多的問題值得我們進(jìn)一步的研究，同時(shí)對于vrp的復(fù)雜性和解決工具還需要更進(jìn)一步的完善。主要的問題有如下：、首先vrp的問題是一個(gè)np的難題。因此在求解的過程中如何優(yōu)化計(jì)算時(shí)間和結(jié)果的精確性是解決問題的重點(diǎn)同時(shí)也是難點(diǎn)。于是對vrp的求解研究快速的高效的智能算法是一個(gè)很有價(jià)值的研究方向。、其次vrp的信息存在不確定性。因此必須對不確定的信息進(jìn)行預(yù)先的處理，于是每次使用的智能算法都需要根據(jù)具體的問題進(jìn)行變化。分析和優(yōu)化不確定因素的解決策略也是vrp的另一研究方面。、還有用于求解動(dòng)態(tài)的vrp的仿真環(huán)境仍然需要開

20、發(fā)研究。仿真環(huán)境中關(guān)于如何產(chǎn)生一條符合實(shí)際情況的的路徑，以及計(jì)算機(jī)模擬等問題都需要我們繼續(xù)不斷的努力。、最后在實(shí)際的物流配送任務(wù)中，對于城市的道路的同行狀況的了解和掌握，因此我們可以考慮在vrp的框架下更進(jìn)一步的研究。1.4 論文的結(jié)構(gòu)為了便于閱讀，本論文的章節(jié)是這樣安排的。首先，在本論文的第一章，對本課題的研究背景、目前國內(nèi)外的研究動(dòng)態(tài)進(jìn)行簡要地概述。第二章，介紹本課題研究設(shè)計(jì)所需的基礎(chǔ)算法粒子群算法的理論知識，介紹離散粒子群算法，其中包括離散粒子群算法的基本原理以及離散粒子群算法在各個(gè)領(lǐng)域中的廣泛應(yīng)用。第三章，介紹物流配送，由物流配送引入車輛路徑問題，深入地剖析車輛路徑問題。第四章，介紹基

21、于離散粒子群算法的車輛路徑問題的建模和總體的算法思路，并且對算法的實(shí)現(xiàn)做了詳細(xì)的設(shè)計(jì)，展示設(shè)計(jì)結(jié)果。第五章，對本論文的工作做了回顧和總結(jié)，歸納出了本論文的主要工作、取得的成果以及不足，并對本研究課題做了分析以及對今后的進(jìn)一步研究工作做了展望。第二章 離散粒子群算法2.1粒子群優(yōu)化算法2.1.1算法介紹 粒子群優(yōu)化算法(particle swarm optimization , pso)算法是1995年提出來的，由kennedy和eberhart二人提出的1，算法的起源靈感是來源于對鳥類等其他各類生物的飲食習(xí)慣觀察、研究并將其簡化而產(chǎn)生所得。自然界中各種各類的生物體基本上都會(huì)有著一定的群體的行為

22、，因此為人類生命的研究的領(lǐng)域的討論群體生物行為所產(chǎn)生的生物學(xué)的特性提供了立體的直觀的模型，同時(shí)為在計(jì)算機(jī)上建立和模擬群體概念提供了模型。其中包括近鄰的速度匹配、多維的搜索以及加速距離的概念，從而形成了關(guān)于pso的初始的版本。在此之后引進(jìn)了shi這個(gè)概念到慣性權(quán)重的算法中來平衡開發(fā)和挖掘的能力，才形成目前標(biāo)準(zhǔn)的版本。由于粒子群算法（pso）的計(jì)算較簡單、速度快的收斂性等優(yōu)點(diǎn)使得算法在近十年內(nèi)得到了較快的發(fā)展，并在很多領(lǐng)域得到了廣泛的應(yīng)用，成為了智能計(jì)算領(lǐng)域的寵兒。粒子群優(yōu)化算法作為啟發(fā)式的全局搜索的算法與此同時(shí)也是一個(gè)新的建立在群體基礎(chǔ)上的智能算法，只需要用過粒子群中的粒子在相互之間進(jìn)行相互地競

23、爭和相互的合作，這樣便能達(dá)到優(yōu)化的效果，并較快速地在一未知或特定的空間中尋找到最優(yōu)的一點(diǎn)從而達(dá)到空間全局最優(yōu)。粒子群算法和其他的進(jìn)化算法大體上是相同的，都是在進(jìn)化和種群的基礎(chǔ)概念之上的，然后使得群體中的個(gè)體之間競爭和合作配合相結(jié)合實(shí)現(xiàn)在復(fù)雜環(huán)境下最優(yōu)的搜索。pso算法（粒子群優(yōu)化算法）作為新的智能的優(yōu)化技術(shù)，它是來自于人工的生命與演化計(jì)算的理論知識：對群體中的每一個(gè)都進(jìn)行一次初始化，初始化后的粒子都將作為一個(gè)可能存在的解或預(yù)備方案，然后不斷地更新搜索迭代出空間里最優(yōu)的解空間。首先pso算法（粒子群優(yōu)化算法）會(huì)對隨機(jī)的一群粒子進(jìn)行初始化，再利用獲得的最優(yōu)解進(jìn)行迭代在找到解的空間的一過程中追蹤兩個(gè)

24、所謂的極值個(gè)別的極端、全局的極值以此來不斷地更新自己的位置和速度等。2.1.2 算法原理在pso算法（粒子群優(yōu)化算法）當(dāng)中，存在的每種需要優(yōu)化的問題都對應(yīng)著在搜索空間里存在的鳥，而在dspo（離散粒子群算法）中這些優(yōu)化問題被稱作粒子。這些粒子全部是需要被函數(shù)所確定的適應(yīng)值，并且會(huì)存在一個(gè)各自的速度來計(jì)算他們運(yùn)動(dòng)的距離和方向。由此便會(huì)產(chǎn)生一個(gè)最優(yōu)粒子，然后群體中的粒子們便會(huì)依據(jù)此最優(yōu)粒子開始在解空間里搜索最優(yōu)。于是每次的計(jì)算迭代，粒子都會(huì)依據(jù)來個(gè)極值來使自己的值保持最新狀態(tài)。首先pso算法（粒子群算法）會(huì)對隨機(jī)的一群粒子進(jìn)行初始化，再利用獲得的最優(yōu)解進(jìn)行迭代在找到解的空間的一過程中追蹤兩個(gè)所謂的

25、極值個(gè)別的極端、全局的極值以此來不斷地更新自己的位置和速度等。由于這樣粒子在整個(gè)的更新過程不會(huì)總得出比較好的值，于是很好的解決了某些問題。以上便是pso（粒子群算法）的原理內(nèi)容。以上對pso（粒子群算法）的原理分析，下面就pso（粒子群算法）的原理闡述pso（粒子群算法）具體的算法過程：首先，需要對群體中的所有的粒子進(jìn)行一個(gè)隨機(jī)的初始化，初始化他們的位置和他們的速度，這樣便能使群體均勻地分布在解空間當(dāng)中。分別使用和來描述群體中的i粒子在解空間中的速度與位置。然后再通過上述的迭代方法得出得出最優(yōu)的解再利用這個(gè)最優(yōu)的解來得出新的關(guān)于速度與位置的值。在這個(gè)迭代的過程產(chǎn)生的個(gè)體極值用來表示。然后通過粒

26、子間的領(lǐng)域得出另一個(gè)全局極值，即為整個(gè)群體中的一個(gè)最優(yōu)的粒子用來表示。最后粒子根據(jù)以下的兩個(gè)計(jì)算公式得到最后具體的關(guān)于粒子的速度與位置。 上述的公式中的c1和c2是用來表示加速度的常數(shù)，這兩個(gè)參數(shù)可以用來調(diào)整在全局中最優(yōu)的粒子與個(gè)體中最優(yōu)的粒子的步長。這兩個(gè)常數(shù)不能太小也不能太大，如果它們的值太小則會(huì)使得粒子們遠(yuǎn)離我們的目標(biāo)區(qū)域，但是如果太大便會(huì)使得粒子突然就向目標(biāo)的區(qū)域飛過去或者甚至可能使得粒子飛出我們的目標(biāo)區(qū)域。因此只有選擇兩個(gè)適當(dāng)?shù)闹蒂x予c1和c2，適當(dāng)?shù)腸1和c2能夠加快整個(gè)算法的收斂速度并且也只有這樣才能使得算法得出的最優(yōu)解釋一個(gè)局部的最優(yōu)解。rand()函數(shù)能產(chǎn)生01的隨機(jī)數(shù)。但是

27、粒子的速度不能超過算法在每一維中設(shè)定的最大的速度vmax。算法設(shè)置這樣的一個(gè)vmax的值的目的在于這樣能確保粒子在群體中能達(dá)到的全局的搜索能力，在算法的整個(gè)運(yùn)算的過程中若將vmax的值設(shè)置的越小就會(huì)越增加粒子在算法中的局部的搜索的能力。由于pso算法（粒子群算法）的思想是來自于鳥群的覓食，在對算法的使用過程中，眾多的學(xué)者們發(fā)現(xiàn)很多的時(shí)候使用動(dòng)物或者是生物的認(rèn)知來展示算法的原理這樣會(huì)顯得更加的具體和完善，并且更容易讓人理解和應(yīng)用。由之前提到的更新速度的公式可將其大致地分為三個(gè)部分，首先一部分是關(guān)于vi一種粒子會(huì)按照原來的方向和形同的速度完成搜索過程的趨勢，而這可以轉(zhuǎn)換為用人的認(rèn)知習(xí)慣來解釋這一原

28、理。其次一部分為，這一部分的內(nèi)容可以解釋為粒子在過去尋找到的最優(yōu)解中繼續(xù)搜索的趨勢，同樣這也可以用人在認(rèn)知的過程使用中所積累的經(jīng)驗(yàn)來解釋。最后一部分為，而這一部分可以表示為粒子能在整個(gè)空間中的領(lǐng)域中以前遇到到過的那些最優(yōu)的解中再次進(jìn)行搜索的可能方向，這個(gè)有可以類比于人類可以通過從他人的所學(xué)會(huì)的知識中而獲得一些經(jīng)驗(yàn)。綜上所述，pso實(shí)質(zhì)上就是通過人或者動(dòng)物的學(xué)習(xí)和認(rèn)知的習(xí)慣過程總結(jié)出尋找到最優(yōu)的解。 通過上述對pso（粒子群算法）原理的分析和概述因而可以總結(jié)出ps的幾大顯著的優(yōu)點(diǎn)：、由于pso算法的來源貼近人的慣性思維所以pso是較容易便能進(jìn)行描述的；、因?yàn)閜so原理和內(nèi)容是簡潔易懂的所以將其實(shí)

29、現(xiàn)的過程也是較為輕松的。、在利用pso來計(jì)算時(shí)用到的參數(shù)的數(shù)量也是較少的，并且這些參數(shù)都為常數(shù)，所以基本上不需要費(fèi)太多的心思在調(diào)整參數(shù)上。、在算法應(yīng)用的整個(gè)過程中由于群體的規(guī)模相比較而言稍微小一點(diǎn)，并且較少次數(shù)的利用到評估的函數(shù)，由此一來收斂速度便快了。、在該過程中由于用到的計(jì)算較少因此對設(shè)備的cpu與內(nèi)存的要求也不那么嚴(yán)格。由以上的優(yōu)點(diǎn)可以顯然地得出目前解決全局的優(yōu)化的問題pso是很有效果的。2.1.3 算法流程 算法的流程：首先，需要對群體中的所有的粒子進(jìn)行一個(gè)隨機(jī)的初始化，初始化他們的位置和他們的速度，這樣便能使群體均勻地分布在解空間當(dāng)中。然后再通過上述的迭代方法得出得出最優(yōu)的解再利用這

30、個(gè)最優(yōu)的解來得出新的關(guān)于速度與位置的值。最后粒子根據(jù)以下的兩個(gè)計(jì)算公式得到最后具體的關(guān)于粒子的速度與位置（如圖2-1所示）。圖2-1粒子群算流程圖2.1.4 本節(jié)小結(jié) 本章對pso算法(粒子群優(yōu)化算法)進(jìn)行了深入淺出的介紹，首先大概介紹了pso算法的來源、形成和發(fā)展。然后展開對pso算法詳細(xì)描述，對pso算法原理進(jìn)行深刻的剖析和認(rèn)識，同時(shí)對pso算法應(yīng)用的優(yōu)點(diǎn)進(jìn)行了具體的闡述。最后為了能更好的對pso算的理解，畫出了pso算法直觀的流程圖，使得算法便于理解和后面的實(shí)現(xiàn)。2.2 離散粒子群算法2.2.1 算法引入pso算法開始只是用于處理一些連續(xù)性的問題，然而隨著近些年的發(fā)展，此算法被越來越廣泛

31、地使用在處理和完善離散問題中,從而逐漸地頻繁地出現(xiàn)在人們的視線中并開始得到關(guān)注，因此在離散問題中衍生出來的pso算法被稱為離散粒子群算法(discrete pso, dpso)22。在關(guān)注dpso這個(gè)過程中，人們對dpso這個(gè)算法的了解也愈深刻，尤其是在我們中國有一些研究者對dpso的研究特別重視。該課題先描述了pso算法的原理和內(nèi)容，然后在基于離散化的情況對pso算法進(jìn)行進(jìn)一步的說明和闡述并基于離散映射不同的方法pso算法，將dpso算法的離散空間進(jìn)行劃分，再將衍生出來的dpso算法應(yīng)用到vrp問題中，最后就該課題現(xiàn)狀的客觀分析以及討論發(fā)展趨勢和在該領(lǐng)域內(nèi)的前景展望。 在dpso的問題中逐漸

32、出現(xiàn)兩條主要的技術(shù)方法：一種方法是依據(jù)以往經(jīng)典的連續(xù)的pso算法，然后再將這個(gè)連續(xù)運(yùn)動(dòng)的粒子映射到離散空間中并適當(dāng)修改算法使之適應(yīng)能夠解決離散問題。另一種方法是離散優(yōu)化問題，用pso為基礎(chǔ)來更新各種新信息，用經(jīng)典的算法的思想和框架重新定義dpso中的粒子的表達(dá)和求解方式。利用離散空間上的位操作的獨(dú)特載體，以取代傳統(tǒng)的矢量的計(jì)算，從信息的流動(dòng)的機(jī)制的角度上來計(jì)算，依然保存著pso的具體的信息交換伴隨流動(dòng)的機(jī)制。而這兩種方式的差別在于：第一種是在以連續(xù)空間的基礎(chǔ)上的dpso，而第二種則是在以離散空間為基礎(chǔ)的dpso。根據(jù)現(xiàn)實(shí)生活中遇到的各類型的問題而言，以上的兩種方法可以分別應(yīng)用于在生活中的不同領(lǐng)

33、域。就連續(xù)空間上研究的dpso形成了二進(jìn)制的pso主要被應(yīng)用在規(guī)劃類型的問題中，除此之外還建立了專屬于改算法的新的計(jì)算的模型還包括了些可能會(huì)被常用到的關(guān)于離散化的研究方法策略。 但是現(xiàn)實(shí)生活中的問題不全是都能在連續(xù)型的模型上建立起來并得到解決，因此bpso在一些離散化的情況中將不再是那么適用。雖然現(xiàn)在急于離散化的pso的研究還是不多的，但是仍然存在著一些這樣的算法應(yīng)用與離散化的相關(guān)的問題中。例如旅行商問題（tsp），在以離散空間為基礎(chǔ)的前提下dspo通過利用位運(yùn)算，這樣雖然可能會(huì)增加一些計(jì)算的時(shí)間，但是這樣便不會(huì)產(chǎn)生多余的搜索的問題，這樣還能自然地描述離散的問題，并能和其他的演化算法緊密地結(jié)合

34、起來，如此使得其有更好的發(fā)展前景。但是由于研究還是不是特別的多，因此缺乏一個(gè)通用的、統(tǒng)一的和標(biāo)準(zhǔn)的模型。2.2.2 算法原理 二進(jìn)制pso利用粒子的速度作為粒子的位置的變化的概率，這個(gè)觀點(diǎn)由kennedy和eberhart兩位博士首次提出的，專門用于解決01類型的規(guī)劃的問題，在這個(gè)算法中，僅僅就是使用二進(jìn)制的量來代表每個(gè)粒子并且利用二進(jìn)制空間來代替超立方的空間，然后用二進(jìn)制的量之間的轉(zhuǎn)化來使得粒子在超空間中移動(dòng)。于是得出更新速度的公式為：公式中的vid為粒子的位置的變化的概率；xid代表了當(dāng)前粒子的確切的位置的值；則為常數(shù)因子，即為該粒子的學(xué)習(xí)因子；公式中的pid和pgd則分別代表了在空間中的

35、粒子的局部的最優(yōu)的位置和全局的最優(yōu)的位置。由于此算法為二進(jìn)制的空間中的算法因此以上的參數(shù)中的xid、pid和pgd的值都只能為0或者是1。于是根據(jù)速度的變化的公式可以得到粒子的位置的公式為：其中. 在上述公式中的sig(vid)表示的是用于限制轉(zhuǎn)換的函數(shù)，目的是為讓vid的值始終能保持在0-1之間的一個(gè)隨機(jī)的數(shù)。其中vid的值的選著直接關(guān)系到xid的確切的值的大小，若vid的值偏大，粒子的xid則為1的概率非常的大，反之，粒子的xid則為0的概率非常大。隨著dpso在各個(gè)領(lǐng)域的廣泛的應(yīng)用，算法的不足之處也慢慢的不斷的涌現(xiàn)出來，比如在組合式的優(yōu)化問題當(dāng)中表現(xiàn)的更為的突出，于是研究學(xué)家們便直接對連

36、續(xù)的pso離散化，將粒子的非整的位置近似的等于整數(shù)，其余的部分保持和連續(xù)的pso中一致。雖然在算法中出現(xiàn)了近似的取整的情況，并利用這些近似的解得可行的解，但是得到的可行解在高維的規(guī)劃問題中仍能式算法具有較高的穩(wěn)定性，并使得算法不會(huì)輕易地陷入停止的搜索狀態(tài)。因此可得離散粒子群算法（dpso）的流程圖如圖3-1所示。圖3-1 離散粒子群算法流程圖2.2.3 算法應(yīng)用由于pso的眾多的優(yōu)點(diǎn)，目前它已經(jīng)應(yīng)用在生活、工業(yè)和科學(xué)等的各個(gè)領(lǐng)域中，并且成為了解決實(shí)際的工程與科學(xué)問題熱門算法。同時(shí)dpso也得到了廣泛的研究應(yīng)用，比如在組合性的優(yōu)化難題上，超大規(guī)模的集成電路上，電力系統(tǒng)上，無線的傳感器的網(wǎng)絡(luò)中和用

37、于挖掘數(shù)據(jù)等等。通過不斷的研究和應(yīng)用，算法將會(huì)被更加廣泛的應(yīng)用，給我們的生活、工業(yè)和科學(xué)帶來更多的便利和突破。以下我們對常見的dpso的應(yīng)用簡單的分析與介紹： 、典型性的組合型的優(yōu)化問題該問題屬于運(yùn)籌學(xué)的一個(gè)重要的部分，其中主要包括了tsp的問題、0-1背包的問題、工作的排序問題還有最小生成樹的問題等。用重新總結(jié)定義的pso來操作算式的方法得出了一種tsp-dpso的算法，于是根據(jù)這一改進(jìn)和突破，更多的學(xué)者以典型性的組合型的優(yōu)化問題為基礎(chǔ)提出了解決tsp的問題23-24、0-1背包的問題25-26、工作的排序問題還有最小生成樹的問題等一系列的的算法。 、電力體統(tǒng)在該領(lǐng)域中，需要解決的是在最低成

38、本的情況下進(jìn)行發(fā)電擴(kuò)張的問題，利用dpso能很有效的處理該種有強(qiáng)約束力的組合型的優(yōu)化問題。由于近幾年來dpso算法得到了有力地發(fā)展，解決這一問題的方法也隨之越來越多，比如可以使用改進(jìn)的bps來恢復(fù)配電網(wǎng)出現(xiàn)的故障；或者可以根據(jù)配輸電網(wǎng)的擴(kuò)展規(guī)劃的問題與電網(wǎng)的重構(gòu)問題來設(shè)計(jì)適合的dpso；又或者可以用dpso處理電力系統(tǒng)中滿足發(fā)電機(jī)的約束的經(jīng)濟(jì)的調(diào)度問題；亦或是就給出的電力市場中盈利區(qū)間內(nèi)的約束問題改進(jìn)我們的dpso；亦或者是關(guān)于熱備、停開機(jī)等約束的機(jī)組的調(diào)度問題與組合機(jī)組的等問題利用dpso可以很好地將其解決。 、vlsivlsi的設(shè)計(jì)中的布置線路、布值全局與布置圖形是整個(gè)vlsi設(shè)計(jì)的最重要

39、的環(huán)節(jié)同時(shí)也是整個(gè)設(shè)計(jì)的核心關(guān)鍵所在。然而其中的布置線路、布值全局與布置圖形又是整個(gè)設(shè)計(jì)中最為復(fù)雜最為困難的，該問題也以被證實(shí)為np的難題。如若使用傳統(tǒng)的算法來優(yōu)化這個(gè)問題要么會(huì)因?yàn)楸康挠?jì)算要么就會(huì)因?yàn)榈贸龅慕Y(jié)果是局部性的而非全局的，很顯然傳統(tǒng)的算法已經(jīng)是不能很好解決這些棘手的問題了。于是為了解決這一抽象性的難題研究學(xué)者們想到了在集成的電路中間使用啟發(fā)式的算法來進(jìn)行優(yōu)化。但是pso擁有更容易被實(shí)現(xiàn)的優(yōu)點(diǎn)和更厲害的全局性的優(yōu)化能力，學(xué)者們轉(zhuǎn)而開始在vlsi的設(shè)計(jì)中使用pso，于是辨得出了更多有效的關(guān)于解決布置線路27-28、布值全局29-30與布置圖形問題的dpso。 、wsnwsn作為新的

40、網(wǎng)絡(luò)出現(xiàn)，它不需要事先配置那些基礎(chǔ)的網(wǎng)絡(luò)的設(shè)施便能實(shí)現(xiàn)傳感器之間節(jié)點(diǎn)的自由組網(wǎng)間的通信，還擁有應(yīng)用空間的廣闊性。雖然wsn擁有很多的優(yōu)點(diǎn)，但是它同時(shí)也存在著不足之處，比如它自身帶有的電能是有限的，它的的通訊能力也存在很大的局限性，在節(jié)點(diǎn)之間的計(jì)算能力也略顯不足和它的存儲能力也十分的有限。以上wsn這些不足會(huì)使得無線的傳感器網(wǎng)絡(luò)之間的游泳資源相對的缺乏例如，因此要解決這些問題就顯得有些迫不及待了。這幾年來，表示已經(jīng)有一些研究學(xué)者對wsn的各種問題展開了研究并且已經(jīng)抽離出了它的數(shù)學(xué)模型來進(jìn)行優(yōu)化了，同時(shí)還建立了對應(yīng)的pso。很多的文獻(xiàn)都已分別提出了pso在wsn領(lǐng)域中的應(yīng)用。還有一些學(xué)者將會(huì)深入的

41、進(jìn)一步在wsn中的任務(wù)的調(diào)度中與wsn的容錯(cuò)拓?fù)涞目刂浦袘?yīng)用pso來求解并得到最優(yōu)的結(jié)果。 、數(shù)據(jù)挖掘它的屬性的選擇使用了bpso得到了解決；并已有文獻(xiàn)提出在dpso基礎(chǔ)之上的特征子集的選擇方法；還有文獻(xiàn)為傳統(tǒng)的特征的選擇的不足引入了粗超的簡約的模型，同時(shí)還給了結(jié)合了pso和領(lǐng)域粗超集的模型得出新的一種新的特征的選擇的算法。 、圖像處理有文獻(xiàn)提出將pso與模糊的理論相結(jié)合得出圖像匹配、識別的混合算法；有文獻(xiàn)提出使用混合的pso與局部的搜索相結(jié)合可以對生物學(xué)中的圖像進(jìn)行標(biāo)準(zhǔn)匹配；有文獻(xiàn)利用了混沌的優(yōu)化的搜索得出以混沌搜索為基礎(chǔ)的pso，而且使的它與圖像匹配的問題有較好的求解效果；還有文獻(xiàn)表示可以

42、在使用pso的基礎(chǔ)上利用紅外的圖像的分割的技術(shù)得到另一種快速的二維的熵算法。 、vrp雖然vrp是tsp的一種拓展的問題，但是在利用pso求解釋vrp時(shí)用到了全不一樣的的技術(shù)?，F(xiàn)有文獻(xiàn)提出了可以通過將連續(xù)空間里的粒子進(jìn)行僅是的離散化然后再加粒子的位置映射到離散的排序空間中，這樣便能得到粒子在離散狀態(tài)下的變化情況。與其他的遺傳的算法相比較，在搜索的時(shí)候rpso擁有更高的成功率，更高的最優(yōu)解的質(zhì)量與更優(yōu)的時(shí)間復(fù)雜度。 、job2shop該問題一直都是調(diào)度和柔韌性制造的系統(tǒng)中人們時(shí)刻關(guān)注的一個(gè)問題之一。其用意在于利用現(xiàn)在擁有的資源來達(dá)到滿足任務(wù)需要的約束，并且使得所有的人物能盡量在規(guī)定的時(shí)間之內(nèi)較好

43、的完成。cagnina等研究學(xué)者曾在使用pso處理單機(jī)的調(diào)度問題時(shí)，邊用到了隨機(jī)的鍵來顯示粒子的具體的位置。然后再利用粒子的鍵值對作業(yè)排序，這需要先將粒子的具體位置影射到一種合法的調(diào)度上，只有這樣才能更為便捷地使用連續(xù)pso來計(jì)算出粒子具體的速度和具體的位置。在各個(gè)領(lǐng)域還廣泛的存在很多關(guān)于pso在job2shop的應(yīng)用。、其他領(lǐng)域綜合以上所敘述的關(guān)于dpso的應(yīng)用，此外，dpso在神經(jīng)元的網(wǎng)絡(luò)訓(xùn)練、一些有關(guān)機(jī)械的設(shè)計(jì)、通訊、化工業(yè)和經(jīng)濟(jì)生活等領(lǐng)域中都有獲得許多的研究性的成果。2.2.4 本節(jié)小結(jié) 本章對dpso算法(離散粒子群算法)進(jìn)行了深入淺出的介紹，首先大概介紹了dpso算法的來源、形成和

44、發(fā)展。然后展開對dpso算法詳細(xì)描述，對dpso算法原理進(jìn)行深刻的剖析和認(rèn)識，最后為了能更好的對dpso算的理解，詳細(xì)的例舉了dpso在各個(gè)領(lǐng)域的應(yīng)用。第三章 車輛路徑問題分析3.1 物流配送由于互聯(lián)的發(fā)展和電子商務(wù)的迅猛的發(fā)展，因而觸發(fā)了物流產(chǎn)業(yè)的蓬勃發(fā)展，形成了物流熱效應(yīng)，于是對于物流管理技術(shù)的需求也日趨提高，傳統(tǒng)的物流管理的方法已經(jīng)不能滿足發(fā)展的要求，因此急需對這些傳統(tǒng)的方法進(jìn)行改進(jìn)，在這個(gè)改進(jìn)的環(huán)節(jié)中，物流配送中問題顯得尤為的重要。物流中一個(gè)重要的直接與消費(fèi)者相連的環(huán)節(jié)便是物流配送。所謂的配送則是貨物從物流節(jié)點(diǎn)送達(dá)到收貨人的這一過程。配送路線的合理與否將直接影響到配送的速度、配送的成本

45、和配送最后的效益，當(dāng)配送的過程是一個(gè)多用戶的配送時(shí)，一條合理的配送路線將會(huì)更加的重要和必要。因此我們需要采用十分科學(xué)和有效地方法來優(yōu)化配送的路線問題。隨著物流產(chǎn)業(yè)一體化的發(fā)展，經(jīng)常會(huì)將配送中的各種問題結(jié)合起來一起考慮，核心部分為配送車輛的集中貨物、貨物的裝配與送貨路線的優(yōu)化。于是對配送系統(tǒng)優(yōu)化的其實(shí)就是對車輛路徑的優(yōu)化。由現(xiàn)在的物流配送的流程圖（圖3.1）顯然可知，配送環(huán)節(jié)成為了整個(gè)物流配送中最重要的，而存儲環(huán)節(jié)則相對顯得不再那么重要且趨于弱化。有數(shù)據(jù)顯示在各不相同的行業(yè)中，在物流運(yùn)輸?shù)娜^程中用于運(yùn)輸?shù)某杀举M(fèi)用竟都已超過了50%，有的甚至到了70%以上。由此可見，對物流配送優(yōu)化的過程最重要就

46、是對配送時(shí)車輛調(diào)度的優(yōu)化，這其中又包括了運(yùn)貨路線的優(yōu)化，裝配貨物的優(yōu)化以及送貨到用戶的線路的優(yōu)化。圖3.1 物流配送流程圖3.2 車輛路徑問題的概述在物流的配送的供應(yīng)中，經(jīng)常會(huì)存在一個(gè)這樣的問題：目前有著一批顧客，當(dāng)前我們是知道它們的具體的位置的坐標(biāo)還知道關(guān)于貨物的具體的需求量，表示供應(yīng)商目前擁有者許多兩的車可以供派送使用，但是這些車輛具體的運(yùn)載能力是確定的，要求每一輛車都必須是從起點(diǎn)出發(fā)的，然后需要完成若干的客戶的點(diǎn)再回到起點(diǎn)的位置?，F(xiàn)在供應(yīng)商要求使用最少的車輛和最小的行程完成整個(gè)配送的任務(wù)。上面所敘述的便是該課題所需研究的vrp，也就是配送中最為關(guān)鍵性的問題之一，同時(shí)還被稱作為車輛計(jì)劃或貨

47、車派送問題等。vrp因此在一般的情況下可以被描述為：在一定問題的約束的條件下，我們可以設(shè)計(jì)不同或者是相同的出發(fā)點(diǎn)，然后從這些出發(fā)點(diǎn)出發(fā)到多個(gè)不同的客戶目的點(diǎn)的最優(yōu)的送貨的巡回的路徑。即設(shè)計(jì)出一個(gè)消耗最小的路徑集，這些最優(yōu)的路徑集需要滿足一下幾個(gè)條件：首先是每個(gè)客戶目的點(diǎn)都只能被我們的車輛訪問一次；其次我們配送的稱量斗必須是從出發(fā)點(diǎn)出發(fā)然后訪問完所有的客戶目的點(diǎn)之后才能回到最初的出發(fā)點(diǎn)；最后還需要滿足具體情況下的一些具體的要求。3.3 車輛路徑問題的分析3.3.1 vrp的研究要素關(guān)于vrp的分析如下：將服務(wù)的抽象對象具體成一位客戶，將滿足客戶需求表示為供應(yīng)點(diǎn)；相反的客戶所在地點(diǎn)則表示為需求點(diǎn)；

48、連接供應(yīng)點(diǎn)和需求點(diǎn)并提供配送服務(wù)的車輛表示配送車輛，配送中心則為配送車輛出發(fā)的地點(diǎn)。現(xiàn)在是在一定的約束條件下，比如配貨司機(jī)連續(xù)的行車時(shí)間、貨物的需求量、配送的時(shí)間以及載重的限制等,然后使用已有的配送車輛，并按照由不同需求確定的順序準(zhǔn)時(shí)地將物品配送至需求點(diǎn)，同時(shí)最達(dá)到滿足一個(gè)配送車輛使用最優(yōu)和車輛路徑最優(yōu)的狀態(tài),使得配送的整個(gè)過程的運(yùn)輸成本能夠達(dá)到最低。(如圖3.2所示)圖3.2 vrp示意圖由以上的分析可得到關(guān)于vrp的核心問題在于配送中心的選擇，其他的影響的因素有：有關(guān)相關(guān)函數(shù)的選擇；不確定的約束條件；配送的車輛、配送地點(diǎn)、配送的時(shí)間限制和道路情況等。3.3.2 vrp的優(yōu)化目標(biāo)為了解決現(xiàn)實(shí)

49、生活中對于vrp的不同的要求，歸納總結(jié)有以下幾點(diǎn)：、最短的總行駛路徑最小化總的行駛路徑能在很大程度上避免一些不可預(yù)知的道路問題。同時(shí)能減少車輛在途中的各種成本消耗。在物流配送中最常用的一種計(jì)量單位是噸位公里，其計(jì)算方法是：車輛所運(yùn)輸貨物的噸位量乘以行駛路徑的公里數(shù)。因此需要優(yōu)化總的行駛路徑。、最少的配送車輛最少化配送車輛數(shù)能減小車輛的各種損耗比如油耗車輛的關(guān)卡費(fèi)。所以最少化車輛數(shù)根本上就是減少總的成本輸出。主要包括：車輛的折損費(fèi)、油耗、過路費(fèi)和人工成本等。所以再一定的目標(biāo)下，竟可能地減少車輛的使用，可以為企業(yè)節(jié)約成本。、最少的用時(shí)在服務(wù)性的行業(yè)中，時(shí)間往往會(huì)騎著決定的作用，因此可以說時(shí)間便是金

50、錢。同時(shí)時(shí)間減少了，可以減少車輛的空載率，從而可以有效地降低運(yùn)輸?shù)某杀?。服?wù)一方面體現(xiàn)在人員的素質(zhì)上面，另一方面時(shí)間越少，顯示出企業(yè)的實(shí)力和管理水平越高。設(shè)計(jì)合理的行車路線可以減少車輛的空載率，從而有效的降低運(yùn)營的成本。、最大的客戶滿意度只有最高效的將貨物送至各戶手中才能得到更多的客戶的信賴的和肯定，從而提高企業(yè)的形象，以此來獲得更高的客戶，給企業(yè)帶來更多的利潤的。顧客就是上帝，企業(yè)所做的一切商務(wù)活動(dòng)，都是圍繞著顧客進(jìn)行的，特別對于一些保存時(shí)間短的貨物，更是要求及時(shí)送達(dá)，以免給顧客造成一些不必要的損失，同時(shí)也損害了企業(yè)的形象。3.3.3 vrp的實(shí)現(xiàn)算法 前面以提到說明vrp屬于np的難題，所

51、以問題的復(fù)雜度會(huì)隨著客戶的增加而呈現(xiàn)指數(shù)式的增長。因此解決vrp這類問題常用的算法有啟發(fā)式，粒子群算法，還有包括本文介紹的dspo(離散粒子群算法)，能更有效的解決vrp中存在的多目標(biāo)性。3.4 本章小結(jié) 本章對vrp(車輛路徑問題)進(jìn)行了深入淺出的介紹，首先大概介紹了物流配送形成和發(fā)展。然后展開對vrp詳細(xì)描述，對vrp原理進(jìn)行深刻的剖析和認(rèn)識，同時(shí)對vrp的模型進(jìn)行了具體的描述。第四章 車輛路徑問題的建模與實(shí)現(xiàn)4.1 車輛路徑問題的建模vrp因此在一般的情況下可以被描述為：在一定問題的約束的條件下，我們可以設(shè)計(jì)不同或者是相同的出發(fā)點(diǎn)，然后從這些出發(fā)點(diǎn)出發(fā)到多個(gè)不同的客戶目的點(diǎn)的最優(yōu)的送貨的

52、巡回的路徑。即設(shè)計(jì)出一個(gè)消耗最小的路徑集，這些最優(yōu)的路徑集需要滿足一下幾個(gè)條件：、首先必須滿足的是每一條配送路線上所有的客戶目的點(diǎn)的總的需求量的和是不得超過每一臺車輛的運(yùn)載的能力，目前現(xiàn)在擁有k輛車，它們的運(yùn)載量應(yīng)該為。、其次每一個(gè)客戶的目的點(diǎn)有且只能被訪問一次，假設(shè)現(xiàn)在有l(wèi)個(gè)客戶的目的點(diǎn)的運(yùn)輸任務(wù)需呀完成，用1-l表示，其中第i個(gè)的發(fā)貨點(diǎn)運(yùn)載量為，并且；、最后每個(gè)運(yùn)輸車輛總的行駛的路程不能超過配送一次的最大的行駛的路程。求解滿足以上要求的運(yùn)輸?shù)淖疃痰能囕v行駛的路徑。此模型明確的要求每一個(gè)客戶的目的點(diǎn)都必須要得到配送的服務(wù)，在此過程中還需要不斷的限制每一個(gè)客戶的目的點(diǎn)的需求量只一車輛來完成；在

53、確保每一條的路徑上的各個(gè)客戶的目的點(diǎn)的需求不能超過了這一條路徑上車輛的總的配送的需求量。如若在所有的車輛路徑的中和達(dá)到了最小，便屬于了對該問題的優(yōu)化了。4.2 算法實(shí)現(xiàn)要是的問題解決的關(guān)鍵還是必須找到復(fù)合算法的表達(dá)式，然后再是的粒子與其相對應(yīng)。有眾多的文獻(xiàn)所給的思路，在根據(jù)實(shí)際的問題產(chǎn)生的具體的實(shí)現(xiàn)步驟如下：第一步：我們首先需要對粒子群進(jìn)行初始化、開始我們需要得到兩個(gè)相互重疊的粒子群，所以我們需要將整個(gè)粒子群進(jìn)行劃分；、對每個(gè)粒子的具體的位置和具體的速度進(jìn)行離散化的映射，是的它們的值都能分別屬于0k和0l之間的的整數(shù)；、利用評價(jià)性的函數(shù)eval對所有的粒子進(jìn)行一個(gè)評估；、將中得到的初始化的值作

54、為一個(gè)個(gè)體的歷史性的最優(yōu)的解pi，然后在找到子群中的最優(yōu)的解pi和總的群體中的最優(yōu)的解pg第二步：、根據(jù)dpso中速度、位置的更新公式進(jìn)行迭代，如若超出范圍的值按邊界的值進(jìn)行取舍。、利用評價(jià)性的函數(shù)eval對所有的粒子進(jìn)行一個(gè)評估；、如若此時(shí)得到的評估值優(yōu)于其之前所有歷史中的任何一個(gè)評估值，便將該評估值記錄為當(dāng)前的歷史最優(yōu)的值，并同時(shí)記錄下它的歷史最優(yōu)的位置。、重復(fù)以上步驟，直到找到滿足條件的最優(yōu)的解或者達(dá)到了要求的最大的迭代的次數(shù)。其中評估函數(shù)eval的主要任務(wù)為： 、函數(shù)將所得到的xr按照小到大的順序再次進(jìn)行排列得到一個(gè)新的規(guī)范的整數(shù)序列，利于以后計(jì)算行駛的距離和后面的迭代的計(jì)算。、計(jì)算每

55、一個(gè)粒子所代表的方案的距離總和。假設(shè)在某一條路徑上的配送任務(wù)的總的需求超過的要求而使得方案不可行時(shí)，則函數(shù)便會(huì)將評估的值置為最大而不可達(dá)。4.3 實(shí)現(xiàn)代碼根據(jù)以上的實(shí)現(xiàn)步驟的詳細(xì)分析,因此可以如下設(shè)計(jì)程序： % 首先進(jìn)行初始化nntwarn offcpdt=25;maxcp=1000;reqerr=0.02;maxneur=30;popsz=20;maxvel= 4;acnst1=2;acnst2=2;inwtl=9;inwt2=0.2;endepoch=1500；maxwt=0.05；cnt=0；%counter for neuron architccture%training paramc

56、ters, change these to experiment with dpso performance%type help traindpso to find out what they dotp=cpdt,maxep,reqerr,popsz,maxvel,acnst2,inwt2,endepoch,maxwt,2,1e-9,200; %選擇優(yōu)化方案disp(-);disp(）；disp（1.1 hiddden layer）；disp（2.2 hiddden layer）；disp（3. no hiddden layer）；arch=input(pick a necural net architecture