基于停靠站選址的響應型接駁公交調度優化

吳典文,彭 宇,田 奇,王正武,姜寧宇

(1.湖南省交通規劃勘察設計院有限公司，湖南 長沙 410200；2.長沙理工大學 交通運輸工程學院，湖南 長沙 410114；3.汕頭市城區公共交通服務所，廣東 汕頭 515031)

0 引言

在城市邊緣地區，居民居住區域較分散，軌道交通和常規公交的覆蓋率較低，公共交通設施有限，居民出行起訖點距離公共交通站點距離較遠，難以實現居民出行便捷、低成本的“門到門”的服務。響應型接駁公交(Responsive Feeder Transit，RFT)如圖1所示，根據乘客預約或實時申請，確定乘客接送時間、分配適宜車型、規劃最佳車輛線路及途經停靠站，能為地鐵等干線公交提供高效、便捷的接駁服務。根據響應方式的不同，可以分為基于乘客需求點(即乘客上傳的上下車位置)的車輛路徑優化模型與基于停靠站(即車輛實際停靠位置)選址的車輛路徑優化模型對RFT系統路徑進行調度優化。基于乘客需求點的車輛路徑優化模型是指響應每一位乘客上傳的需求點進行停靠服務，而基于停靠站選址的車輛路徑優化模型則是對乘客需求點進行整合，確定停靠位置及每個位置服務的乘客，再通過路徑優化等方法確定車輛路徑與對應的停靠位置等。

圖1 系統示意圖Figure 1 System diagram

目前，公交停靠站選址的相關研究主要集中于停靠站覆蓋率[1-3]、覆蓋半徑[4-5]、設置間距[6-8]及停靠站選址方法[9-10]，少數研究者探討了校車、應急公交停靠站設置及路徑優化的協調問題[11-12]。高選幸[11]在校車路徑優化中分析了停靠站設置的影響，支曉宇[12]在城市軌道交通應急公交線路優化中探討了駐車點的選址分配問題。響應型接駁公交的相關研究主要集中于車輛路徑優化[13-14]，運行路徑幾乎均是根據乘客需求點來優化的，很少基于停靠站選址來進行車輛路徑優化；而且停靠站選址研究中，對乘客出行因素的考慮較為單一，實際上，不同乘客的出行行為特性、出行目的存在差異，會影響到乘客對上車站點的選擇，從而影響車輛運營路徑。

針對上述不足，本文對基于乘客需求點的車輛路徑優化模型進行改進，考慮乘客需求空間分布，基于聚類分析和重心位置法進行停靠站選址，以企業運營成本最小為目標構建車輛路徑優化模型并設計模擬退火求解算法，盡量提高RFT系統的乘客服務質量、降低車輛運營成本。

1 基于停靠站選址的路徑優化

受到土地利用性質、出行目的、出行方式等因素影響，乘客出行需求在空間上隨機散狀分布。響應型接駁公交通過兩種坐乘模式為乘客提供接駁服務：乘客在自主選擇的需求點坐乘和乘客需步行到要求的停靠站坐乘。兩種模式的比較如表1所示。由表1可知，為兼顧乘客便利性和運營成本，宜采用小間距停靠站布設策略。

表1 兩種坐乘模式的比較Table 1 Comparison of two ride modes坐乘模式在需求點坐乘在停靠站坐乘乘客便利程度便利性高,乘客步行距離短便利性一般,乘客需步行至停靠站,步行約100～300 m運營費用車輛運營費用較高車輛運營費用較低,伴隨著乘客步行時間增加車輛運行路徑車輛運行距離較長,存在繞行車輛運行距離較短,路徑選擇較簡單路網條件要求路網密度大,否則車輛不能到達路網密度要求一般

本文分停靠站選址與車輛路徑優化兩步，停靠站的選址又由兩步確定：首先根據乘客需求分布采用K-means聚類，在乘客最大步行距離閾值下基于聚類分析對乘客需求點進行空間聚類，確定各聚類簇的質心；然后考慮乘客需求的多樣性和差異性，基于重心位置法確定停靠站選址。在停靠站選址確定之后，再由系統對RFT車輛路徑進行優化，具體流程如圖2所示。

圖2 系統流程Figure 2 System flow

1.1 基于K-means的乘客空間聚類

為降低K-means聚類算法中點之間距離的復雜程度，減小孤立點的影響，避免陷入局部最優解，本文在K-means聚類算法中引入Canopy初始聚類方法。聚類算法步驟如圖3所示。

圖3 乘客空間聚類流程Figure 3 Passenger space clustering process

圖3中，L可根據乘客步行距離要求確定，一般為100～300 m。算法終止準則是乘客需求點到聚類中心的距離均小于L、且新質心與原質心的距離小于約定的一個值。

1.2 基于重心位置法的停靠站選址

考慮乘客出行需求的差異性和多樣性，本文采用重心位置法[15]確定了各聚類簇對應的停靠站選址。本文考慮乘客年齡、出行目的、支付意愿、違背時間窗等4個影響來運用重心位置法調整聚類簇pi所有乘客位置：

(1)

(2)

1.3 車輛路徑模型

根據乘客需求和確定的停靠站選址，系統進行車輛調度，在滿足乘客時間窗、車輛容量等約束下，通過車輛路徑優化模型，使系統中企業運營成本最小。車輛路徑優化時，遵循如下假設：①接駁公交在行駛中按勻速行駛，一個班次服務的線路唯一；②乘客需求均為預約需求；③接駁公交的容量和保有量已知；④接駁公交在停靠站之間以最短路運行，且中途不停車。

