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

王志利，張昕明

(1.山西省城鄉(xiāng)規(guī)劃設(shè)計研究院工程設(shè)計中心，太原 030001；2.青島海信網(wǎng)絡(luò)科技股份有限公司，山東 青島 266000)

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

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

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

1 問題描述

1.1 公交網(wǎng)絡(luò)

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

圖1 公交網(wǎng)絡(luò)
Fig.1 Public transport network

1.2 符號定義

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

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

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

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

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

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

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

Mk(t1,t2)——在(t1,t2)時段內(nèi)已經(jīng)到達站點k的乘客的數(shù)量；

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

1.3 目標函數(shù)

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

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

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

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

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

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

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

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

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

其中NP為所有乘客的總數(shù)。

2 實時分布控制方法

2.1 結(jié)構(gòu)框架

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

圖2 多智能體系統(tǒng)結(jié)構(gòu)圖
Fig.2 Multi-agent system structure

2.2 協(xié)商機制

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

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

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

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

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

2.3 最優(yōu)化條件

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

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

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

圖3 最優(yōu)化條件
Fig.3 Optimal conditions

即最優(yōu)化的滯站時間滿足：

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

由此得到協(xié)商算法：

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 基本設(shè)置

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

3.2 策略設(shè)置

設(shè)置四種策略進行比較分析：

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

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

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

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

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

3.3 仿真結(jié)果

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

假設(shè)所有車輛在始發(fā)站處都按時出發(fā)，則在實施不同的控制策略的基礎(chǔ)上，相比于不實施策略(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：公交車輛在行駛過程中遇到計劃外的突發(fā)干擾，如站點需求激增、路段嚴重擁堵、道路交通事故等，導致車輛運行延誤較大，不能按既定時刻表發(fā)車。

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

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

其中NS為站點數(shù)，NB為車輛數(shù)。

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

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

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

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

得到滯站時間s為0.2.

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

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

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

4 結(jié) 論

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