基于粒子群算法的最優(yōu)物流運(yùn)輸線(xiàn)路規(guī)劃方法研究

葉平

(上海邦德職業(yè)技術(shù)學(xué)院 經(jīng)濟(jì)與管理學(xué)院，上海 200444)

0 引言

科學(xué)、合理的物流運(yùn)輸路徑能夠大大降低物流成本，提高物流經(jīng)濟(jì)效益。這就要求我們對(duì)物流運(yùn)輸路徑進(jìn)行優(yōu)化設(shè)計(jì)，進(jìn)而提高物流運(yùn)行效率。對(duì)于一個(gè)城市的交通網(wǎng)絡(luò)來(lái)說(shuō)，道路交叉口是實(shí)現(xiàn)交通流疏散的重要節(jié)點(diǎn)，但同時(shí)也是影響城市通行能力的主要因素，這就對(duì)物流運(yùn)輸造成了一定的影響[1]。

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

總的來(lái)說(shuō)，國(guó)內(nèi)外物流運(yùn)輸路徑的研究方向主要分為以上5個(gè)方向，關(guān)于國(guó)內(nèi)外產(chǎn)品物流現(xiàn)狀的研究較多，且多集中于物流系統(tǒng)更新重造，相關(guān)研究針對(duì)帶時(shí)間窗的多目標(biāo)車(chē)輛路徑規(guī)劃問(wèn)題，構(gòu)建運(yùn)輸成本最低與客戶(hù)滿(mǎn)意度最高的配送路徑優(yōu)化模。但是，關(guān)于產(chǎn)品運(yùn)輸工具的研究較少，幾乎都是對(duì)飛機(jī)、鐵路和汽車(chē)這3種傳統(tǒng)運(yùn)輸工具的研究，對(duì)于高速鐵路運(yùn)輸?shù)难芯可婕拜^少。

雖然上述方法在一定程度上實(shí)現(xiàn)了路徑優(yōu)化，提高了運(yùn)輸效率。但是在面對(duì)車(chē)流量巨大的城市中，路徑的選擇和優(yōu)化上還存在一定的制約。為解決這一問(wèn)題，提出一種基于粒子群算法的最優(yōu)物流運(yùn)輸線(xiàn)路規(guī)劃方法，首先利用車(chē)聯(lián)網(wǎng)技術(shù)實(shí)現(xiàn)城市交叉口交通的合理管控，然后充分利用粒子群算法的優(yōu)勢(shì)，組建引導(dǎo)需求和指令匹配對(duì)車(chē)輛的引導(dǎo)路徑進(jìn)行規(guī)劃，實(shí)現(xiàn)物流運(yùn)輸線(xiàn)路的最優(yōu)規(guī)劃。

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

利用智能交通與物聯(lián)網(wǎng)技術(shù)高效結(jié)合的車(chē)聯(lián)網(wǎng)技術(shù)，通過(guò)多種信息傳感器對(duì)車(chē)輛交通情況和信息進(jìn)行收集，實(shí)現(xiàn)對(duì)車(chē)輛、道路和人的智能調(diào)度、協(xié)調(diào)和管理。利用車(chē)聯(lián)網(wǎng)技術(shù)在車(chē)流量控制過(guò)程中，獲取、傳輸和處理交通信息對(duì)城市交叉口交通的合理管控尤其重要。其中，車(chē)輛網(wǎng)的結(jié)構(gòu)如圖1所示。

圖1 車(chē)聯(lián)網(wǎng)結(jié)構(gòu)示意圖

其中，應(yīng)用層由安全調(diào)控、車(chē)路協(xié)同系統(tǒng)等組成，結(jié)合大數(shù)據(jù)等技術(shù)讓車(chē)聯(lián)網(wǎng)顯示實(shí)際價(jià)值。網(wǎng)絡(luò)層主要信息的傳遞，由Wave協(xié)議棧和多種通信技術(shù)結(jié)合，是整個(gè)車(chē)聯(lián)網(wǎng)的核心部分。感知層主要進(jìn)行信息的采集，包括車(chē)輛信息、道路信息等，其中應(yīng)用了3S技術(shù)、定位技術(shù)、數(shù)據(jù)處理技術(shù)等，是車(chē)聯(lián)網(wǎng)有效運(yùn)行的基礎(chǔ)保障。應(yīng)用層、網(wǎng)絡(luò)層、感知層之間相輔相成、緊密聯(lián)系、不可分割。

