定制公交站點和線路規(guī)劃研究

馬繼輝 王 飛 王 嬌 涂文苑

（北京交通大學(xué)交通運輸學(xué)院，北京 100044）

定制公交站點和線路規(guī)劃研究

馬繼輝 王 飛 王 嬌 涂文苑

（北京交通大學(xué)交通運輸學(xué)院，北京 100044）

近幾年來，定制公交作為一種新興的公交服務(wù)模式，在各大城市快速興起，成為社會各界關(guān)注的熱點。本文基于乘客出行需求，研究“多起點—多目的地”模式的定制公交站點和線路規(guī)劃問題，提出了定制公交站點規(guī)劃方法，構(gòu)建了定制公交線路規(guī)劃模型。通過實例，驗證了模型的正確性和可行性。

定制公交；站點規(guī)劃；線路規(guī)劃；蟻群算法

引言

近幾年來，隨著信息和通訊技術(shù)的迅猛發(fā)展，一種新的公交服務(wù)模式——定制公交呈現(xiàn)在公眾面前。定制公交是介于常規(guī)公交與出租車之間的一種公共交通服務(wù)模式，是為具有相同出行起訖點和出行時間等出行需求的人群量身定制的一種公共交通服務(wù)[1]。定制公交因其直達(dá)、快捷、舒適、經(jīng)濟(jì)等特點，吸引了較多自駕車通勤者，有效緩解了城市交通擁堵和環(huán)境污染等問題。目前，國內(nèi)各大城市已陸續(xù)推出這種交通方式。

定制公交上下車區(qū)域內(nèi)的站點和線路規(guī)劃作為整個定制公交線網(wǎng)規(guī)劃的關(guān)鍵一步，對乘客的出行成本和公交企業(yè)的運營成本起著舉足輕重的作用。科學(xué)合理的站點設(shè)置和線路規(guī)劃能有效減少乘客走行時間和公交企業(yè)運營成本，滿足大部分乘客的出行需求，使定制公交資源得到最大程度的利用，提高定制公交吸引力，因此必須科學(xué)、系統(tǒng)的對定制公交站點和線路規(guī)劃進(jìn)行研究。

1 問題分析

科學(xué)合理的定制公交站點和線路規(guī)劃能增加定制公交的吸引力，提升定制公交服務(wù)品質(zhì)，提高定制公交上座率，緩解城市交通擁堵和減少環(huán)境污染。

JF Potts等人（2010）研究了美國和加拿大近十年以來的定制公交服務(wù)，提出了分別適用于大、中、小城市及鄉(xiāng)村的不同定制公交模式，為不同地區(qū)的定制公交運營組織提供了結(jié)合當(dāng)?shù)貙嶋H情況決定是否開行定制公交以及如何開行定制公交的指導(dǎo)意見[2]。Scott Le Vine等人（2014）調(diào)查研究了“點對點”以及“往返行程”兩種模式的定制公交，預(yù)測出倫敦未來“點對點”定制公交人數(shù)是“往返行程”定制公交人數(shù)的三到四倍，“點對點”定制公交可以作為公共交通的替代方式，“往返行程”定制公交可作為“點對點”定制公交的一種補充[3]。T Liu和A Ceder（2015）研究了中國定制公交的發(fā)展背景，分析了中國定制公交的設(shè)計運營過程，總結(jié)了定制公交在中國的發(fā)展利弊與趨勢，為定制公交運營者、政策制定者及學(xué)術(shù)研究者提供了參考資料[4]。李彬（2013）分析了城市居民出行方式的變化和減少私家車出行的各項舉措，得出應(yīng)提供多層次服務(wù)提升公交吸引力，并以北京市和西安市為實例，探討了定制公交的發(fā)展市場，提出了定制公交車型開發(fā)的基本原則，初步規(guī)劃了定制公交線路，為后期運營提供了理論基礎(chǔ)[5]。張敏捷等人（2014）針對單目的地的定制公交線網(wǎng)優(yōu)化問題，提出了以線網(wǎng)覆蓋率最大、上座率最高、運營投入最少為目標(biāo)函數(shù)的線路規(guī)劃模型，改進(jìn)蟻群算法進(jìn)行求解，并通過實例分析證明了算法的有效性[6]。王中航和王如松（2015）分析了大城市面臨的交通擁堵及霧霾效應(yīng)等現(xiàn)象，提出應(yīng)從管理角度出發(fā)，提升常規(guī)公交服務(wù)水平并推行中高級公共交通，以此解決城市交通問題，用定制公交有效替換部分小汽車出行，引導(dǎo)交通出行結(jié)構(gòu)改變，并分析了定制公交所帶來的自然、經(jīng)濟(jì)和社會效益，為城市交通管理提供了參考意見[7]。國內(nèi)外研究定制公交的理論和方法較少，對于“多起點—多目的地”模式的定制公交站點和線路規(guī)劃研究更是少之又少。

