朱辰陽，趙春曉

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

0 引 言

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

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

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

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

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

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

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

1 問題描述

1.1 PRT系統(tǒng)

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

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

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

Ti={x:d(x,pi)

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

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

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

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

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

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

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

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

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

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

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

(1)

(2)

(3)

(4)

uij∈{0,1}

(5)

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

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

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

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

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

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

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

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

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

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

3.1 粒子群算法

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

(6)

(7)

3.2 粒子群算法與實際問題映射

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

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

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

(8)

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

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

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

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

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

while searching-time != 0

ifelse 處于搜尋的初始階段

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

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

end if

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

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

end if

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

計算其適應(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每個粒子

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

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

end if

end while

ask 所有粒子 die

4 仿真結(jié)果分析

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

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

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

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

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

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

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

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

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

表4 里程利用率

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

5 結(jié)束語

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

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