基于混合需求的高鐵快巴動態(tài)線路規(guī)劃方法研究

王瑜瓊

摘要：為滿足旅客在高鐵站的接駁及疏散需求，增強高鐵站作為城市綜合交通樞紐的作用，建立基于提前預約和實時混合需求的高鐵快巴動態(tài)線路規(guī)劃模型。在運營開始前，基于提前預約需求，兼顧公交公司的運營成本和乘客出行時間成本，建立線路規(guī)劃模型；利用小生境技術對傳統(tǒng)遺傳算法進行改進，設計算法求解。運營開始后，允許實時需求插入既定路線，引入臨時站點，以最小化系統(tǒng)變動成本為目標，建立整數(shù)規(guī)劃模型決策動態(tài)線路規(guī)劃方案。應用本方法在北京市北太平莊街道區(qū)域隨機生成并求解30組需求算例。結(jié)果顯示，該模型可以在兩階段生成最優(yōu)的高鐵快巴線路方案滿足混合需求；與傳統(tǒng)遺傳算法相比，小生境遺傳算法有效避免了算法早熟，運算結(jié)果更優(yōu)，模型和算法具有可行性。

關鍵詞：高鐵快巴；混合需求；動態(tài)線路；臨時站點

中圖分類號：U491?? 文獻標志碼：A?? 文章編號：1002-4026（2024）01-0118-10

Dynamic route planning method for a high-speed rail feeder bus based on mixed demand

Abstract∶To meet the needs of passengers for connection and evacuation at high-speed rail stations and enhance the role of high-speed rail stations as urban comprehensive transportation hubs， a dynamic route planning model of a high-speed rail feeder bus is established based on mixed demand that includes reservation and real-time demands. Based on the reservation demand， considering the operation cost of a bus company as well as the travel time cost， the route planning model is established before the start of operation. An improved genetic algorithm was designed using niche methods to solve the problem. After the start of operation， real-time demand can be inserted into the established vehicle route with temporary stations. To realize a dynamic route planning scheme， an integer planning model is established to minimize the variable cost of the system. Using the proposed method，30 demand groups were randomly generated and solved in the Beitaipingzhuang street area， Beijing. Results show that the model can generate an optimal dynamic route planning scheme for a high-speed rail feeder bus in two periods to satisfy the mixed demand. Compared with traditional genetic algorithm， niche genetic algorithm can effectively avoid premature and obtain better results， thus confirming the feasibility of the proposed model and the niche genetic algorithm.

Key words∶high-speed rail feeder bus; mixed demand; dynamic route; temporary station

為提高高鐵站的城市綜合交通樞紐的地位，滿足旅客在高鐵站的接駁及疏散需求，出現(xiàn)了一種新型的城市公共交通運營模式——高鐵快巴。高鐵快巴是以高鐵站為接駁站點，采用站內(nèi)換乘的模式，在常規(guī)公共交通運力不足的早晚出行高峰期和夜間運營，服務于選擇高鐵出行的人群，是一種快速反應式公交[1]。

國內(nèi)學者對高鐵快巴的線路設計規(guī)劃、車輛調(diào)度等運營管理方法等進行了諸多研究。張英群等[2]提出了一種基于交通引導開發(fā)（transit oriented development，TOD）理念構建高鐵快巴服務網(wǎng)絡的方法；安久燁等[3]考慮回程的服務去往，研究高鐵車站接駁公交靈活線路的優(yōu)化設計方法；姚恩建等[4]針對鐵路車站夜間乘客疏散問題提出基于定制公交的解決方案，并對其核心的多線路動態(tài)規(guī)劃問題展開研究。

