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

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

0 引言

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

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

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

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

1 基于停靠站選址的路徑優(yōu)化

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

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

本文分停靠站選址與車(chē)輛路徑優(yōu)化兩步，?？空镜倪x址又由兩步確定：首先根據(jù)乘客需求分布采用K-means聚類，在乘客最大步行距離閾值下基于聚類分析對(duì)乘客需求點(diǎn)進(jìn)行空間聚類，確定各聚類簇的質(zhì)心；然后考慮乘客需求的多樣性和差異性，基于重心位置法確定停靠站選址。在?？空具x址確定之后，再由系統(tǒng)對(duì)RFT車(chē)輛路徑進(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]確定了各聚類簇對(duì)應(yīng)的?？空具x址。本文考慮乘客年齡、出行目的、支付意愿、違背時(shí)間窗等4個(gè)影響來(lái)運(yùn)用重心位置法調(diào)整聚類簇pi所有乘客位置：

(1)

(2)

1.3 車(chē)輛路徑模型

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

根據(jù)上述假設(shè)，預(yù)約需求、固定發(fā)車(chē)時(shí)間下響應(yīng)型接駁公交發(fā)出車(chē)型和運(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)為車(chē)輛容量約束； 式(7)為車(chē)輛行程時(shí)間約束； 式(8)表示車(chē)輛單次運(yùn)行線路長(zhǎng)度約束； 式(9)、 式(10)為車(chē)輛到達(dá)?？空緋j的時(shí)間約束。

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

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

2 算例分析

尚雙塘地鐵站是長(zhǎng)沙市軌道交通1號(hào)線一期工程的終點(diǎn)站，地處長(zhǎng)沙郊區(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ū)域，接駁車(chē)輛的速度為v=30 km/h。設(shè)定兩種類型的接駁車(chē)輛：車(chē)型A有8輛、容量為15人/輛、啟動(dòng)成本5元/輛、γA=0.001 5元/m；車(chē)型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 基于?？空具x址的協(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

通過(guò)改進(jìn)K-means聚類算法生成了20個(gè)聚類簇，基于重心位置法確定的?？空具x址表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、鏈長(zhǎng)N為200。調(diào)用模擬退火算法分別應(yīng)用基于?？空具x址的、基于需求點(diǎn)的車(chē)輛協(xié)調(diào)調(diào)度模型獲得優(yōu)化的車(chē)輛路徑和發(fā)出車(chē)型(其中基于需求點(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 基于停靠站選址的協(xié)調(diào)調(diào)度結(jié)果表Table 3 Table of coordinated dispatching results based on station location序號(hào)發(fā)車(chē)時(shí)刻到達(dá)時(shí)刻發(fā)出車(chē)型載客量/人車(chē)輛路徑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ā)車(chē)時(shí)刻到達(dá)時(shí)刻發(fā)出車(chē)型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ā)出車(chē)型B5次，乘客的人均坐乘距離476 m/人、人均總成本1.510元/人，平均行駛距離成本0.003 1元/m；② 基于需求點(diǎn)的方法，發(fā)出車(chē)型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)行了?？空具x址研究，并以系統(tǒng)運(yùn)營(yíng)成本最小為目標(biāo)，建立了基于?？空镜腞FT協(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)度研究。