劉鵬杰，鄭亮

(中南大學(xué) 交通運輸工程學(xué)院，湖南 長沙 410075)

公交出行作為城市居民最重要的出行方式之一，是推動交通可持續(xù)發(fā)展、維系城市快速運轉(zhuǎn)的重要基礎(chǔ)與支撐。然而，日益增長的公交出行需求和逐漸惡化的交通環(huán)境同落后的公交運營產(chǎn)生了矛盾，嚴(yán)重制約了城市交通健康穩(wěn)定發(fā)展。因此，如何通過有效的管理提升公交系統(tǒng)的服務(wù)水平成為了迫切需要解決的問題。公交規(guī)劃與運營主要包括線網(wǎng)設(shè)計、時刻表編制、車輛調(diào)度、人員排班4個部分[1]。其中，時刻表作為公交企業(yè)與出行乘客之間的溝通橋梁，提供了公交在特定站點(主要為始發(fā)站)的出發(fā)時間信息，在滿足乘客需求、增強公交可靠性等方面起著至關(guān)重要的作用?？煽康臅r刻表不僅能夠滿足時空不均勻的乘客需求、適應(yīng)復(fù)雜的道路交通狀態(tài)，同時有助于減少乘客等待/出行時間、提升公交吸引力、緩解交通擁堵。因此如何編制科學(xué)的時刻表成為解決公交運營問題的重點。在以往的研究中，以乘客需求為導(dǎo)向設(shè)計公交時刻表主要分為均勻發(fā)車間隔和均衡載客量2種方法[2]。均勻發(fā)車間隔是指相鄰兩班次公交駛離始發(fā)站的時間間隔相同，旨在提供規(guī)則有序的服務(wù)，乘客只需了解發(fā)車時間間隔無需知曉精確的時刻表[3]。目前，均勻發(fā)車間隔的時刻表設(shè)計通常根據(jù)乘客需求首先將公交運營時間分為若干個時間段，而后綜合考慮運營成本、服務(wù)水平等因素決定每個時間段內(nèi)固定的發(fā)車間隔或發(fā)車頻率[4]。CEDER[5]基于最大客流和斷面客流分別提出了2種確定發(fā)車間隔的經(jīng)驗公式法。考慮隨機的行程時間與乘客需求，HADAS等[6]在一個供應(yīng)鏈模型框架下以最小化空座率和過載成本為目標(biāo)提出了優(yōu)化發(fā)車頻率的新方法。另外，DONG等[7]通過對乘客需求及交通擁堵狀態(tài)進(jìn)行聚類分析，研究了交通擁堵狀態(tài)對公交運營產(chǎn)生的影響，并提出交通擁堵條件下發(fā)車間隔的設(shè)計方法和過渡模型。SHANG等[8]首先定義了乘客滿意度和公交運營效率的評價函數(shù)，而后以乘客滿意度為目標(biāo)設(shè)計了優(yōu)化發(fā)車頻率和車頭時距的初步方法，最后在負(fù)載約束下，提出了平衡乘客滿意度和公交運營效率的時刻表優(yōu)化方法。最近，為解決客流時空不均衡造成的供需不匹配問題，胡寶雨等[9]從公交企業(yè)與出行乘客兩方面考慮構(gòu)建了多車型的公交時刻表多目標(biāo)優(yōu)化模型，并引入圖論及最短路思想求解Pareto最優(yōu)解。采用均勻發(fā)車間隔設(shè)計時刻表普遍認(rèn)為乘客在單一時間段內(nèi)需求是固定的，并且乘客會依據(jù)給定的時刻表調(diào)整出行時間[1]。然而，乘客出行受土地性質(zhì)、人口密度、出行目的等因素的影響呈現(xiàn)出時空不均勻性，即使在短時間內(nèi)乘客需求、出行規(guī)律也會不斷變化[1]。因此，均勻發(fā)車間隔并不能很好地應(yīng)對時變的乘客需求，往往造成不均衡的載客量。與均勻發(fā)車間隔不同，均衡載客量希望公交運營達(dá)到最大客流時每輛公交上的乘客數(shù)相對均衡，意在減少乘客擁擠，滿足時空不均勻的乘客需求。以往對均衡載客量的時刻表研究較少，CEDER等[10]綜合利用不同的車隊規(guī)模和車輛類型進(jìn)行運力配置和發(fā)車時間調(diào)整，提出了均衡最大客流斷面載客量的時刻表，案例顯示，乘客等待時間降低了15%，小時空座數(shù)減少了47%。為最小化乘客等待時間以及最大化公交運載數(shù)量，LI等[11]構(gòu)建了考慮車輛超車、容量限制、乘客不確定選擇下改善發(fā)車間隔組合的時刻表非線性模型，并提出混合粒子群算法和遺傳算法進(jìn)行求解。針對以往研究在乘客分類和處理滯站乘客方面的不足，王洋等[12]通過量化服務(wù)指標(biāo)，組合車輛類型、發(fā)車模式、發(fā)車間隔構(gòu)建了時刻表優(yōu)化模型，提出了最大最小蟻群系統(tǒng)算法進(jìn)行求解。實驗表明，采用發(fā)車間隔不定的組合策略能夠均衡站點客流，降低乘客時間成本及車輛耗燃成本。雖然采用均衡載客量設(shè)計的時刻表能夠盡力滿足時空不均勻的乘客需求，但有效性過分依賴于乘客需求數(shù)據(jù)的質(zhì)量[13]。此外，不規(guī)律的發(fā)車不僅阻礙了公交企業(yè)與出行乘客之間有效的溝通，而且會使不同時間段的乘客產(chǎn)生嚴(yán)重的等待時間反差影響公交體驗。由此可見，均勻發(fā)車間隔和均衡載客量的時刻表各有利弊，存在沖突，且難以權(quán)衡。IBARRA-ROJA[14]研究指出，對均勻的發(fā)車間隔進(jìn)行微調(diào)并不會影響乘客對規(guī)則時刻表的感知。因此，如何在均勻發(fā)車間隔時刻表的基準(zhǔn)上進(jìn)行微調(diào)再編制，使其盡可能滿足時空不均勻的乘客需求成為研究的重點。此外，站間行程時間和站內(nèi)乘客需求等隨機因素往往造成公交系統(tǒng)復(fù)雜多變，使得現(xiàn)有的時刻表難以充分發(fā)揮效用。所以，考慮隨機本文首先將問題描述為隨機規(guī)劃模型。然后，在求解方面本文另辟蹊徑，采用Monte Carlo仿真刻畫隨機因素將隨機規(guī)劃模型轉(zhuǎn)化為隨機仿真優(yōu)化模型，并使用仿真優(yōu)化方法對問題進(jìn)行求解。一般地，仿真優(yōu)化方法主要包括3類：直接搜索法、隨機梯度法和代理模型法[15]。本文選擇運用最為廣泛的基于代理模型的仿真優(yōu)化方法，其核心思想是采用歷史仿真樣本信息建立目標(biāo)函數(shù)或約束條件的近似解析模型，然后采用傳統(tǒng)的優(yōu)化算子和代理模型更新機制進(jìn)行迭代尋優(yōu)[16]?；诖砟Ｐ偷慕?jīng)典仿真優(yōu)化算法可參考文獻(xiàn)[17]和[18]。與經(jīng)典的仿真優(yōu)化問題不同，本文聚焦于帶有隨機性的仿真優(yōu)化問題，研究能夠適應(yīng)隨機問題的仿真優(yōu)化算法。1) 為解決均勻發(fā)車間隔和均衡載客量時刻表之間的沖突，本文提出一種時刻表再編制方法。該方法不僅能夠在均勻發(fā)車間隔的基礎(chǔ)上盡可能均衡最大載客量，同時能夠減少乘客平均等待時間。2) 本文考慮了隨機的行程時間和乘客需求，使得再編制的時刻表能夠適應(yīng)復(fù)雜多變的公交系統(tǒng)。3) 針對難以求解的隨機規(guī)劃問題，本文從仿真優(yōu)化的角度出發(fā)，采用Monte Carlo仿真刻畫隨機因素將問題轉(zhuǎn)化為隨機仿真優(yōu)化問題，并通過改進(jìn)的仿真優(yōu)化算法進(jìn)行求解。

