【正文】 離散粒子群算法較免疫算法、生成樹(shù)算法和遺傳算法都具有比較明顯的優(yōu)勢(shì)，在實(shí)際應(yīng)用中能提高計(jì)算的時(shí)間，較好的選擇出較優(yōu)路徑，同時(shí)算大理解容易，實(shí)現(xiàn)速度快并具有較強(qiáng)的收斂性，被廣泛的應(yīng)用到其他的研究領(lǐng)域。并 將 DPSO 算法與免疫算法、生成樹(shù)算法和遺傳算法進(jìn)行比較得出了離散粒子群算法的優(yōu)越性和實(shí)際的研究意義。以此可見(jiàn)離散粒子群算法的優(yōu)點(diǎn)便更突出了。 end 由以上的算法代碼得出如下的結(jié)果： 第 27 頁(yè) 共 40 頁(yè) 將以上的兩個(gè)顯示結(jié)果與 DPSO 算法 的結(jié)果進(jìn)行對(duì)比可以直觀有效的得出DPSO 的收斂效果很顯然由于免疫算法，充分地體現(xiàn)出了 DPSO 算法的優(yōu)點(diǎn)。2370,2975]。3429,1908。1332,695。3238,1229。 if meth==1 [w1,b1,w2,b2,w3,b3,te,tr] = traindpso(w1,b1,’tansig’,w2,b2,’logsig’,w3,b3,’purelin’,P,T,TP)。 if meth==1 [w1,b1,te,tr] = trainbp(w1,b1,’tansig’,P,T,TP)。 T=[1。 disp(‘2. Standard Backprop’)。 ast2=2。假 設(shè)在某一條路徑上的配送任務(wù)的總的需求超過(guò)的要求而使得方案不可行時(shí)，則函數(shù)便會(huì)將評(píng)估的值置為最大而不可達(dá)。 此模型明確的要求每一個(gè)客戶的目的點(diǎn)都必須要得到配送的服務(wù)，在此過(guò)程中還需要不斷的限制每一個(gè)客戶的目的點(diǎn)的需求量只一車輛來(lái)完成；在確保每一條的路徑上的各個(gè)客戶的目的點(diǎn)的需求不能超過(guò)了這一條路徑上車輛的總的配送的需求量。 VRP 的實(shí)現(xiàn)算法 前面以提到說(shuō)明 VRP 屬于 NP 的難題，所以問(wèn)題的復(fù)雜度會(huì)隨著客戶的增加而呈現(xiàn)指數(shù)式的增長(zhǎng)。主要包括：車輛的折損 費(fèi)、油耗、過(guò)路費(fèi)和人工成本等。 現(xiàn)在是在一定的約束條件下，比如配貨司機(jī)連續(xù)的行車時(shí)間、貨物的需求量、配送的時(shí)間以及載重的限制等 ,然后使用已有的配送車輛，并按照由不同需求確定的順序準(zhǔn)時(shí)地將物品配送至需求點(diǎn)，同時(shí)最達(dá)到滿足一個(gè)配送車輛使用最優(yōu)和車輛路徑最優(yōu)的狀態(tài) ,使得配送的整個(gè)過(guò)程的運(yùn)輸成本能夠達(dá)到最低。有數(shù)據(jù)顯示在各不相同的行業(yè)中，在物流運(yùn)輸?shù)娜^(guò)程中用于運(yùn)輸?shù)某杀举M(fèi)用竟都已超過(guò)了50%，有的甚至到了 70%以上。 第 16 頁(yè) 共 40 頁(yè) 第三章 車輛路徑問(wèn)題分析 物流配送 由于互聯(lián)的發(fā)展和電子商務(wù)的迅猛的發(fā)展，因而觸發(fā)了物流產(chǎn)業(yè)的蓬勃發(fā)展，形成了物流熱效應(yīng)，于是對(duì)于物流管理技術(shù)的需求也日趨提高，傳統(tǒng)的物流管理的方法已經(jīng)不能滿足發(fā)展的要求，因此急需對(duì)這些傳統(tǒng)的方法進(jìn)行改進(jìn)，在這個(gè)改進(jìn)的環(huán)節(jié)中，物流配送中問(wèn)題顯得尤為的重要。 ⑧、 Job2Shop—— 該問(wèn)題一直都是調(diào)度和柔韌性制造的系統(tǒng)中人們時(shí)刻關(guān)注的一個(gè)問(wèn)題之一。這幾年來(lái)，表示已經(jīng)有一些研究學(xué)者對(duì) WSN 的各種問(wèn) 題展開(kāi)了研究并且已經(jīng)抽離出了它的數(shù)學(xué)模型來(lái)進(jìn)行優(yōu)化了，同時(shí)還建立了對(duì)應(yīng)的 PSO。 ③、 VLSI—— VLSI 的設(shè)計(jì)中的布置線路、布值全局與布置圖形是整個(gè) VLSI設(shè)計(jì)的最重要的環(huán)節(jié)同時(shí)也是整個(gè)設(shè)計(jì)的核心關(guān)鍵所在。因此可得離散粒子群算法（ DPSO）的流程圖如圖 31 所示。但是由于研究還是不是特別的多，因此缺乏一個(gè)通用的、統(tǒng)一的和標(biāo)準(zhǔn)的模型。另一種方法是離散優(yōu)化問(wèn)題，用 PSO 為基礎(chǔ)來(lái)更新各種新信息，用經(jīng)典的算法的思想和框架重新定義 DPSO 中的粒子的表達(dá)和求解方式。最后粒子根據(jù)以下的兩個(gè)計(jì)算公式得到最后具體的關(guān)于粒子的速度與位置（如圖 21 所示）。綜上所述， PSO 實(shí)質(zhì)上就是通過(guò)人或者動(dòng)物的學(xué)習(xí)和認(rèn)知的習(xí)慣過(guò)程總結(jié)出尋找到最優(yōu)的解。因此只有選擇兩個(gè)適當(dāng)?shù)闹蒂x予 c1 和 c2，適當(dāng)?shù)?c1 和 c2 能夠加快整個(gè)算法的收斂速度并且也只有這樣才能使得算法得出的最優(yōu)解釋一個(gè)局部的最優(yōu)解。 以上對(duì) PSO（粒子群算法） 的原理分析，下面就 PSO（粒子群算法） 的原理闡述 PSO（粒子群算法） 具體的算法過(guò)程：首先，需要對(duì)群體中的所有的粒子進(jìn)行一個(gè)隨機(jī)的初始化，初始化他們的位置和他們的速度，這樣便能使群體均勻地分布在解空間當(dāng)中。首先 PSO 算法（粒子群優(yōu)化算法）會(huì)對(duì)隨機(jī)的一群粒子進(jìn)行初始化，再利用獲得的最優(yōu)解進(jìn)行迭代在找到解的空間的一過(guò)程中追蹤兩個(gè)所謂的極值 —— 個(gè)別的極端、全局的極值以此來(lái)不斷地更 新自己的位置和速度等。 第 6 頁(yè) 共 40 頁(yè) 第二章 離散粒子群算法 粒子群優(yōu)化算法 算法介紹 粒子群優(yōu)化算法 (particle swarm optimization , PSO)算法是 1995 年提出來(lái)的，由 Kennedy 和 Eberhart 二人提出的 [1]，算法的起源靈感是來(lái)源于對(duì)鳥(niǎo)類等其他各類生物的飲食習(xí)慣觀察、研究并將其簡(jiǎn)化而產(chǎn)生所得。仿真環(huán)境中關(guān)于如何產(chǎn)生一條符合實(shí)際情況的的路徑，以及計(jì)算機(jī)模擬等問(wèn)題都需要我們繼續(xù)不斷的努力。對(duì) VRP 的研究國(guó)內(nèi)已經(jīng)達(dá)到了相當(dāng)?shù)囊?guī)模，雖然如此，但是 VRP 仍然存在很多的問(wèn)題值得我們進(jìn)一步的研究，同時(shí)對(duì)于 VRP 的復(fù)雜性和解決工具還需要更進(jìn)一步的完善。當(dāng)前最普遍的車輛路徑問(wèn)題是帶有時(shí)間窗的靜態(tài)車輛問(wèn)題，世界各國(guó)的研究學(xué)者通過(guò)對(duì)基本的 VRP 的研究得出了基本的模型，使用得出的基本的模型做出各種類型的題庫(kù)，比如 Fisher 題庫(kù)等。由于研究重點(diǎn) 的不同模型存在不同的方式。 課題意義 隨著物流產(chǎn)業(yè)的發(fā)展，產(chǎn)業(yè)中同時(shí)也產(chǎn)生了諸多的問(wèn)題引人注目，其中運(yùn)輸配送的成本占物流配送總成本中的 60%，所以對(duì)于物流行業(yè)最急需解決的問(wèn)題便是運(yùn)輸配送的成本的問(wèn)題。 Path Optimization Problem 第 1 頁(yè) 共 40 頁(yè) 第一章 緒論 課題背景 根據(jù)中國(guó)入世承諾，使得物流行業(yè)和服務(wù)行業(yè)成為中國(guó)最早的開(kāi)放的行業(yè)其中之一。 應(yīng)用于車輛路徑問(wèn)題中的離散粒子群算法同時(shí)也克服了其他算法的不足和缺點(diǎn)，離散粒子群算法編碼比較簡(jiǎn)單克服遺傳算法實(shí)現(xiàn)的復(fù)雜性，并且該算法具有一般的特性，適用于絕大多數(shù)的目標(biāo)優(yōu)化問(wèn)題。 物流配送中亟待解決的問(wèn)題是怎樣得到一條費(fèi)用最小的車輛路徑并將貨物配送給每個(gè)客戶，即車輛路徑問(wèn)題 (VRP)[33]。 Discrete Particle Swarm Optimization。 該問(wèn)題自 1959 年被首先提出，到現(xiàn)在目前已經(jīng)有將近五十多年的的研究歷史，它已經(jīng)是組合優(yōu)化問(wèn)題領(lǐng)域和運(yùn)籌學(xué)研究的熱點(diǎn)和重點(diǎn)。 國(guó)內(nèi)外研究現(xiàn)狀 國(guó)外的研究現(xiàn)狀 1959 年的時(shí)候有學(xué)者 Dantzig 與 Ramser 二人第一次提出了車輛問(wèn)題(Vechicle Routing Problem， VRP)[33],當(dāng)時(shí)提出該問(wèn)題的背景是運(yùn)輸汽油，然后給出了出數(shù)學(xué)模型和求解的具體方法。 按任務(wù) 的性質(zhì)，有確定信息的和不確定的；需求的動(dòng)態(tài)性和靜態(tài)性等等。到目前為止，可 第 4 頁(yè) 共 40 頁(yè) 以在國(guó)內(nèi)的各大期刊網(wǎng)站上都能搜索到有關(guān) VRP 的研究成果近千篇，同時(shí)著也說(shuō)明了 VRP 這個(gè)問(wèn)題的研究?jī)r(jià)值和重要性，同時(shí)還說(shuō)明了國(guó)內(nèi)學(xué)者對(duì)不同類型的 VRP 的研究做出了不可磨滅的貢獻(xiàn)。因此必須對(duì)不確定的信息進(jìn)行預(yù)先的處理，于是每次使用的智能算法都需要根據(jù)具體的問(wèn)題進(jìn)行變化。 第三章，介紹物流配送，由物流配送引入車輛路徑問(wèn)題，深入地剖析車輛路徑問(wèn)題。粒子群優(yōu)化算法作為啟發(fā)式的全局搜索的算法與此同時(shí)也是一個(gè)新的建立在群體基礎(chǔ)上的智能算法，只需要用過(guò)粒子群中的粒子在相互之間進(jìn)行相互地競(jìng)爭(zhēng)和相互的合作，這樣便能達(dá)到優(yōu)化的效果，并較快速地在一未知或特定的空間中尋找到最優(yōu)的一點(diǎn)從而達(dá)到空間全局最優(yōu)。 首先 PSO 算法 （粒子群算法）會(huì)對(duì)隨機(jī)的一群粒子進(jìn)行初始化，再利用獲得的最優(yōu) 解進(jìn)行迭代在找到解的空間的一過(guò)程中追蹤兩個(gè)所謂的極值 —— 個(gè)別的極端、全局的極值以此來(lái)不斷地更新自己的位置和速度等。最后粒子根據(jù)以下的兩個(gè)計(jì)算公式得到最后具體的關(guān)于粒子的速度與位置。由之前提到的更新速度的公式可將其大致地分為三個(gè)部分，首先一部分是關(guān)于 Vi—— 一種粒子會(huì)按照原來(lái)的方向和形同的速度完成搜索過(guò)程的趨勢(shì)，而這可以轉(zhuǎn)換為用人的認(rèn)知習(xí)慣來(lái)解釋這一原理。由以上的優(yōu)點(diǎn)可以顯然地得出目前解決全局的優(yōu)化的問(wèn)題 PSO 是很有效果的。在關(guān)注 DPSO 這個(gè)過(guò)程中，人們對(duì) DPSO這個(gè)算法的了解也愈深刻，尤其是在我們中國(guó)有一些研究者對(duì) DPSO 的研究特別重視。 但是現(xiàn)實(shí)生活中的問(wèn)題不全是都能在連續(xù)型的模型上建立起來(lái)并得到解決，因此 BPSO 在一些離散化的情況中將不再是那么適用。其中 vid 的值的選著直接關(guān)系到 xid 的確切的值的大小，若 vid 的值偏大，粒子的 xid 則為 1 的概率非常的大，反之，粒子的 xid 則為 0 的概率非常大。用重新總結(jié)定義的 PSO 來(lái)操作算式的方法得出了一種 TSPDPSO 的算法，于是根據(jù)這一改進(jìn)和突破，更多的學(xué)者以典型性的組合型的優(yōu)化問(wèn)題為基礎(chǔ)提出了解決 TSP 的問(wèn)題 [2324]、 01 背包的問(wèn)題 [2526]、工作的排序問(wèn)題還有最小生成樹(shù)的問(wèn)題等一系列的的算法。 ④、 WSN—— WSN 作為新的網(wǎng)絡(luò)出現(xiàn)，它不需要事先配置那些基礎(chǔ)的網(wǎng)絡(luò)的設(shè)施便能實(shí)現(xiàn)傳感器之間節(jié)點(diǎn)的自由組網(wǎng)間的通信，還擁有應(yīng)用空間的廣闊性。 ⑦、 VRP—— 雖然 VRP 是 TSP 的一種拓展的問(wèn)題，但是在利用 PSO 求解釋VRP 時(shí)用到了全不一樣的的技術(shù)。 ⑨、其他領(lǐng)域 —— 綜合以上所敘述的關(guān)于 DPSO 的應(yīng)用，此外， DPSO 在神經(jīng)元 第 15 頁(yè) 共 40 頁(yè) 的網(wǎng)絡(luò)訓(xùn)練、一些有關(guān)機(jī)械的設(shè)計(jì)、通訊、化工業(yè)和經(jīng)濟(jì)生活等領(lǐng)域中都有獲得許多的研究性的成果。隨著物流產(chǎn)業(yè)一體化的發(fā)展，經(jīng)常會(huì)將配送中的各種問(wèn)題結(jié)合起來(lái)一起考慮，核心部分為配送車輛的集中貨物、貨物的裝配與送貨路線的優(yōu)化。 VRP 因此在一般的情況下可以被描述為：在一定問(wèn)題的約束的條件下，我們可以設(shè)計(jì)不同或者是相同的出發(fā)點(diǎn)，然后從這些出發(fā)點(diǎn)出發(fā)到多個(gè)不同的客戶目的點(diǎn)的最優(yōu)的送貨的巡回的路徑 。因此需要優(yōu)化總的行駛路徑。設(shè)計(jì)合理的行車路線可以減少車輛的空載率，從而有效的降低運(yùn)營(yíng)的成本。即設(shè)計(jì)出一個(gè)消耗最小的路徑集，這些最優(yōu)的路徑集需要滿足一下幾個(gè)條件： ①、首先必須滿足的是每一條配送路線 上所有的客戶目的點(diǎn)的總的需求量的和是不得超過(guò)每一臺(tái)車輛的運(yùn)載的能力，目前現(xiàn)在擁有 K 輛車，它們的運(yùn)載量應(yīng)該為 ),...,2,1( kkqk ? 。 ④、重復(fù)以上步驟，直到找到滿足條件的最優(yōu)的解或者達(dá)到了要求的最大的迭代的次數(shù)。 popsz=20。 disp(‘’）； disp（ ‘ hiddden layer’）； disp（ ‘ hiddden layer’）； disp（ ‘3. no hiddden layer’）； arch=input(‘Pick a necural architecture’)。 %XOR function test set P=[0, 0 。 l2=1。 elseif meth==2 [w1,b1,w2,b2,te,tr]=trainbp(w1,b1,’tansig’,w2,b2,’purelin’,P,T)。3712,1399。2562,1756。3676,2578。3140,3550。)。生成 樹(shù)算法有兩種分別是 Prim算法和克魯斯卡爾算法。說(shuō)明在該問(wèn)題上離散粒子群算法 (DPSO)效率高于遺傳算法。但是由于時(shí)間有限，考慮到的的可能性不能很周全，問(wèn)題處理的不是那么的盡善盡美，只能達(dá)到小型的物流配送的一個(gè)過(guò)程的優(yōu)化。 OPERATIONS RESEARCH, 20xx,35: 34123438. [16] , , . Competitive analysis of a dispatch policy for a dynamic multiperiod routing problem. OPERATIONS RESEARCH LETTERS. 20xx,35: 71372. [17] 龍磊 ,陳秋雙 ,華彥寧 ,徐亞 .具有同時(shí)集送貨需求的車輛路徑問(wèn)題的自適 應(yīng)混合遺傳算法 .計(jì)算機(jī)集成制造系統(tǒng) .20xx,14(3):549557. [18] 王素欣 ,高利 ,崔小光 ,曹宏美 .多需求點(diǎn)車輛調(diào)度模型及其群體智能混合求解 .自。一次來(lái)提高物流產(chǎn)業(yè)中物流運(yùn)輸?shù)男б婧褪袌?chǎng)競(jìng)爭(zhēng)的力度，具有很大的現(xiàn)實(shí)的研究?jī)r(jià)值和意義。具體參數(shù)設(shè)置如下： 遺傳算法參數(shù)：群體規(guī)模 n=40，交叉概率 Pc=；變異概率 Pm=；輪盤(pán)賭法選擇子代，最大迭代次數(shù)為 200。對(duì)于 n 個(gè)頂點(diǎn)的連通網(wǎng)可以建立許多不同的生成樹(shù)，每一棵生成樹(shù)都可以是一個(gè)發(fā)貨網(wǎng)。)。3439,3201。4061,2370。4386,570。3639,1315。 [w1,b1,w2,b2] = initff(minax,l1,’tansig’,1,’purelin’)。1]’。 disp(‘’)。 endepoch=1500； maxwt=； t=0； %coun