王瑜瓊

（鐵道黨校 經(jīng)濟學和企業(yè)管理教研部,北京 100088）

0 引言

為滿足旅客在高鐵站的接駁及疏散需求，增強高鐵站作為城市綜合交通樞紐的作用，高鐵快巴應運而生。高鐵快巴是以高鐵站為接駁站點，在常規(guī)公共交通運力不足的早晚出行高峰期和夜間運營，服務于選擇高鐵出行的人群的快速反應式公交[1]。

高鐵快巴是定制公交的一種模式，對高鐵快巴的系統(tǒng)設(shè)計規(guī)劃可借鑒定制公交的研究成果。在定制公交的站點選址研究中，溫東等[2]通過漁網(wǎng)與核密度分析實現(xiàn)熱點區(qū)域聚類分析及合乘站點分類；Kim 等[3]以乘客總出行距離最短為目標建立定制班車的站點選址模型，并兼顧每位乘客出行距離；Shaffiei 等[4]在常規(guī)的定制班車路徑規(guī)劃方法中引入時間成本的概念，靈活調(diào)整和增加站點。在定制公交線路規(guī)劃方法研究中，MUELAS 等[5]設(shè)計變領(lǐng)域搜索算法求解大規(guī)模定制出行的線路方案；ZHENG 等[6]為滿足高峰時段短時大規(guī)模客流，設(shè)計1 種接駁線路與主干線路銜接的多層次定制公交線路規(guī)劃方法；彭理群等[7]基于非勢能場的非參數(shù)強化學習算法進行跨區(qū)域定制公交路徑規(guī)劃；陳汐等[8]構(gòu)建了多區(qū)域運營模式的通勤定制公交線路規(guī)劃模型。在站點選址研究中，近鄰傳播（Affinity Propagation，AP）算法不易受到離群節(jié)點的干擾，AP 算法有較好的魯棒性?，F(xiàn)有AP 算法在研究站點選址時，僅考慮節(jié)點地址位置及相互關(guān)系，較少考慮節(jié)點需求強度對聚類的影響，該文使用考慮節(jié)點需求強度的改進AP 聚類算法進行站點選址研究。在此基礎(chǔ)上，以運營成本、乘客在途時間成本和乘客到達時間懲罰成本最小為目標，利用遺傳算法求解高鐵快巴的動態(tài)運營服務模式下的最優(yōu)線路。以北京南站至天通苑居住區(qū)域的高鐵快巴線路為案例，證明該方法的可行性與合理性。

1 問題描述

按照不同的線路類型和服務模式，高鐵快巴分為固定和動態(tài)兩類運營線路。固定線路是參照常規(guī)公交的運營方式；動態(tài)線路依托系統(tǒng)支持按照乘客需求動態(tài)響應乘客需求，自動規(guī)劃生成車輛行駛路徑，將具有相同出行方向的一部分高鐵旅客快速送達其目的地[9]。該文研究的對象為高鐵快巴動態(tài)運營線路，具有以下幾個特點：①線路在高鐵站與一定范圍內(nèi)的客流集中區(qū)域之間運行；②線路在非高鐵站一端的服務區(qū)域內(nèi)設(shè)置多個?？空?，中途不設(shè)站，快速直達；③根據(jù)乘客預約的地點和時間窗動態(tài)規(guī)劃車輛行駛路徑和時刻表。以夜間運行、從高鐵站發(fā)至居住區(qū)的高鐵快巴動態(tài)線路為例，其線路布局如圖1 所示。

圖1 高鐵快巴線路圖

該文借鑒國內(nèi)外學者對定制公交的系統(tǒng)設(shè)計規(guī)劃的框架與方法，在對高鐵快巴進行系統(tǒng)設(shè)計時采用2 階段方法：①站點選址階段；②線路規(guī)劃階段。

2 站點選址方法

2.1 經(jīng)典AP 聚類算法

AP 聚類算法的一般步驟如下[10]。