1 問題描述與符號說明

隨機環(huán)境下時刻表再編制問題可以描述為：在給定均勻發(fā)車間隔時刻表的基礎(chǔ)上，如何在小范圍內(nèi)對公交的發(fā)車時間進(jìn)行調(diào)整，使得公交服務(wù)能夠進(jìn)一步得到改善。此外，考慮了公交運營中行程時間和乘客需求的隨機性。具體而言，如圖1所示，設(shè)單一公交線路上有J個站點，公交從0時刻開始以固定的發(fā)車間隔T從始發(fā)站發(fā)車，共發(fā)出I輛車。實線刻畫了均勻發(fā)車間隔下公交的運動軌跡，其中每輛車在站間的行程時間和在站內(nèi)的服務(wù)時間都存在差異，分別代表行程時間和乘客需求的隨機性。虛線為發(fā)車時間調(diào)整后的公交運動軌跡，對于公交i，其調(diào)整發(fā)車時間的范圍為[xlbi,xubi]，調(diào)整值為xi。

圖1 時刻表再編制軌跡示意圖Fig.1 Trajectory diagram for timetable reprogramming

為將以上描述的隨機環(huán)境下時刻表再編制問題抽象成數(shù)學(xué)模型，本文參考以往研究建立如下假設(shè)：1) 站間的行程時間服從正態(tài)分布[13]。2) 站內(nèi)乘客需求服從泊松分布[19]。3) 每個站點的下車率固定，不隨時間發(fā)生變化。4) 公交行駛過程中不允許超車[19?20]。5) 不考慮不同車型的組合運營，即車輛容量一致[20]。相關(guān)符號說明如表1所示。

