基于粒子群算法的最優物流運輸線路規劃方法研究

葉平

(上海邦德職業技術學院 經濟與管理學院，上海 200444)

0 引言

科學、合理的物流運輸路徑能夠大大降低物流成本，提高物流經濟效益。這就要求我們對物流運輸路徑進行優化設計，進而提高物流運行效率。對于一個城市的交通網絡來說，道路交叉口是實現交通流疏散的重要節點，但同時也是影響城市通行能力的主要因素，這就對物流運輸造成了一定的影響[1]。

為優化物流運輸路徑，提高物流運輸效率，首先需要有效地對城市交叉口的車流量進行控制。目前已有一些學者在車流量控制方面開展了大量的研究和應用，先后提出了多種交通控制方法和模型，如基于PLC的交叉口車流疏導系統[2]、擁擠車流控制技術[3]、交通網絡流量預測與控制方法[4]等，對改善道路交通狀況、緩解交通壓力提供了重要支持。在此基礎上相關學者提出了物流運輸車輛的運輸路徑研究。文獻[5]提出了基于多準則的帕累托最優公交路線的定義，利用隨機搜索方法，通過估計每個解空間的值來指導搜索過程。文獻[6]研究了一類隨機需求下的電動汽車電池交換站選址—路徑問題，提出了一種混合可變鄰域搜索算法，該算法將二進制粒子群算法和可變鄰域搜索技術相結合，以交互式方式解決位置和路由問題。

總的來說，國內外物流運輸路徑的研究方向主要分為以上5個方向，關于國內外產品物流現狀的研究較多，且多集中于物流系統更新重造，相關研究針對帶時間窗的多目標車輛路徑規劃問題，構建運輸成本最低與客戶滿意度最高的配送路徑優化模。但是，關于產品運輸工具的研究較少，幾乎都是對飛機、鐵路和汽車這3種傳統運輸工具的研究，對于高速鐵路運輸的研究涉及較少。

雖然上述方法在一定程度上實現了路徑優化，提高了運輸效率。但是在面對車流量巨大的城市中，路徑的選擇和優化上還存在一定的制約。為解決這一問題，提出一種基于粒子群算法的最優物流運輸線路規劃方法，首先利用車聯網技術實現城市交叉口交通的合理管控，然后充分利用粒子群算法的優勢，組建引導需求和指令匹配對車輛的引導路徑進行規劃，實現物流運輸線路的最優規劃。

1 城市交叉口交通的合理管控

利用智能交通與物聯網技術高效結合的車聯網技術，通過多種信息傳感器對車輛交通情況和信息進行收集，實現對車輛、道路和人的智能調度、協調和管理。利用車聯網技術在車流量控制過程中，獲取、傳輸和處理交通信息對城市交叉口交通的合理管控尤其重要。其中，車輛網的結構如圖1所示。

圖1 車聯網結構示意圖

其中，應用層由安全調控、車路協同系統等組成，結合大數據等技術讓車聯網顯示實際價值。網絡層主要信息的傳遞，由Wave協議棧和多種通信技術結合，是整個車聯網的核心部分。感知層主要進行信息的采集，包括車輛信息、道路信息等，其中應用了3S技術、定位技術、數據處理技術等，是車聯網有效運行的基礎保障。應用層、網絡層、感知層之間相輔相成、緊密聯系、不可分割。

利用圖1中的車聯網結構獲取相關信息，主要包括如下4類：車輛信息，如速度、位置、數量環境參數等[7]；路邊供應設備信息，如車流密度、交通密度、位置狀態、障礙物、行人狀況等[8]；網絡傳輸緊急狀況信息，如道路維修及養護信息、交通事故信息、緊急狀況等；社會資源信息，如停車場、加油站等。根據對相關信息的收集，建立的城市交叉口車輛動態信息流獲取模型如圖2所示。

圖2 城市交叉口動態車輛信息流獲取模型

通過車聯網技術獲取城市交叉口的交通信息，建立城市交叉口車輛動態信息流獲取模型，獲取、傳輸和處理交通信息對城市交叉口交通的合理管控信息，為車流量預測提供信息基礎。

