適于配送車輛導航路徑規(guī)劃的遍歷模型的改進型粒子群優(yōu)化算法*

章權(quán) 溫惠英 孫博

(1.長安大學公路學院，陜西 西安710064;2.廣東省公路管理局，廣東廣州510075;3.華南理工大學土木與交通學院，廣東廣州510640)

車輛路徑規(guī)劃，是指在旅行前或旅行中為駕駛員提供參考行駛路線的一個過程，是車輛導航系統(tǒng)的基本功能之一，同時也是配送車輛導航系統(tǒng)中的技術(shù)難點，是一個NP-hard問題，直接影響著物流配送車輛導航的實時性能［1］.車輛路徑規(guī)劃問題本質(zhì)上是一個旅行商問題(TSP)，又是一個非確定性多項式問題即NP問題.由于車輛路徑規(guī)劃需考慮多旅行商多目標、交發(fā)貨時間、車輛容量限制、行駛里程限制、時間限制等限制因素［2］，該問題比TSP更復雜.

配送車輛導航路徑規(guī)劃(VND)不同于普通物流配送車輛路徑規(guī)劃，它是指單個車輛從配送中心到各個貨物需求點的路徑規(guī)劃，是對單個車輛行駛過程中的動態(tài)路徑優(yōu)化［3］，而普通物流配送車輛路徑規(guī)劃優(yōu)化的結(jié)果在車輛行駛過程中一般是不變的［4-6］.文中建立了VND問題的遍歷模型，并用改進粒子群算法求解，最后通過仿真實驗證明模型的合理性和算法的有效性.

1 配送車輛導航路徑規(guī)劃遍歷模型的建立

如果把城市路網(wǎng)中的交叉路口表示為節(jié)點，則任意兩個交叉路口之間的道路就是連接兩節(jié)點的邊(也稱為弧)，邊的權(quán)值由路網(wǎng)提供.這樣，城市路網(wǎng)可以表示成一個帶權(quán)有向圖G=(V，{E})，其中V是節(jié)點(也可簡稱為點)的集合，E是邊的集合，＜i，j＞是E中從節(jié)點i至j的邊.物流配送車輛導航的其中一個重要特點是遍歷性，即每輛車都有自己需要訪問的多個貨物需求點.在物流配送車輛導航中，遍歷模型是指單個車輛遍歷所有貨物需求點的路徑規(guī)劃模型.通常每輛車所需要訪問的貨物需求點有多個，即要考慮多個貨物需求點的遍歷問題，該問題是一個NP問題.

設對權(quán)值產(chǎn)生影響的因素共有l(wèi)種，遍歷模型可以描述為:

式中:tij∈{0，1}，如果 tij=1 表示邊 ＜ i，j＞ 被選中，否則為未被選中;αk為比例系數(shù)，表示第k種因素的權(quán)重;fk(tij)表示第k種因素對邊＜i，j＞產(chǎn)生影響后的值，若邊未被選中，則無影響，fk(tij)=0.

式(1)為目標函數(shù)，約束條件式(2)表示節(jié)點ui(i=1，2，…，n－1)有且只有一個出口，目標節(jié)點 un無出口;式(3)表示節(jié)點uj(j=2，3，…，n)有且只有一個入口，起始節(jié)點無入口.

物流配送車輛導航的遍歷問題和一般的遍歷問題不同處如下.

(1)一般的遍歷問題，如TSP，起始節(jié)點和目標節(jié)點可以是任意的.而對于文中的VND問題，起始節(jié)點和目標節(jié)點是確定的.

例如，設節(jié)點有 3個(A，B，C)，則 ABCA 和BCAB都是TSP問題的可行解.但對于VND問題，如果節(jié)點A對應的是起始節(jié)點，則BCAB不是可行解.

(2)在TSP問題中，每個點既有出口也有入口.在VND問題中，既包含起始節(jié)點有入口的情況(車輛剛出發(fā)時，此時起始節(jié)點為物流配送中心，車輛完成任務后必須回到該點)，也包含起始節(jié)點沒有入口的情況(車輛開始行駛時，起始節(jié)點是車輛的當前位置，不再是物流配送中心).

