基于PSO算法的物流配送車輛路徑問題的研究

趙宇橙

摘要：粒子群優(yōu)化優(yōu)化（PSO）算法是受自然界生物群體機制啟發(fā)而得出的一種仿生進化算法。本文首先簡要介紹了群智能、粒子群優(yōu)化、物流配送和車輛路徑問題。然后介紹了PSO算法的基本原理，與遺傳算法比較證明其優(yōu)越性。再在PSO算法的基礎(chǔ)上，融入爬山算法，使算法性能有所提升，并應(yīng)用于車輛路徑問題。最后對全文進行總結(jié)，提出VRP發(fā)展的幾點建議。

關(guān)鍵詞：PSO算法；VRP；爬山算法；遺傳算法；優(yōu)化問題

中圖分類號：TP18；O224 文獻識別碼：A 文章編號：1001-828X（2017）001-0000-03

ABSTRACT：The particle swarm optimizaton（PSO）algorithm is an evolutionary algorithm that simulates the mechanism of biologicaI swarm social behavior.Swarm Intelligence， particle swarm optimizaton， distribution and vehicle routing problem are firstly introduced Afterwards，compared to genetic algorithm，PSO has an obvious advantage，the basic principle of which is analyzed.In addition，the article combines PSO with genetic algorithm to improve algorithm performance and applies mixed algorithm to routing problems.Finally，some suggestions on VRPs development are put forward and summaries are included.

Key Words Particle Swarm Optimization Algorithm； Vehicle Routing Problem； Mounting Climbing Method； Genetic Algorithm； Optimization Problem

一、引言

簡單來說，所謂的群智能（Swarm Intelligence），指的是就是一種對于自然界當(dāng)中，蜜蜂、螞蟻與鳥群等相關(guān)生物群體所進行的行為機制研究。在這當(dāng)中，雖然說單一生物個體所產(chǎn)生的行為通常都比較簡單，但是當(dāng)許多簡單的個體，通過合作來表現(xiàn)出的行為具有明顯的復(fù)雜性，并且能夠完成更加復(fù)雜的任務(wù)。粒子群優(yōu)化（Particle Swarm Optimization）算法是群智能方法中較為典型的一種。其是于1995年，由美國的J.Kennedy和R.Eberhart提出的，其中，J.Kenned是一位社會心理學(xué)家，而R.Eberhart則是一名電氣工程師。其中，PSO算法主要是從人工生命研究開始的，油漆是針對于魚群與鳥群等的模仿，并且在這當(dāng)中充分的加入了進化計算的思想。起初，這一算法主要是被運用在函數(shù)優(yōu)化與神經(jīng)網(wǎng)絡(luò)的訓(xùn)練當(dāng)中，之后，相關(guān)的研究人員又對其做出了進一步的優(yōu)化，并開發(fā)出了不同的版本，來使的該工具成功的在多個領(lǐng)域中得以運用[1]。

就針對于我國而言，物流概念最早是于1979年出現(xiàn)的，一直到20世紀90年代中期，企業(yè)與政府開始重視物流，并賦予其“第三利潤的源泉”的價值和戰(zhàn)略地位。從本質(zhì)上來說，物流配送是以供應(yīng)鏈管理為基礎(chǔ)的，而現(xiàn)階段，由于存儲環(huán)節(jié)的要求越來越弱化，使的配送變成了其中最為關(guān)鍵的一個環(huán)節(jié)。而就針對于配送來說，其最核心的部分，就是配送車輛的集貨與貨物的配送過程。在這個過程當(dāng)中，怎樣選擇車輛的配送道路，來使配送更加合理，對于整個物流運輸來說尤為重要[2]。這就使得車輛路徑問題受到了廣泛的關(guān)注。在VRP提出以后，其已經(jīng)出現(xiàn)了許多相對成熟的算法，并很快得到了廣泛的重視，在運籌與組合優(yōu)化領(lǐng)域當(dāng)中成為一個熱點內(nèi)容[3]。

本項目是研究基于PSO算法的物流配送車輛路徑問題，查閱資料整合而成。本項目旨在在PSO算法的基礎(chǔ)上融入爬山算法，實現(xiàn)物流配送車輛的路徑的優(yōu)化。

二、PSO算法基本原理

1.基本原理

