基于多智能體協商的公交分布式滯站控制策略

王志利，張昕明

(1.山西省城鄉規劃設計研究院工程設計中心，太原 030001；2.青島海信網絡科技股份有限公司，山東 青島 266000)

優先發展公共交通，并不是只擴充公交車輛數，單方面增加供給，而應該根據公交需求，合理利用現有公交資源，實現公交均衡運量，提高公交運行準點率和滿載率?，F實公交車輛運行過程中，往往會出現“公交串車”的現象。這種現象主要由兩個原因引起：一是車輛在公交站點間行程時間的不穩定性；二是乘客需求的時變性。這些因素導致了公交車輛到站間時間間隔的不穩定，從而增加了乘客的平均等待時間。尤其是在公交需求量大、公交車輛經常超載的情況下，這種影響會更加明顯。

為避免公交串車現象，需要對公交車輛進行行車控制，常用的策略就是滯站策略[1]，可以分為兩類，一類是通過車輛滯站來匹配既定的運行時刻表，另一類是通過滯站均衡車輛到站時間間隔。Daganzo以盡可能保持公交車輛最快運營速度為出發點，提出了使車輛到站時間間隔近似均勻的自適應控制策略[2]?？刂撇呗曰谇败嚨膶崟r信息動態的決定車輛在滯站點的滯站時間。但其在交通干擾較大時，控制策略的效果并不能令人滿意。為了克服這個問題，Daganzo和Pilachowski又基于公交前后輛車的間距，提出了一種雙向合作的協同策略[3]。Bartholdi和Eisenstein則不以到站時間間隔均勻為目標，而是尋找能夠適應當前系統的最優的到站時間間隔[4]。滕靖、楊曉光以優化全線車輛加權離站車頭時距方差為目標，建立了基于APTS 條件下公交車輛單線路實時控制模型[5-6]。李細霞考慮了中途站點的車輛?？啃袨閷Τ丝秃蜍嚂r間的影響，建立了一種車輛?？靠刂颇Ｐ?，達到了均衡中途各站待運乘客的候車時間的目的[7]。董高成等針對快速公交系統車輛出現串車和大間隔對車輛延誤和乘客候車滿意度的影響較大的情況，提出了一種基于區段劃分的實時行車控制算法，為了進一步降低間隔不合理的情況，提出了對多線BRT匯入點的控制方法[8-9]。

本文構建了公交車分布式滯站控制的多智能體結構體系，結合邊際費用計算方法，基于多智能體協商機制，設計了基于智能體協商機制，分布式的公交行車滯站控制策略。

1 問題描述

1.1 公交網絡

本文以單向環路公交線路為例研究，如圖1所示，公交線路包含K個站點和N輛公交車。

圖1 公交網絡
Fig.1 Public transport network

1.2 符號定義

ai,k——車輛i到達站點k的時間；

di,k——車輛i在站點k的離站時間；

λk(t)——t時刻站點k處乘客到達率；

Bi,k——車輛i在站點k上車乘客數量；

Gi,k——車輛i在站點k下車乘客數量；

tm,k——乘客m到達站點k的時刻，m∈Pk(t1,t2)；

bm,k——乘客m在站點k處的上車的時刻，m∈Pk(t1,t2)；

Mk(t1,t2)——在(t1,t2)時段內已經到達站點k的乘客的數量；

Pk(t1,t2)——在(t1,t2)時段內已經到達站點k的乘客的集合。

1.3 目標函數

在公交出行中，由于天氣等因素，乘客在車外等待較車內等待更為不便，所以將乘客的等待費用分為車外的等待費用和車內的等待費用。

(1)車外等待費用WF，即乘客在車站等待公交車輛到來的費用，可由下式計算得到：

其中fF(t)為單個乘客車外等待的費用函數，fF(0)=0，當t≥0時，fF(t)≥0，t為乘客的等待時間。

(2)車內等待費用WN，即乘客在車內等待車輛出發時的費用，可由下式計算得到：

