基于時空等待特征系數(shù)的大型活動出行規(guī)劃研究

胡臣杰，張軍

(1.北京航空航天大學，電子信息工程學院，北京100191；2.阿里云計算有限公司，杭州310024；3.北京理工大學，前沿交叉科學研究院，北京100081)

0 引言

近年來，隨著綜合國力和國際影響力的穩(wěn)步提升，我國承辦國際大型活動的次數(shù)顯著增加。大型活動吸引大規(guī)?？土鲙砭薮蠼?jīng)濟收益的同時，也給城市路網(wǎng)帶來了巨大的壓力，影響人們?nèi)粘５纳畛鲂?。大型活動中不同角色的活動參與者在交通出行模式上存在多維度的差異，其中，觀眾群體以其數(shù)量眾多、來源地廣泛分散、可選交通方式多樣等特點引起活動組織方與交通部門的關注。為廣大活動參與者提供合理、安全、高效的多模式交通出行路徑規(guī)劃方案是維護大型活動交通秩序和為公眾提供高質(zhì)量交通服務的重要保障。

國內(nèi)外學者針對大型活動交通組織管理，乘客多模式出行規(guī)劃及誘導等方面發(fā)表了相關研究。葉霞等[1]從人流預測的角度提出大型活動散場時的人群疏散模型，并基于調(diào)度優(yōu)化算法求解疏散方案，提高人群疏散效率。GOERIGK 等[2]考慮觀眾乘坐巴士進行疏散，有效處理不同規(guī)模的疏散問題。CORDEAU等[3]提出變體禁忌搜索算法求解大型活動中車輛路徑優(yōu)化問題。在多模式出行規(guī)劃相關研究中，研究者依據(jù)場景特征提出多種模型。LOZANO 等[4]提出多模態(tài)超圖和可行超路徑的概念，定義了多模式交通網(wǎng)絡中的最短可行超路徑問題。佟路[5]等研究基于時空可達性的網(wǎng)絡設計問題，提出基于時空網(wǎng)絡模型和拉格朗日分解的公共交通路徑規(guī)劃方法。李浩楠[6]將馬爾可夫決策過程引入多模式交通網(wǎng)絡路徑規(guī)劃建模中。針對大城市多模式交通出行中的乘客換乘與非線性票價因素，LO 等[7]提出狀態(tài)增強多模式網(wǎng)絡，并與嵌套Logit 方法集成，通過案例研究票價競爭對公司盈利能力與網(wǎng)絡擁堵的影響。FU 等[8]在多模式交通網(wǎng)絡中引入一種新的基于活動的時空可達性度量指標，建立雙層規(guī)劃模型并設計人工蜂群算法，優(yōu)化公共交通線路的車頭時距與票價。在考慮誘導信息的出行問題研究方面，基于對交通網(wǎng)絡中出行者選擇行為的分析，韓凌輝[9]將出行信息誘導與基礎路網(wǎng)的連續(xù)網(wǎng)絡設計結合，設計了一種交通管理方法。更進一步，宋翠穎等[10]提出基于智能手機車內(nèi)擁擠信息的乘客公交路徑選擇模型，考慮乘客獲得擁擠信息后出行與換乘的策略調(diào)整，為智能化交通出行選擇提供有效方案。SONG等[11]結合乘客對出行時間、換乘時間和等待時間的不同偏好，探究乘客獲得智能手機實時交通信息對節(jié)約出行成本和公共交通線路負荷的影響。ABANE[12]調(diào)查斯里蘭卡部分居民的出行行為，通過定量研究，得出家庭收入、出行安全及舒適度等因素會影響出行者的出行行為?；诠步煌ňW(wǎng)絡的特點，吳震宇[13]對出行者路徑選擇模型進行數(shù)學描述，并設置廣義出行費用函數(shù)，引導出行者的路徑選擇。