表1 符號說明Table 1 Symbol description

2 隨機仿真優(yōu)化模型

為使公交時刻表在隨機的站間行程時間和站內(nèi)乘客需求下提高公交系統(tǒng)服務(wù)水平，本節(jié)首先建立以最小化期望乘客平均等待時間和最小化期望公交最大載客量方差為目標(biāo)的隨機規(guī)劃模型，用于在均勻發(fā)車間隔的基礎(chǔ)上進(jìn)行再編制微調(diào)每輛車的發(fā)車時間。同時，針對難以求解的隨機規(guī)劃模型，本文通過Monte Carlo方法轉(zhuǎn)化為了隨機仿真優(yōu)化模型。

2.1 隨機規(guī)劃模型

2.1.1 目標(biāo)函數(shù)

該隨機規(guī)劃模型的目標(biāo)函數(shù)分為2部分：

1) 最小化期望乘客平均等待時間

乘客等待時間由3部分組成，(12)?P1,j?(T+x1)表示第1輛公交到達(dá)站點j時新產(chǎn)生乘客的等待時間，這里設(shè)新乘客是在T+x1時間段內(nèi)產(chǎn)生，且均勻到達(dá)。(12)?Pi,j?(Di.j-Di-1,j)表示公交i到達(dá)站點j時新產(chǎn)生乘客均勻到達(dá)的等待時間，即從Di-1,j(公交i-1離開站點j時間)到Di.j(公交i離開站點j時間)時間段內(nèi)產(chǎn)生的乘客。Pˉi,j?(Di.j-Di-1,j)表示公交i到達(dá)站點j時在站點j滯留乘客的額外等待時間。

2) 最小化期望公交最大載客量方差

公交最大載客量方差代表了每輛公交最擁擠時載客量之間的差異程度，反映了載客量的均衡性以及公交運營對乘客需求時空不均勻的適應(yīng)能力。

本文考慮采用加權(quán)的方式組合2個目標(biāo)，即

其中，w1和w2分別是目標(biāo)F1和F2的權(quán)重。

2.1.2 約束條件

約束條件描述了公交運行的整個過程，主要分為3部分：

1) 公交到站時間約束

式(4)計算了公交i在站點1的到達(dá)時間，由均勻的發(fā)車間隔和調(diào)整值而定；式(5)計算了公交i在除站點1以外其他站點的到達(dá)時間，其中行程時間ti,j服從正態(tài)分布；式(6)確保公交之間不發(fā)生超車行為；式(7)約束了決策變量xi的取值。

2) 公交離站時間約束

式(8)表示公交i在站點1的離開時間等于到達(dá)時間，即：在始發(fā)站不產(chǎn)生乘客；式(9)計算了公交i在除站點1以外其他站點的離開時間；式(10)同樣保證了不發(fā)生超車行為。

3) 公交乘客服務(wù)約束

式(11)定義了公交i在站點1時的車輛剩余容量、實際上車人數(shù)和下車人數(shù)；式(12)計算了車輛容量約束下公交i在除站點1以外其他站點的實際上車人數(shù)，其中乘客數(shù)Pi.j服從泊松分布(i=1時Pi.j在T+x1時間段內(nèi)產(chǎn)生；i≠1時Pi.j在Di.j-Di-1,j時間段內(nèi)產(chǎn)生)；式(13)通過下車率計算了公交i在除站點1以外其他站點的下車人數(shù)，并進(jìn)行向下取整；式(14)計算了公交i到達(dá)除站點1以外其他站點時的車輛剩余容量；式(15)設(shè)公交i到達(dá)站點1和公交1到達(dá)站點j時被滯留乘客數(shù)為0；式(16)計算了除公交1和站點1以外，公交i到達(dá)站點j時被滯留乘