利用圖1中的車(chē)聯(lián)網(wǎng)結(jié)構(gòu)獲取相關(guān)信息，主要包括如下4類(lèi)：車(chē)輛信息，如速度、位置、數(shù)量環(huán)境參數(shù)等[7]；路邊供應(yīng)設(shè)備信息，如車(chē)流密度、交通密度、位置狀態(tài)、障礙物、行人狀況等[8]；網(wǎng)絡(luò)傳輸緊急狀況信息，如道路維修及養(yǎng)護(hù)信息、交通事故信息、緊急狀況等；社會(huì)資源信息，如停車(chē)場(chǎng)、加油站等。根據(jù)對(duì)相關(guān)信息的收集，建立的城市交叉口車(chē)輛動(dòng)態(tài)信息流獲取模型如圖2所示。

圖2 城市交叉口動(dòng)態(tài)車(chē)輛信息流獲取模型

通過(guò)車(chē)聯(lián)網(wǎng)技術(shù)獲取城市交叉口的交通信息，建立城市交叉口車(chē)輛動(dòng)態(tài)信息流獲取模型，獲取、傳輸和處理交通信息對(duì)城市交叉口交通的合理管控信息，為車(chē)流量預(yù)測(cè)提供信息基礎(chǔ)。

2 基于粒子群算法引導(dǎo)和規(guī)劃物流運(yùn)輸路徑

2.1 車(chē)流量預(yù)測(cè)

在進(jìn)行車(chē)流量智能控制之前，首先需要對(duì)車(chē)流量進(jìn)行預(yù)測(cè)。隨機(jī)選取一個(gè)城市交叉口為預(yù)測(cè)點(diǎn)，車(chē)輛經(jīng)過(guò)該預(yù)測(cè)點(diǎn)需要滿(mǎn)足如下條件[9]。

(1)在不重疊的時(shí)間內(nèi)，經(jīng)過(guò)的車(chē)輛數(shù)量是獨(dú)立的。

(2)對(duì)于足夠小的時(shí)間段Δt，時(shí)間區(qū)間[t,t+Δt]內(nèi)車(chē)輛經(jīng)過(guò)的概率與t不產(chǎn)生關(guān)聯(lián)，則有p(t,t+Δt)=μΔt+o(Δt)，其中μ表示單位時(shí)間經(jīng)過(guò)的車(chē)輛數(shù)量；p(t,t+Δt)表示在時(shí)間區(qū)間[t,t+Δt]內(nèi)有一輛車(chē)經(jīng)過(guò)該預(yù)測(cè)點(diǎn)的概率，以此類(lèi)推，pn(t1,t2)=p{N(t2)-N(t1)=n}，N(t)為[0,t]時(shí)間段內(nèi)經(jīng)過(guò)的車(chē)輛總數(shù)；n為可能經(jīng)過(guò)的車(chē)輛數(shù)。

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

(1)

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

(2)

令Δt→0，則車(chē)流量預(yù)測(cè)模型為式(3)。

(3)

2.2 車(chē)輛路徑引導(dǎo)設(shè)計(jì)

在上述城市交叉口車(chē)流量智能控制方法的基礎(chǔ)上，基于粒子群算法對(duì)車(chē)輛進(jìn)行路徑引導(dǎo)，進(jìn)一步實(shí)現(xiàn)不同路況下的車(chē)流量調(diào)控，實(shí)現(xiàn)物流運(yùn)輸?shù)淖顑?yōu)路徑規(guī)劃，保障路面交通狀態(tài)的平穩(wěn)性。當(dāng)粒子由于局部最優(yōu)值而陷入停滯時(shí)，讓該粒子向其個(gè)體歷史最差位置進(jìn)行學(xué)習(xí)，快速引導(dǎo)這些粒子逃離最優(yōu)值，提升種群的多樣性，提高算法的搜索能力。PSO算法流程圖如圖3所示。

圖3 PSO 算法流程圖

利用泊松分布模型預(yù)測(cè)城市交叉口車(chē)流量變化，結(jié)合粒子群算法組建引導(dǎo)需求和指令匹配，對(duì)車(chē)輛進(jìn)行路徑引導(dǎo)，進(jìn)一步實(shí)現(xiàn)不同路況下的車(chē)流量調(diào)控，實(shí)現(xiàn)物流運(yùn)輸?shù)淖顑?yōu)路徑規(guī)劃。

2.2.1 路徑引導(dǎo)需求組建

