基于停靠站選址的響應(yīng)型接駁公交調(diào)度優(yōu)化

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

(1.湖南省交通規(guī)劃勘察設(shè)計(jì)院有限公司，湖南 長沙 410200；2.長沙理工大學(xué) 交通運(yùn)輸工程學(xué)院，湖南 長沙 410114；3.汕頭市城區(qū)公共交通服務(wù)所，廣東 汕頭 515031)

0 引言

在城市邊緣地區(qū)，居民居住區(qū)域較分散，軌道交通和常規(guī)公交的覆蓋率較低，公共交通設(shè)施有限，居民出行起訖點(diǎn)距離公共交通站點(diǎn)距離較遠(yuǎn)，難以實(shí)現(xiàn)居民出行便捷、低成本的“門到門”的服務(wù)。響應(yīng)型接駁公交(Responsive Feeder Transit，RFT)如圖1所示，根據(jù)乘客預(yù)約或?qū)崟r(shí)申請，確定乘客接送時(shí)間、分配適宜車型、規(guī)劃最佳車輛線路及途經(jīng)?？空?，能為地鐵等干線公交提供高效、便捷的接駁服務(wù)。根據(jù)響應(yīng)方式的不同，可以分為基于乘客需求點(diǎn)(即乘客上傳的上下車位置)的車輛路徑優(yōu)化模型與基于?？空?即車輛實(shí)際停靠位置)選址的車輛路徑優(yōu)化模型對RFT系統(tǒng)路徑進(jìn)行調(diào)度優(yōu)化?；诔丝托枨簏c(diǎn)的車輛路徑優(yōu)化模型是指響應(yīng)每一位乘客上傳的需求點(diǎn)進(jìn)行停靠服務(wù)，而基于?？空具x址的車輛路徑優(yōu)化模型則是對乘客需求點(diǎn)進(jìn)行整合，確定?？课恢眉懊總€(gè)位置服務(wù)的乘客，再通過路徑優(yōu)化等方法確定車輛路徑與對應(yīng)的?？课恢玫?。

圖1 系統(tǒng)示意圖Figure 1 System diagram

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

針對上述不足，本文對基于乘客需求點(diǎn)的車輛路徑優(yōu)化模型進(jìn)行改進(jìn)，考慮乘客需求空間分布，基于聚類分析和重心位置法進(jìn)行停靠站選址，以企業(yè)運(yùn)營成本最小為目標(biāo)構(gòu)建車輛路徑優(yōu)化模型并設(shè)計(jì)模擬退火求解算法，盡量提高RFT系統(tǒng)的乘客服務(wù)質(zhì)量、降低車輛運(yùn)營成本。

1 基于?？空具x址的路徑優(yōu)化

受到土地利用性質(zhì)、出行目的、出行方式等因素影響，乘客出行需求在空間上隨機(jī)散狀分布。響應(yīng)型接駁公交通過兩種坐乘模式為乘客提供接駁服務(wù)：乘客在自主選擇的需求點(diǎn)坐乘和乘客需步行到要求的?？空咀?。兩種模式的比較如表1所示。由表1可知，為兼顧乘客便利性和運(yùn)營成本，宜采用小間距?？空静荚O(shè)策略。

表1 兩種坐乘模式的比較Table 1 Comparison of two ride modes坐乘模式在需求點(diǎn)坐乘在?？空咀顺丝捅憷潭缺憷愿?乘客步行距離短便利性一般,乘客需步行至?？空?步行約100～300 m運(yùn)營費(fèi)用車輛運(yùn)營費(fèi)用較高車輛運(yùn)營費(fèi)用較低,伴隨著乘客步行時(shí)間增加車輛運(yùn)行路徑車輛運(yùn)行距離較長,存在繞行車輛運(yùn)行距離較短,路徑選擇較簡單路網(wǎng)條件要求路網(wǎng)密度大,否則車輛不能到達(dá)路網(wǎng)密度要求一般

本文分?？空具x址與車輛路徑優(yōu)化兩步，?？空镜倪x址又由兩步確定：首先根據(jù)乘客需求分布采用K-means聚類，在乘客最大步行距離閾值下基于聚類分析對乘客需求點(diǎn)進(jìn)行空間聚類，確定各聚類簇的質(zhì)心；然后考慮乘客需求的多樣性和差異性，基于重心位置法確定?？空具x址。在?？空具x址確定之后，再由系統(tǒng)對RFT車輛路徑進(jìn)行優(yōu)化，具體流程如圖2所示。

圖2 系統(tǒng)流程Figure 2 System flow

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

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

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

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

1.2 基于重心位置法的?？空具x址

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

(1)

(2)

1.3 車輛路徑模型

