【導(dǎo)讀】烈，同時對人們的日常生活產(chǎn)生愈來愈廣的影響。其中物流企業(yè)也逐漸凸顯期重。配送也必不可少。優(yōu)化車輛路徑問題則需要優(yōu)化。應(yīng)用離散粒子群算法[22]這種群體智能算法能更好更快地解決。有一般的特性，適用于絕大多數(shù)的目標(biāo)優(yōu)化問題。粒子依據(jù)自身和群體經(jīng)驗進(jìn)行。優(yōu)化更新，具有記憶和學(xué)習(xí)能力，克服其他算法的眾多參數(shù)的問題。子群算法適合應(yīng)用在車輛路徑問題。

　　

【正文】 g’,w3,b3,’purelin’,P,T)。 end if l1maxneur break end end end 演示結(jié)果 DPSO 算法與其他算法的比較 DPSO 算法與免疫算法的比較 將免疫算法 [2]應(yīng)用與 VRP 問題中，根據(jù)免疫算法得出其對應(yīng)的主要的 fitness 第 26 頁 共 40 頁 實現(xiàn)代碼如下： function fit=fitness(individual) %計算個體適應(yīng)度值 %individual input 個體 %fit output 適應(yīng)度值 %城市坐標(biāo) city_coordinate=[1304,2312。3639,1315。4177,2244。3712,1399。3488,1535。3326,1556。3238,1229。4196,1044。4312,790。4386,570。 3007,1970。2562,1756。2788,1491。2381,1676。1332,695。3715,1678。3918,2179。4061,2370。3780,2212。3676,2578。 4029,2838。4263,2931。3429,1908。3507,2376。3394,2643。3439,3201。2935,3240。3140,3550。2545,2357。2778,2826。2370,2975]。 %貨物量 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]。 %找出最近配送點 for i=1:31 distance(i,:)=dist(city_coordinate(i,:),city_coordinate(individual,:)39。)。 end [a,b]=min(distance39。)。 %計算費用 for i=1:31 expense(i)=carge(i)*a(i)。 end %距離大于 3000 取一個懲罰值 fit=sum(expense) + +4*length(find(a3000))。 end 由以上的算法代碼得出如下的結(jié)果： 第 27 頁 共 40 頁 將以上的兩個顯示結(jié)果與 DPSO 算法 的結(jié)果進(jìn)行對比可以直觀有效的得出DPSO 的收斂效果很顯然由于免疫算法，充分地體現(xiàn)出了 DPSO 算法的優(yōu)點。 第 28 頁 共 40 頁 DPSO 算法與最小生成樹的比較 假設(shè)要在物流的 n 個客戶點建立發(fā)貨網(wǎng)，則連通 n 個客戶點只需要 n1 條線路?？梢杂眠B通網(wǎng)來表示 n 個客戶點及 n 個客戶點間可能設(shè)置的連通線路，其中網(wǎng)的頂點表示客戶點，邊表示兩客戶點之間的線路，賦予邊的權(quán)值表示相應(yīng)的路程。對于 n 個頂點的連通網(wǎng)可以建立許多不同的生成樹，每一棵生成樹都可以是一個發(fā)貨網(wǎng)。 這個問題就是構(gòu)造連通網(wǎng)的最小代價生成樹（簡稱最小生成樹）的問題。生成 樹算法有兩種分別是 Prim算法和克魯斯卡爾算法。其中 Prim 算法結(jié)果是唯一的，但是它的時間復(fù)雜度是 O（ n2） ， n 代表節(jié)點數(shù)；而克魯斯卡爾算法結(jié)果并不唯一，時間復(fù)雜度是 O（ e） ， e 代表邊數(shù)。所以再實際應(yīng)用中客戶點數(shù)比較多時，生成樹算法的缺點就明顯顯現(xiàn)出來了，運算時間長且算法結(jié)果不定。以此可見離散粒子群算法的優(yōu)點便更突出了。 DPSO 算法與遺傳算法的比較 文獻(xiàn) [31]比較遺傳算法和離散粒子群算法在車輛路徑問題上的應(yīng)用。所采用的平臺 windows7， MATLAB7，其中遺傳算法采用文獻(xiàn) [32]染色體 編碼的方式和相關(guān)參數(shù)；離散粒子群算法參數(shù)采用文獻(xiàn) [33]中的約束條件的參數(shù)。具體參數(shù)設(shè)置如下： 遺傳算法參數(shù)：群體規(guī)模 n=40，交叉概率 Pc=；變異概率 Pm=；輪盤賭法選擇子代，最大迭代次數(shù)為 200。 DPSO 算法參數(shù)：粒子數(shù) n=40，鄰居群采用環(huán)形 （ Ring） 拓?fù)浣Y(jié)構(gòu)，鄰居群規(guī)模為 3； w=； c1=c2=；最大迭代次數(shù)為 200. 文獻(xiàn) [31]對遺傳算法和 DPSO 算法分別進(jìn)行運行 50 次，統(tǒng)計結(jié)果如下表 所示： 表 算法比較 算法 達(dá)到最優(yōu)路徑次數(shù) 未達(dá)到最優(yōu)路徑次 數(shù) 達(dá)到最優(yōu)路徑時平均迭代數(shù) % 達(dá)到最優(yōu)路徑時平均時間 S 遺傳算法 32 18 第 29 頁 共 40 頁 DPSO 算法 50 0 實驗結(jié)果表明， DPSO 方法對該問題的搜索成功率 100%，遠(yuǎn)遠(yuǎn)高于遺傳算法的64%，而且達(dá)到最優(yōu)的路徑速度比遺傳算法提高 10 倍左右。說明在該問題上離散粒子群算法 (DPSO)效率高于遺傳算法。 本章小結(jié) 本章就基于離散粒子群算法的車輛路徑問題做了算法設(shè)計。首先對車輛路徑問題進(jìn)行了建模，然后根據(jù)數(shù)學(xué)模型設(shè)計與編寫了實現(xiàn)的代碼，最后得出實現(xiàn)結(jié)果。并 將 DPSO 算法與免疫算法、生成樹算法和遺傳算法進(jìn)行比較得出了離散粒子群算法的優(yōu)越性和實際的研究意義。 第 30 頁 共 40 頁 第五章 結(jié)論和展望 對整個課題準(zhǔn)備和研究，差不多前后歷經(jīng)了一個多月的設(shè)計和制作，終于將給予 DPSO 的物流配送中的 VRP 的優(yōu)化和設(shè)計開發(fā)研究基本已經(jīng)完成。該課題主要是設(shè)計了一個總的耗費最小的路線的集，然后使用最少的車輛、最少的車輛的路程來實現(xiàn)貨物運輸?shù)呐渌偷娜蝿?wù)。一次來提高物流產(chǎn)業(yè)中物流運輸?shù)男б婧褪袌龈偁幍牧Χ?，具有很大的現(xiàn)實的研究價值和意義。 本課題采用了 DPSO 和 MATLAB 進(jìn)行編程，簡單并且容易 懂。但是由于時間有限，考慮到的的可能性不能很周全，問題處理的不是那么的盡善盡美，只能達(dá)到小型的物流配送的一個過程的優(yōu)化。課題中設(shè)計的功能也并不是那么的全面，規(guī)模更是不夠那么的強大。因此，本課題有有待進(jìn)一步深入的提高改進(jìn)，使得本課題的設(shè)計更加的趨于完善和功能完全。 離散粒子群算法較免疫算法、生成樹算法和遺傳算法都具有比較明顯的優(yōu)勢，在實際應(yīng)用中能提高計算的時間，較好的選擇出較優(yōu)路徑，同時算大理解容易，實現(xiàn)速度快并具有較強的收斂性，被廣泛的應(yīng)用到其他的研究領(lǐng)域。 第 31 頁 共 40 頁 參考文獻(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].計算機工程與應(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。06, 20xx: 30133020. [5] F. Alonso, M. J. Alvarez, J. . A tabu search algorithm for the periodic vehicle routing problem with multiple vehicle trips and accessibility restrictions. Journal of the Operational Research Society, 20xx,59: 963976. [6] P. P. Repoussis, Tarantilis, G Ioannou. A hybrid metaheuristic for a real life vehicle routing problem. Lecture Notes in Computer Science, Numerical Methods and Applications 6th International Conference, NMA 20xx, (4310): 247254. [7] A. Goel, V Gruhn. A General Vehicle Routing Problem. European Journal of Operational Research, 20xx, 191 (3): 650660. [8] , , . A discrete time dynamic fow model and a formulation and solution method for dynamic route choice [J]. Transportation Research Part B, 20xx, 39(7): 593620. [9] , , , . A robust branchcutandprice algorithm for the heterogeneous fleet vehicle routing problem. Lecture Notes in Computer Science, v4525LNCS, Experimental Algorithms6th International Workshop, WEA 20xx, Proceedings, 20xx: 150160. [10] I. Gribkovskaia, G. Laporte, A. Shyshou. The single vehicle routing problem with deliveries and selective pickups. Computers and Operations Research, 20xx,(35): 第 32 頁 共 40 頁 29082924. [11] P. , C. D. Tarantilis, . The open vehicle routing problem with time windows Journal of the Operational Research Society, 20xx,58: 355367. [12] Zhu Qing, Qian. Limin. Li. Yingchun, Zhu Shanjun. An improved particle swarm optimization algorithm for vehicle routing problem with time windows. 20xx IEEE Congress on Evolutionary Computation, CEC 20xx: 13861390. [13] N. A. Wassan. A reactive tabu search for the vehicle routing problem. Journal of the Operational Research Society, 20xx,57: 111116. [14] . J. Renaud, F. Boctor, . A perturbation metaheuristic for the vehicle routing problem with private fleet and mon carriers. Journal of the Operational Research Society, 20xx,59: 776787. [15] , , . Hybrid adaptive predictive control for the multivehicle dynamic pickup and delivery problem based on geic algorithms and fuzzy clustering. COMPUTERS amp。 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] 龍磊 ,陳秋雙 ,華彥寧 ,徐亞 .具有同時集送貨需求的車輛路徑問題的自適 應(yīng)混合遺傳算法 .計算機集成制造系統(tǒng) .20xx,14(3):549557. [18] 王素欣 ,高利 ,崔小光 ,曹宏美 .多需求點車輛調(diào)度模型及其群體智能混合求