步驟2 吸引度和歸屬度計算見公式（3）~（4），初始狀態(tài)時 、取值為0。

2.2 考慮節(jié)點需求強度的改進AP 聚類算法

該文改進的AP 聚類算法的步驟與經(jīng)典AP 聚類算法相同，不同之處僅在相似度矩陣計算過程中加入需求強度調(diào)節(jié)因子，即用公式（7）替換公式（2），則表示節(jié)點與其他節(jié)點的相似度計算公式[11]如下：

3 動態(tài)線路規(guī)劃方法

3.1 基本假設(shè)

該文以夜間運行、從高鐵站發(fā)至居住區(qū)域的高鐵快巴動態(tài)線路為研究對象，作出如下假設(shè)。

（1）高鐵快巴從高鐵站出發(fā)，到達居住區(qū)域各合乘站點，最后到達居住區(qū)域內(nèi)的調(diào)度站；車輛勻速行駛，在每個站點停留時間相等。

（2）乘客預約的上車地點為高鐵站，下車地點為合乘站點。

（3）由于乘客期望盡早到達目的地，若車輛實際到達時間早于乘客期望達到時間，懲罰成本為0；否則，產(chǎn)生懲罰成本。

（4）提供一人一座的服務，不允許超載；有最大單程行駛距離限制。

3.2 動態(tài)線路規(guī)劃模型建立

（1）目標函數(shù)。以運營成本、乘客在途時間成本和乘客到達時間懲罰成本最小為目標，建立高鐵快巴動態(tài)線路規(guī)劃模型。運營成本如下：

式中，N——合乘站點集合；V——調(diào)度站集合；H——高鐵站集合；M—— 車輛集合；—— 車輛啟動成本（元/輛）；——車輛單位距離運輸成本（元/km）；dij——站點i和j間的行駛距離（km）；車輛m從站點i到站點j時，為1，否則為0。

乘客在途時間成本如下：

乘客到達時間懲罰成本如下：

綜上，動態(tài)線路規(guī)劃模型的目標函數(shù)如下：

（2）約束條件。車輛均從高鐵站出發(fā)，最終到達調(diào)度站，滿足以下約束：

乘車乘客不超過車輛座位數(shù)，滿足約束：

車輛的單程行駛距離不能超過最大行駛距離，滿足約束：

每組乘客由同一輛車提供服務，車輛?？空军c滿足乘客預約的合乘站點需求，車輛發(fā)車時間在乘客最早可接受服務時間之后，滿足以下約束：

3.3 基于遺傳算法的最優(yōu)路徑求解

該問題可轉(zhuǎn)化為旅行商（TSP）問題，即所有需求點僅被經(jīng)過一次且需求均被滿足的車輛路徑問題。在該文問題中同1 個站點存在不同組需求，因此將目的地為同1個站點的不同組需求進行拆分，生成相應的虛擬站點。采用經(jīng)典遺傳算法求解，通過初始化、適應度函數(shù)計算、遺傳操作等步驟求解最大進化代數(shù)內(nèi)的最優(yōu)結(jié)果。

4 案例分析

現(xiàn)計劃開通北京南站至天通苑居住區(qū)域的高鐵快巴，該線路在研究區(qū)域內(nèi)的起點和調(diào)度站位置如圖2 所示。研究區(qū)域被快速路立湯路隔開，有機動車通行路徑，并且有天橋和地下通道，由于乘客可能攜帶大件行李，所以不考慮乘客步行跨越立湯路的可能。將研究區(qū)域分為西部區(qū)域和東部區(qū)域，在2 個區(qū)域內(nèi)分別進行合乘站點聚類。

圖2 研究區(qū)域示意圖

4.1 合乘站點選址結(jié)果與分析

模擬研究區(qū)域內(nèi)乘客請求位置數(shù)為40，累計請求人數(shù)為218，請求站點分布的平面坐標圖下的散點圖如圖3所示。使用R2014a 版本的MATLAB 軟件編程求解。AP聚類算法參數(shù)設(shè)置如下：最大迭代次數(shù)為500，迭代不變次數(shù)為50，阻尼系數(shù)為0.5。