2 基于粒子群算法引導和規劃物流運輸路徑

2.1 車流量預測

在進行車流量智能控制之前，首先需要對車流量進行預測。隨機選取一個城市交叉口為預測點，車輛經過該預測點需要滿足如下條件[9]。

(1)在不重疊的時間內，經過的車輛數量是獨立的。

(2)對于足夠小的時間段Δt，時間區間[t,t+Δt]內車輛經過的概率與t不產生關聯，則有p(t,t+Δt)=μΔt+o(Δt)，其中μ表示單位時間經過的車輛數量；p(t,t+Δt)表示在時間區間[t,t+Δt]內有一輛車經過該預測點的概率，以此類推，pn(t1,t2)=p{N(t2)-N(t1)=n}，N(t)為[0,t]時間段內經過的車輛總數；n為可能經過的車輛數。

由于上述條件滿足泊松分布所需要的前提，因此利用泊松分布模型對城市交叉口車流量變化進行預測[10-11]。根據條件(1)、條件(2)可得式(1)

(1)

根據條件(2)、條件(3)可得式(2)

(2)

令Δt→0，則車流量預測模型為式(3)。

(3)

2.2 車輛路徑引導設計

在上述城市交叉口車流量智能控制方法的基礎上，基于粒子群算法對車輛進行路徑引導，進一步實現不同路況下的車流量調控，實現物流運輸的最優路徑規劃，保障路面交通狀態的平穩性。當粒子由于局部最優值而陷入停滯時，讓該粒子向其個體歷史最差位置進行學習，快速引導這些粒子逃離最優值，提升種群的多樣性，提高算法的搜索能力。PSO算法流程圖如圖3所示。

圖3 PSO 算法流程圖

利用泊松分布模型預測城市交叉口車流量變化，結合粒子群算法組建引導需求和指令匹配，對車輛進行路徑引導，進一步實現不同路況下的車流量調控，實現物流運輸的最優路徑規劃。

2.2.1 路徑引導需求組建

為了保證高質量的交叉口車流量控制和車輛路徑引導，需要捕捉動態車輛的數據。采用粒子群算法[12-13]結合三元問題法對在最小代價條件下對城市交叉口動態車輛信息進行篩選判斷，其表述如式(4)。

(4)

其中，x代表一項動態路徑引導的原子任務；y代表安全項；z代表突發事件后原路徑可行狀態；L代表執行任務的最小代價；Prec代表車輛信息流；Tras代表路徑甄選；Effect代表車輛調控確認項。將路徑引導數據經過格雷馬斯矩陣篩選后得出以下2種選擇判斷。

(1)當tras 1AT.Tras時，tras.p0=tras.pt；

(2)當tras1,tras2.Tras時，tras1.p0tras2.p0=tras1.pttras2.pt。

其中，tras1為備選路徑，如發生事故，那么tras1表示當前狀態下選擇路徑；tras2為備選路徑，依次類推。設p0為初始狀態的路徑引導任務狀態集合，目的地狀態判斷集合為pt。根據格雷馬斯矩陣進行如下判斷，為式(5)。

(5)

由式(5)可以看出，當突發任務集合M為空時，任務保持選項；當突發任務集M不為空，則需要通過類型匹配計算進行引導路徑的重新判斷。

2.2.2 路徑引導指令匹配

想要動態車輛路徑引導得到安全、穩健的運行，需要讓路徑引導需求與路徑引導算法達到匹配，這就要通過agent算法，針對車輛的路徑進行規劃，當引導需求與 agent 算法范圍重合時，從引導需求輸入到算法處理以及判斷結果輸出的過程就可以實現一次動態車輛的路徑引導[14-15]。采用相似度函數以及語義距離方法將引導需求與agent算法規劃能力相匹配，該過程如下。

(1)注冊規劃申請；

(2)設置不匹配判斷條件，確認所接收到的引導需求是否與agent算法規劃能力相匹配；

(3)返回。