(3)對于TSP問題，起始節(jié)點和目標節(jié)點一般是相同的，而對于物流配送車輛導航的遍歷問題，起始節(jié)點和目標節(jié)點可以不同.

2 基本粒子群優(yōu)化算法及改進思路

2.1 粒子群優(yōu)化算法概述

粒子群優(yōu)化算法PSO是一種群智能優(yōu)化算法，由Kennedy等［7］于1995年首次提出.PSO源于對鳥群捕食行為的研究，鳥群覓食時，總是有一只鳥對食源的大致方向具有較好的洞察力，同時，在找尋食源的途中，它們通過一套自己獨有的方式隨時相互傳遞著信息，特別是較好的信息.在“好消息”的指引下，導致鳥群“一窩蜂”的奔向食源，達到在食源的群集.在PSO算法中，每一只鳥稱為一個“粒子”，解群相當于一個鳥群，從一地到另一地的遷徙相當于解群的進化，“好消息”相當于解群每代進化中的最優(yōu)解，食源相當于全局最優(yōu)解［7］.PSO算法優(yōu)點在于算法流程簡單易實現(xiàn)，算法參數(shù)簡潔且無需復雜的調(diào)整.

基本 PSO 算法由 Shi和 Eberhart提出［8］，但是該算法在計算的早期收斂較快，精度較低.文中將把遺傳算法中的交叉和變異的思想引入到PSO算法中，建立適于VND的PSO算法.

2.2 適于VND模型的基本PSO算法改進思路

VND本身的特點決定了基本PSO算法不能直接用于求解VND問題［3］，需要對基本PSO算法進行編碼、初始種群的產(chǎn)生、種群的進化策略等方面的改進.參考文獻［3，9-10］，文中采用可行解空間的搜索方式對PSO算法進行改進.對于物流配送車輛導航的兩種不同的路徑規(guī)劃模型，采用相同的編碼方案，即將一個路徑規(guī)劃問題的可行解定義為一串字符串，假設P表示起點為S到目標節(jié)點為E的可變字符串，P=A1A2…Ak，其中 Ai(i=1，2，…，k)為路網(wǎng)中的節(jié)點，且Ai和 Ai+1直接連通(i=1，2，…，k－1)，A1=S，Ak=E.可行解P的值定義為其中dAiAi+1為節(jié)點Ai和Ai+1之間的連結(jié)權(quán)值.

3 遍歷模型的粒子群優(yōu)化算法

下面結(jié)合VND本身的特點，通過改進初始種群的產(chǎn)生方法和種群的進化策略，提出適于VND遍歷模型的改進型IPSO(Improved Particle Swarm Optimization)算法.

3.1 初始種群產(chǎn)生方法的改進

文中采用將節(jié)點進行隨機排列的方式產(chǎn)生初始種群.由于物流配送車輛導航中，起始節(jié)點和目標節(jié)點往往是固定的，所以起始節(jié)點和目標節(jié)點不參與隨機排列.比如節(jié)點只有5個，起始節(jié)點和目標節(jié)點的編號分別為1和5，那么隨機排列產(chǎn)生的個體只可能有6種情況，分別是(1，2，3，4，5)，(1，2，4，3，5)，(1，3，2，4，5)，(1，4，2，3，5)，(1，3，4，2，5)，(1，4，3，2，5).

3.2 種群進化策略的改進

這里將交叉運算引入PSO算法中，以改進VND遍歷模型求解的進化策略，使得PSO算法中的粒子能進行優(yōu)化組合.在VND遍歷模型求解中，兩個解之間的差實際上是解所在路網(wǎng)中節(jié)點的位置不同.因此，可以用節(jié)點位置的差別來表示PSO算法中的距離.設和是兩個不同的可行解，則最多只需要進行l(wèi)次交換就可以使其中一個解變成另一個解，可以將交換的次數(shù)看作是兩個粒子間的距離.