高鐵快巴具有“一人一座、預約出行、快速直達”的運營特點，是定制公交的一種模式。近年來國內(nèi)外學者對定制公交路徑優(yōu)化和車輛調(diào)度方面進行了研究，LEE等[5]和BELHAIZA[6]以最小化運營時間或成本、最小化乘客出行時間等為目標，以車輛行程距離或時間、預約時間窗、乘客最大等待時間等為約束，建立數(shù)學模型；邵文等[7]進一步考慮乘客乘坐和到達的時間要求，建立兼顧降低成本和乘客滿意度的調(diào)度模型；程仁輝等[8]考慮乘客心理和道路交通的影響，對定制公交給予一定的擁堵道路停車載客懲罰；趙力萱等[9]通過建立模型和構建算例研究以碳減排為目標的定制公交線路規(guī)劃問題。路徑優(yōu)化和車輛調(diào)度的求解算法，多采用領域搜索算法、分布式算法、遺傳算法等。信息采集和交互技術的發(fā)展為乘客需求的精細化管理提供了可能，乘客可以提前或?qū)崟r定制出行需求。國內(nèi)外學者同樣在滿足混合需求的定制公交調(diào)度方面做了許多研究，QUADRIFOGLIO等[10]提出了一種簡單插入算法， 以效用變化最小的為目標， 將乘客逐次插入到每個班次中；邱豐等[11]建立了同時處理靜態(tài)需求和動態(tài)需求的2階段調(diào)度模型；邵孜科等[12]從減少乘客平均出行時間和降低系統(tǒng)拒絕率兩個方向出發(fā)，對簡單插入算法進行優(yōu)化。

既有研究未考慮乘客需求點的分散性、路網(wǎng)的復雜性和封閉式小區(qū)的存在，以及乘客對在車時間、等待時間、步行時間等不同狀態(tài)下時間的感知差異。在此基礎上，本文考慮乘客需求點位于封閉式小區(qū)內(nèi)部等復雜情況，引入臨時站點，同時考慮乘客對在車時間、等待時間、步行時間的感知差異，建立基于混合需求的高鐵快巴動態(tài)線路規(guī)劃模型，提高響應實時需求預約的成功率。

1 問題描述

按照不同的線路類型和服務模式，高鐵快巴分為固定和動態(tài)兩類運營線路。固定線路是參照常規(guī)公交的運營方式；動態(tài)線路依托系統(tǒng)支持按照乘客需求動態(tài)響應，自動規(guī)劃生成車輛行駛路徑[13]。

本文研究的對象為高鐵快巴動態(tài)運營線路，該模式線路在高鐵站與一定范圍內(nèi)的乘客居住區(qū)之間運行，在居住區(qū)內(nèi)部有調(diào)度站。本文將車輛發(fā)車前收到的預約定義為提前預約需求，將車輛發(fā)車后收到的預約定義為實時需求，車輛運行方向為乘客居住區(qū)至高鐵站，建立基于混合需求的動態(tài)線路規(guī)劃模型。車輛發(fā)車前，

乘客選擇一個固定站點作為出行起點、高鐵站作為出行終點，調(diào)度中心接收提前預約信息集合，生成多車輛行駛路線和時刻表信息，其中一輛車的行駛路線如圖1（a）所示。車輛發(fā)車后以既定路線行駛，乘客可定位其當前所在位置為出行起點、高鐵站作為出行終點，調(diào)度中心收到實時需求Q1、Q2，由于

Q1、Q2所在位置不適宜作為站點，將Q1、Q2引導到臨時站點上車，實時調(diào)整車輛行駛路線，將車輛行駛路徑和延誤信息反饋給乘客，此階段車輛行駛路線調(diào)整為圖1（b）。

2 模型建立基礎

2.1 基本假設

從實際問題中構建模型，作如下假設：

（1）車輛均從居住區(qū)內(nèi)的調(diào)度站出發(fā)，響應乘客需求后通過城市快速路直達高鐵站。

（2）每兩個固定站點或臨時站點間均可以通達，站點之間的距離固定。公交車輛在任一兩個站點之間以一定速度勻速行駛，在每個站點的停留時間相等。

（3）滿足所有提前預約乘客需求，但不一定滿足所有實時乘客需求。

（4）由于響應實時需求會增加既定的行程時間，設置tr為單程松弛時間，單程增加的行程時間不能超過tr。

（5）提前預約乘客可預約出發(fā)和到達時間窗，實時需求乘客期望預約后盡快接受服務。

（6）為保持較高的服務質(zhì)量，實行一人一座。

（7）臨時站點位置由調(diào)度系統(tǒng)根據(jù)路網(wǎng)情況實時生成。