已有研究少有針對大型活動中觀眾群體的公共交通路徑規(guī)劃，涉及群眾出行路徑規(guī)劃的研究也極少考慮乘客的個體出行偏好。鑒于大型活動規(guī)模不斷增加與乘客出行選擇日趨多樣的現(xiàn)狀，綜合考慮上述因素以保障大型活動的舉辦亟待研究。本文提出面向乘客出行偏好的時空等待特征系數(shù)，建立基于時間-空間-交通方式網(wǎng)絡的多模式交通路徑規(guī)劃模型，以乘客出行時間成本最小為目標函數(shù)。在此基礎上，提出基于拉格朗日松弛的次梯度下降算法進行求解，從而為出行者提供個性化出行規(guī)劃方案。

1 面向乘客偏好的時空等待特征系數(shù)

出行前，乘客將根據(jù)出行目的與個人偏好計算備選路徑的成本，比較并選擇最佳出行方案。在眾多出行成本的計算方式中，出行時間是不可忽視的關鍵因素。出行時間包括：行程時間、換乘時間和等待時間。其中，行程時間指乘坐交通工具時間，換乘時間指乘客在站點內(nèi)換乘不同交通方式的時間，等待時間指從抵達站點到乘坐交通工具等待所需時間。出行過程中行程時間及換乘時間通過出行路線確定，而等待時間因乘客不同選擇而不同?？臻g上相同的出行路徑，不同乘客可在同一站點等待不同的時間以乘坐不同車次的車輛。經(jīng)調(diào)研分析發(fā)現(xiàn)，等待時乘客考慮的主要因素為舒適度及交通方式的可靠性[13]。其中，舒適度由等待場所的基礎設施建設程度及交通擁擠程度決定，交通方式的可靠性受車輛到站的準點程度和車次間隔的均勻程度等影響。本文對于每個等待場所的3 個指標均采用5 等級李克特量表進行量化。基建程度F的取值為1.00，0.50，0.30，0.25，0.20，值越低，基建程度越低；擁擠程度S的取值為1，2，3，4，5，值越高，擁擠程度越高；交通工具可靠性R的取值為1.00，0.50，0.30，0.25，0.20，值越低，可靠性越低。本文提出基于乘客偏好的時空等待特征系數(shù)，表達乘客對出行過程中某個地點對影響等待決策的不同因素的關注程度。進行等待成本計算時，為等待場所的基建程度F、擁擠程度S及交通工具可靠性R等因素加個體偏好系數(shù)θ，不同的出行者，偏好系數(shù)θ不相同，但同一名乘客的所有時空等待特征系數(shù)θ之和為1。面向個體出行偏好的等待成本公式為

式中：Cpv為乘客p在節(jié)點v處的等待成本；tpv為乘客p在節(jié)點v處的等待時間；Fv、Sv、Rv分別為節(jié)點v處基建程度、擁擠程度及交通工具可靠性，基建程度越高，擁擠程度越低，交通方式可靠性越高，等待成本越低；為乘客p對不同因素的關注程度，。

是否考慮乘客出行偏好的不同等待成本如圖1所示。以某乘客為例，圖1(a)實線表示在不同節(jié)點處設置不同等待成本；虛線表示不進行區(qū)分。其中，v1、v2、v3和v4分別表示不同的等待地點，c1、c2、c3和c4表示乘客在對應地點的等待成本。圖1(b)表示對不同節(jié)點處的等待成本加以區(qū)分時，若等待總時間相同，在各點處的等待時間分配將影響出行過程中的累積等待成本。圖1 中，T1、T2、T3和T4分別表示不同的等待時間，和表示考慮出行偏好后乘客等待不同時間的累計等待成本。因此，引入面向乘客出行偏好的時空等待特征系數(shù)將影響乘客的時空出行路徑。

圖1 考慮乘客出行偏好的等待成本示意Fig.1 Schematic diagram of waiting costs considering passenger travel preferences

2 基于時空等待特征系數(shù)的公共交通出行路徑規(guī)劃問題建模

2.1 問題描述及相關假設

固定的運行線路與周期性運行時刻表組成了單一公共交通方式的運行方案。運行方案可以通過公共交通時空網(wǎng)絡進行建模。其中，空間維度包含站點位置與運行線路，時間維度包含車輛在站點間的行駛時間和在站點的停車時間。乘客出行過程可以抽象為點在網(wǎng)絡中通過時空弧的移動。公共交通時空網(wǎng)絡如圖2所示。