其中，x=[x1,x2,…,xI]為決策變量，代表了所有公交發(fā)車時間的調(diào)整值；Ω為決策空間；w=[w1,w2]為2個目標(biāo)的權(quán)重向量；t={ti,j|i?{1 ,2,…,I},j? {2 ,3,…,J}}為Monte Carlo方法隨機采樣的行程時間集合；p={pi,j|i?{1 ,2,…,I},j?{ 2 ,3,…,J}}是Monte Carlo方法隨機采樣乘客數(shù)的集合；Φ(x,t,p)表示將x,t,p輸入仿真獲得的乘客平均等待時間與公交最大載客量方差加權(quán)和；Εw[Φ(x,t,p)]表示對于給定w，在隨機的t和p下目標(biāo)的仿真期望值。

此外，在給定的w下，只要對特定的x仿真的次數(shù)足夠多，目標(biāo)的期望值可以表示為：客數(shù)。

2.2 仿真優(yōu)化模型

上述模型中行程時間和乘客需求的隨機性使得問題難以求解。另外，簡單的數(shù)值運算也難以展現(xiàn)真實公交系統(tǒng)中復(fù)雜的隨機性對運營產(chǎn)生的影響。因此，基于上述隨機規(guī)劃模型本文采用Monte Carlo仿真的方法對行程時間和乘客需求進(jìn)行隨機采樣，構(gòu)建了隨機仿真優(yōu)化模型。描述如下：

其中，Kx表示對x仿真的總次數(shù)；tk和pk分別為第k次仿真時t和p的隨機值。

3 隨機仿真優(yōu)化算法

對于上述隨機仿真優(yōu)化模型，本文使用LI等[21]提出的基于克里金(KG)的多點填充采樣全局優(yōu)化算法進(jìn)行求解。該算法通過擴展JONES等[22]提出的期望改進(jìn)(EI)構(gòu)造了2個采樣函數(shù)，并通過求解最小化采樣函數(shù)的多目標(biāo)優(yōu)化問題獲得多個具有潛力的樣本。實驗表明，該算法能夠在消耗較少仿真資源的情況下獲得滿意解。此外，本文使用了隨機克里金[23](SKG)代替KG以抹平仿真中的隨機噪聲，具體流程如圖2所示。

圖2 基于SKG的多點填充采樣全局優(yōu)化算法流程圖Fig.2 Flow chart of global optimization algorithm for multi-point filling sampling based on SKG

算法應(yīng)用步驟如下。

1) 參數(shù)設(shè)置：需設(shè)置的主要參數(shù)有權(quán)重向量w，仿真總數(shù)Z，每個方案的仿真次數(shù)K，初始采樣數(shù)G，每次迭代得到的潛力樣本數(shù)L等。

2) 初始采樣：使用拉丁超立方抽樣法生成G個時刻表調(diào)整方案x，并放入樣本集合S。

3) 仿真評價：對集合S中未評價過的樣本x#仿真K次，計算目標(biāo)期望和方差。若仿真次數(shù)Z耗盡，則算法結(jié)束，輸出當(dāng)前最佳時刻表調(diào)整方案x*。

4) 建立代理模型：使用SKG擬合樣本集合S中方案x與([x],[x])之間的關(guān)系。

6) 獲得候選潛力樣本：基于SKG使用MOEA/D算法求解最小化2個采樣函數(shù)的多目標(biāo)優(yōu)化問題獲得多個潛力樣本。

7) 篩選候選潛力樣本：利用SKG預(yù)測值和空間相關(guān)性對多個候選潛力樣本進(jìn)行篩選獲得L個潛在樣本，并加入樣本集合S，返回到步驟3。

4 實驗分析

4.1 場景及參數(shù)設(shè)置

為驗證模型的有效性，增加方法的可信程度，本文以深圳市331路公交(上行)為例構(gòu)建仿真系統(tǒng)。為不失一般性，選取高峰(7∶00～8∶00)和平峰(6∶00～7∶00和8∶00～9∶00)3 h作為研究時段，其間共發(fā)車24輛(即：I=24，T=7.5 min)。根據(jù)統(tǒng)計數(shù)據(jù)，選取25個關(guān)鍵站點(即：J=25)作為研究對象，其隨機行程時間的正態(tài)分布參數(shù)、隨機乘客需求的泊松分布參數(shù)及站點的下車率如表2所示。其他公交系統(tǒng)參數(shù)設(shè)為：C=70[19]，ta=1.2 s，tb=1.5 s，toc=3.5 s[24]。算法相關(guān)參數(shù)設(shè)為：Z=4 000，K=20，G=50，L=5，其中Z受限于時長，Z越大算法計算時間越長尋優(yōu)次數(shù)越多；K取決于仿真的隨機程度，隨機程度越大樣本所需評價次數(shù)越多；G值決定了初始SKG對仿真的代理精度，進(jìn)而影響尋優(yōu)；L由候選潛力樣本的質(zhì)量而定。

