【正文】 常數(shù)，這兩個(gè)參數(shù)可以用來(lái)調(diào)整在全局中最優(yōu)的粒子與個(gè)體中最優(yōu)的粒子的步長(zhǎng)。由于這樣粒子在整個(gè)的更新過(guò)程不會(huì)總得出比較好的值，于是很好的解決了某些問(wèn)題。粒子群算法和其他的進(jìn)化算法大體 上是相同的，都是在進(jìn)化和種群的基礎(chǔ)概念之上的，然后使得群體中的個(gè)體之間競(jìng)爭(zhēng)和合作配合相結(jié)合實(shí)現(xiàn)在復(fù)雜環(huán)境下最優(yōu)的搜索。 第 5 頁(yè) 共 40 頁(yè) 第四章，介紹基于離散粒子群算法的車輛路徑問(wèn)題的建模和總體的算法思路，并且對(duì)算法的實(shí)現(xiàn)做了詳細(xì)的設(shè)計(jì)，展示設(shè)計(jì)結(jié)果。分析和優(yōu)化不確定因素的解決策略也是 VRP 的另一 研究方面。其中這些研究主要有取送貨問(wèn)題 [17]，多需求點(diǎn)調(diào)度問(wèn)題 [18]，裝卸一體化問(wèn)題 [19]等。 隨著生活和生產(chǎn)不斷地在進(jìn)步和發(fā)展，為了滿足這其中的各種的需求，車輛 第 3 頁(yè) 共 40 頁(yè) 路徑問(wèn)題 (VRP)需要不斷地進(jìn)行擴(kuò)展和完善。到目前為止已經(jīng)提出了很多的只能算法和啟發(fā)式算法應(yīng)用在輛路徑問(wèn)題中 ,從提出到現(xiàn)在 VRP 的研究經(jīng)過(guò)了近 50 年的發(fā)展，在此過(guò)程中已經(jīng)出現(xiàn)眾多的模型和求解算法。在互聯(lián)網(wǎng)和電子商務(wù)發(fā)展的帶動(dòng)下，物流產(chǎn)業(yè)得到了飛速的發(fā)展， VRP 問(wèn)題模型已經(jīng)建立在現(xiàn)實(shí)生活和生產(chǎn)的各個(gè)方面，比如水運(yùn)的船舶、公共汽車、火車和飛機(jī)等的調(diào)度問(wèn)題以及郵政投遞的問(wèn)題，還有電力的調(diào)度問(wèn)題也同 樣能抽象為車輛路徑問(wèn)題。 Vehicle Routing Problem。優(yōu)化車輛路徑問(wèn)題 (VRP)則需要優(yōu)化配送速度、服務(wù)質(zhì)量、配送成本等決定性因素，因此在這些問(wèn)題中涉及到多種多樣優(yōu)化方案。應(yīng)用離散粒子群算法 (DPSO)[22]這種群體智能算法能更好更快地解決這些多樣化的問(wèn)題，該算法以快速收斂性而獲取最佳是通過(guò) 模擬鳥群覓食得到的。 Logistics Problem。簡(jiǎn)而言之，深入對(duì)車輛路徑問(wèn)題的研究，很具有工程和科學(xué)的應(yīng)用價(jià)值。從提出的改進(jìn)版的模擬的退火算法到動(dòng)態(tài)的蟻群算法再到改進(jìn)的粒子群算法等算法來(lái)解決車輛路徑問(wèn)題。通過(guò)調(diào)整標(biāo)準(zhǔn)的 VRP 的不同的建設(shè)條件，從而來(lái)擴(kuò)寬 VRP 的研究。同時(shí)為了解決 VRP 的各種確定性問(wèn)題用了各類型的不同算法，如遺傳算法 [20]、混合算法 [21]等。 ③ 、還有用于求解動(dòng)態(tài)的 VRP 的仿真環(huán)境仍然需要開發(fā)研究。 第五章，對(duì)本論文的工作做了回顧和總結(jié)，歸納出了本論文的主要工作、取得的成果以及不足，并對(duì)本研究課題做了分析以及對(duì)今后的進(jìn)一步研究工作做了展望。 PSO 算法 （粒子群優(yōu)化算法） 作為新的智能的優(yōu)化技術(shù)，它是來(lái)自于人工的生命與演化計(jì)算的理論知識(shí)：對(duì)群體中的每一個(gè)都進(jìn)行一次初始化，初始化后的粒子都將作為一個(gè)可能存在的解或預(yù)備方案，然后不斷地更新搜索迭代出空間里最優(yōu)的解空間。以上便是 PSO（粒子群算法） 的原理內(nèi)容。這兩個(gè)常數(shù)不能太小也不能太大，如果它們的值太小則會(huì)使得粒子們遠(yuǎn)離我們的目標(biāo)區(qū)域，但是如果太大便會(huì)使得粒子 突然就向目標(biāo)的區(qū)域飛過(guò)去或者甚至可能使得粒子飛出我們的目標(biāo)區(qū)域。 最 后 一 部 分 為)(*()*1 ii XN b estra ndc ?，而這一部分可以表示為粒子能在整個(gè)空間中的領(lǐng)域中以前遇到到過(guò)的那些最優(yōu)的解中再次進(jìn)行搜索的可能方向，這個(gè)有可以類比于人類可以通過(guò)從他人的所學(xué)會(huì)的知識(shí)中而獲得一些經(jīng)驗(yàn)。 然后再通過(guò)上述的迭代方法得出得出最優(yōu)的解再利用這個(gè)最優(yōu)的解來(lái)得出新的關(guān)于速度與位置的值。 在 DPSO 的問(wèn)題中逐漸出現(xiàn)兩條主要的技術(shù)方法：一種方法是依據(jù)以往經(jīng)典的 連續(xù)的 PSO 算法，然后再將這個(gè)連續(xù)運(yùn)動(dòng)的粒子映射到離散空間中并適當(dāng)修改算法使之適應(yīng)能夠解決離散問(wèn)題。例如旅行商問(wèn)題 （ TSP） ，在以離散空間為基礎(chǔ)的前提下 DSPO 通過(guò)利 第 11 頁(yè) 共 40 頁(yè) 用 位運(yùn)算，這樣雖然可能會(huì)增加一些計(jì)算的時(shí)間，但是這樣便不會(huì)產(chǎn)生多余的搜索的問(wèn)題，這樣還能自然地描述離散的問(wèn)題，并能和其他的演化算法緊密地結(jié)合起來(lái)，如此使得其有更好的發(fā)展前景。雖然在算法中出現(xiàn)了近似的取整的情況，并利用這些近 第 12 頁(yè) 共 40 頁(yè) 似的解得可行的解，但是得到的可行解在高維的規(guī)劃問(wèn)題中仍能式算法具有較高的穩(wěn)定性，并使得算法不會(huì)輕易地陷入停止的搜索狀態(tài)。由于近幾年來(lái) DPSO 算法得到了有力地發(fā)展，解決這一問(wèn)題的 方法也隨之越來(lái)越多，比如可以使用改進(jìn)的 BPS 來(lái)恢復(fù)配電網(wǎng)出現(xiàn)的故障；或者可以根據(jù)配輸電網(wǎng)的擴(kuò)展規(guī)劃的問(wèn)題與電網(wǎng)的重構(gòu)問(wèn)題來(lái)設(shè)計(jì)適合的 DPSO；又或者可以用DPSO 處理電力系統(tǒng)中滿足發(fā)電機(jī)的約束的經(jīng)濟(jì)的調(diào)度問(wèn)題；亦或是就給出的電力市場(chǎng)中盈利區(qū)間內(nèi)的約束問(wèn)題改進(jìn)我們的 DPSO；亦或者是關(guān)于熱備、停開機(jī)等約束的機(jī)組的調(diào)度問(wèn)題與組合機(jī)組的等問(wèn)題利用 DPSO 可以很好地將其解決。以上 WSN 這些不足會(huì)使得無(wú)線的 第 14 頁(yè) 共 40 頁(yè) 傳感器網(wǎng)絡(luò)之間的游泳資源相對(duì)的缺乏例如，因此要解決這些問(wèn)題就顯得有些迫不及待了。與其他的遺傳的算法相比較，在搜索的時(shí)候RPSO 擁有更高的成功率，更高的最優(yōu)解的質(zhì)量與更優(yōu)的時(shí)間復(fù)雜度。然后展開對(duì) DPSO 算法詳細(xì)描述，對(duì) DPSO算法原理進(jìn)行深刻的剖析和認(rèn)識(shí)，最后為了能更好的對(duì) DPSO 算的理解，詳細(xì)的例舉了 DPSO 在各個(gè)領(lǐng)域的應(yīng)用 。 由現(xiàn)在的物流配送的流程圖（圖 ）顯然可知，配送環(huán)節(jié)成為了整個(gè)物流配送中最重要的，而存儲(chǔ)環(huán)節(jié)則相對(duì)顯得 不再那么重要且趨于弱化。 車輛路徑問(wèn)題的分析 第 18 頁(yè) 共 40 頁(yè) VRP 的研究要素 關(guān)于 VRP 的分析如下：將服務(wù)的抽象對(duì)象具體成一位客戶，將滿足客戶需求表示為供應(yīng)點(diǎn)；相反的客戶所在地點(diǎn)則表示為需求點(diǎn)；連接供應(yīng)點(diǎn)和需求點(diǎn)并提供配送服務(wù)的車輛表示配送車輛，配送中心則為配送車輛出發(fā)的地點(diǎn)。所以最少化車輛數(shù)根本上就是減少總的成本輸出。顧客就是上帝，企業(yè)所做的一切商務(wù)活動(dòng)，都是圍繞著顧客進(jìn)行的，特別對(duì)于一些保存時(shí)間短的貨物，更是要求及時(shí)送達(dá)，以免給顧客造成一些不必要的損失，同時(shí)也損害了企業(yè)的形象。求解滿足以上要求的運(yùn)輸?shù)淖疃痰能囕v行駛的路徑。 ②、計(jì)算每一個(gè)粒子所代表的方案的距離總和。 ast1=2。 disp(‘1. Particle Swarm Optimization’)。1,1]’。 %arbitrary choice of inital error just used to update of neurons %%判斷選擇結(jié)果，運(yùn)行相關(guān)子函數(shù) if arch==3 [w1,b1]= initff (minmax,1,’tansig’)。 end [w1,b1,w2,b2,w3,b3]=initff(minmax,l2,’tansig’,l1,’logsig’,l,’purclin’)。3326,1556。2381,1676。4263,2931。2778,2826。 end %距離大于 3000 取一個(gè)懲罰值 fit=sum(expense) + +4*length(find(a3000))。所以再實(shí)際應(yīng)用中客戶點(diǎn)數(shù)比較多時(shí)，生成樹算法的缺點(diǎn)就明顯顯現(xiàn)出來(lái)了，運(yùn)算時(shí)間長(zhǎng)且算法結(jié)果不定。首先對(duì)車輛路徑問(wèn)題進(jìn)行了建模，然后根據(jù)數(shù)學(xué)模型設(shè)計(jì)與編寫了實(shí)現(xiàn)的代碼，最后得出實(shí)現(xiàn)結(jié)果。因此，本課題有有待進(jìn)一步深入的提高改進(jìn)，使得本課題的設(shè)計(jì)更加的趨于完善和功能完全。 第 31 頁(yè) 共 40 頁(yè) 參考文獻(xiàn) [1] Kennedy J,EberhartR C . Particle swarm optim ization [G ]//Proc of IEEE Int Conf on York: IEEE, 1995: 19421948. [2] 高鷹 ,謝勝利 .免疫粒子群優(yōu)化算法 [J].計(jì)算機(jī)工程與應(yīng)用 , 20xx(6): 462. [3] . A. Wassan, . A reactive tabu search algorithm for the vehicle routing problem with simultaneous pickups and deliveries. Journal of Combinatorial Optimization, 20xx,15: 368386. [4] , , , . Reducing traveled distance in the vehicle routing problem with time windows using a multistart simulated annealing. International Joint Conference on Neural Networks 20xx, IJCNN 39。 第 30 頁(yè) 共 40 頁(yè) 第五章 結(jié)論和展望 對(duì)整個(gè)課題準(zhǔn)備和研究，差不多前后歷經(jīng)了一個(gè)多月的設(shè)計(jì)和制作，終于將給予 DPSO 的物流配送中的 VRP 的優(yōu)化和設(shè)計(jì)開發(fā)研究基本已經(jīng)完成。 DPSO 算法與遺傳算法的比較 文獻(xiàn) [31]比較遺傳算法和離散粒子群算法在車輛路徑問(wèn)題上的應(yīng)用。 第 28 頁(yè) 共 40 頁(yè) DPSO 算法與最小生成樹的比較 假設(shè)要在物流的 n 個(gè)客戶點(diǎn)建立發(fā)貨網(wǎng)，則連通 n 個(gè)客戶點(diǎn)只需要 n1 條線路。 %貨物量 carge=[20,90,90,60,70,70,40,90,90,70,60,40,40,40,20,80,90,70,100,50,50,50,80,70,80,40,40,60,70,50,30]。3507,2376。3715,1678。4196,1044。 elseif meth=2 第 25 頁(yè) 共 40 頁(yè) [w1,b1,w2,b2,w3,b3,te,tr] = trainbp(w1,b1,’tansig’,w2,b2,’logsig’,w3,b3,’purelin’,P,T)。 elseif meth==2 [w1,b1,te,tr]=trainbp(w1,b1,’tansig’,P,T)。0。 meth=input(‘Pick trainning method’)。 inwtl=9。 實(shí)現(xiàn)代碼 根據(jù)以上的實(shí)現(xiàn)步驟的詳細(xì)分析 ,因此可以如下設(shè)計(jì)程序： %% 首先進(jìn)行初始化 nntwarn off cpdt=25。如若在所有的車輛路徑的中和達(dá)到了最小，便屬于了對(duì)該問(wèn)題的優(yōu)化了。因此解決 VRP 這類問(wèn)題 常用的算法有啟發(fā)式，粒子群算法，還有包括本文介紹的 DSPO(離散粒子群算法 )，能更有效的解決 VRP 中存在的多目標(biāo)性。所以再一定的目標(biāo)下，竟可能地減少車輛的使用，可以為企業(yè)節(jié)約成本。 (如圖 所示 ) 配 送 中 心圖 VRP 示意圖 由以上的分析可得到關(guān)于 VRP 的核心問(wèn)題在于配送中心的選擇，其他的影響的因素有：有關(guān)相關(guān)函數(shù)的選擇；不確定的約束條件；配送的車輛、配送地點(diǎn)、配送 的時(shí)間限制和道路情況等。由此可見(jiàn)，對(duì)物流配送優(yōu)化的過(guò)程最重要就是對(duì)配送時(shí)車輛調(diào)度的優(yōu)化，這其中又包括了運(yùn)貨路線的優(yōu)化，裝配貨物的優(yōu)化以及送貨到用戶的線路的優(yōu)化。物流中一個(gè)重要的直接與消費(fèi)者相連的環(huán)節(jié)便是物流配送。其用意在于利用現(xiàn)在擁有的資源來(lái)達(dá)到滿足任務(wù)需要的約束，并且使得所有的人物能盡量在規(guī)定的時(shí)間之內(nèi)較好的完成。很多的文獻(xiàn)都已分別提出了 PSO 在 WSN 領(lǐng)域中的應(yīng)用。然而其 中的 布置線路、布值全局與布置圖形又是整個(gè)設(shè)計(jì)中最為復(fù)雜最為困難的，該問(wèn)題也以被證實(shí)為NP 的難題。 開 始初 始 化 粒 子 的 位 置和 速 度尋 找 個(gè) 體 最 優(yōu) 和 全局判 斷 是 否 滿 足 的約 束 條 件利 用 公 式 更 新 粒 子的 位 置 和 速 度尋 找 當(dāng) 前 個(gè) 體 最 優(yōu)和 全 局 最 優(yōu)計(jì) 算 粒 子 的 群 體 相似 度判 斷 群 體 相 似 度是 否 大 于 給 定 的伐 值啟 用 排 斥 算 子判 斷 是 否 滿 足 結(jié)束 條 件結(jié) 束是是否否否 圖 31 離散粒子群算法流程圖 算法應(yīng) 用 由于 PSO 的眾多的優(yōu)點(diǎn)，目前它已經(jīng)應(yīng)用在生活、工業(yè)和科學(xué)等的各個(gè)領(lǐng)域中，并且成為了解決實(shí)際的工程與科學(xué)問(wèn)題熱門算法。 算法原理 二進(jìn)制 PSO 利用粒子的速度作為粒子的位置的變化的概率，這個(gè)觀點(diǎn)由Kennedy和 Eberhart 兩位博士首次提出的，專門用于解決 0~1 類型的規(guī)劃的問(wèn)題，在這個(gè)算法中，僅僅就是使用二進(jìn)制的量來(lái)代表每個(gè)粒子并且利用二進(jìn)制空間來(lái)代替超立方的空 間，然后用二進(jìn)制的量之間的轉(zhuǎn)化來(lái)使得粒子在超空間中移動(dòng)。利用離散空間上的位操作的獨(dú)特載體，以取代傳統(tǒng)的矢量的計(jì)算，從信息的流動(dòng)的機(jī)制的角度上來(lái)計(jì)算，依然保存著 PSO 的具體的信息交換伴隨流動(dòng)的機(jī)制。 開 始初 始 化 粒 子群計(jì) 算 粒 子 適應(yīng) 度 值求 解 p B e a t 和g B e s t是 否 滿 足輸 出 求 解g B e s t 值結(jié) 束是否 圖 21 粒子群算流程圖 本節(jié)小結(jié) 本章對(duì) PSO 算法 (粒子群優(yōu)化算法 )進(jìn)行了深入淺出的介紹，首先大概介紹了PSO 算法的來(lái)源、形成和發(fā)展。 通過(guò)上述對(duì) PSO（粒子群算法）原理的分析和概述因而可以總結(jié)出 PS 的幾大顯著的優(yōu)點(diǎn)：①、由于 PSO 算法的來(lái)源貼 近人的慣性思維所以 PSO 是較容易