高鐵快巴站點(diǎn)選址及動(dòng)態(tài)線路規(guī)劃研究

王瑜瓊

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

0 引言

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

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

1 問題描述

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

圖1 高鐵快巴線路圖

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

2 站點(diǎn)選址方法

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

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

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

2.2 考慮節(jié)點(diǎn)需求強(qiáng)度的改進(jìn)AP 聚類算法

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

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

3.1 基本假設(shè)

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

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

（2）乘客預(yù)約的上車地點(diǎn)為高鐵站，下車地點(diǎn)為合乘站點(diǎn)。

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

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

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

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

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

乘客在途時(shí)間成本如下：

乘客到達(dá)時(shí)間懲罰成本如下：

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

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

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

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

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

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

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

4 案例分析

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

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

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

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

圖3 笛卡爾坐標(biāo)系下需求位置散點(diǎn)圖

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

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

表1 合乘站點(diǎn)信息

圖4 聚類結(jié)果圖

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

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

表2 實(shí)時(shí)預(yù)約需求信息

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

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

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

表3 高鐵快巴線路信息

5 結(jié)語

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