為了保證高質(zhì)量的交叉口車(chē)流量控制和車(chē)輛路徑引導(dǎo)，需要捕捉動(dòng)態(tài)車(chē)輛的數(shù)據(jù)。采用粒子群算法[12-13]結(jié)合三元問(wèn)題法對(duì)在最小代價(jià)條件下對(duì)城市交叉口動(dòng)態(tài)車(chē)輛信息進(jìn)行篩選判斷，其表述如式(4)。

(4)

其中，x代表一項(xiàng)動(dòng)態(tài)路徑引導(dǎo)的原子任務(wù)；y代表安全項(xiàng)；z代表突發(fā)事件后原路徑可行狀態(tài)；L代表執(zhí)行任務(wù)的最小代價(jià)；Prec代表車(chē)輛信息流；Tras代表路徑甄選；Effect代表車(chē)輛調(diào)控確認(rèn)項(xiàng)。將路徑引導(dǎo)數(shù)據(jù)經(jīng)過(guò)格雷馬斯矩陣篩選后得出以下2種選擇判斷。

(1)當(dāng)tras 1AT.Tras時(shí)，tras.p0=tras.pt；

(2)當(dāng)tras1,tras2.Tras時(shí)，tras1.p0tras2.p0=tras1.pttras2.pt。

其中，tras1為備選路徑，如發(fā)生事故，那么tras1表示當(dāng)前狀態(tài)下選擇路徑；tras2為備選路徑，依次類(lèi)推。設(shè)p0為初始狀態(tài)的路徑引導(dǎo)任務(wù)狀態(tài)集合，目的地狀態(tài)判斷集合為pt。根據(jù)格雷馬斯矩陣進(jìn)行如下判斷，為式(5)。

(5)

由式(5)可以看出，當(dāng)突發(fā)任務(wù)集合M為空時(shí)，任務(wù)保持選項(xiàng)；當(dāng)突發(fā)任務(wù)集M不為空，則需要通過(guò)類(lèi)型匹配計(jì)算進(jìn)行引導(dǎo)路徑的重新判斷。

2.2.2 路徑引導(dǎo)指令匹配

想要?jiǎng)討B(tài)車(chē)輛路徑引導(dǎo)得到安全、穩(wěn)健的運(yùn)行，需要讓路徑引導(dǎo)需求與路徑引導(dǎo)算法達(dá)到匹配，這就要通過(guò)agent算法，針對(duì)車(chē)輛的路徑進(jìn)行規(guī)劃，當(dāng)引導(dǎo)需求與 agent 算法范圍重合時(shí)，從引導(dǎo)需求輸入到算法處理以及判斷結(jié)果輸出的過(guò)程就可以實(shí)現(xiàn)一次動(dòng)態(tài)車(chē)輛的路徑引導(dǎo)[14-15]。采用相似度函數(shù)以及語(yǔ)義距離方法將引導(dǎo)需求與agent算法規(guī)劃能力相匹配，該過(guò)程如下。

(1)注冊(cè)規(guī)劃申請(qǐng)；

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

(3)返回。

根據(jù)當(dāng)前引導(dǎo)需求設(shè)置agent算法參數(shù)R{Sio,Sim,Sit,Outi},其中Sio,Sim,Sit分別代表R的初始狀態(tài)，運(yùn)行中狀態(tài)和最終狀態(tài)，Outi為R的輸出集合。

當(dāng)agent算法中參數(shù)SAi{Sio,Sim,Sit,Outi,Reli}，其中Sio,Sim,Sit,Outi,Reli分別表示S的初始狀態(tài)、運(yùn)行中狀態(tài)、最終狀態(tài)和輸出集合。Reli表示S的依賴(lài)關(guān)系集合。路徑引導(dǎo)需求與算法引導(dǎo)能力匹配代碼如下。

RSMatdhSA(rs,sa):

InPut:R,

S,

OutPut:TRUE(匹配)，

FALSE(不匹配).

//返回車(chē)聯(lián)網(wǎng)數(shù)據(jù)加載，

進(jìn)行數(shù)據(jù)更新//

該部分判斷了agent算法規(guī)劃范圍及其子功能模塊與路徑引導(dǎo)需求的范圍是否匹配，匹配時(shí)完成路徑引導(dǎo)，不匹配時(shí)返回車(chē)聯(lián)網(wǎng)數(shù)據(jù)庫(kù)，進(jìn)行算法知識(shí)庫(kù)的更新后再進(jìn)行匹配，得出最優(yōu)路徑，進(jìn)而實(shí)現(xiàn)對(duì)城市交叉口車(chē)輛路徑的智能、有效引導(dǎo)。

