馬繼輝 王 飛 王 嬌 涂文苑
(北京交通大學(xué)交通運(yùn)輸學(xué)院,北京 100044)
定制公交站點(diǎn)和線路規(guī)劃研究
馬繼輝 王 飛 王 嬌 涂文苑
(北京交通大學(xué)交通運(yùn)輸學(xué)院,北京 100044)
近幾年來(lái),定制公交作為一種新興的公交服務(wù)模式,在各大城市快速興起,成為社會(huì)各界關(guān)注的熱點(diǎn)。本文基于乘客出行需求,研究“多起點(diǎn)—多目的地”模式的定制公交站點(diǎn)和線路規(guī)劃問題,提出了定制公交站點(diǎn)規(guī)劃方法,構(gòu)建了定制公交線路規(guī)劃模型。通過(guò)實(shí)例,驗(yàn)證了模型的正確性和可行性。
定制公交;站點(diǎn)規(guī)劃;線路規(guī)劃;蟻群算法
近幾年來(lái),隨著信息和通訊技術(shù)的迅猛發(fā)展,一種新的公交服務(wù)模式——定制公交呈現(xiàn)在公眾面前。定制公交是介于常規(guī)公交與出租車之間的一種公共交通服務(wù)模式,是為具有相同出行起訖點(diǎn)和出行時(shí)間等出行需求的人群量身定制的一種公共交通服務(wù)[1]。定制公交因其直達(dá)、快捷、舒適、經(jīng)濟(jì)等特點(diǎn),吸引了較多自駕車通勤者,有效緩解了城市交通擁堵和環(huán)境污染等問題。目前,國(guó)內(nèi)各大城市已陸續(xù)推出這種交通方式。
定制公交上下車區(qū)域內(nèi)的站點(diǎn)和線路規(guī)劃作為整個(gè)定制公交線網(wǎng)規(guī)劃的關(guān)鍵一步,對(duì)乘客的出行成本和公交企業(yè)的運(yùn)營(yíng)成本起著舉足輕重的作用??茖W(xué)合理的站點(diǎn)設(shè)置和線路規(guī)劃能有效減少乘客走行時(shí)間和公交企業(yè)運(yùn)營(yíng)成本,滿足大部分乘客的出行需求,使定制公交資源得到最大程度的利用,提高定制公交吸引力,因此必須科學(xué)、系統(tǒng)的對(duì)定制公交站點(diǎn)和線路規(guī)劃進(jìn)行研究。
科學(xué)合理的定制公交站點(diǎn)和線路規(guī)劃能增加定制公交的吸引力,提升定制公交服務(wù)品質(zhì),提高定制公交上座率,緩解城市交通擁堵和減少環(huán)境污染。
JF Potts等人(2010)研究了美國(guó)和加拿大近十年以來(lái)的定制公交服務(wù),提出了分別適用于大、中、小城市及鄉(xiāng)村的不同定制公交模式,為不同地區(qū)的定制公交運(yùn)營(yíng)組織提供了結(jié)合當(dāng)?shù)貙?shí)際情況決定是否開行定制公交以及如何開行定制公交的指導(dǎo)意見[2]。Scott Le Vine等人(2014)調(diào)查研究了“點(diǎn)對(duì)點(diǎn)”以及“往返行程”兩種模式的定制公交,預(yù)測(cè)出倫敦未來(lái)“點(diǎn)對(duì)點(diǎn)”定制公交人數(shù)是“往返行程”定制公交人數(shù)的三到四倍,“點(diǎn)對(duì)點(diǎn)”定制公交可以作為公共交通的替代方式,“往返行程”定制公交可作為“點(diǎn)對(duì)點(diǎn)”定制公交的一種補(bǔ)充[3]。T Liu和A Ceder(2015)研究了中國(guó)定制公交的發(fā)展背景,分析了中國(guó)定制公交的設(shè)計(jì)運(yùn)營(yíng)過(guò)程,總結(jié)了定制公交在中國(guó)的發(fā)展利弊與趨勢(shì),為定制公交運(yùn)營(yíng)者、政策制定者及學(xué)術(shù)研究者提供了參考資料[4]。李彬(2013)分析了城市居民出行方式的變化和減少私家車出行的各項(xiàng)舉措,得出應(yīng)提供多層次服務(wù)提升公交吸引力,并以北京市和西安市為實(shí)例,探討了定制公交的發(fā)展市場(chǎng),提出了定制公交車型開發(fā)的基本原則,初步規(guī)劃了定制公交線路,為后期運(yùn)營(yíng)提供了理論基礎(chǔ)[5]。張敏捷等人(2014)針對(duì)單目的地的定制公交線網(wǎng)優(yōu)化問題,提出了以線網(wǎng)覆蓋率最大、上座率最高、運(yùn)營(yíng)投入最少為目標(biāo)函數(shù)的線路規(guī)劃模型,改進(jìn)蟻群算法進(jìn)行求解,并通過(guò)實(shí)例分析證明了算法的有效性[6]。王中航和王如松(2015)分析了大城市面臨的交通擁堵及霧霾效應(yīng)等現(xiàn)象,提出應(yīng)從管理角度出發(fā),提升常規(guī)公交服務(wù)水平并推行中高級(jí)公共交通,以此解決城市交通問題,用定制公交有效替換部分小汽車出行,引導(dǎo)交通出行結(jié)構(gòu)改變,并分析了定制公交所帶來(lái)的自然、經(jīng)濟(jì)和社會(huì)效益,為城市交通管理提供了參考意見[7]。國(guó)內(nèi)外研究定制公交的理論和方法較少,對(duì)于“多起點(diǎn)—多目的地”模式的定制公交站點(diǎn)和線路規(guī)劃研究更是少之又少。
定制公交開行模式有四種:?jiǎn)纹瘘c(diǎn)—單目的地、單起點(diǎn)—多目的地、多起點(diǎn)—單目的地、多起點(diǎn)—多目的地。在這四種開行模式中,“多起點(diǎn)—多目的地”模式最為復(fù)雜,本文基于此種開行模式進(jìn)行研究,結(jié)合常規(guī)公交和已有的定制公交規(guī)劃經(jīng)驗(yàn),提出了基于出行需求的站點(diǎn)和線路規(guī)劃方法,具體思路如下:
(1)上下車站點(diǎn)規(guī)劃。定制公交上下車站點(diǎn)是定制公交線路的組成要素,站點(diǎn)規(guī)劃的合理與否直接影響到整個(gè)定制公交線路規(guī)劃的成敗。若站點(diǎn)設(shè)置過(guò)多,雖能減少乘客的走行時(shí)間和距離,但頻繁的停站也會(huì)浪費(fèi)乘客的出行時(shí)間;反之,若站點(diǎn)設(shè)置過(guò)少,則會(huì)增加乘客的走行時(shí)間和距離,降低定制公交的吸引力,這兩種情況均不利于定制公交的長(zhǎng)期發(fā)展。應(yīng)根據(jù)乘客出行起點(diǎn)和目的地的分布情況,將相近的需求集中到一個(gè)站點(diǎn)。針對(duì)“多起點(diǎn)—多目的地”模式的定制公交站點(diǎn)規(guī)劃,需要將上車區(qū)域站點(diǎn)和下車區(qū)域站點(diǎn)分別進(jìn)行規(guī)劃。
(2)線路規(guī)劃模型。定制公交的開行是為了給出行需求相類似的乘客提供一種舒適快捷的乘車環(huán)境。定制公交線路里程的長(zhǎng)短直接影響到乘客的出行時(shí)間成本和公交企業(yè)的運(yùn)營(yíng)成本,將線路里程最小化作為目標(biāo)函數(shù),構(gòu)建線路規(guī)劃模型。
(3)設(shè)計(jì)求解算法。定制公交線路規(guī)劃問題可以歸為車輛路徑問題(VRP),VRP問題可通過(guò)改進(jìn)的蟻群算法進(jìn)行求解。對(duì)于“多起點(diǎn)—多目的地”模式的定制公交線路規(guī)劃問題,依據(jù)定制公交的線路特點(diǎn),需要綜合考慮上車區(qū)域的公交線路和下車區(qū)域的公交線路,使其總運(yùn)營(yíng)里程最小。
2.1 定制公交站點(diǎn)規(guī)劃方法
定制公交站點(diǎn)的合理布局是定制公交線路規(guī)劃的前提保障,由于乘客出行需求時(shí)間和地點(diǎn)的不同,不可能做到每個(gè)需求點(diǎn)均設(shè)置一個(gè)站點(diǎn),因此有必要對(duì)乘客出行需求數(shù)據(jù)進(jìn)行聚類分析,合理布局定制公交站點(diǎn)。
K-means聚類算法是一種基于距離相似性度量而劃分的聚類算法。K-means的基本思想:已知一個(gè)數(shù)據(jù)集,并給定該數(shù)據(jù)集要被聚類的數(shù)目K,首先隨機(jī)選取K個(gè)樣本作為初始簇類中心,然后根據(jù)相似性度量函數(shù)采用迭代的方法,計(jì)算未劃分的樣本與每個(gè)簇類中心點(diǎn)之間的距離,將未劃分的每個(gè)樣本歸為與它距離最小的那個(gè)簇類中心所在的簇類中,在每個(gè)樣本均計(jì)算分配完之后,通過(guò)計(jì)算每個(gè)簇類內(nèi)所有樣本的平均值,移動(dòng)簇類中心重新劃分聚類,直到類內(nèi)誤差平方和數(shù)值最小且沒有變化時(shí)為止[8]。
基于K-means聚類算法分別對(duì)定制公交上車區(qū)域和下車區(qū)域的出行需求數(shù)據(jù)進(jìn)行聚類分析,具體步驟如下:
Step 1:對(duì)出行需求數(shù)據(jù)進(jìn)行預(yù)處理,得到所有需求點(diǎn)的坐標(biāo)集;
Step 2:根據(jù)需求數(shù)據(jù)分布情況,確定聚類數(shù)目K,結(jié)合運(yùn)營(yíng)經(jīng)驗(yàn),選定K個(gè)初始聚類中心點(diǎn)ZK;
Step 3:對(duì)每個(gè)需求點(diǎn),計(jì)算與每個(gè)聚類中心點(diǎn)間的距離,進(jìn)行比對(duì)選出最小距離的聚類中心點(diǎn),將這個(gè)需求點(diǎn)放入到該簇類CK中;
Step 5:根據(jù)公式(1),計(jì)算類內(nèi)誤差平方和
Step 6:對(duì)E值進(jìn)行多次迭代計(jì)算,當(dāng)E值變化停止或不大時(shí),結(jié)束運(yùn)行;否則,重復(fù)Step3到Step5。
針對(duì)“多起點(diǎn)—多目的地”模式的定制公交問題,使用K-means聚類算法我們可分別得到上車區(qū)域的站點(diǎn)和下車區(qū)域的站點(diǎn),通過(guò)將每個(gè)出行需求進(jìn)行編號(hào),還可得到每個(gè)需求的上下車站點(diǎn)匹配表。
2.2 定制公交線路規(guī)劃模型
模型的建立基于如下假設(shè):
(1)每個(gè)出行需求只對(duì)應(yīng)一個(gè)上車站點(diǎn)和一個(gè)下車站點(diǎn)(上車區(qū)域的線路會(huì)決定下車區(qū)域的線路);
(2)上車區(qū)域到下車區(qū)域的中間路程是固定值。
約束條件包括:
(2)線路長(zhǎng)度滿足最低要求,保證一定的服務(wù)覆蓋率,即L(P)≥ Lmin(P)。
2.3 求解模型
該問題可以歸為車輛路徑問題(VRP),可通過(guò)改進(jìn)基本蟻群算法進(jìn)行求解[9]。本文設(shè)計(jì)的求解算法的基本思想:使用改進(jìn)的基本蟻群算法求解上車區(qū)域線路,結(jié)合每個(gè)需求的上下車站點(diǎn)匹配表,得到下車區(qū)域線路,通過(guò)站點(diǎn)間距矩陣計(jì)算整個(gè)線路的距離,繼而更新全局信息素,經(jīng)過(guò)多次迭代得到最終解。該問題的解由三部分組成:定制公交線路數(shù)量,每條線路的行車路徑和每個(gè)站點(diǎn)的上下車人數(shù)。所求解由節(jié)點(diǎn)鏈表達(dá),為該車輛通過(guò)的上下車站點(diǎn)和上下車人數(shù)的有序組合,如Pi={Ai1,Ai2,…,Bi1,Bi2…;u(Ai1),u(Ai2),…,u(Bi1),u(Bi2),…}。求解算法的具體步驟如下:
Step 1:參數(shù)初始化。確定蟻群總數(shù)G和迭代次數(shù)N,當(dāng)前迭代次數(shù)iter=1;
Step 2:當(dāng)前蟻群序號(hào)ag=1;
Step 3:當(dāng)前蟻群ag中的螞蟻數(shù)量as=1;
Step 4:對(duì)螞蟻as,置于上車區(qū)域任意NS(未被完全服務(wù)的站點(diǎn)集合)站點(diǎn)上,按站點(diǎn)間的信息素濃度搜索下一個(gè)有出行需求的站點(diǎn),更新禁忌表tabuas,更新該站點(diǎn)需求狀態(tài)和線路狀態(tài);
Step 5:若該站點(diǎn)剩余需求量為0,則將該站點(diǎn)加入DS節(jié)點(diǎn)集(已被完全服務(wù)的站點(diǎn)集合),并將該站點(diǎn)在NS節(jié)點(diǎn)集上去除;
Step 6:若NS不為空且該線路剩余服務(wù)量為0,輸出該條上車區(qū)域線路,蟻群ag中的螞蟻數(shù)量as=as+1,返回Step 4;
Step 7:若NS為空,則蟻群ag的一次迭代結(jié)束,輸出該蟻群的上車區(qū)域線路解,然后通過(guò)上下車站點(diǎn)匹配表得到下車區(qū)域線路,記錄并計(jì)算整個(gè)線路的總里程。ag=ag+1;
Step 8:若ag ≤G,返回Step 3。否則,更新最優(yōu)解和全局信息素,iter=iter+1;
Step 9:若iter ≤ N,返回Step 2。否則,輸出最優(yōu)解。
選擇北京市“梨園—國(guó)貿(mào)”的乘客出行需求數(shù)據(jù)作為研究案例,進(jìn)行定制公交站點(diǎn)和線路規(guī)劃研究,驗(yàn)證本文所提出的求解算法的有效性。
首先,通過(guò)K-means算法對(duì)乘客出行需求數(shù)據(jù)進(jìn)行聚類分析,分別得到上車區(qū)域和下車區(qū)域的備選站點(diǎn)及相對(duì)應(yīng)的上下車人數(shù),見表1和表2,同時(shí)能得到每個(gè)需求的上下車站點(diǎn)匹配表(限于篇幅該項(xiàng)數(shù)據(jù)省略)。
從運(yùn)行結(jié)果可以看出,該算法優(yōu)先選出出行需求聚集性高的線路,其余較分散的出行需求通過(guò)后期線路招募的形式得到滿足。該方案中,開通線路的上座率達(dá)到了96%,75%的線路實(shí)現(xiàn)了滿載運(yùn)營(yíng),車輛運(yùn)力得到了最大化利用。同時(shí),每條線路的上下車站點(diǎn)至少為3個(gè),保證了一定的定制公交服務(wù)覆蓋率。
表2 下車區(qū)域站點(diǎn)及下車人數(shù)
表3 定制公交線路方案
定制公交作為對(duì)傳統(tǒng)公交的一種有效補(bǔ)充,豐富了市民的出行方式,提升了公交服務(wù)水平,因其一站式直達(dá)、乘車環(huán)境舒適等特點(diǎn)受到更多出行者的青睞。積極開展定制公交的服務(wù)和線路研究,對(duì)于改善城市公共交通運(yùn)營(yíng)管理水平和緩解城市交通擁堵有重大意義。
本文基于乘客出行需求,通過(guò)K-means聚類算法分別得到定制公交上車區(qū)域和下車區(qū)域內(nèi)的站點(diǎn),基于運(yùn)營(yíng)成本最低原則構(gòu)建了定制公交線路規(guī)劃模型,并設(shè)計(jì)了一種有效的求解算法。本文的研究成果在定制公交理論和實(shí)際應(yīng)用中具有指導(dǎo)作用,對(duì)推動(dòng)現(xiàn)代城市公共交通健康發(fā)展有一定的現(xiàn)實(shí)意義。
[ 1 ] 徐康明, 李佳玲, 馮浚等. 定制公交服務(wù)初探[J]. 城市交通, 2013, 11(5): 24-27.
[ 2 ] Potts J F, Marshall M A, Crockett E C, et al. A Guide for Planning and Operating Flexible Public Transportation Services [M]. Tcrp Report, 2010.
[ 3 ] Vine S L, Lee-Gosselin M, Sivakumar A, et al. A new approach to predict the market and impacts of roundtrip and point-to-point carsharing systems: Case study of London [J]. Transportation Research Part D Transport & Environment, 2014, 32:218-229.
[ 4 ] Liu T, Ceder A. Analysis of a new public-transportservice concept: Customized bus in China [J]. Transport Policy, 2015, 39:63-76.
[ 5 ] 李彬. 定制公交與定制公交客車的研究[D]. 長(zhǎng)安大學(xué), 2013.
[ 6 ] 張敏捷, 馮偲, 呂晨曦,等. 定制公交線路優(yōu)化模型及求解算法[C]// 2014第九屆中國(guó)智能交通年會(huì)大會(huì)論文集. 2014.
[ 7 ] 王中航, 王如松. 北京城市交通適應(yīng)性管理--以定制公交為例[J]. 現(xiàn)代城市研究, 2015(03).
[ 8 ] 李薈嬈. K-means 聚類方法的改進(jìn)及其應(yīng)用[D]. 東北農(nóng)業(yè)大學(xué), 2014.
[ 9 ] 楊劍峰. 蟻群算法及其應(yīng)用研究[D]. 浙江大學(xué)電氣工程學(xué)院 浙江大學(xué), 2007.
The study of customized bus site and route planning
(School of Traffi c and Transportation,
Beijing Jiaotong University, Beijing 100044, China)
Ma Jihui Wang Fei Wang Jiao Tu Wenyuan
In recent years, customized bus as a new public transport mode has been springing up in some big cities and become the focus of attention of the community. This paper studies the customized bus site and route planning problem of the "multi- origin and multi-destination" mode, puts forward the planning method of customized bus site based on the trip demand of passengers, establishes the customized bus route planning model and designs an algorithm for solving the model. The case shows the effectiveness of the algorithm.
customized bus; site planning; route planning; ant colony algorithm
U491.1+2
A