個(gè)人快速交通動(dòng)態(tài)任務(wù)分配問題的優(yōu)化研究

朱辰陽，趙春曉

(1.北京建筑大學(xué) 電氣與信息工程學(xué)院，北京 100044；2.北京建筑大學(xué) 北京未來城市設(shè)計(jì)高精尖創(chuàng)新中心，北京 100044)

0 引 言

近年來，城市汽車連年暴增，交通擁堵越來越嚴(yán)重，行路難、停車難已經(jīng)成為阻礙國內(nèi)城市發(fā)展的主要因素[1]。當(dāng)前交通結(jié)構(gòu)的主要矛盾是私人轎車和開放式道路之間的矛盾，是徹底治堵的切入點(diǎn)?，F(xiàn)有的公共交通無法與私人轎車競爭，只有轎車化的公共交通方式才能徹底緩解交通擁堵問題。

轎車化公交車和架空輕軌，構(gòu)成了一種新型交通系統(tǒng)——個(gè)人快速交通(Personal Rapid Transit，PRT)系統(tǒng)，采用離線車站，用軌道轎車實(shí)現(xiàn)點(diǎn)到點(diǎn)的快速直達(dá)，其最大的價(jià)值是可以在未來取代一部分的私人轎車，從而徹底解決交通擁堵。但此系統(tǒng)中乘客的出行模式在空間和時(shí)間上不對稱導(dǎo)致PRT資源無法被充分利用。因此，如何在考慮乘客行程需求、電池容量約束的情況下，使整個(gè)PRT系統(tǒng)的效益最大化，是PRT系統(tǒng)亟待解決的問題。

目前PRT動(dòng)態(tài)任務(wù)分配方面的研究相對較少，主要原因是無人駕駛技術(shù)、傳感器技術(shù)等關(guān)鍵技術(shù)尚未成熟，同時(shí)已運(yùn)營的PRT系統(tǒng)線路結(jié)構(gòu)較為簡單，對PRT動(dòng)態(tài)任務(wù)分配的要求不高。近年來，無人駕駛等關(guān)鍵技術(shù)以及相關(guān)的硬件設(shè)備不斷完善，隨著PRT系統(tǒng)在城市公共交通的廣泛推廣應(yīng)用，對PRT動(dòng)態(tài)任務(wù)分配的要求會(huì)越來越高，因此，深入研究PRT動(dòng)態(tài)任務(wù)分配極為重要。

雖然當(dāng)前任務(wù)分配的研究未有直接應(yīng)用在PRT系統(tǒng)的研究方案，但針對其他不同的應(yīng)用場景，國內(nèi)外學(xué)者提出了諸多卓有成效的任務(wù)分配實(shí)現(xiàn)方法。盧騫[2]將改進(jìn)的模擬退火算法和移動(dòng)策略相結(jié)合；周晶[3]引入遷移策略和貪心算法對任務(wù)分配方案進(jìn)行局部提升。

在文獻(xiàn)[4]中，作者提出了一種基于魚群的多無人機(jī)任務(wù)分配算法(FIAM)；蔣碩[5]在標(biāo)準(zhǔn)粒子群算法中采用階層分級策略來為不同粒子選擇相應(yīng)的學(xué)習(xí)模型來解決多無人機(jī)協(xié)同任務(wù)分配問題。

文獻(xiàn)[6]提出了一種細(xì)菌覓食啟發(fā)式算法；曹鵬飛[7]將生物免疫網(wǎng)絡(luò)的工作機(jī)理應(yīng)用到多機(jī)器人動(dòng)態(tài)任務(wù)分配算法中；Fang[8]綜合機(jī)器人情感因素，提出了一種基于情緒渲染的尋蹤任務(wù)分配算法(PTA-EC);楊惠珍[9]引入動(dòng)態(tài)蟻群勞動(dòng)分工中的刺激—響應(yīng)原理，將任務(wù)的狀態(tài)預(yù)測納入響應(yīng)閾值;李珣[10]提出了一種基于智能體博弈理論的分布式自主決策框架。