WNi,k=(Bi,k-1-Gi,k)·fN(di,k-ai,k)+

其中fN(t)為單個乘客車內等待的費用函數，fN(0)=0，當t≥0時，fN(t)≥0.

費用函數fF(t)和fN(t)的形式如下：

fF(t)=K1FtK2FeK3Ft,fN(t)=K1NtK2NeK3Nt，如果令K1F=K1N=K2F=K2N=1，K3F=K3N=0，則fF(t)=t,fN(t)=t.

模型的目標是使乘客的平均等待費用最小化，包括車外等待費用和車內等待費用，目標函數如下式：

其中NP為所有乘客的總數。

2 實時分布控制方法

2.1 結構框架

本文設計了分布控制的多智能體結構框架，如圖2所示，Stop Agent表征該站點的控制策略，并且儲存相鄰站點的信息。Bus Agent利用這些信息在不同的Stop Agent中進行協調，以達到最優方案。

圖2 多智能體系統結構圖
Fig.2 Multi-agent system structure

2.2 協商機制

本文設計了基于邊際費用計算的協商算法。滯站策略的實施會增加車內的等待費用，但由于時間間隔(di,k,di+1,k)的長度會逐漸的減小，相應的車外的等待費用也會降低。因此，當車內等待的邊際費用與預期的車外等待的邊際費用相等時，就會形成局部的最優化。

假設在t時刻，對車輛i和站點k協商。車內等待的邊際費用MNi,k(t)如下：

預期的車外等待的邊際費用MFi+1,k(t)則較為復雜。車外等待費用的期望E(WFi+1,k|t)如下所示，

其中，fai+1,k(y)是下一輛車到達時間的條件概率密度函數。則預期的車外等待的邊際費用為：

給定費用函數為fF(t)=fN(t)=t，則

2.3 最優化條件

上述協商機制只是最優化的必要條件，需要進行適當約束，使其成為最優化的充分條件，再此引入兩個引理，引理證明過程詳見文獻[9]：

引理1：若fN(t)為凸函數，則車內等待邊際費用函數MNi,k(t)對于t單調遞增。

由于滯站策略在減少車外等待時間的同時相應增加了車內的等待時間，故可以將車內等待時間的增加看作成本，車外等待時間的減少看作價格，則控制目標即為使利潤最大化。由引理1和引理2可知，當成本曲線和價格曲線斜率相等時，即為最優化，如圖3所示。

圖3 最優化條件
Fig.3 Optimal conditions

即最優化的滯站時間滿足：

MNi,k(di,k*)=MFi+1,k(di,k*)

由此得到協商算法：

Step1：在t0時刻，Bus Agent和Stop Agent分別計算他們的邊際費用MNi,k(t)和MFi+1,k(t)；

Step2：若MNi,k(t)≥MFi+1,k(t)，則不滯站；否則，滯站并更新時間，令t0=t0+Δt，回到Step 1.

3 仿真實驗

3.1 基本設置

設置包括10個站點、5輛車的公交線路，每個站點的乘客的到達率符合泊松分布，且到達率λ=1.0/min.每個站點乘客的下車率ρ=0.4，兩個站點之間的行程時間服從對數正態分布，期望TBS=5min，方差σ2=4，費用函數fF(t)=fN(t)=t.每個乘客的上車所用時間DW=0.05min.

3.2 策略設置

設置四種策略進行比較分析：

(1)無策略(No Wait)：對車輛不進行控制，沒有上車或下車人數時車輛即開出。

(2)基于車-車間隔的滯站策略(Headway-Based)：車輛在進站后進行滯站，目的是使該車輛與前、后同線路車輛時間間隔均勻。

(3)基于時刻表的滯站策略(Schedule-Based)：當車輛到站時間早于時刻表既定時間，則滯站以符合時刻表運行。

(4)基于邊際費用的協商滯站策略(Negotiate)：利用本文提出的算法進行滯站。