圖2 公共交通時空網(wǎng)絡Fig.2 Time-space operation diagram of public transportation

實際中，單一公共交通出行往往不能滿足觀眾參與大型活動的交通需求，觀眾基于經(jīng)濟性、時效性、舒適性等多方面考慮，通常會選擇綜合公共交通方式組合的出行路徑。本文將交通方式設置為新的維度，建立時間-空間-交通方式網(wǎng)絡。

2.2 時間-空間-交通方式網(wǎng)絡

以觀眾參與冬奧會為例，建立的網(wǎng)絡如圖3所示，其中，橫軸表示時間，縱軸表示位置，豎軸表示交通方式。此外，由于不同的交通方式具有不同且固定的運行計劃，因此，在時間-空間平面，每一層具有不同的網(wǎng)絡結構。同時，由于不同交通方式的換乘僅在某些站點可以實現(xiàn)，所建立的空間-交通方式平面的網(wǎng)絡邊應與實際情況保持一致。圖3中，實線為觀眾的出行路徑；虛線為出行路徑在空間-交通方式平面的投影，表示換乘路線；點劃線為觀眾位移軌跡。

圖3 時間-空間-交通方式網(wǎng)絡[5]Fig.3 Time-space-transport mode network diagram

2.3 時間-空間-交通方式網(wǎng)絡設計步驟

2.3.1 構建時空點集合

將一維空間點集N、離散時間點集T、備選交通方式集合M做笛卡爾積，生成時間-空間- 交通方式網(wǎng)絡點集：V=N×T×M=。

2.3.2 構建時空弧集合

時空旅行?。簩?a∈M，根據(jù)對應交通方式運行規(guī)劃，在相鄰到達的時空點對與間建立時空旅行弧，并將其添加至時空旅行弧集合E。

時空換乘?。喝裟滁c同時有兩種或以上的交通方式可通過，即存在時空點對和，則可在該時空點對間建立時空換乘弧，并將其添加至時空換乘弧集合C。

時空等待弧：對?i∈N,a∈M，用時空點對和表示乘客在原位置原交通方式處進行等待，因此，可在時空點對間建立時空等待弧，并將其添加至時空等待弧集合W。

2.3.3 設置時空弧對應成本

2.4 模型建立

2.4.1 目標函數(shù)

模型的目標函數(shù)為所有乘客的出行時間成本之和最小。出行成本包含3 部分：旅行成本、換乘成本和等待成本，模型的目標函數(shù)為

2.4.2 出發(fā)地約束

保證任意乘客p從出發(fā)地前往確定的出發(fā)站點，乘坐公共交通工具完成出行的約束為

式中：φ(O)(p)為符合乘客p出發(fā)地設置的可出行線路集合。

2.4.3 車輛滿載率約束

考慮不同交通方式具有不同承載能力，使得選擇相同時空旅行弧出行的乘客數(shù)不超過對應最大承載率H(Cap)(a)。此外，基于常態(tài)化疫情防控措施，應適當下調(diào)滿載率以保證合適的社交間隔，設修正因子為α，則實際車輛滿載率為α·H(Cap)(a)。車輛滿載率約束為

2.4.4 時空網(wǎng)絡流平衡約束

網(wǎng)絡流模型中基本的流平衡約束是保證每個時空點的流量平衡，即

式中：對于乘客p，O(G)(p)、D(G)(p)分別為出發(fā)地與目的地；O(T)(p)、D(T)(p)分別為最早出發(fā)時間與最晚到達時間；O(M)(p)、D(M)(p)分別為出發(fā)及到達時所使用的交通工具。

2.4.5 決策變量約束

保證決策變量xi,j,t,s,a,b(p)的取值為0或1，即

3 基于時空等待特征系數(shù)的多模式出行路徑規(guī)劃模型求解算法

時空網(wǎng)絡特征系數(shù)具有降低建模難度，減少復雜約束及增加模型理解性的優(yōu)勢，但將模型應用于真實數(shù)據(jù)集時，求解速度慢仍是難以忽視的難題。因此，本文提出一種基于拉格朗日松弛的優(yōu)化算法。

3.1 基于拉格朗日松弛的時空網(wǎng)絡多模式出行路徑規(guī)劃求解