設需更新的粒子是u1，其更新目標是u2(u2可以是gbest1或pbest2，這里的gbest1、pbest2指的是種群最優(yōu)解)，它們之間的距離是l，具體做法是:

(1)產(chǎn)生一個［0，l］之間的隨機整數(shù)l0;

(2)隨機掃描u1和u2共l0次;

(3)如果掃描到某一位置時，兩個粒子中的節(jié)點不同，則以u2為準對u1進行更新.

這樣，經(jīng)改進后的 IPSO算法就可以應用于VND遍歷模型求解.

3.3 適于VND遍歷模型的改進型PSO算法

通過大量實驗發(fā)現(xiàn)，PSO算法在開始時收斂很快，但在計算的后期收斂速度很慢，且粒子慢慢趨于同一個方向，陷入了局部最優(yōu)解.受小生境思想的啟發(fā)，文章提出適于VND遍歷模型的改進型IPSO算法，該算法通過縮短每個粒子的壽命來達到跳出局部最優(yōu)解的目的.具體做法是:當結(jié)果在幾次飛行后(實驗中取20次)沒有改善時，保留該群粒子所找到的最好結(jié)果，然后讓其它的粒子消失，它們所保存的歷史記錄也隨之消失;再重新產(chǎn)生一群新的粒子來繼續(xù)進行PSO算法流程.

采用14個節(jié)點的標準TSP問題對算法進行測試.各節(jié)點的坐標分別為{(16.47，96.10)，(16.47， 94.44)， (20.09， 92.54)， (22.39，93.37)， (25.23， 97.24)， (22.00， 96.05)，(20.47， 97.02)， (17.20， 96.29)， (16.30，97.38)， (14.05， 98.12)， (16.53， 97.38)，(21.52， 95.59)， (19.41， 97.13)， (20.09，94.55)}.為簡單起見，節(jié)點之間的權(quán)值取節(jié)點之間的歐氏距離.實驗中，種群大小為100，從粒子第1次飛行到粒子倒數(shù)第2次飛行的時間限定為5 s，此時飛行次數(shù)不固定.共測試100次，每次實驗如果找到最優(yōu)解，則立即停止.

算法進化情況見圖1、圖2，改進型PSO算法與基本PSO算法的性能比較見表1，由實驗結(jié)果可知:

(1)在獲得全局最優(yōu)值的前提下改進型IPSO算法比基本PSO算法的迭代次數(shù)更少，收斂速度較快，具有更高的搜索效率;

(2)改進型IPSO算法最好結(jié)果的平均總代價和平均計算時間都比基本PSO算法的小，因此，改進型IPSO算法總體性能要優(yōu)于基本PSO算法.

圖1 兩種算法進化代數(shù)曲線比較圖Fig.1 Algebraic curve of evolution comparison for two algorithms

圖2 兩種算法最好結(jié)果曲線比較圖Fig.2 Curve of the optimum relation comparison for two algorithms

表1 算法比較Table 1 Algorithm comparison

4 改進型粒子群優(yōu)化算法仿真實驗

實驗中，取系數(shù) c0=1，c1=1，c2=1，r1、r2每次迭代均取［0，1］之間的隨機數(shù)，種群規(guī)模為100，節(jié)點之間的權(quán)值取節(jié)點之間的歐氏距離，節(jié)點數(shù)據(jù)為14個節(jié)點的標準TSP問題.實驗環(huán)境:CPU 1.66GHz，內(nèi)存512MB DDR2，WindowsXP，Matlab7.0.圖3、圖4分別給出了初始解中的最優(yōu)解及最終計算結(jié)果.

圖3 初始解中的最優(yōu)解Fig.3 Optimum relation of initial evolution

圖4 IPSO算法實驗結(jié)果Fig.4 Tests results of IPSO

針對此問題，本算法在第19代得到最優(yōu)解，耗時0.19s.文獻［9］中對同一問題在20000代得到了最優(yōu)解，IPSO算法總代價曲線圖如圖5所示.

圖5 IPSO算法總代價曲線圖Fig.5 Total cost curve of IPSO