根據上述假設，預約需求、固定發車時間下響應型接駁公交發出車型和運行路徑的協調優化模型可描述為：

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

式(3)表示所有接駁公交的啟動成本和運行成本之和最小；式(4)保證停靠站服務范圍的乘客均被響應；式(5)、 式(6)為車輛容量約束； 式(7)為車輛行程時間約束； 式(8)表示車輛單次運行線路長度約束； 式(9)、 式(10)為車輛到達停靠站pj的時間約束。

車輛路徑問題可用遺傳算法等啟發式算法求解，本文選用模擬退火算法(Simulated Annealing，SA)求解基于停靠站的車輛路徑問題[14]。模擬退火算法是一種通用的概率算法，常用來搜尋較大空間的最優解，且對于初始值和參數條件要求較低，適用于本文的車輛路徑問題。路徑優化模型求解模擬退火算法的具體流程見圖4。

圖4 SA算法求解流程圖Figure 4 SA algorithm solution flow chart

2 算例分析

尚雙塘地鐵站是長沙市軌道交通1號線一期工程的終點站，地處長沙郊區三環外，周邊公共交通系統不完善，附近居民分散，出行分布不均勻，符合需求RFT的設置初衷，本文擬以尚雙塘地鐵站為仿真案例進行研究，設定地鐵站點坐標為(0，0)，正東方向為X軸正方向，正北方向為Y軸正方向建立直角坐標系。服務半徑是R=4 000 m的圓形區域，接駁車輛的速度為v=30 km/h。設定兩種類型的接駁車輛：車型A有8輛、容量為15人/輛、啟動成本5元/輛、γA=0.001 5元/m；車型B有5輛、容量為20人/輛、啟動成本10元/輛、γB=0.002元/m。L為200 m、Tmax為40 min、Lmax、Lmin分別為10、4 km。隨機生成研究時段8:00～9:00內乘客需求90位，乘客需求分布情況如圖5、圖6所示。

圖5 基于停靠站選址的協調調度結果圖Figure 5 Coordinated dispatching results based on station location

圖6 基于需求點的協調調度結果圖Figure 6 Coordination and scheduling results based on demand points

通過改進K-means聚類算法生成了20個聚類簇，基于重心位置法確定的停靠站選址表2所示。

表2 停靠站選址Table 2 Location of stops停靠站編號X坐標Y坐標停靠站編號X坐標Y坐標18781 05011-2 2861 65421 7682 44512-234-2 49031 8972 51613-161-1 06049561 51914-1 015-1 73353 04062315-2 195-2 39462 0811 55416-2 019-1 9557-66396617648-7958-1 5342 081183 022-1 5259-76236219129-3 12110-2882 665201 585-2 147

基于MATLAB編程，應用模擬退火算法求解協調調度模型，設降溫速率q為0.9、初始溫度T0為1 000、結束溫度Tend為0.001、鏈長N為200。調用模擬退火算法分別應用基于停靠站選址的、基于需求點的車輛協調調度模型獲得優化的車輛路徑和發出車型(其中基于需求點的協調調度模型與基于停靠站選址的基本相同，只需將停靠站改為需求點)，基于停靠站選址的協調調度結果如表3與圖5所示，基于需求點的協調調度結果如表4與圖6所示。

表3 基于停靠站選址的協調調度結果表Table 3 Table of coordinated dispatching results based on station location序號發車時刻到達時刻發出車型載客量/人車輛路徑18:008:37B170-1-10-8-11-028:108:41B180-7-4-2-3-038:208:56B160-9-16-15-12-048:308:59B190-13-14-19-20-058:409:15B200-17-18-5-6-0注:平均滿載率為90%,運行距離為42.84 km,系統總成本為135.86元。

表4 基于需求點的協調調度結果表Table 4 Coordinated dispatching results based on demand points序號發車時刻到達時刻發出車型18:008:40B28:108:49B38:208:58B48:309:07B58:409:18B載客量/人服務的需求點201、42～45、33～37、46～48、28～32、38～39、203、2、4～5、15～18、6～9、10～14、25～271340～41、67～70、64～66、60～631754～59、49～53、82～872071～75、88～90、76～81、19～24注:平均滿載率為90%,運行距離為47.62 km,系統總成本為167.84元。

比較表3和表4可知：① 基于停靠站選址的方法，發出車型B5次，乘客的人均坐乘距離476 m/人、人均總成本1.510元/人，平均行駛距離成本0.003 1元/m；② 基于需求點的方法，發出車型B5次，乘客的人均坐乘529 m/人，人均總成本1.865元/人，平均行駛距離成本0.003 5元/m；③ 與基于需求點的方法比較，基于停靠站選址的方法，乘客的人均坐乘距離減少了10%，人均總成本減少了23.5%，平均行駛距離成本減少了11.4%，基于停靠站選址的方法能顯著提升系統運行效率。

3 結論

a.運用改進K-means聚類算法和重心位置法進行了停靠站選址研究，并以系統運營成本最小為目標，建立了基于停靠站的RFT協調調度模型。

b.算例表明，基于停靠站選址的協調調度方法能顯著降低系統總成本，運行效率提升效果顯著。

下階段的研究應是乘客時空分布影響下的響應型接駁公交協調調度研究，同時具有預約需求、實時需求下的響應型接駁公交協調調度研究。