針對多車站、多PRT、乘客隨機(jī)到達(dá)等復(fù)雜動(dòng)態(tài)任務(wù)分配問題，該文建立了以PRT車輛里程利用率、乘客等待時(shí)間為優(yōu)化目標(biāo)的PRT車輛動(dòng)態(tài)任務(wù)分配模型，并進(jìn)行了針對此模型優(yōu)化算法的研究。

1 問題描述

1.1 PRT系統(tǒng)

PRT系統(tǒng)可以簡單地表示為一個(gè)四元組，其中V表示PRT車輛實(shí)體，GN是一個(gè)導(dǎo)軌網(wǎng)絡(luò)，E是城市社區(qū)，是V和GN所在的環(huán)境，f是系統(tǒng)目標(biāo)函數(shù)，是實(shí)體狀態(tài)的非線性函數(shù)。

V={v1,v2,…,vm}表示一組PRT車輛實(shí)體，代表軌道路網(wǎng)上m個(gè)運(yùn)行的車輛。GN包括節(jié)點(diǎn)和鏈接。節(jié)點(diǎn)是一個(gè)地理位置，鏈接連接兩個(gè)節(jié)點(diǎn)，類型有主線、出站、入站、合并、分叉、側(cè)線(站)等。GN可以被建模為一個(gè)完整的有向圖GN=(N,L)的子圖，其中N={1,2,…,n}代表n個(gè)節(jié)點(diǎn)，L={(i,j)|i,j∈N,i≠j}代表n(n-1)條從節(jié)點(diǎn)i到j(luò)的有向鏈接。E是用來規(guī)劃PRT系統(tǒng)的城市社區(qū)。f是系統(tǒng)目標(biāo)函數(shù)。在四元組中，給定一個(gè)軌道網(wǎng)GN和車隊(duì)V，選擇能實(shí)現(xiàn)里程利用率和乘客等待時(shí)間之間最佳權(quán)衡的調(diào)度策略作為系統(tǒng)目標(biāo)函數(shù)f。

Voronoi圖是將一定的區(qū)域范圍按照最近鄰原則劃分為n個(gè)凸邊形子區(qū)域，其中n是區(qū)域范圍中包含的點(diǎn)數(shù)量。在PRT系統(tǒng)中，以乘客需求點(diǎn)集{p1,p2,…,pn}中的點(diǎn)為中心，以相同的速率向外擴(kuò)張，直到覆蓋整個(gè)區(qū)域范圍，由此形成PRT車輛的任務(wù)范圍S。任一點(diǎn)擴(kuò)張出的多邊形Ti內(nèi)的點(diǎn)滿足下列條件：