根據(jù)實驗結(jié)果可知，改進型IPSO算法可以大大減少在解空間中的搜索量，收斂速度較快，在第19代得到了最優(yōu)解，每代搜索了100個解，共搜索1900個解.而對14個節(jié)點的物流配送車輛導航遍歷模型的路徑規(guī)劃問題，可行解共有13個，文章的改進型IPSO算法只搜索了整個解空間的0.000030512%.

5 結(jié)論

文中結(jié)合VND問題的實際特點，建立了VND遍歷模型.分析了PSO算法存在的不足之處，即計算初期收斂很快，但在后期收斂速度很慢，結(jié)果基本上沒有改善，而粒子也慢慢趨于同一個方向，陷入了局部最優(yōu)解.針對PSO算法的缺陷，文中引入小生境思想來縮短每個粒子的壽命，對PSO算法在初始種群的產(chǎn)生方法和種群的進化策略方面進行改進，并提出了適于求解VND遍歷模型的改進型PSO算法，使原本不能直接用于求解VND模型的PSO算法，在求解VND問題上取得了很好的效果.仿真實驗表明，改進后的IPSO算法具有運算快速，收斂效果好等優(yōu)點，在求解VND遍歷模型問題時，大大縮短了計算時間，較基本PSO算法有較大的改進.

［1］溫惠英，沈毅賢.基于層次分析法的物流配送車輛導航路徑規(guī)劃求權(quán)方法［J］.公路交通科技，2008，8(25):114-118.Wen Hui-ying，Sheng Yi-xian.A method of computing weight of logistics navigation route planning based on analytic hierarchy process［J］.Journal of Highway and Transportation Research and Development，2008，8(25):114-118.

［2］姜大立.車輛路徑問題的GA研究［J］.系統(tǒng)工程理論與實踐，1999(6):40-45.Jiang Da-li.GA research of vehicle routing problem ［J］.Systems Engineering-Theory ＆ Practice，1999(6):40-45.

［3］溫惠英，李俊輝，周瑋明.適于車輛路徑規(guī)劃的改進型粒子群優(yōu)化算法［J］.華南理工大學學報:自然科學版，2009，37(7):1-5.Wen Hui-ying，Li Jun-hui，Zhou Wei-ming.Improved particle swarm optimization algorithm for vehicle routing planning［J］.Journal of South China University of Technology:Natural Science Edition，2009，37(7):1-5.

［4］蔣忠中，汪定偉.物流配送車輛路徑優(yōu)化的模糊規(guī)劃模型與算法［J］.系統(tǒng)仿真學報，2006，18(11):3301-3312.Jiang Zhong-zhong，Wang Ding-wei.Fuzzy programming model and algorithm of logistics distribution vehicle routing problem ［J］.Journal of System Simulation，2006，18(11):3301-3312.

［5］Schwefel H.Evolution and optimum seeking［M］.New York:John Wiley ＆ Sons，1994.

［6］Maniezzo V，Colorni A.The ant system applied to the quadratic assignment problem［J］.IEEE Trans on Knowl Data Eng，1999，1(5):769-798.

［7］Kennedy J，Eberhart R.Particle swarm optimization［C］∥Proceedings of IEEE International Conference on Neural Networks.Piscataway:IEEE Service Center，1995:1942-1948.

［8］Eberhart R C，Shi Y.Particle swarm optimization:developments，applications and resources［C］∥Proc Congress on Evolutionary Computation.Piscataway:IEEE Press，2001:81-86.

［9］張利彪，周春光，馬銘，等.基于PSO算法的模糊C-均值聚類［J］.吉林大學學報:理學版，2006，44(2):217-222.Zhang Li-biao，Zhou Chun-guang，Ma Ming，et al.Fuzzy C-mean clustering based on particle swarm optimization［J］.Journal of Jilin University:Sci Ed，2006，44(2):217-222.

［10］Van Den Bergh F，Engelbrecht A P.Using cooperative particle swarm optimization to train product unit neural networks［C］∥IEEE International Joint Conference on Neural Networks.Washington D C:［s.n.］，2001.