簡單來說，所謂的PSO算法，指的就是一種通過以種群為基礎(chǔ)的優(yōu)化算法。粒子定義成D維空間中的點xi（xi1，xi2，xi3，…，xid，…，xiD），D維空間是要優(yōu)化問題的解空間，與此同時，粒子要具有一定的速度vi（vi1，vi2，…，vid，…，viD），粒子允許在搜索空間飛行。開始時，算法取一組隨機解（x1，x2，x3，…，xN，N為粒子個數(shù)）初始化，隨后粒子根據(jù)自身在解空間中的飛行經(jīng)驗和粒子群體的飛行狀況更新自己的速度以及位置，還用有關(guān)函數(shù)和相應(yīng)方法計算適應(yīng)度的值來評價解的好壞，選出pbest（個體極值）和gbest（全局極值）并記錄位置，再根據(jù)速度更新公式（2-1）和位置更新公式（2-2）更新下一代粒子的速度和位置，依次迭代尋找最優(yōu)值。公式如下：

（2-1）

（2-2）

公式中，c1和c2指的是正的加速系數(shù)，而c1則代表了粒子對于自身記憶的依賴程度，c2則決定了整個粒子群體當(dāng)中，所包含的其他粒子，對于自身所產(chǎn)生的影響程度，其能夠讓每個粒子分別向個體極值和全局極值的位置靠近。rand（）和Rand（）是均勻分布在[0，1]區(qū)間的隨機數(shù)；Pid是個體極值的第d維分量。需要注意的是，在這當(dāng)中，要求粒子的速度必須要地域上限vmax，并且，如果將vmax設(shè)置的比較大，其就能過有效的確粒子的種群全局搜索能力得以充分展現(xiàn)，而如果vmax較小，那么粒子種群的局部搜索能力將會得到進一步的強化，而vmax值過小會使算法陷入局部最優(yōu)。

2.PSO與遺傳算法的比較

通過對比可以看出，PSO和遺傳算法之間存在許多的共同之處[4]：這兩者都能隨機初始化種群，并且，其都是通過運用評價函數(shù)，來評價個體的優(yōu)劣程度，并根據(jù)這個評價，來得到一個適應(yīng)值，并對其進行隨機的搜索，不過，在實際的搜索過程中，PSO在性能比遺傳算法更具優(yōu)勢，因為：

第一，在PSO當(dāng)中，不存在交叉和變異等遺傳操作，其主要是通過運用個體在空間當(dāng)中的隨機速度，來對個體加以改變的，與進化代數(shù)相比來說，其解具有更強的隨機性，因此，其計算的復(fù)雜度也就相對于遺傳算法更低一些。

第二，粒子本身有著顯著的“記憶”的特性，其可以通過“自我”學(xué)習(xí)，或者是通過向“他人”學(xué)習(xí)，來讓下一代解能夠更好的結(jié)成這些信息，并在更短的時間中，找到一個最優(yōu)的解。

第三，相對于遺傳算法來說，PSO有著不同的信息共享機制。因此，在遺傳算法當(dāng)中，染色體能夠?qū)π畔⑦M行互相的共享，因此，就針對于整個種群的移動而言，其通常是比較均勻的，來向著最優(yōu)區(qū)域移動的。

三、基于PSO的VRP問題優(yōu)化

為了提高PSO性能，采用慣性權(quán)重（inertia weight）法。慣性權(quán)重w是與前一次速度有關(guān)的比例因數(shù)。在（2-1）和（2-2）的基礎(chǔ)上進行變化。仍設(shè)所搜索的空間為D維，總粒子數(shù)為n。第i個粒子位置表示為，速度為，其他向量類似。粒子的位置按如下式進 行變化：

具體操作步驟是：

第一步：初始化粒子群，從1～（K+L-1）中取一個實數(shù)作為任一粒子位置向量X的其中一維，從-（ K+L-2）～（K+L-2）取一實數(shù)作為每個速度向量V的每一維。設(shè)定參數(shù)w，c1，c2，R（評價函數(shù)中用到）；

第二步：用每個粒子的總路徑取代其位置向量；

第三步：評價每個粒子的適應(yīng)值，將一開始的評價值作為個體極值，并求全局極值；

第四步：每個粒子按照（3-1）求得速度V，再按照（3-2）計算下一代的位置X，如果計算的V、X超過邊界值，就用總路徑取代X；

第五步：評價每個粒子的適應(yīng)值，并將其與個體極值以及全局極值之間進行對比，如果說其適應(yīng)值更小，那么就對全局或者個體極值進行更新。如果說其適應(yīng)值更小，那么就對全局極值進行更新，一直到其能夠滿足其所規(guī)定的爬山次數(shù)為止。