圖3 笛卡爾坐標系下需求位置散點圖

使用經(jīng)典AP 聚類方法對研究區(qū)域的請求站點進行聚類，運行10 次。結(jié)果表明每次運算的聚類結(jié)果均相同，得到7 個合乘站點，所有乘客平均步行距離為318.6 m，算法平均運算時間為0.60 s。

使用考慮節(jié)點需求強度的AP 聚類方法對研究區(qū)域的請求站點進行聚類，運行10 次。結(jié)果表明每次運算的聚類結(jié)果均相同，得到7 個合乘站點，聚類結(jié)果如表1所示。平面直角坐標系下的聚類圖如圖4 所示。模擬試驗中所有乘客平均步行距離為313.1 m，較經(jīng)典AP 聚類方法減小1.7%，聚類結(jié)果得到優(yōu)化。算法平均運算時間為0.61 s，較經(jīng)典AP 聚類算法的平均運算時間0.60 s 差別不大，求解速度快。

表1 合乘站點信息

圖4 聚類結(jié)果圖

4.2 線路規(guī)劃結(jié)果與分析

參考北京南站列車時刻表，模擬夜間時段16 組共22 個乘客的實時預約需求，需求信息見表2，高鐵快巴在北京南站的發(fā)車時間候選集為{22:40，22:50，23:00，23:10，23:20}。

表2 實時預約需求信息

模型參數(shù)取值如下：該文采用載客量為9 位的小型公交車，車輛座位數(shù)U=9 人/輛，經(jīng)估算車輛啟動成本c0=50 元/輛，車輛單位距離行駛成本c1=3 元/km；在天通苑區(qū)域內(nèi)車輛平均行駛速度為20 km/h，在城市快速路上車輛平均行駛速度為45 km/h；車輛單程在天通苑區(qū)域內(nèi)的最大行駛距離為5 km，則單程最大行駛距離D=35 km；車輛在每個站點停留時間為30 s；乘客單位時間成本f1=12 元/h，乘客到達時間懲罰單位時間成本f2=20 元/h。

遺傳算法參數(shù)取值如下：種群數(shù)100、最大進化代數(shù)200、交叉概率0.9、變異概率0.2。經(jīng)過算法運行，得到高鐵快巴線路3 條。算法在136 代完成收斂，算法求解時間為58.7 s，求解速度較快。高鐵快巴系統(tǒng)運營成本為454.7 元，人均運營成本為20.7 元；乘客在途時間成本為218.5 元，人均在途時間成本為9.9 元，人均在途時間為49.5 min；乘客到達時間懲罰成本為42.5 元，人均到達時間懲罰成本為1.9 元，人均到達時間晚于期望5.7 min。優(yōu)化結(jié)果較為合理。

3 條線路在研究區(qū)域內(nèi)的?？空军c數(shù)分別為4、3、4，線路信息如表3 所示。所有線路在研究區(qū)域內(nèi)的非直線系數(shù)平均為1.38、全程非直線系數(shù)平均為1.03、全程時間均在1 h 之內(nèi)，所有高鐵快巴車輛的平均滿載率為81.5%。

表3 高鐵快巴線路信息

5 結(jié)語

案例結(jié)果表明：改進的AP 聚類算法運算產(chǎn)生的合乘站點選址結(jié)果科學合理，乘客平均步行距離為313.1 m，較經(jīng)典AP 聚類方法減小1.7%；優(yōu)化得到的高鐵快巴線路的全程非直線系數(shù)平均為1.03、全程時間均在1 h 之內(nèi)，所有高鐵快巴車輛的平均滿載率為81.5%，人均到達時間晚于期望5.7 min。該文的動態(tài)線路規(guī)劃模型和遺傳算法可生成覆蓋合乘站點、降低成本和提高乘客時間窗滿意度的高鐵快巴動態(tài)線路。