根據當前引導需求設置agent算法參數R{Sio,Sim,Sit,Outi},其中Sio,Sim,Sit分別代表R的初始狀態，運行中狀態和最終狀態，Outi為R的輸出集合。

當agent算法中參數SAi{Sio,Sim,Sit,Outi,Reli}，其中Sio,Sim,Sit,Outi,Reli分別表示S的初始狀態、運行中狀態、最終狀態和輸出集合。Reli表示S的依賴關系集合。路徑引導需求與算法引導能力匹配代碼如下。

RSMatdhSA(rs,sa):

InPut:R,

S,

OutPut:TRUE(匹配)，

FALSE(不匹配).

//返回車聯網數據加載，

進行數據更新//

該部分判斷了agent算法規劃范圍及其子功能模塊與路徑引導需求的范圍是否匹配，匹配時完成路徑引導，不匹配時返回車聯網數據庫，進行算法知識庫的更新后再進行匹配，得出最優路徑，進而實現對城市交叉口車輛路徑的智能、有效引導。

3 實驗及結果分析

為了驗證基于粒子群算法的最優物流運輸線路規劃方法的有效性，選取某城市的真實道路網，采用PreSdan軟件對所選道路進行微觀場景重建。該交通場景共計路段29個，共存在20個路口，其中12個三叉路口、5個直行路口、3個十字路口。交通場景的3D效果圖如圖4所示。

圖4 交通場景的3D效果圖

從圖4可以看出，實驗所選路段路口繁多，極容易出現交通擁堵。為了便于對路口進行觀察，故此，將圖像由3D簡化為網絡拓撲圖簡化拓撲圖，并對道路路口進行了編號排序，如圖5所示。

圖5 實驗路段交通場景拓撲圖

3.1 車輛路徑引導效果檢驗

采用所提方法和文獻[2]方法、文獻[3]方法在道路交叉口擁堵情況下，對車輛進行路徑疏散引導，對引導效果進行比對。所提方法與文獻[2]方法、文獻[3]方法的路徑引導結果如圖6所示。

由圖6可以看出，采用文獻[2]方法引導后，車輛經過編號1、3、4、8路口，在編號11路口處再次擁堵無法前進。采用文獻[3]方法引導后，車輛經過編號1、2、5、9、11、16路口后，在編號16路口處無法前進。而采用所提方法引導后，車輛在經過11號路口時，智能選擇折返回歸到8路口轉向7、6、10、13路口最終完成車輛的安全引導。且在速度相同情況下，所提的引導方法在時間和效率上優勝于其他2種方法，說明了基于粒子群算法的最優物流運輸線路規劃方法能夠在多個交叉口路口進行實時監控，更好地完成疏導車流的任務。

文獻[2]方法

3.2 物流運輸線路運輸效率檢測

以十字交叉口為實驗對象，為檢驗所提的基于粒子群算法的最優物流運輸線路規劃方法的運輸效率，以文獻方法為對比對象，檢驗2種方法下的城市交叉口信號平均延誤和車輛停車次數。實驗結果如圖7、圖8所示。

圖7 交叉口信號平均延誤對比圖

圖8 交叉口平均停車次數對比圖

分析圖7和圖8可知，所提的基于粒子群算法的最優物流運輸線路規劃方法的信號控制和車流量控制要優于文獻方法，可有效降低城市交叉口信號的平均延誤和交叉口處的車輛平均停車次數，進一步提高物流運輸線路的運輸效率。與文獻方法相比，當車流量較小時(2 400 veh/h)，交叉口信號平均延誤時間和平均停車次數分別降低約18% 和22%；當車流量較大時(7 200 veh/h)，交叉口信號平均延誤時間和平均停車次數分別降低約32% 和16%。

4 總結

對城市交叉口車流量進行有效控制，能有效實現車流的疏散和分離，保障城市交通的暢通和安全。對此，本文提出了一種基于粒子群算法的最優物流運輸線路規劃方法，通過對交叉口信號進行調控和對車輛進行智能引導，實現對城市交叉口交通的合理管控，提高物流運輸效率。