【正文】 便能進(jìn)行描述的；②、因?yàn)?PSO 原理和內(nèi)容是簡(jiǎn)潔易懂的所以將其實(shí)現(xiàn)的過程也是較為輕松的。 第 8 頁 共 40 頁 Rand()函數(shù)能產(chǎn)生 0~1 的隨機(jī)數(shù)。分別使用 )v,...,v,(vV idi2i11 ? 和 )x,...,x,(xX idi2i11 ? 來描述群體中的 i粒子在解空間中的速度與位置。 算法原理 第 7 頁 共 40 頁 在 PSO 算法（粒子群優(yōu)化算法）當(dāng)中，存在的每種需要優(yōu)化的問題都對(duì)應(yīng)著在搜索空間里存在的鳥，而在 DSPO（離散粒子群算法）中這些優(yōu)化問題被稱作粒子。自然界中各種各類的生物體基本上都會(huì)有著一定的群體的行為，因此為人類生命的研究的領(lǐng)域的討論 ——群體生物行為所產(chǎn)生的生物學(xué)的特性提供了立體的直觀的模型，同時(shí)為在計(jì)算機(jī)上建立和模擬群體概念提供了模型。 ④ 、最后在實(shí)際的物流配送任務(wù)中，對(duì)于城市的道路的同行狀況的了解和掌握，因此我們可以考慮在 VRP 的框架下更進(jìn)一步的研究。主要的問題有如下： ① 、 首先 VRP 的問題是一個(gè) NP 的難題。 將不同的擴(kuò)寬元素再與標(biāo)準(zhǔn)的 VRP 相結(jié)合 ,然后可以構(gòu)造出不同的車輛路徑問題 ,比如： 有能力約束的 VRP(CVR)、有時(shí)間窗的約束的 VRP(VRPTW)、帶取送貨的 VRP(VRPPD)、周期性的 VRP(PVRP)、分散配送 VRP(SDVRI)和 帶回程載貨的 VRP(VRPB)等 [316]。 標(biāo)準(zhǔn)的車輛路徑問題其實(shí)是指帶裝載限制的車輛路徑問題 (Capacitatied VRP， CVRP)，其他的各類型的問題都是從此問題延伸展開。然而影響運(yùn)輸配送的成本的最主要的問題便是車輛路徑問題 (VRP)，以現(xiàn)代的物流產(chǎn)業(yè)的發(fā)展的重要性可見的車輛路徑問題的顯著，因此成功地合理地規(guī)劃處理車輛路徑問題會(huì)帶來可喜可贊的經(jīng)濟(jì)的效益和科學(xué) 第 2 頁 共 40 頁 的效益。從而在經(jīng)濟(jì)全球化的趨勢(shì)下，我國(guó)的經(jīng)濟(jì)得到了迅猛的發(fā)展，在高水平經(jīng)濟(jì)的平臺(tái)上科學(xué)技術(shù)同時(shí)也得到了進(jìn)步。粒子依據(jù)自身和群體經(jīng)驗(yàn)進(jìn)行優(yōu)化更新，具有記憶和學(xué)習(xí)能力，克服其他算法的眾多參數(shù)的問題。其中物流企業(yè)也逐漸凸顯期重要性，然而物流配送則是物流企業(yè)日常生產(chǎn)中一個(gè)最為重要的環(huán)節(jié)，物流配送效率的高低直接將會(huì)影響到整個(gè)物流企業(yè)的運(yùn)作效益，同時(shí)對(duì)于電子商務(wù)活動(dòng)物流配送也必不可少。s daily lives. Which of logistics enterprises have gradually highlights the importance is the logistics and distribution logistics panies 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 emerce logistics and distribution also essential. Logistics and distribution 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 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 birds. Applied to the vehicle routing problem discrete particle swarm algorithm also overes the deficiencies and shortings of other algorithms, discrete particle swarm algorithm coded geic algorithm is relatively simple to overe the plexity and the algorithm has the general characteristics 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 overe the problems of many other parameters of the algorithm. Therefore d iscrete particle swarm algorithm suitable for applications in vehicle routing problem. iii Keywords: Particle Swarm Optimization?，F(xiàn)實(shí)生活的交通中，對(duì)于車輛的行駛會(huì)有 著各種的影響因素，比如天氣的變化、突發(fā)的交通事故、交通流量等等各種的非主觀的因素，因此配送的時(shí)間也會(huì)相應(yīng)的被改變，于是研究在諸多的不確定的因素下得出一條最優(yōu)的或者最優(yōu)的路徑是非常具有意義的。粒子依據(jù)自身和群體經(jīng)驗(yàn)進(jìn)行優(yōu)化更新，具有記憶和學(xué)習(xí)能力，克服其他算法的眾多參數(shù)的問題，因此離散粒子群算法適合應(yīng)用在車輛路徑問題。 在限定的條件方面，單一的配送點(diǎn)；多個(gè)配送點(diǎn)；帶有時(shí)間窗口的和沒有時(shí)間窗口的；開放型的和封閉型的；單一車型配送的和多個(gè)車型配送的等。 標(biāo)準(zhǔn)的車輛路徑問題帶 時(shí) 間 窗 口 車輛 路 徑 問 題隨 機(jī) 車 輛 路 徑為 問 題動(dòng) 態(tài) 需 求 車 輛路 徑 問 題依 賴 時(shí) 間 車 輛路 徑 問 題時(shí) 間 窗 口 約 束需 求 劇 透 統(tǒng) 計(jì) 性需 求 統(tǒng) 計(jì) 規(guī) 律旅 行 時(shí) 間 約 束隨 機(jī) 需 求 車 輛路 徑 問 題模 糊 需 求 車 輛路 徑 問 題概 率 統(tǒng) 計(jì)模 糊 語 言圖 VRP 擴(kuò)展問題以及關(guān)系 國(guó)外的研究現(xiàn)狀 從上個(gè)世紀(jì)的 90 年代開始，國(guó)內(nèi)也開始對(duì) VRP 進(jìn)行 研究。 ② 、其次 VRP 的信息存在不確定性。 第二章，介紹本課題研究設(shè)計(jì)所需的基礎(chǔ)算法粒子群算法的理論知識(shí)，介紹離散粒子群算法， 其中包括離散粒子群算法的基本原理以及離散粒子群算法在各個(gè)領(lǐng)域中的廣泛應(yīng)用。由于粒子群算法 （ PSO） 的計(jì)算較簡(jiǎn)單、速度快的收斂性等優(yōu)點(diǎn)使得算法在近十年內(nèi)得到了較快的發(fā)展，并在很多領(lǐng)域得到了廣泛的應(yīng)用，成為了智能計(jì)算領(lǐng)域的寵兒。于是每次的計(jì)算迭代，粒子都會(huì)依據(jù)來個(gè)極值來使自己的值保持最新狀態(tài)。然后通過粒子間的領(lǐng)域得出另一 個(gè) 全 局 極 值 ， 即 為 整 個(gè) 群 體 中 的 一 個(gè) 最 優(yōu) 的 粒 子 用)N b e s t,...,N b e s t,( N b e s tN b e s t d21i ? 來表示。 由于 PSO 算法（粒子群算法） 的思想是來自于鳥群的覓食，在對(duì)算法的使用過程中，眾多的學(xué)者們發(fā)現(xiàn)很多的時(shí)候使用動(dòng)物或者是生物的認(rèn)知來展示算法的原理這樣會(huì)顯得更加的具體和完善，并且更容易讓人理解和應(yīng)用。⑤、在該過程中由于用到的計(jì)算較少因此對(duì)設(shè)備的 CPU 與內(nèi)存的要求也不那么嚴(yán)格。 第 10 頁 共 40 頁 離散粒子群算法 算法引入 PSO 算法開始只是用于處理一些連續(xù)性的問題，然而隨著近些年的發(fā)展，此算法被越來越廣泛地使用在處理和完善離散問題中 ,從而逐漸地頻繁地出現(xiàn)在人們的視線中并開始得到關(guān)注，因此在離散問題中衍生出來的 PSO 算法被稱為離散粒子群算法 (discrete PSO, DPSO)[22]。就連續(xù)空間上研究的 DPSO 形成了二進(jìn)制的 PSO 主要被應(yīng)用在規(guī)劃類型的問題中，除此之外還建立了專屬于改算法的新的計(jì)算的模型還包括了些可能會(huì)被常用到的關(guān)于離散化的研究方法策略。于是根據(jù)速度的變化的公式可以得到粒子的位置的 公式為： ??? ?? )(0 ( ) ) )()((1 e sle sigran difx id 其中)e x p(1 1)( idid vvsig ???. 在上述公式中的 sig(vid)表示的是用于限制轉(zhuǎn)換的函數(shù)，目的是為讓 vid 的值始終能保持在 01 之間的一個(gè)隨機(jī)的數(shù)。 以下我們對(duì)常見的 DPSO 的應(yīng)用簡(jiǎn)單的分析與介紹： 第 13 頁 共 40 頁 ①、典型性的組合型的優(yōu)化問題 —— 該問題屬于運(yùn)籌學(xué)的一個(gè)重要的部分，其中主要包括了 TSP 的問題、 01 背 包的問題、工作的排序問題還有最小生成樹的問題等。但是 PSO 擁有更容易被實(shí)現(xiàn)的優(yōu)點(diǎn)和更厲害的全局性的優(yōu)化能力，學(xué)者們轉(zhuǎn)而開始在 VLSI 的設(shè)計(jì)中使用 PSO，于是辨得出了更多有效的關(guān)于解決布置線路 [2728]、布值全局 [2930]與布置圖形問題的 DPSO。 ⑥ 、圖像 處理 —— 有文獻(xiàn)提出將 PSO 與模糊的理論相結(jié)合得出圖像匹配、識(shí)別的混合算法；有文獻(xiàn)提出使用混合的 PSO 與局部的搜索相結(jié)合可以對(duì)生物學(xué)中的圖像進(jìn)行標(biāo)準(zhǔn)匹配；有文獻(xiàn)利用了混沌的優(yōu)化的搜索得出以混沌搜索為基礎(chǔ)的 PSO，而且使的它與圖像匹配的問題有較好的求解效果；還有文獻(xiàn)表示可以在使用 PSO 的基礎(chǔ)上利用紅外的圖像的分割的技術(shù)得到另一種快速的二維的熵算法。在各個(gè)領(lǐng)域還廣泛的存在很多關(guān)于 PSO 在 Job2Shop 的應(yīng)用。因此我們需要采用十分科學(xué)和有效地方法來優(yōu)化配送的路線問題。上面所敘述的便是該課題所需研究的 VRP，也就是配送中最為關(guān)鍵性的問題之一，同時(shí)還被稱作為車輛計(jì)劃或貨車派送問題等。在物流配送中最常用的一種計(jì)量單位是噸位公 第 19 頁 共 40 頁 里，其計(jì)算方法是：車輛所運(yùn)輸貨物的噸位量乘以行駛路徑的公里數(shù)。服務(wù)一方面體現(xiàn)在人員的素質(zhì)上面，另一方面時(shí)間越少，顯示出企業(yè)的實(shí)力和管理水平越高。 第 21 頁 共 40 頁 第四章 車輛路徑問題的建模與實(shí)現(xiàn) 車輛路徑問題的建模 VRP 因此在一般的情況下可以被描述為：在一定問題的約束的條件下，我們可以設(shè)計(jì)不同或者是相同的出發(fā)點(diǎn)，然后從這些出發(fā)點(diǎn)出發(fā)到多個(gè)不同的客戶目的點(diǎn)的最優(yōu)的送貨的巡回的路徑。 ②、 利用評(píng)價(jià)性的函數(shù) Eval對(duì)所有的粒子進(jìn)行一個(gè)評(píng)估； ③、如若此時(shí)得到的評(píng)估值優(yōu)于其之前所有歷史中的任何一個(gè)評(píng)估值，便將該評(píng)估值記錄為當(dāng)前的歷史最優(yōu)的值，并同時(shí)記錄下它的歷史最優(yōu)的位置。 maxneur=30。 %%選擇優(yōu)化方案 disp(‘’)。 disp(‘’)。 l1=0。 if meth ==1 [w1,b1,w2,b2]=initff(minmax,l1,’tansig’,w2 ,b2,’purelin’,P,T,TP)。4177,2244。 3007,1970。3780,2212。2935,3240。 end [a,b]=min(distance39。 這個(gè)問題就是構(gòu)造連通網(wǎng)的最小代價(jià)生成樹（簡(jiǎn)稱最小生成樹）的問題。 DPSO 算法參數(shù)：粒子數(shù) n=40，鄰居群采用環(huán)形 （ Ring） 拓?fù)浣Y(jié)構(gòu)，鄰居群規(guī)模為 3； w=； c1=c2=；最大迭代次數(shù)為 200. 文獻(xiàn) [31]對(duì)遺傳算法和 DPSO 算法分別進(jìn)行運(yùn)行 50 次，統(tǒng)計(jì)結(jié)果如下表 所示： 表 算法比較 算法 達(dá)到最優(yōu)路徑次數(shù) 未達(dá)到最優(yōu)路徑次 數(shù) 達(dá)到最優(yōu)路徑時(shí)平均迭代數(shù) % 達(dá)到最優(yōu)路徑時(shí)平均時(shí)間 S 遺傳算法 32 18 第 29 頁 共 40 頁 DPSO 算法 50 0 實(shí)驗(yàn)結(jié)果表明， DPSO 方法對(duì)該問題的搜索成功率 100%，遠(yuǎn)遠(yuǎn)高于遺傳算法的64%，而且達(dá)到最優(yōu)的路徑速度比遺傳算法提高 10 倍左右。 本課題采用了 DPSO 和 MATLAB 進(jìn)行編程，簡(jiǎn)單并且