2.2 乘客時間窗分析

考慮到接駁高鐵客流的特點，乘客對于到達時間的準時性要求更高。到達時間為硬時間窗，若乘客到達時間不在期望時間窗內(nèi)時，乘客放棄高鐵快巴出行，故將到達時間窗作為模型的約束。乘客出發(fā)時間為軟時間窗，軟時間窗乘客滿意度函數(shù)如圖2所示。為反映乘客對出發(fā)時間滿意度的變化，構建懲罰函數(shù)來反映滿足乘客時間窗的程度，函數(shù)圖像如圖3所示。

乘客出發(fā)時間懲罰函數(shù)g（t）為

式中：［Et，Lt］為乘客期望出發(fā)時間窗；［Et′，Lt′］為乘客可忍受出發(fā)時間窗；η、λ均為單位時間懲罰系數(shù)，且η>λ。

3 基于混合需求的高鐵快巴動態(tài)線路規(guī)劃模型

3.1 基于提前預約需求的線路規(guī)劃模型

由于高鐵快巴為社會提供公共服務，公交公司應綜合考慮運營成本和滿足乘客出行成本。達到系統(tǒng)最優(yōu)時，公交運營成本、乘客出行成本和乘客時間窗懲罰的總和最小，目標函數(shù)可表示為

式中：N為固定站點集合；V為調(diào)度站集合；H為高鐵站集合；K為車輛集合；N（k）為車輛k經(jīng)過的站點的集合；Qi為i站點上車需求集合；f為乘客出行時間成本；c0p為車型p的公交車輛啟動成本；c1p為車型p的公交車輛單位距離運輸成本；qmaxp為車型p的公交車輛座位數(shù)；qα為預留座位數(shù)；dmax為車輛單程最大行駛距離；dij為站點i和j間的實際距離；p（k）為車輛k的車型；oki為車輛k離開i站時的載客人數(shù)；tki為車輛到達站點i時間；tqi為站點i的第qi個乘客接受服務的時間；tα為車輛在站點最小服務時間；tr為單程松弛時間;tlateqi為站點i第qi個乘客的可忍受最晚到達時間；車輛k從站點i到站點j時，xkij為1，否則xkij為0；站點i的第qi個乘客由車輛k提供服務時，ykqi為1，否則ykqi為0。

式（2）為模型的目標函數(shù)，為車輛固定成本、車輛變動成本、乘客出行時間成本、乘客時間窗懲罰值之和；式（3）表示車輛從調(diào)度站出發(fā)；式（4）表示車輛最終到達高鐵站；式（5）表示固定站點至少由一輛車進行服務；式（6）表示一輛車不能重復經(jīng)過某個站點；式（7）表示滿足所有提前預約乘客；式（8）表示乘客只能由經(jīng)過其預約站點的車輛提供服務；式（9）為考慮預留座位的載客量約束；式（10）為單程行駛距離約束；式（11）為考慮車輛單程松弛時間下的乘客到達時間窗約束。

該問題可轉(zhuǎn)化為旅行商（TSP）問題，即所有需求點僅被經(jīng)過一次且需求均被滿足的車輛路徑問題。將同一個站點不同的需求進行拆分，生成相應的虛擬站點。這些虛擬站點的位置信息與其真實站點相同，將虛擬站點放入需求站點集合N中，并將模型約束式（5）調(diào)整為式（12）。

3.2 考慮實時需求的動態(tài)線路規(guī)劃模型

系統(tǒng)因滿足實時需求，增加的系統(tǒng)變動成本包括車輛變動成本、預約乘客的時間成本和實時需求乘客的時間成本。由于乘客傾向認為與在車的時間成本相比，等待和步行的時間成本更大，且步行消耗體力更大，本文引入轉(zhuǎn)換系數(shù)表示這一感知差異，三者的轉(zhuǎn)換系數(shù)由大到小為：步行時間轉(zhuǎn)換系數(shù)、等待時間轉(zhuǎn)換系數(shù)、在車時間轉(zhuǎn)換系數(shù)。模型的目標為最小化系統(tǒng)變動成本，即