3 實(shí)驗(yàn)及結(jié)果分析

為了驗(yàn)證基于粒子群算法的最優(yōu)物流運(yùn)輸線(xiàn)路規(guī)劃方法的有效性，選取某城市的真實(shí)道路網(wǎng)，采用PreSdan軟件對(duì)所選道路進(jìn)行微觀場(chǎng)景重建。該交通場(chǎng)景共計(jì)路段29個(gè)，共存在20個(gè)路口，其中12個(gè)三叉路口、5個(gè)直行路口、3個(gè)十字路口。交通場(chǎng)景的3D效果圖如圖4所示。

圖4 交通場(chǎng)景的3D效果圖

從圖4可以看出，實(shí)驗(yàn)所選路段路口繁多，極容易出現(xiàn)交通擁堵。為了便于對(duì)路口進(jìn)行觀察，故此，將圖像由3D簡(jiǎn)化為網(wǎng)絡(luò)拓?fù)鋱D簡(jiǎn)化拓?fù)鋱D，并對(duì)道路路口進(jìn)行了編號(hào)排序，如圖5所示。

圖5 實(shí)驗(yàn)路段交通場(chǎng)景拓?fù)鋱D

3.1 車(chē)輛路徑引導(dǎo)效果檢驗(yàn)

采用所提方法和文獻(xiàn)[2]方法、文獻(xiàn)[3]方法在道路交叉口擁堵情況下，對(duì)車(chē)輛進(jìn)行路徑疏散引導(dǎo)，對(duì)引導(dǎo)效果進(jìn)行比對(duì)。所提方法與文獻(xiàn)[2]方法、文獻(xiàn)[3]方法的路徑引導(dǎo)結(jié)果如圖6所示。

由圖6可以看出，采用文獻(xiàn)[2]方法引導(dǎo)后，車(chē)輛經(jīng)過(guò)編號(hào)1、3、4、8路口，在編號(hào)11路口處再次擁堵無(wú)法前進(jìn)。采用文獻(xiàn)[3]方法引導(dǎo)后，車(chē)輛經(jīng)過(guò)編號(hào)1、2、5、9、11、16路口后，在編號(hào)16路口處無(wú)法前進(jìn)。而采用所提方法引導(dǎo)后，車(chē)輛在經(jīng)過(guò)11號(hào)路口時(shí)，智能選擇折返回歸到8路口轉(zhuǎn)向7、6、10、13路口最終完成車(chē)輛的安全引導(dǎo)。且在速度相同情況下，所提的引導(dǎo)方法在時(shí)間和效率上優(yōu)勝于其他2種方法，說(shuō)明了基于粒子群算法的最優(yōu)物流運(yùn)輸線(xiàn)路規(guī)劃方法能夠在多個(gè)交叉口路口進(jìn)行實(shí)時(shí)監(jiān)控，更好地完成疏導(dǎo)車(chē)流的任務(wù)。

文獻(xiàn)[2]方法

3.2 物流運(yùn)輸線(xiàn)路運(yùn)輸效率檢測(cè)

以十字交叉口為實(shí)驗(yàn)對(duì)象，為檢驗(yàn)所提的基于粒子群算法的最優(yōu)物流運(yùn)輸線(xiàn)路規(guī)劃方法的運(yùn)輸效率，以文獻(xiàn)方法為對(duì)比對(duì)象，檢驗(yàn)2種方法下的城市交叉口信號(hào)平均延誤和車(chē)輛停車(chē)次數(shù)。實(shí)驗(yàn)結(jié)果如圖7、圖8所示。

圖7 交叉口信號(hào)平均延誤對(duì)比圖

圖8 交叉口平均停車(chē)次數(shù)對(duì)比圖

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

4 總結(jié)

對(duì)城市交叉口車(chē)流量進(jìn)行有效控制，能有效實(shí)現(xiàn)車(chē)流的疏散和分離，保障城市交通的暢通和安全。對(duì)此，本文提出了一種基于粒子群算法的最優(yōu)物流運(yùn)輸線(xiàn)路規(guī)劃方法，通過(guò)對(duì)交叉口信號(hào)進(jìn)行調(diào)控和對(duì)車(chē)輛進(jìn)行智能引導(dǎo)，實(shí)現(xiàn)對(duì)城市交叉口交通的合理管控，提高物流運(yùn)輸效率。