通常在制定公交時刻表的過程中，都會在到站時間上留有余地，即若兩站點間的行程時間為TBS，余留時間。

3.3 仿真結果

(1)情景1：公交車輛運行過程中未發生異常擾動，即交通狀況、站點需求都在預期內，公交車輛能夠按照既定時刻表按時發車，公交正常運行。

假設所有車輛在始發站處都按時出發，則在實施不同的控制策略的基礎上，相比于不實施策略(No Wait)而言，在不同的既定間隔的情況下，乘客等待時間的減少率如圖4所示。

圖4 不同既定間隔下的等待時間變化趨勢
Fig.4 The relationship of the waiting time versus different intervals

可知當既定間隔較小時(小于15 min)，Negotiate策略效果較好；當既定間隔在15～20 min之間時，三種策略的性能相當；而當既定間隔較大時(大于20 min時)，Schedule-Based策略的效果更為明顯。

(2)情景2：公交車輛在行駛過程中遇到計劃外的突發干擾，如站點需求激增、路段嚴重擁堵、道路交通事故等，導致車輛運行延誤較大，不能按既定時刻表發車。

由于車輛在行駛中的延誤，可能會導致始發站發車班次的延遲，設定既定間隔SH與其他參數之間的關系為：

SH=TBS(1+s)·NS/NB

其中NS為站點數，NB為車輛數。

不同的策略下既定間隔與乘客平均等待時間關系如圖5所示。

圖5 不同的策略下既定間隔與乘客平均等待時間關系
Fig.5 The relationship between the given intervals and average passenger waiting time with different strategies

由圖5可知，既定間隔在區間1和區間2時，No Wait和Schedule-based策略的平均等待時間隨滯站時間增大而減少，但變化趨勢不穩定，而Negotiate和Headway-based策略則表現穩定且平均等待時間均較小，這是因為Negotiate和Headway-based兩種策略并不依賴于固定的時刻表，具有自組織的能力；區間3內四種策略都較穩定，區間3為最佳的既定間隔；區間4內隨既定間隔的增大，平均等待時間遞增，可見既定間隔不宜超過區間3的范圍。由圖可知車輛的最佳時間間隔為12 min，由

SH=TBS(1+s)·NS/NB

得到滯站時間s為0.2.

為更深入對四種策略進行比較分析，研究四種策略下各站點到站時間間隔的變異系數及平均到站時間間隔。由圖6所示，Headway-based策略各站點到站時間間隔的變異系數最小，No Wait策略的變異系數最大，說明在不實施任何策略情況下車輛的到站間隔極不均勻；而由圖7所示，Headway-based策略雖然變異系數小，但是其平均到站時間間隔為13.5 min，為四種策略最大。綜合圖6和圖7，Negotiate策略均表現穩定，具有很好的魯棒性。

圖6 各站點到站時間間隔變異系數
Fig.6 Each site arrival time interval of coefficient of variation

圖7 各站點平均到站時間間隔
Fig.7 The average arrival time interval of each site

4 結 論

由于公交車輛在運行過程中經常受到外界干擾導致公交服務質量降低，乘客等待時間增加。本文根據車內、車外乘客的邊際等待費用，設計了Bus Agent和Stop Agent之間的協商算法，提出了公交車輛的分布式滯站控制策略，能夠通過對車輛的發車滯站控制，降低外界路況、需求等異常情況對公交運行的影響，提高公交服務的可靠性。仿真實驗表明本文提出的算法對于不同的車輛運行情景具有很好的魯棒性，能夠顯著降低乘客平均等待時間，提高公交服務質量。不過，由于乘客需求的時變特性難以準確把握，目前在公交運行中車輛的運力安排并不能與需求相匹配，存在運力不足或浪費的現象。今后的研究將重點解決乘客到達率不固定的情況，即不確定公交需求的情況下的車輛控制策略，以實現根據需求合理安排公交發車，實現公交資源優化配置，進一步提高服務水平和運營效率。