Ti={x:d(x,pi)

式中，d表示需求點(diǎn)間的歐氏距離，Ti內(nèi)任意一點(diǎn)到達(dá)pi的距離都小于該點(diǎn)到{p1,p2,…,pn}內(nèi)其他點(diǎn)的距離。

1.2 PRT車輛動(dòng)態(tài)任務(wù)分配模型

傳統(tǒng)公共交通大多采用靜態(tài)任務(wù)分配，根據(jù)線路乘客需求提前確定發(fā)車時(shí)刻表[11]。但由于各車站的客流是不斷波動(dòng)的，客流在一天內(nèi)的波動(dòng)會(huì)不斷打破原有的車輛供需平衡[12]，這使得PRT系統(tǒng)隨之動(dòng)態(tài)變化。為了增加整個(gè)運(yùn)行時(shí)段系統(tǒng)的穩(wěn)定性，減少系統(tǒng)中乘客的等待時(shí)間，需要PRT系統(tǒng)在靜態(tài)任務(wù)分配的基礎(chǔ)上，根據(jù)客流的變化動(dòng)態(tài)調(diào)整車輛的運(yùn)行狀態(tài)，實(shí)現(xiàn)車輛的動(dòng)態(tài)任務(wù)分配。

系統(tǒng)優(yōu)化的目標(biāo)是制定一個(gè)力求為所有行程請求提供服務(wù)的任務(wù)分配策略，在滿足每輛車的電池容量的前提下，找到里程利用率和乘客等待時(shí)間之間的最佳權(quán)衡。該文僅考慮每個(gè)行程請求之間的次序選擇，對于具體線路規(guī)劃暫不予考慮。為此，對該P(yáng)RT系統(tǒng)做出如下假設(shè):

(1)所有車輛的電池容量和初始電量相同，且電池不會(huì)發(fā)生損耗。

(2)PRT車輛的行駛速率恒定。

(3)每個(gè)行程需求的乘客規(guī)模不超過6人，即每個(gè)需求由一輛車即可完成。

(4)每個(gè)乘客行程請求所需車輛電量不超過車輛的電池容量。

(5)任務(wù)的產(chǎn)生是獨(dú)立且隨機(jī)的，即任務(wù)到達(dá)是泊松過程。

對于運(yùn)營者而言，PRT系統(tǒng)要減少車輛資源的浪費(fèi)，降低運(yùn)營成本，提高整個(gè)線網(wǎng)的運(yùn)行效率；對于乘客而言，PRT系統(tǒng)要提供快捷和有效的交通服務(wù)。因此，制定有效的動(dòng)態(tài)任務(wù)分配策略來實(shí)現(xiàn)這種平衡是PRT系統(tǒng)的重點(diǎn)和難點(diǎn)。PRT動(dòng)態(tài)任務(wù)分配模型如圖1所示。

針對特定環(huán)境下的動(dòng)態(tài)任務(wù)分配，根據(jù)任務(wù)和車輛特點(diǎn)，可得多站點(diǎn)動(dòng)態(tài)任務(wù)分配的目標(biāo)函數(shù)和約束條件為：

(1)

(2)

(3)

(4)

uij∈{0,1}

(5)

式中，式(1)、(2)均為目標(biāo)函數(shù)，式(1)表示系統(tǒng)載客里程利用率、式(2)表示乘客總等待時(shí)間；式(3)～式(5)均為約束條件，式(3)表示PRT車輛電池容量約束，式(4)、(5)表示每一個(gè)任務(wù)點(diǎn)只能由一輛PRT負(fù)責(zé)。模型中的參數(shù)及變量見表1。

表1 模型參數(shù)及變量

2 PRT系統(tǒng)多智能體模型構(gòu)建

2.1 PRT與多智能體系統(tǒng)

為了實(shí)現(xiàn)PRT系統(tǒng)的高效率，在車輛運(yùn)行過程中，車輛安全間距較小，車輛與中央調(diào)度系統(tǒng)之間通信實(shí)時(shí)性要求較高，如果采用集中控制的方式，就會(huì)導(dǎo)致車輛自主性不高，運(yùn)行過程當(dāng)中如遇緊急情況需完全依賴中央調(diào)度系統(tǒng)回傳指令，往往由于通信時(shí)間問題和信息掌握不全導(dǎo)致指令失效，系統(tǒng)的容錯(cuò)性較低。分布式控制方式可以很好地解決PRT系統(tǒng)車輛動(dòng)態(tài)任務(wù)分配問題。每一個(gè)車輛就是一個(gè)簡單的個(gè)體，具有相對獨(dú)立性，個(gè)體之間可以進(jìn)行一些簡單的信息交互，車輛可以根據(jù)感知周圍的環(huán)境信息進(jìn)行自主控制。一方面中央調(diào)度系統(tǒng)可以對車輛的運(yùn)行狀態(tài)進(jìn)行實(shí)時(shí)監(jiān)測和調(diào)整，另一方面車輛也具備了一定的自行控制的能力，這降低了中央調(diào)度系統(tǒng)控制的難度，同時(shí)提高了系統(tǒng)的智能化程度和適應(yīng)環(huán)境的能力。多智能體系統(tǒng)建模使分布式控制實(shí)現(xiàn)成為可能。

多智能體系統(tǒng)通過由實(shí)際系統(tǒng)總結(jié)出的系統(tǒng)中個(gè)體的運(yùn)行機(jī)制，構(gòu)建由這些自治智能體組成的復(fù)雜系統(tǒng)，觀察個(gè)體之間以及個(gè)體與環(huán)境進(jìn)行交互后，整個(gè)系統(tǒng)的演變趨勢[13]。采用多智能體系統(tǒng)對分布式控制方式進(jìn)行建模，優(yōu)點(diǎn)是在系統(tǒng)中個(gè)體可以自下而上地進(jìn)行智能決策，而不是中央系統(tǒng)自上而下地調(diào)整個(gè)體的行為，仿真結(jié)果更加貼近實(shí)際系統(tǒng)。

2.2 PRT系統(tǒng)多智能體模型

多智能體系統(tǒng)建模技術(shù)是對“主體”(Agent)自身以及它們之間的通信交互等行為進(jìn)行模擬，通過觀察系統(tǒng)整體涌現(xiàn)的行為，進(jìn)而揭示實(shí)際系統(tǒng)的運(yùn)行規(guī)律[14]。該文旨在基于多智能體模型從隨時(shí)間變化的PRT系統(tǒng)中探究PRT個(gè)體行為與系統(tǒng)群體行為之間的微觀關(guān)系。假設(shè)所有車輛最初位于停車場，車輛從出發(fā)站到目的站的路徑最短。PRT系統(tǒng)多智能體模型中，主要有三類智能體形式，即靜態(tài)主體道路和動(dòng)態(tài)主體PRT車輛以及乘客。不同智能體主要屬性及含義如表2所示。

表2 不同智能體主要屬性及含義

3 PRT車輛動(dòng)態(tài)任務(wù)分配算法設(shè)計(jì)

3.1 粒子群算法

粒子群算法模擬了某一群體中個(gè)體通過與其他成員間的交互來共享與獲得信息，一群粒子由個(gè)體曾到達(dá)過的最優(yōu)點(diǎn)以及群體曾到達(dá)過的最優(yōu)點(diǎn)的引導(dǎo)，在指定的搜索空間內(nèi)隨機(jī)移動(dòng)[15]。在整個(gè)粒子群的運(yùn)動(dòng)過程中，粒子間相互影響，包含解的最佳局部點(diǎn)和全局點(diǎn)的信息在各個(gè)粒子之間傳遞、更新，每個(gè)粒子再根據(jù)這些信息調(diào)整其速度和方向，并繼續(xù)在搜索空間內(nèi)探索最優(yōu)解的解空間。該文采用基于淘汰機(jī)制的粒子群算法求解任務(wù)分配問題。給出PSO的標(biāo)準(zhǔn)形式，如公式(6)、(7)所示：

(6)

(7)

3.2 粒子群算法與實(shí)際問題映射

應(yīng)用PSO解決PRT車輛動(dòng)態(tài)任務(wù)分配問題時(shí)，把實(shí)際站點(diǎn)上候車的乘客看作任務(wù)點(diǎn)，PRT在順利完成每次任務(wù)后，會(huì)在該點(diǎn)產(chǎn)生一定數(shù)量的粒子，其能夠隨虛擬區(qū)域的環(huán)境變化做出選擇、決策。由于新的乘客不斷以一定的到達(dá)率隨機(jī)出現(xiàn)，車輛事先無法得知乘客所在的位置，只能通過不斷搜尋迭代，才能找到適應(yīng)度函數(shù)較優(yōu)的乘客位置。

3.3 適應(yīng)度函數(shù)的改進(jìn)

在PSO中，適應(yīng)度函數(shù)的確定決定了一個(gè)問題能否找到一個(gè)更優(yōu)的解。在該文背景下，適應(yīng)度函數(shù)若為單一的距離指標(biāo)，可以極大地提高里程利用率，但同時(shí)忽略了乘客的等待時(shí)間，也就意味著此時(shí)默認(rèn)無論等待時(shí)間多長，乘客都不會(huì)離開，這與實(shí)際情況不符。綜合考慮區(qū)域邊界、目標(biāo)出現(xiàn)位置概率以及整體覆蓋率后，最終確定適應(yīng)度函數(shù)如公式(8)所示：

(8)

式中，distij、Wj、m、n含義同表1，a、b分別為距離與等待時(shí)間的權(quán)重系數(shù)。

3.4 改進(jìn)的粒子群算法

標(biāo)準(zhǔn)粒子群算法中，在某一區(qū)域范圍內(nèi)任何一點(diǎn)都可能是局部最優(yōu)值或者全局最優(yōu)值，但在針對PRT車輛動(dòng)態(tài)任務(wù)分配模型中，只有特定的車站站點(diǎn)處才可能成為局部最優(yōu)值或者全局最優(yōu)值。在改進(jìn)后的適應(yīng)度函數(shù)評價(jià)標(biāo)準(zhǔn)下，粒子群從PRT所在位置產(chǎn)生后，總體的趨勢是不斷向外的，此時(shí)適應(yīng)度函數(shù)的第一項(xiàng)不斷變大，因此不斷向外搜尋到的乘客需求點(diǎn)的適應(yīng)度函數(shù)隨之變大的概率很高，除非在此過程之中搜尋到了等待時(shí)間較長的乘客需求點(diǎn)，這導(dǎo)致很大概率上搜尋的時(shí)間越長，算法搜尋的結(jié)果越差。在文中模型背景下，乘客需求點(diǎn)是未知的、不斷產(chǎn)生的，且任務(wù)分配方案評價(jià)指標(biāo)之一是乘客的等待時(shí)間，因此對于整個(gè)系統(tǒng)分配方案的解的要求并不苛刻，且很難搜尋到最優(yōu)解，所以更傾向于在較短的時(shí)間內(nèi)得到較為滿意的解而不是最優(yōu)的解，標(biāo)準(zhǔn)粒子群算法很難適應(yīng)文中針對的模型。為了提高算法的效率，首先將Voronoi圖融合進(jìn)PSO的初期搜索過程中，每當(dāng)車輛完成運(yùn)輸任務(wù)后，粒子群會(huì)從車輛所在點(diǎn)產(chǎn)生，一旦粒子群超出了Voronoi圖形成的車輛所在的任務(wù)區(qū)域之后，隨即調(diào)整適應(yīng)度函數(shù)中距離的權(quán)重系數(shù)a。然后為了應(yīng)對在搜索后期結(jié)果變差的問題，該文引入了遺傳算法的選擇淘汰策略，提出了一種基于淘汰機(jī)制的粒子群算法(Elimination-Based Particle Swarm Optimization，EBPSO)，并將新的EBPSO算法與Voronoi圖結(jié)合。當(dāng)PSO優(yōu)化進(jìn)行到一定時(shí)間后，從當(dāng)前的全局最優(yōu)值處重新產(chǎn)生一定數(shù)量的粒子來替換掉那些原本適應(yīng)度值較差的粒子繼續(xù)進(jìn)行優(yōu)化。EBPSO調(diào)度算法的偽代碼設(shè)計(jì)如下：

算法1：EBPSO調(diào)度算法

ask PRT所在點(diǎn)產(chǎn)生population-size個(gè)粒子

while searching-time != 0

ifelse 處于搜尋的初始階段

if not Voronoi圖劃定的子區(qū)域范圍

動(dòng)態(tài)調(diào)整適應(yīng)度函數(shù)中距離的權(quán)重系數(shù)a

end if

ask 一部分適應(yīng)度差的粒子die

ask 全局最優(yōu)值所在點(diǎn)產(chǎn)生相應(yīng)數(shù)量的粒子

end if

if 搜尋到的當(dāng)前點(diǎn)有乘客 and not 通信列表中其他PRT已確定的目標(biāo)乘客

計(jì)算其適應(yīng)度

if適應(yīng)度優(yōu)于粒子局部最優(yōu)值

更新personal-best-x、personal-best-y

end if

ask粒子群中適應(yīng)度最優(yōu)的粒子

if適應(yīng)度優(yōu)于全局最優(yōu)值

更新global-best-x、global-best-y

end if

ask每個(gè)粒子

按公式(6)更新粒子速度

按公式(7)更新粒子位置

end if

end while

ask 所有粒子 die

4 仿真結(jié)果分析

基于上述的多智能體模型，在NetLogo中實(shí)現(xiàn)了PRT系統(tǒng)模擬器，這是一個(gè)多智能體可編程建模環(huán)境。模擬器支持PRT系統(tǒng)任務(wù)分配求解，仿真內(nèi)容包括PRT初始運(yùn)行階段對線網(wǎng)上已聚集的乘客的靜態(tài)任務(wù)分配以及對整個(gè)運(yùn)行階段不斷到達(dá)的乘客的動(dòng)態(tài)任務(wù)分配。仿真環(huán)境的中心為坐標(biāo)系原點(diǎn)(0,0)，通過設(shè)定121*59個(gè)點(diǎn)構(gòu)成的坐標(biāo)系來模擬一個(gè)4 km*2 km的區(qū)域范圍。

4.1 靜態(tài)任務(wù)分配

PRT系統(tǒng)剛開始運(yùn)行時(shí)，線網(wǎng)中聚集了一定數(shù)量的乘客需求點(diǎn)，這要求首先進(jìn)行目標(biāo)位置已知的靜態(tài)任務(wù)分配。對于靜態(tài)任務(wù)分配問題，該文以基本的K-means聚類算法為基礎(chǔ)，綜合考慮已知需求點(diǎn)間的距離以及PRT車庫與需求點(diǎn)的距離，同時(shí)根據(jù)PRT車輛數(shù)量限定形成聚類需求點(diǎn)的數(shù)量以及單個(gè)車輛集群的覆蓋范圍。模型中，共有4個(gè)PRT車庫，分別為(-56，29)、(-22，29)、(24，-29)、(57，-29)，在仿真區(qū)域范圍內(nèi)隨機(jī)生成20個(gè)初始乘客需求點(diǎn)，需求點(diǎn)位置分布如圖2所示。采用K-means聚類算法求解得到20個(gè)初始乘客需求點(diǎn)的聚類結(jié)果如圖3所示。

根據(jù)車庫數(shù)量，20個(gè)初始需求點(diǎn)聚類生成的集群數(shù)量為4個(gè)，各集群中心分別為 (-49，8)、(-8，4)、(18，-12)、(48，9)。綜上，采用K-means聚類算法得到PRT車輛初始靜態(tài)任務(wù)分配的方案。

4.2 動(dòng)態(tài)任務(wù)分配

在實(shí)際PRT系統(tǒng)中，任務(wù)目標(biāo)狀態(tài)和車輛狀態(tài)會(huì)隨客流發(fā)生變化，因此采用該文提出的基于淘汰機(jī)制的粒子群算法解決PRT車輛動(dòng)態(tài)任務(wù)分配問題。對于求解模型的參數(shù)和優(yōu)化算法的參數(shù)，主要是參考實(shí)驗(yàn)測試情況選取優(yōu)化能力較好的設(shè)置，主要參數(shù)設(shè)置如表3所示。

表3 模型主要參數(shù)、參考值及取值范圍

仿真環(huán)境的時(shí)間直接采用NetLogo內(nèi)建的時(shí)鐘計(jì)數(shù)ticks，為方便結(jié)果統(tǒng)計(jì)，實(shí)驗(yàn)均運(yùn)行3 000 ticks。隨機(jī)選取T=1 000 ticks和T=2 000 ticks時(shí)的關(guān)于乘客需求點(diǎn)的Voronoi圖如圖4和圖5所示。值得注意的是，NetLogo平臺拓?fù)湓试S回繞，即智能體可以從邊界出現(xiàn)在另一邊。因此從圖上可以看出，回繞距離更短時(shí)，Voronoi圖采用的是回繞距離。