式（13）為目標函數(shù)，求解系統(tǒng)增加的車輛變動成本、提前預約乘客增加的出行時間成本、實時預約乘客的出行時間成本之和最小的系統(tǒng)響應方案；式（14）為所有提前預約乘客增加的等價出行時間計算公式，為在車時間和等待時間之和；式（15）為該實時需求乘客的等價出行時間計算公式，為在車時間、等待時間和步行時間之和；式（16）表示每個可響應的實時需求在一個響應站點由一輛車提供服務。

4 算法設計

4.1 基于提前預約需求的線路規(guī)劃模型的求解算法

遺傳算法是一種基于概率統(tǒng)計的隨機搜索算法，對求解TSP問題具有一定的優(yōu)勢，本文用遺傳算法求解基于預約需求的線路規(guī)劃模型。

4.1.1 編碼與解碼

采用整數(shù)排列編碼方法編碼種群的染色體。每條染色體分為N+K段，其中N為對應需求點的編號，K為每輛車車型編號。利用式（9）載客量約束和式（10）單程行駛距離約束將一條所有站點訪問順序染色體轉(zhuǎn)化為多輛車路徑信息，該過程如圖4所示。

4.1.2 計算適應度函數(shù)

通過解碼得到的多車輛路徑滿足約束式（3）～ （10），為滿足乘客到達硬時間窗約束，即約束式（11），構造適應度函數(shù)為

i=1/（Fi+Mi），（17）

式中：i為個體i的適應度；Fi為個體i的目標函數(shù)；Mi為硬時間窗懲罰值，當所有預約需求滿足約束式（11）時，Mi=‘0，否則Mi=‘10 000。

4.1.3 更新適應度函數(shù)

本文利用小生境技術對傳統(tǒng)遺傳算法進行改進，通過共享函數(shù)調(diào)整適應度使較低適應度的個體被淘汰的概率增大，使得適應度較高的個體得以保留 [14]，更新個體適應度值′i的計算公式如下

式中：ωi，j為個體i與個體j的共享函數(shù)；σ為峰半徑；α控制共享函數(shù)的形狀，通常取α=1，表示線性共享函數(shù)；l（i，j）為個體i與個體j之間的歐氏距離；Si為個體i的共享度；π為遺傳算法種群個體集合。

4.1.4 求解步驟

遺傳算法的其他遺傳操作與傳統(tǒng)遺傳算法相似，算法步驟如下。

Step1：初始化。設計遺傳算法染色體的編碼方案，確定參數(shù)，如種群規(guī)模、最大進化代數(shù)、交叉概率、變異概率、小生境技術參數(shù)等，生成滿足模型約束的初始種群。

Step2：解碼染色體，進行適應度計算和更新。

Step3：終止判定。如果進化代數(shù)達到最大進化代數(shù)，則停止算法，解碼染色體，輸出最優(yōu)解的函數(shù)值、車型配置及線路路徑；否則轉(zhuǎn)step4。

Step4：進行遺傳操作。執(zhí)行選擇、交叉、變異和逆轉(zhuǎn)，轉(zhuǎn)Step2。

4.2 實時需求響應機制

可響應實時需求的備選車輛為實時需求生成時刻正在運行或等待運行的車輛，備選響應站點為臨時需求周邊具備停車條件的臨時站點，則當每個實時需求生成時，系統(tǒng)響應步驟如下。

Step3：枚舉法求解動態(tài)線路規(guī)劃模型，生成響應方案，調(diào)整線路方案，將信息反饋給司機和乘客。

5 案例分析

5.1 案例區(qū)域及參數(shù)取值

