個人快速交通動態任務分配問題的優化研究

朱辰陽，趙春曉

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

0 引 言

近年來，城市汽車連年暴增，交通擁堵越來越嚴重，行路難、停車難已經成為阻礙國內城市發展的主要因素[1]。當前交通結構的主要矛盾是私人轎車和開放式道路之間的矛盾，是徹底治堵的切入點。現有的公共交通無法與私人轎車競爭，只有轎車化的公共交通方式才能徹底緩解交通擁堵問題。

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

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

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

在文獻[4]中，作者提出了一種基于魚群的多無人機任務分配算法(FIAM)；蔣碩[5]在標準粒子群算法中采用階層分級策略來為不同粒子選擇相應的學習模型來解決多無人機協同任務分配問題。

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

針對多車站、多PRT、乘客隨機到達等復雜動態任務分配問題，該文建立了以PRT車輛里程利用率、乘客等待時間為優化目標的PRT車輛動態任務分配模型，并進行了針對此模型優化算法的研究。

1 問題描述

1.1 PRT系統

PRT系統可以簡單地表示為一個四元組，其中V表示PRT車輛實體，GN是一個導軌網絡，E是城市社區，是V和GN所在的環境，f是系統目標函數，是實體狀態的非線性函數。

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

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

Ti={x:d(x,pi)

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

1.2 PRT車輛動態任務分配模型

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

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

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

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

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

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

(5)任務的產生是獨立且隨機的，即任務到達是泊松過程。

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

針對特定環境下的動態任務分配，根據任務和車輛特點，可得多站點動態任務分配的目標函數和約束條件為：

(1)

(2)

(3)

(4)

uij∈{0,1}

(5)

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

表1 模型參數及變量

2 PRT系統多智能體模型構建

2.1 PRT與多智能體系統

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

多智能體系統通過由實際系統總結出的系統中個體的運行機制，構建由這些自治智能體組成的復雜系統，觀察個體之間以及個體與環境進行交互后，整個系統的演變趨勢[13]。采用多智能體系統對分布式控制方式進行建模，優點是在系統中個體可以自下而上地進行智能決策，而不是中央系統自上而下地調整個體的行為，仿真結果更加貼近實際系統。

2.2 PRT系統多智能體模型

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

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

3 PRT車輛動態任務分配算法設計

3.1 粒子群算法

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

(6)

(7)

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

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

3.3 適應度函數的改進

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

(8)

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

3.4 改進的粒子群算法

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

算法1：EBPSO調度算法

ask PRT所在點產生population-size個粒子

while searching-time != 0

ifelse 處于搜尋的初始階段

if not Voronoi圖劃定的子區域范圍

動態調整適應度函數中距離的權重系數a

end if

ask 一部分適應度差的粒子die

ask 全局最優值所在點產生相應數量的粒子

end if

if 搜尋到的當前點有乘客 and not 通信列表中其他PRT已確定的目標乘客

計算其適應度

if適應度優于粒子局部最優值

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

end if

ask粒子群中適應度最優的粒子

if適應度優于全局最優值

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

end if

ask每個粒子

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

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

end if

end while

ask 所有粒子 die

4 仿真結果分析

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

4.1 靜態任務分配

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

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

4.2 動態任務分配

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

表3 模型主要參數、參考值及取值范圍

仿真環境的時間直接采用NetLogo內建的時鐘計數ticks，為方便結果統計，實驗均運行3 000 ticks。隨機選取T=1 000 ticks和T=2 000 ticks時的關于乘客需求點的Voronoi圖如圖4和圖5所示。值得注意的是，NetLogo平臺拓撲允許回繞，即智能體可以從邊界出現在另一邊。因此從圖上可以看出，回繞距離更短時，Voronoi圖采用的是回繞距離。

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

表4 里程利用率

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

5 結束語

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

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