定制公交開行模式有四種：單起點—單目的地、單起點—多目的地、多起點—單目的地、多起點—多目的地。在這四種開行模式中，“多起點—多目的地”模式最為復(fù)雜，本文基于此種開行模式進(jìn)行研究，結(jié)合常規(guī)公交和已有的定制公交規(guī)劃經(jīng)驗，提出了基于出行需求的站點和線路規(guī)劃方法，具體思路如下：

（1）上下車站點規(guī)劃。定制公交上下車站點是定制公交線路的組成要素，站點規(guī)劃的合理與否直接影響到整個定制公交線路規(guī)劃的成敗。若站點設(shè)置過多，雖能減少乘客的走行時間和距離，但頻繁的停站也會浪費乘客的出行時間；反之，若站點設(shè)置過少，則會增加乘客的走行時間和距離，降低定制公交的吸引力，這兩種情況均不利于定制公交的長期發(fā)展。應(yīng)根據(jù)乘客出行起點和目的地的分布情況，將相近的需求集中到一個站點。針對“多起點—多目的地”模式的定制公交站點規(guī)劃，需要將上車區(qū)域站點和下車區(qū)域站點分別進(jìn)行規(guī)劃。

（2）線路規(guī)劃模型。定制公交的開行是為了給出行需求相類似的乘客提供一種舒適快捷的乘車環(huán)境。定制公交線路里程的長短直接影響到乘客的出行時間成本和公交企業(yè)的運營成本，將線路里程最小化作為目標(biāo)函數(shù)，構(gòu)建線路規(guī)劃模型。

（3）設(shè)計求解算法。定制公交線路規(guī)劃問題可以歸為車輛路徑問題（VRP），VRP問題可通過改進(jìn)的蟻群算法進(jìn)行求解。對于“多起點—多目的地”模式的定制公交線路規(guī)劃問題，依據(jù)定制公交的線路特點，需要綜合考慮上車區(qū)域的公交線路和下車區(qū)域的公交線路，使其總運營里程最小。

2 定制公交站點和線路規(guī)劃模型

2.1 定制公交站點規(guī)劃方法

定制公交站點的合理布局是定制公交線路規(guī)劃的前提保障，由于乘客出行需求時間和地點的不同，不可能做到每個需求點均設(shè)置一個站點，因此有必要對乘客出行需求數(shù)據(jù)進(jìn)行聚類分析，合理布局定制公交站點。

K-means聚類算法是一種基于距離相似性度量而劃分的聚類算法。K-means的基本思想：已知一個數(shù)據(jù)集，并給定該數(shù)據(jù)集要被聚類的數(shù)目K，首先隨機選取K個樣本作為初始簇類中心，然后根據(jù)相似性度量函數(shù)采用迭代的方法，計算未劃分的樣本與每個簇類中心點之間的距離，將未劃分的每個樣本歸為與它距離最小的那個簇類中心所在的簇類中，在每個樣本均計算分配完之后，通過計算每個簇類內(nèi)所有樣本的平均值，移動簇類中心重新劃分聚類，直到類內(nèi)誤差平方和數(shù)值最小且沒有變化時為止[8]。

基于K-means聚類算法分別對定制公交上車區(qū)域和下車區(qū)域的出行需求數(shù)據(jù)進(jìn)行聚類分析，具體步驟如下：

Step 1:對出行需求數(shù)據(jù)進(jìn)行預(yù)處理，得到所有需求點的坐標(biāo)集；

Step 2:根據(jù)需求數(shù)據(jù)分布情況，確定聚類數(shù)目K，結(jié)合運營經(jīng)驗，選定K個初始聚類中心點ZK；

Step 3:對每個需求點，計算與每個聚類中心點間的距離，進(jìn)行比對選出最小距離的聚類中心點，將這個需求點放入到該簇類CK中；

Step 5:根據(jù)公式（1），計算類內(nèi)誤差平方和

Step 6:對E值進(jìn)行多次迭代計算，當(dāng)E值變化停止或不大時，結(jié)束運行；否則，重復(fù)Step3到Step5。

針對“多起點—多目的地”模式的定制公交問題，使用K-means聚類算法我們可分別得到上車區(qū)域的站點和下車區(qū)域的站點，通過將每個出行需求進(jìn)行編號，還可得到每個需求的上下車站點匹配表。