本文選擇北京市北太平莊街道轄區(qū)南部地區(qū)為高鐵快巴的服務區(qū)域，該區(qū)域以住宅用地為主，商業(yè)用地、辦公用地及綠化設施用地為輔。根據(jù)道路條件和客流調(diào)研，設置13個固定站點和若干個臨時站點，調(diào)度站位置在積水潭地鐵站，終點站為北京南站。案例區(qū)域示意圖見圖5。模型參數(shù)取值如下[15-18]：vwalk=1.5m/s，f=12元/h，η=‘1.5元/min、γ=‘0.5元/min；β1=‘1.1，β2=‘1.2，β3=‘1.5；本文采用載客量為9人和14人的小型公交車，經(jīng)估算qmax1=‘9，c01=‘50元/輛，c11=‘0.003元/m，qmax2=14，c01=‘70元/輛，c11=‘0.005元/m；dmax=20 km；在北太平莊街道區(qū)域內(nèi)車輛vbus=‘15 km/h，在城市快速路上vbus=30 km/h；其他參數(shù)根據(jù)實際調(diào)研和需求賦值，qα=‘3，tα=‘30 s，tr=5 ‘min，第一輛車的發(fā)車時間為早7：00，發(fā)車間隔為10 min；模擬30組早高峰時段預約和實時需求，提前預約乘客的期望出發(fā)時間窗為2 min，可忍受出發(fā)時間為提前或推遲3 min范圍內(nèi)。其中一組需求見表1和表2，實時需求的位置見圖5。

5.2 模型與算法的有效性驗證

設計3組對比試驗：A組為使用本文模型和算法的基本組；B組為使用本文模型、傳統(tǒng)遺傳算法的對照組，與A組結(jié)果對照來驗證本文使用的小生境遺傳算法的可行性與適應性；C組為在響應實時需求時取消臨時站點、使用本文模型和算法的對照組，與A組結(jié)果對照來驗證設置臨時站點的合理性。對30組需求進行求解并進行對比試驗，所有試驗都在最大進化代數(shù)內(nèi)收斂，結(jié)果見表3。A組與B組相比，系統(tǒng)成本降低3.4%，人均成本降低3.3%，得到的線路規(guī)劃結(jié)果更優(yōu)，證明小生境遺傳算法有效避免傳統(tǒng)遺傳算法易陷入局部最優(yōu)解的缺陷。A組與C組相比，實時需求響應率由54.6%提升至89.4%；由于A組服務的乘客更多，系統(tǒng)總成本稍高于C組；A組與C組相比，人均成本降低4.1%，說明臨時站點的設置使響應方案更加柔性化，在大幅度提高響應率的同時降低了系統(tǒng)人均成本，具有經(jīng)濟性。

5.3 車輛動態(tài)線路規(guī)劃結(jié)果

以表1～2中的需求為例，采用本文模型與算法進行車輛動態(tài)線路規(guī)劃，算法在第117代完成收斂，優(yōu)化過程如圖6所示，高鐵快巴在北太平莊區(qū)域內(nèi)行駛路線圖如圖7，高鐵快巴動態(tài)線路規(guī)劃方案如表4所示，所有實時需求均能被響應。

6 結(jié)論

高鐵快巴作為一種定制公交運營模式的綠色出行方式，滿足旅客在高鐵站的接駁及疏散需求，增強高鐵站作為城市綜合交通樞紐的作用。本文研究基于混合需求的高鐵快巴動態(tài)線路規(guī)劃模型，以系統(tǒng)總成本和變動成本最小為目標，建立基于提前預約需求和考慮實時需求的高鐵快巴動態(tài)線路規(guī)劃模型。案例驗證了本文模型在提供更便捷靈活的線路規(guī)劃方法的同時，可以提高實時需求響應率，降低系統(tǒng)人均成本；設計的小生境遺傳算法可以保證種群多樣性，提高進化效率，得到更優(yōu)的結(jié)果。本文的案例是基于小規(guī)模需求，未來可在大規(guī)模需求中進行試驗，進一步驗證模型算法的可行性，并進一步精細考慮乘客預約時間要求，提高乘客滿意度。

參考文獻：

［1］李佳暉， 宋瑞， 郭小樂. 高鐵快巴運營效果綜合評價指標體系研究[J]. 大連交通大學學報， 2018， 39（4）： 1-6. DOI： 10.13291/j.cnki.djdxac.2018.04.001.

[2]張英群， 宋瑞， 何世偉， 等. TOD理念下高鐵快巴服務網(wǎng)絡設計研究[J]. 鐵道學報， 2019， 41（9）： 12-19. DOI： 10.3969/j.issn.1001-8360.2019.09.002.