第六步；如果不滿足終止條件就返回第四步。

2.混合爬山算法的方案二

在PSO的基礎(chǔ)上加入爬山算法的混合PSO算法方案二流程圖見圖3-2。

具體操作步驟是：

第一步：初始化粒子群，從1～（K+L-1）中取一個實數(shù)作為任一粒子位置向量X的其中一維，從-（ K+L-2）～（K+L-2）取一實數(shù)作為每個速度向量V的每一維。設(shè)定參數(shù)w，c1，c2，R（評價函數(shù)中用到）；

第二步：用每個粒子的總路徑取代其位置向量；

第三步：評價每個粒子的適應(yīng)值，將一開始的評價值作為個體極值，并求全局極值；

第四步：每個粒子按照（3-1）求得速度V，再按照（3-2）計算下一代的位置X，如果計算的V、X超過邊界值，就用總路徑取代X；

第五步：對各個粒子的適應(yīng)值進行評價，并對粒子進行相應(yīng)的爬山操作，若其適應(yīng)值更小，那就對個體極值進行更新，一直到其能夠達到規(guī)定的爬山次數(shù)為止。接著再把個體極值和全局極值進行比較，如果適應(yīng)值更小，就更新個體極值。

第六步；如果不滿足終止條件就返回第四步。

3.VRP舉例與結(jié)果分析

（1）VRP舉例

在本次研究當(dāng)中，我們所參考的文獻[5]里面，有一個算例問題為：8個連鎖店和1個配送中心的配送系統(tǒng)。其中，在這個配送中心當(dāng)中，有2輛用來進行配送的車輛，并且，車輛容量均為8噸。在這當(dāng)中，各個連鎖店之間的距離（km）與需求量（噸）見下表。

將標準PSO、PSO混合爬山算法的方案一和混合方案二分別進行20次運算，運算結(jié)果參考文獻[6]表4-2部分數(shù)據(jù)，整合成表3-2。通過表3-2數(shù)據(jù)比較可以得出結(jié)論：①在PSO基礎(chǔ)上融入爬山算法并應(yīng)用于VRP問題，性能均優(yōu)于標準PSO算法 ；②三種方法比較，混合PSO算法方案二收斂速度最快，是一種實行可用的優(yōu)化方法，能較好地求解物流配送路徑問題。

四、結(jié)語

為了優(yōu)化物流配送車輛問題，需要借助改進優(yōu)化的算法。在查閱大量文獻的基礎(chǔ)上，本項目對物流配送、粒子群優(yōu)化算法、遺傳算法和車輛路徑問題做了簡單的介紹和總結(jié)，選擇了基于粒子群優(yōu)化算法的混合粒子群算法進行研究。

物流配送車輛路徑問題是一個典型的組合優(yōu)化難題，根據(jù)問題的提出形式及約束條件的變化，其求解的復(fù)雜度各有不同，本文只針對其中的一部分進行了研究，今后要做的工作還很多，下面幾點建議可以作為未來的研究方向：1.多配送中心以及多車型的配送路線優(yōu)化。2.隨機型配送路線優(yōu)化。3.開發(fā)物流配送車輛調(diào)度系統(tǒng)。4.PSO算法與其他優(yōu)化算法的比較、融合和應(yīng)用。

參考文獻：

[1]倪慶劍，邢漢承，張志政，王蓁蓁，文巨峰.粒子群優(yōu)化算法研究進展[J].模 式識別與人工智能，第20卷第3期：350.

[2]王惠.引入顧客滿意度求解車輛優(yōu)化調(diào)度問題[D].遼寧：大連海事大學(xué).2006：1-13.

[3]李軍，郭耀煌.物流配送車輛優(yōu)化調(diào)度理論與方法[M].北京：中國物資出版社，2001.

[4]沈艷，郭兵，古天祥.粒子群優(yōu)化算法及其與遺傳算法的比較[J].電子科技大學(xué)學(xué)報，2005，5（34）：696-699.

[5]趙燕偉，吳斌，蔣麗，等.車輛路徑問題的雙種群遺傳算法求解方法[J].計算機集成制造系統(tǒng)，2004，10（3）：303-306.

[6]陳利.基于混合粒子群算法的物流配送車輛路徑問題的研究[D].湖南：中南大學(xué)，2007：38.