仿真實(shí)驗(yàn)分別用標(biāo)準(zhǔn)粒子群算法、改進(jìn)適應(yīng)度函數(shù)后的粒子群算法和EBPSO算法進(jìn)行求解，每個(gè)算法分別獨(dú)立運(yùn)行20次。隨機(jī)選取其中的20個(gè)站點(diǎn)，以公式(1)所示的PRT里程利用率和公式(2)所示的乘客等待時(shí)間作為性能評價(jià)依據(jù)，車輛速度默認(rèn)為60 km/h，實(shí)驗(yàn)結(jié)果如表4、圖6和圖7所示。

表4 里程利用率

經(jīng)過多次實(shí)驗(yàn)得出結(jié)果，標(biāo)準(zhǔn)粒子群算法的平均等待時(shí)間為294.33 s，最長平均等待時(shí)間為501.19 s，平均里程利用率為54.71%；對適應(yīng)度函數(shù)改進(jìn)后，平均等待時(shí)間為172.47 s，最長平均等待時(shí)間為345.45 s，平均里程利用率為54.14%；采用EBPSO算法后，平均等待時(shí)間為153.21 s，最長平均等待時(shí)間為294.16 s，平均里程利用率為54.46%?？梢钥闯觯诮鉀QPRT車輛動(dòng)態(tài)任務(wù)分配的問題上，EBPSO算法在不損失里程利用率的前提下，相比標(biāo)準(zhǔn)粒子群算法使平均等待時(shí)間和最長平均等待時(shí)間分別降低了47.95%和41.31%；相比僅改進(jìn)適應(yīng)度函數(shù)的粒子群算法使平均等待時(shí)間和最長平均等待時(shí)間分別降低了11.17%和14.85%，且通過對算法結(jié)果的標(biāo)準(zhǔn)差分析可知，EBPSO算法的實(shí)驗(yàn)數(shù)據(jù)波動(dòng)更小，在運(yùn)行上更加穩(wěn)定。仿真實(shí)驗(yàn)結(jié)果表明，EBPSO算法在解決PRT車輛動(dòng)態(tài)任務(wù)分配問題上比標(biāo)準(zhǔn)粒子群算法以及僅改進(jìn)適應(yīng)度函數(shù)的粒子群算法都更具優(yōu)勢。

