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

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

0 引言

在城市邊緣地區(qū)，居民居住區(qū)域較分散，軌道交通和常規(guī)公交的覆蓋率較低，公共交通設(shè)施有限，居民出行起訖點距離公共交通站點距離較遠，難以實現(xiàn)居民出行便捷、低成本的“門到門”的服務(wù)。響應(yīng)型接駁公交(Responsive Feeder Transit，RFT)如圖1所示，根據(jù)乘客預(yù)約或?qū)崟r申請，確定乘客接送時間、分配適宜車型、規(guī)劃最佳車輛線路及途經(jīng)停靠站，能為地鐵等干線公交提供高效、便捷的接駁服務(wù)。根據(jù)響應(yīng)方式的不同，可以分為基于乘客需求點(即乘客上傳的上下車位置)的車輛路徑優(yōu)化模型與基于停靠站(即車輛實際?？课恢?選址的車輛路徑優(yōu)化模型對RFT系統(tǒng)路徑進行調(diào)度優(yōu)化?；诔丝托枨簏c的車輛路徑優(yōu)化模型是指響應(yīng)每一位乘客上傳的需求點進行?？糠?wù)，而基于停靠站選址的車輛路徑優(yōu)化模型則是對乘客需求點進行整合，確定停靠位置及每個位置服務(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)化中探討了駐車點的選址分配問題。響應(yīng)型接駁公交的相關(guān)研究主要集中于車輛路徑優(yōu)化[13-14]，運行路徑幾乎均是根據(jù)乘客需求點來優(yōu)化的，很少基于?？空具x址來進行車輛路徑優(yōu)化；而且?？空具x址研究中，對乘客出行因素的考慮較為單一，實際上，不同乘客的出行行為特性、出行目的存在差異，會影響到乘客對上車站點的選擇，從而影響車輛運營路徑。

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

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

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

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

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

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

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

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

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

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

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

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

(1)

(2)

1.3 車輛路徑模型

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

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

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

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

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

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

2 算例分析

尚雙塘地鐵站是長沙市軌道交通1號線一期工程的終點站，地處長沙郊區(qū)三環(huán)外，周邊公共交通系統(tǒng)不完善，附近居民分散，出行分布不均勻，符合需求RFT的設(shè)置初衷，本文擬以尚雙塘地鐵站為仿真案例進行研究，設(shè)定地鐵站點坐標為(0，0)，正東方向為X軸正方向，正北方向為Y軸正方向建立直角坐標系。服務(wù)半徑是R=4 000 m的圓形區(qū)域，接駁車輛的速度為v=30 km/h。設(shè)定兩種類型的接駁車輛：車型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內(nèi)乘客需求90位，乘客需求分布情況如圖5、圖6所示。

圖5 基于?？空具x址的協(xié)調(diào)調(diào)度結(jié)果圖Figure 5 Coordinated dispatching results based on station location

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

通過改進K-means聚類算法生成了20個聚類簇，基于重心位置法確定的?？空具x址表2所示。

表2 停靠站選址Table 2 Location of stops?？空揪幪朮坐標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編程，應(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址的、基于需求點的車輛協(xié)調(diào)調(diào)度模型獲得優(yōu)化的車輛路徑和發(fā)出車型(其中基于需求點的協(xié)調(diào)調(diào)度模型與基于?？空具x址的基本相同，只需將停靠站改為需求點)，基于停靠站選址的協(xié)調(diào)調(diào)度結(jié)果如表3與圖5所示，基于需求點的協(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序號發(fā)車時刻到達時刻發(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%,運行距離為42.84 km,系統(tǒng)總成本為135.86元。

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

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

3 結(jié)論

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

b.算例表明，基于停靠站選址的協(xié)調(diào)調(diào)度方法能顯著降低系統(tǒng)總成本，運行效率提升效果顯著。

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