針對所提出的模型，本文對所有約束中最為復雜的車輛滿載率約束使用拉格朗日松弛理論進行松弛，最大程度簡化問題。設拉格朗日乘子λi,j,t,s,a≥0，得到對偶函數(shù)為

對應的，得到對偶問題為

約束條件為式(3)、式(5)及式(6)。ZLR(λ)的解為原問題解的下界，本文采用次梯度優(yōu)化算法求解提出的對偶問題。

3.2 次梯度優(yōu)化算法設計

次梯度優(yōu)化算法通過計算次梯度更新拉格朗日乘子，迭代求解對偶問題。次梯度優(yōu)化算法流程如下：

Step 1 初始化

給定循環(huán)次數(shù)限制m及提前終止閾值ε，初始化拉格朗日乘子λi,j,t,s,a,0。

Step 2 拉格朗日對偶問題求解

Step 2.1 將乘子的值代入松弛子問題進行求解，得到當前步最優(yōu)解xi,j,t,s,a,b(p)。

Step 2.2 將變量xi,j,t,s,a,b(p)的值代入對偶問題ZLD，求出最優(yōu)解的下界。

Step 2.3 檢驗解是否滿足原問題約束式(4)，若滿足，說明當前解為原問題可行解，亦為最優(yōu)解，算法終止；若不滿足，采用貪婪算法將不滿足原問題約束條件的解的相關部分進行可行化處理，得到最優(yōu)解的上界。

Step 3 拉格朗日乘子更新

Step 4 終止條件檢驗

Step 4.2 判斷迭代次數(shù)是否超過m，若超過，中止算法；否則，返回Step 2。

4 數(shù)值實驗及分析

4.1 參數(shù)設置

為驗證模型正確性與算法有效性，本文以2022年冬奧會為背景進行算例實驗。假設觀眾參與觀看國家高山滑雪中心某日11:00 的比賽，以北京市內(nèi)10 個地鐵站為開始交通節(jié)點，觀眾從市內(nèi)乘坐京張高鐵前往延慶賽區(qū)，延慶賽區(qū)內(nèi)設有2個班車服務點，觀眾通過乘坐班車從高鐵站到達比賽場館。實際交通網(wǎng)絡如圖4所示。

圖4 實際交通網(wǎng)絡Fig.4 Actual transportation network diagram

本文統(tǒng)計了不同交通方式的出行時刻表。

(1)地鐵時刻表

13 個地鐵站相鄰站點間運行時間及高峰期發(fā)車間隔如表1所示。

表1 地鐵發(fā)車時刻表Table 1 Subway departure timetable

(2)高鐵時刻表

前往觀賽的觀眾可以乘坐京張高鐵從北京市區(qū)抵達延慶賽區(qū)，符合出行需求的高鐵班次為：6:00 從清河站出發(fā)，于6:26 抵達延慶站的G8881次高鐵；8:51 從北京北站出發(fā)，9:06 途徑清河站，并于9:37 到達延慶站的G8883 次高鐵。觀眾可根據(jù)出行需求選擇出發(fā)高鐵站。

(3)班車時刻表

從延慶高鐵站至國家高山滑雪中心賽區(qū)班車頻次設置為5 min·班-1，每趟的行程時間為35 min。

(4)換乘時間設置

實驗中將地鐵換乘高鐵的時間設置為30 min；高鐵換乘班車的時間設置為15 min。

(5)面向乘客出行偏好的等待成本設置

由于每位乘客對等待時各種因素的敏感性不同，因此，為每個個體隨機生成3個取值均在0～1間的偏好系數(shù)θ1、θ2、θ3，并將其進行歸一化處理。然后為乘客出行的不同節(jié)點設置基礎設施建設程度值Fv、擁擠程度Sv以及交通工具可靠性Rv。不同節(jié)點情況不同：①乘客在出發(fā)地等待舒適度高，擁擠程度低，基建程度及可靠性都極高；②地鐵站因舉辦大型活動發(fā)生擁擠，但班次間隔小，有較高的可靠性；③高鐵站基礎設施較好，且實名制購票使得可靠性較高，但仍可能發(fā)生擁擠；④戶外班車站基建程度較低，大量觀眾排隊上車，可靠性差；⑤賽事場館，持票觀眾進入場館落座不存在擁擠狀況，且由于已經(jīng)抵達賽場，出行路徑已完成，故可靠性高。各類節(jié)點的取值如表2所示。