5 結(jié)束語

PRT是一種新型公共交通方式，有潛力與當(dāng)前主流交通方式競爭，以實(shí)現(xiàn)從本質(zhì)上緩解交通擁堵問題。該研究的目的是為PRT系統(tǒng)中的動(dòng)態(tài)任務(wù)分配問題提出一個(gè)有效的調(diào)度策略，實(shí)現(xiàn)里程利用率和乘客等待時(shí)間的最佳權(quán)衡。

首先基于NetLogo平臺建立了PRT系統(tǒng)多智能體模型，然后對于系統(tǒng)中多站點(diǎn)動(dòng)態(tài)任務(wù)分配問題，建立了以里程利用率和等待時(shí)間為優(yōu)化目標(biāo)的PRT車輛動(dòng)態(tài)任務(wù)分配模型，最后針對PRT系統(tǒng)的主要特征以及模型中動(dòng)態(tài)目標(biāo)的特點(diǎn)，提出了對標(biāo)準(zhǔn)粒子群算法的適應(yīng)度函數(shù)的改進(jìn)方案，并將Voronoi圖和淘汰選擇策略與粒子群算法進(jìn)行有效融合。通過多次對比實(shí)驗(yàn)，所提算法在不損失里程利用率的前提下，相比標(biāo)準(zhǔn)粒子群算法使平均等待時(shí)間和最長平均等待時(shí)間分別降低了47.95%和41.31%；相比僅改進(jìn)適應(yīng)度函數(shù)的粒子群算法使平均等待時(shí)間和最長平均等待時(shí)間分別降低了11.17%和14.85%。實(shí)驗(yàn)結(jié)果證實(shí)了所提算法在解決PRT車輛動(dòng)態(tài)任務(wù)分配問題上具有優(yōu)越性。