2.2 定制公交線路規(guī)劃模型

模型的建立基于如下假設(shè)：

（1）每個出行需求只對應(yīng)一個上車站點和一個下車站點（上車區(qū)域的線路會決定下車區(qū)域的線路）；

（2）上車區(qū)域到下車區(qū)域的中間路程是固定值。

約束條件包括：

（2）線路長度滿足最低要求，保證一定的服務(wù)覆蓋率，即L（P）≥ Lmin（P）。

2.3 求解模型

該問題可以歸為車輛路徑問題（VRP），可通過改進(jìn)基本蟻群算法進(jìn)行求解[9]。本文設(shè)計的求解算法的基本思想：使用改進(jìn)的基本蟻群算法求解上車區(qū)域線路，結(jié)合每個需求的上下車站點匹配表，得到下車區(qū)域線路，通過站點間距矩陣計算整個線路的距離，繼而更新全局信息素，經(jīng)過多次迭代得到最終解。該問題的解由三部分組成：定制公交線路數(shù)量，每條線路的行車路徑和每個站點的上下車人數(shù)。所求解由節(jié)點鏈表達(dá)，為該車輛通過的上下車站點和上下車人數(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)前蟻群序號ag=1;

Step 3:當(dāng)前蟻群ag中的螞蟻數(shù)量as=1；

Step 4:對螞蟻as，置于上車區(qū)域任意NS（未被完全服務(wù)的站點集合）站點上，按站點間的信息素濃度搜索下一個有出行需求的站點，更新禁忌表tabuas，更新該站點需求狀態(tài)和線路狀態(tài)；

Step 5:若該站點剩余需求量為0，則將該站點加入DS節(jié)點集（已被完全服務(wù)的站點集合），并將該站點在NS節(jié)點集上去除；

Step 6:若NS不為空且該線路剩余服務(wù)量為0，輸出該條上車區(qū)域線路，蟻群ag中的螞蟻數(shù)量as=as+1，返回Step 4；

Step 7:若NS為空，則蟻群ag的一次迭代結(jié)束，輸出該蟻群的上車區(qū)域線路解，然后通過上下車站點匹配表得到下車區(qū)域線路，記錄并計算整個線路的總里程。ag=ag+1；

Step 8:若ag ≤G，返回Step 3。否則，更新最優(yōu)解和全局信息素，iter=iter+1；

Step 9:若iter ≤ N，返回Step 2。否則，輸出最優(yōu)解。

3 實證研究

選擇北京市“梨園—國貿(mào)”的乘客出行需求數(shù)據(jù)作為研究案例，進(jìn)行定制公交站點和線路規(guī)劃研究，驗證本文所提出的求解算法的有效性。

首先，通過K-means算法對乘客出行需求數(shù)據(jù)進(jìn)行聚類分析，分別得到上車區(qū)域和下車區(qū)域的備選站點及相對應(yīng)的上下車人數(shù)，見表1和表2，同時能得到每個需求的上下車站點匹配表（限于篇幅該項數(shù)據(jù)省略）。

從運行結(jié)果可以看出，該算法優(yōu)先選出出行需求聚集性高的線路，其余較分散的出行需求通過后期線路招募的形式得到滿足。該方案中，開通線路的上座率達(dá)到了96%，75%的線路實現(xiàn)了滿載運營，車輛運力得到了最大化利用。同時，每條線路的上下車站點至少為3個，保證了一定的定制公交服務(wù)覆蓋率。

表2 下車區(qū)域站點及下車人數(shù)

表3 定制公交線路方案

4 結(jié)論

定制公交作為對傳統(tǒng)公交的一種有效補充，豐富了市民的出行方式，提升了公交服務(wù)水平，因其一站式直達(dá)、乘車環(huán)境舒適等特點受到更多出行者的青睞。積極開展定制公交的服務(wù)和線路研究，對于改善城市公共交通運營管理水平和緩解城市交通擁堵有重大意義。

本文基于乘客出行需求，通過K-means聚類算法分別得到定制公交上車區(qū)域和下車區(qū)域內(nèi)的站點，基于運營成本最低原則構(gòu)建了定制公交線路規(guī)劃模型，并設(shè)計了一種有效的求解算法。本文的研究成果在定制公交理論和實際應(yīng)用中具有指導(dǎo)作用，對推動現(xiàn)代城市公共交通健康發(fā)展有一定的現(xiàn)實意義。

[ 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]. 長安大學(xué), 2013.

[ 6 ] 張敏捷, 馮偲, 呂晨曦,等. 定制公交線路優(yōu)化模型及求解算法[C]// 2014第九屆中國智能交通年會大會論文集. 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