根據(jù)乘客需求和確定的?？空具x址，系統(tǒng)進(jìn)行車輛調(diào)度，在滿足乘客時(shí)間窗、車輛容量等約束下，通過車輛路徑優(yōu)化模型，使系統(tǒng)中企業(yè)運(yùn)營成本最小。車輛路徑優(yōu)化時(shí)，遵循如下假設(shè)：①接駁公交在行駛中按勻速行駛，一個(gè)班次服務(wù)的線路唯一；②乘客需求均為預(yù)約需求；③接駁公交的容量和保有量已知；④接駁公交在?？空局g以最短路運(yùn)行，且中途不停車。

根據(jù)上述假設(shè)，預(yù)約需求、固定發(fā)車時(shí)間下響應(yīng)型接駁公交發(fā)出車型和運(yùn)行路徑的協(xié)調(diào)優(yōu)化模型可描述為：

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

式(3)表示所有接駁公交的啟動(dòng)成本和運(yùn)行成本之和最?。皇?4)保證?？空痉?wù)范圍的乘客均被響應(yīng)；式(5)、 式(6)為車輛容量約束； 式(7)為車輛行程時(shí)間約束； 式(8)表示車輛單次運(yùn)行線路長度約束； 式(9)、 式(10)為車輛到達(dá)停靠站pj的時(shí)間約束。

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

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

2 算例分析

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

圖5 基于停靠站選址的協(xié)調(diào)調(diào)度結(jié)果圖Figure 5 Coordinated dispatching results based on station location

圖6 基于需求點(diǎn)的協(xié)調(diào)調(diào)度結(jié)果圖Figure 6 Coordination and scheduling results based on demand points

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

表2 ?？空具x址Table 2 Location of stops?？空揪幪?hào)X坐標(biāo)Y坐標(biāo)?？空揪幪?hào)X坐標(biāo)Y坐標(biāo)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編程，應(yīng)用模擬退火算法求解協(xié)調(diào)調(diào)度模型，設(shè)降溫速率q為0.9、初始溫度T0為1 000、結(jié)束溫度Tend為0.001、鏈長N為200。調(diào)用模擬退火算法分別應(yīng)用基于?？空具x址的、基于需求點(diǎn)的車輛協(xié)調(diào)調(diào)度模型獲得優(yōu)化的車輛路徑和發(fā)出車型(其中基于需求點(diǎn)的協(xié)調(diào)調(diào)度模型與基于?？空具x址的基本相同，只需將?？空靖臑樾枨簏c(diǎn))，基于?？空具x址的協(xié)調(diào)調(diào)度結(jié)果如表3與圖5所示，基于需求點(diǎn)的協(xié)調(diào)調(diào)度結(jié)果如表4與圖6所示。

表3 基于?？空具x址的協(xié)調(diào)調(diào)度結(jié)果表Table 3 Table of coordinated dispatching results based on station location序號(hào)發(fā)車時(shí)刻到達(dá)時(shí)刻發(fā)出車型載客量/人車輛路徑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%,運(yùn)行距離為42.84 km,系統(tǒng)總成本為135.86元。

表4 基于需求點(diǎn)的協(xié)調(diào)調(diào)度結(jié)果表Table 4 Coordinated dispatching results based on demand points序號(hào)發(fā)車時(shí)刻到達(dá)時(shí)刻發(fā)出車型18:008:40B28:108:49B38:208:58B48:309:07B58:409:18B載客量/人服務(wù)的需求點(diǎn)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%,運(yùn)行距離為47.62 km,系統(tǒng)總成本為167.84元。

比較表3和表4可知：① 基于?？空具x址的方法，發(fā)出車型B5次，乘客的人均坐乘距離476 m/人、人均總成本1.510元/人，平均行駛距離成本0.003 1元/m；② 基于需求點(diǎn)的方法，發(fā)出車型B5次，乘客的人均坐乘529 m/人，人均總成本1.865元/人，平均行駛距離成本0.003 5元/m；③ 與基于需求點(diǎn)的方法比較，基于?？空具x址的方法，乘客的人均坐乘距離減少了10%，人均總成本減少了23.5%，平均行駛距離成本減少了11.4%，基于?？空具x址的方法能顯著提升系統(tǒng)運(yùn)行效率。

3 結(jié)論

a.運(yùn)用改進(jìn)K-means聚類算法和重心位置法進(jìn)行了停靠站選址研究，并以系統(tǒng)運(yùn)營成本最小為目標(biāo)，建立了基于停靠站的RFT協(xié)調(diào)調(diào)度模型。

b.算例表明，基于?？空具x址的協(xié)調(diào)調(diào)度方法能顯著降低系統(tǒng)總成本，運(yùn)行效率提升效果顯著。

下階段的研究應(yīng)是乘客時(shí)空分布影響下的響應(yīng)型接駁公交協(xié)調(diào)調(diào)度研究，同時(shí)具有預(yù)約需求、實(shí)時(shí)需求下的響應(yīng)型接駁公交協(xié)調(diào)調(diào)度研究。