表2 不同節(jié)點的Fv、Sv、Rv 取值Table 2 Values of Fv,Sv,Rv for different nodes

(6)其他設置

對于不同交通方式，使用交通工具的容量也有所區(qū)別，本文根據(jù)實際情況按比例設置每種交通工具所能搭載的最大人數(shù)限制。

4.2 案例實驗結果分析

鑒于本文模型復雜、搜索空間龐大，規(guī)劃大規(guī)模觀眾路徑的求解效率較低，因此，提出了一種基于逆向推斷的搜索空間約減方法，即在進行案例實驗時基于所考慮場景的特點，通過倒推的方式對搜索空間進行約減。在本文的設置下，若觀眾欲觀看11:00的比賽，據(jù)京張高鐵現(xiàn)行運行時刻表倒推，得出此名觀眾需8:51 從北京北站或9:06 從清河站乘坐G8883次高鐵抵達延慶站，并推斷乘客應在7:30-8:30區(qū)間乘坐地鐵出發(fā)，在9:37高鐵到達延慶站后換乘班車，抵達高山滑雪中心。經(jīng)統(tǒng)計，使用該種約減方法，在本文設置的算例中可將所有乘客待選時空弧由1293500條減少為530000條，節(jié)約了59.03%的搜索空間，大幅提高了搜索效率。

本算例通過通用代數(shù)建模系統(tǒng)(General Algebraic Modeling System,GAMS)在乘客規(guī)模為100 的數(shù)據(jù)集上進行建模和求解，實驗所用計算機性能為：Intel Xeon E3-1505M v5@2.80 GHz CPU和16 GB RAM。

實驗結果中某乘客具體的出行方案如表3所示。第1、第2 列給出該名乘客從出發(fā)地到達比賽場館的路徑與交通方式。后兩列分別給出是否考慮出行偏好時在各點所需的出行、等待時間。對比兩種不同的出行方案，可以驗證引入時空等待特征系數(shù)后，乘客可以獲得更為靈活、人性化的出行方案。

表3 觀眾出行時空路徑列表Table 3 List of time and space paths for visitors to travel

測試過程中解的迭代過程可以進一步分析提出算法的性能。梯度優(yōu)化迭代結果如圖5所示。

圖5 次梯度優(yōu)化迭代結果Fig.5 Graph of sub-gradient optimization iteration results

圖5 中精確解為通過求解器進行長時間計算所得。由圖5可知，本文所提出的算法具有較好的收斂性與收斂速度，可以快速且高質(zhì)量的得到一定規(guī)模觀眾群體的出行路徑方案。

此外，為展現(xiàn)引入時空等待特征系數(shù)后對觀眾等待時間的影響，本文統(tǒng)計了引入時空等待特征系數(shù)前、后不同節(jié)點的人均等待時間，如表4所示。

表4 時空等待特征系數(shù)對人均等待時間影響Table 4 Influence of time-space waiting theory on average waiting time

引入時空等待特征系數(shù)后，觀眾更傾向于推遲出發(fā)及提前到達，以避開較為擁擠的換乘站點，因此，行程中的總等待時間由34.50 min 變?yōu)?.42 min，大幅下降。由于對觀眾出行路徑進行了統(tǒng)籌規(guī)劃，一定程度上緩解了公共交通的運行壓力，減輕了大型活動期間交通路網(wǎng)的擁堵狀況。

5 結論

本文提出基于時空等待特征系數(shù)的大型活動綜合公共交通出行規(guī)劃模型，通過數(shù)值實驗得到相較于忽視出行偏好的情況，本文提出的模型得到更合理的出行路徑規(guī)劃方案，避免所規(guī)劃的時空路徑使得乘客在擁堵的地鐵站和班車站點進行換乘等待。同時，通過個人的合理路徑規(guī)劃方案，也能減輕大型活動舉辦期間的路網(wǎng)擁堵情況。