[3]安久煜， 宋瑞， 畢明凱， 等. 高鐵車站接駁公交靈活線路優(yōu)化設計研究[J]. 交通運輸系統(tǒng)工程與信息， 2019， 19（5）： 150-155. DOI： 10.16097/j.cnki.1009-6744.2019.05.021.

[4]姚恩建， 馬斯瑋， 向鎮(zhèn)， 等. 面向鐵路夜間乘客疏散的定制公交線路優(yōu)化[J]. 北京交通大學學報， 2021， 45（1）： 78-84. DOI： 10.11860/j.issn.1673-0291.20200046.

[5]LEE A L， SAVELSBERGH M. An extended demand responsive connector[J]. EURO Journal on Transportation and Logistics， 2017， 6（1）： 25-50. DOI： 10.1007/s13676-014-0060-6.

[6]BELHAIZA S. A data driven hybrid heuristic for the dial-a-ride problem with time windows[C]//2017 IEEE Symposium Series on Computational Intelligence （SSCI）. Honolulu， HI， USA： IEEE， 2017： 1-8. DOI： 10.1109/SSCI.2017.8285366.

[7]邵文， 賈順平， 曹文娟. 基于混合車型的靈活型接駁公交路徑協(xié)同優(yōu)化研究[J]. 山東科學， 2019， 32（4）： 64-73. DOI： 10.3976/j.issn.1002-4026.2019.04.009.

[8]程仁輝， 賈順平. 考慮擁堵道路停車懲罰的定制公交調(diào)度研究[J]. 山東科學， 2021， 34（1）： 53-61. DOI： 10.3976/j.issn.1002-4026.2021.01.007.

[9]趙力萱， 吳澤駒， 何康園， 等. 碳減排背景下定制公交路線規(guī)劃方法[J]. 交通運輸研究， 2022， 8（3）： 56-65. DOI： 10.16503/j.cnki.2095-9931.2022.03.006.

[10]QUADRIFOGLIO L， DESSOUKY M M， PALMER K. An insertion heuristic for scheduling Mobility Allowance Shuttle Transit （MAST） services[J]. Journal of Scheduling， 2007， 10（1）： 25-40. DOI： 10.1007/s10951-006-0324-6.

[11]邱豐， 李文權， 沈金星. 可變線路式公交的兩階段車輛調(diào)度模型[J]. 東南大學學報（自然科學版）， 2014， 44（5）： 1078-1084. DOI： 10.3969/j.issn.1001-0505.2014.05.036.

[12]邵孜科， 張泉， 王樹盛， 等. 可變線路公交車輛調(diào)度算法優(yōu)化研究[J]. 交通信息與安全， 2018， 36（5）： 83-89. DOI： 10.3963/j.issn.1674-4861.2018.05.011.

[13]萬逸飛， 吳天真. 需求、平臺、供給——創(chuàng)新驅(qū)動公交服務新模式：北京公交高鐵快巴的思考與實踐[J]. 人民公交， 2018（7）： 54-55. DOI： 10.16857/j.cnki.cn11-5903/u.2018.07.008.

[14]GOLDBERG D E. Genetic algorithms in search， optimization， and machine learning[M]. Reading， Mass.： Addison-Wesley Pub. Co.， 1989.

[15]閆平， 宋瑞. 城市公共交通概論[M]. 北京： 機械工業(yè)出版社， 2011.

[16]孫楊， 孫小年， 孔慶峰， 等. 軌道交通新線投入運營下常規(guī)公交網(wǎng)絡優(yōu)化調(diào)整方法研究[J]. 鐵道學報， 2014， 36（3）： 1-8. DOI： 10.3969/j.issn.1001-8360.2014.03.001.

[17]范文豪. 需求響應式接駁公交路徑優(yōu)化模型研究[D]. 南京： 東南大學， 2017.

[18]沈犁， 楊京帥， 王周全， 等. 城市機動式輔助客運方式時間效用改進[J]. 長安大學學報（自然科學版）， 2016， 36（4）： 95-102. DOI： 10.19721/j.cnki.1671-8879.2016.04.013.