表2 隨機參數(shù)設(shè)置Table 2 Random parameter setting

4.2 實驗結(jié)果

首先對均勻發(fā)車間隔(調(diào)整前)時刻表進(jìn)行大量仿真實驗，分別計算了高峰、低峰和全程乘客平均等待時間期望E高(F1)=278.59，E低(F1)=238.72和E(F1)=256.72，以及分別計算了高峰、低峰和全程公交最大載客量方差期望E高(F2)=98.67，E低(F2)=38.45和E(F2)=115.85。而后，考慮對均勻發(fā)車間隔進(jìn)行微調(diào)，設(shè)調(diào)整范圍系數(shù)α=0.2，并將權(quán)重分為11組，使用上述算法求解每組加權(quán)目標(biāo)的最小期望值，得到實驗結(jié)果如表3所示。

表3 實驗結(jié)果Table 3 Experimental results

從數(shù)值上進(jìn)行對比，調(diào)整后的時刻表在總目標(biāo)上都優(yōu)于調(diào)整前的時刻表，且在各組權(quán)重下最多能改進(jìn)29.68%，最少也能優(yōu)化8.38%。然而，對比高峰和平峰改進(jìn)比發(fā)現(xiàn)，高峰得到了更大的改進(jìn)，且為了最小化總目標(biāo)，平峰時的平均等待時間和公交最大載客量方差甚至可能會增大。其次，通過比較調(diào)整前后目標(biāo)值的增減情況看出，在均勻發(fā)車的基礎(chǔ)上對時刻表進(jìn)行微調(diào)可以同時減少乘客平均等待時間和均衡最大載客量，體現(xiàn)了2個目標(biāo)優(yōu)化方向的一致性。此外，比較目標(biāo)F1和F2的期望隨權(quán)重不同的變化趨勢發(fā)現(xiàn)，乘客平均等待時間和均衡載客量在一定程度上存在沖突。

4.3 參數(shù)α靈敏度分析

為探究發(fā)車時間調(diào)整范圍對目標(biāo)值的影響，本節(jié)在w1=0.0，w2=1.0和w1=1.0，w2=0.0權(quán)重設(shè)置下對參數(shù)α進(jìn)行了靈敏度分析，結(jié)果如圖3所示。當(dāng)w1=0.0，w2=1.0時，隨著參數(shù)α增大(即：發(fā)車時間調(diào)整范圍擴大)，E(F2)一直下降且下降幅度逐漸減緩，而E(F1)在α=[0,0.25]區(qū)間下降卻在α=[0.25,0.5]區(qū)間上升，說明F1和F2在α=[0.25,0.5]區(qū)間存在明顯沖突，為滿足均衡載客量犧牲了平均等待時間。當(dāng)w1=1.0，w2=0.0時，隨著參數(shù)α增大，E(F1)在α=[0,0.2]區(qū)間保持下降，并在α=0.2處達(dá)到平衡，持續(xù)增大α并不能改善乘客平均等待時間。此外，E(F2)的變化同樣驗證了目標(biāo)之間的沖突。

圖3 不同α下目標(biāo)期望值的變化Fig.3 Change of target expected value under different α

5 結(jié)論

1) 實驗數(shù)據(jù)表明，對均勻發(fā)車間隔進(jìn)行微調(diào)能夠同時減少乘客平均等待時間和均衡最大載客量，且在不同權(quán)重組合下總目標(biāo)至少能改進(jìn)8.38%，最多能改進(jìn)達(dá)29.68%。

2) 相比于平峰，高峰得到了更大的改進(jìn)，且為了最小化總目標(biāo)，平峰時的平均等待時間和公交最大載客量方差甚至可能會增大。

3) 乘客平均等待時間和均衡載客量雖然能夠得到同時優(yōu)化，但在一定程度上存在沖突，特別是當(dāng)調(diào)整范圍系數(shù)擴大時，兩者的沖突關(guān)系越加明顯。

4) 基于SKG的多點填充采樣全局優(yōu)化算法能夠在消耗較少仿真資源的情況下解決具有隨機的仿真優(yōu)化問題，并獲得滿意解。