周佳麗,鄧躍進

(武漢大學(xué) 測繪遙感信息工程國家重點實驗室,武漢 430079)

基于時刻表的多模式交通網(wǎng)絡(luò)路徑規(guī)劃①

周佳麗,鄧躍進

(武漢大學(xué) 測繪遙感信息工程國家重點實驗室,武漢 430079)

城市交通系統(tǒng)正逐漸由原來的單一模式轉(zhuǎn)變?yōu)橄嗷ミB通的多模式,為了更準確地表達多模式交通網(wǎng)絡(luò)系統(tǒng),并滿足個人出行時路線規(guī)劃和時間預(yù)測的要求,該文以O(shè)racle空間網(wǎng)絡(luò)數(shù)據(jù)模型為建?；A(chǔ),以武漢市為例,選取了道路網(wǎng)、公交路網(wǎng)和地鐵路網(wǎng)三種路網(wǎng)模式構(gòu)建了多模式交通路網(wǎng),并且加入公交線路和地鐵線路的時刻表因素,旨在使出行者通過該模型可以找到到達目的地的最快路線并預(yù)估該路線所需時間.

多模式交通網(wǎng)絡(luò); 路徑規(guī)劃; Oracle 空間網(wǎng)絡(luò)數(shù)據(jù)模型; 時刻表; 最短路徑

隨著經(jīng)濟的飛速發(fā)展,有限的生存空間和多樣化的城市生活使人們的出行方式由單一模式逐步轉(zhuǎn)向了多模式[1],交通基礎(chǔ)設(shè)施建設(shè)也在不斷地建立和完善中. 多模式交通是指出行者從對交通出行的便捷性和其自身出行的經(jīng)濟性考慮,選擇多種混合的交通模式出行,常用的模式有步行,公交,地鐵,出租車等. 如先步行到公交站點,乘公交到某一中轉(zhuǎn)站再步行到地鐵站換乘為地鐵,最后在地鐵站點下車步行至目的地.

本文以湖北省武漢市為例,建立了基于道路網(wǎng)、公交路網(wǎng)和地鐵線路網(wǎng)的多模式交通網(wǎng)絡(luò)模型,并添加了武漢市公交車時刻表和地鐵時刻表數(shù)據(jù)來進行基于時刻表的多模式交通路網(wǎng)最短路徑規(guī)劃,給出行者提供了更為準確的到達時間預(yù)估.

1 多模式交通路網(wǎng)

路徑規(guī)劃一直以來是一個受到普遍學(xué)者研究的話題,從 Dijkstra 算法,Floyd 算法,A*算法,到后來從生物學(xué)領(lǐng)域獲得靈感衍生出來的蟻群算法,其目標都是求取最短路徑(或最少權(quán)重的路線)來到達目的地. 但是如Dijkstra和Floyd等算法都是在單一出行的交通網(wǎng)絡(luò)上求解最短路徑,沒有對交通層次進行細分,忽略了交通出行方式多樣性的現(xiàn)狀[2]. 在實際生活中,如果只考慮了單層網(wǎng)絡(luò)和單一模式交通出行方式,將難以適應(yīng)城市交通出行從單一模式向一個多模式交通體系的轉(zhuǎn)變,同時,更有效的路線規(guī)劃算法還應(yīng)該考慮其他因素,除了用戶在交通工具上消耗的時間,還應(yīng)考慮到從一個模式到另一個模式的換乘時間、用戶在換乘時的等待時間等.

考慮了車輛行駛和到達的時間、等待時間和換乘所需的步行時間的多模式交通路網(wǎng)模型,更有利于規(guī)劃最佳路線并準確預(yù)估到達時間. 很多學(xué)者都使用許多建模方法和算法來解決多模式交通路徑規(guī)劃的問題.李學(xué)全[3]基于隨機用戶平衡理論構(gòu)造了多模式的交通配流模型; 熊麗音[4]采用了非平面數(shù)據(jù)模型,借鑒了ISO GDF 4.0 邏輯數(shù)據(jù)模型,建立了多模式交通網(wǎng)絡(luò)及其連通關(guān)系的數(shù)據(jù)模型; 四兵鋒[5]基于圖論提出了一種分層網(wǎng)絡(luò)結(jié)構(gòu)來描述多模式交通系統(tǒng),研究了出行者在該系統(tǒng)中的選擇行為,并考慮了不同模式道路流量之間的相互影響; 李想[6]引入了超網(wǎng)絡(luò)概念對多模式城市交通網(wǎng)絡(luò)進行網(wǎng)絡(luò)描述,利用基于圖的遍歷算法進行有效路徑搜索,根據(jù)各交通模式自身的特點建立路段阻抗函數(shù),最后用非集計方式描述出行者的彈性需求. 這些學(xué)者基于不同出發(fā)點建立了多模式交通系統(tǒng)并進行優(yōu)化,但是很少考慮時間消耗問題. 劉新華[7]建立了基于乘客屬性的地鐵配流模型及算法,并考慮地鐵需求的動態(tài)屬性,建立基于時刻表的地鐵客流動態(tài)分配模型及算法;劉志謙[8]在傳統(tǒng)的Logit模型中引入公交路徑獨立系統(tǒng),建立了容量限制下基于時刻表的隨機用戶均衡模型. 但是這些學(xué)者僅考慮了單一的出行模式,未考慮到多模式交通網(wǎng)絡(luò).

本文利用Oracle公司提供的網(wǎng)絡(luò)數(shù)據(jù)模型[9](Network data model,NDM),可以較容易地構(gòu)建多模式交通網(wǎng)絡(luò),并以湖北省武漢市為例,建立了基于道路網(wǎng)、公交路網(wǎng)和地鐵線路網(wǎng)(僅考慮已投入運行的1號線、2號線和4號線)的多模式交通網(wǎng)絡(luò)模型,添加了武漢市公交車時刻表和地鐵時刻表數(shù)據(jù)來進行基于時刻表的多模式交通路網(wǎng)最短路徑規(guī)劃,給出行者提供了更為準確的到達時間預(yù)估.

2 構(gòu)建多模式交通路網(wǎng)模型

Oracle空間網(wǎng)絡(luò)數(shù)據(jù)模型是由Oracle公司設(shè)計開發(fā)的可用于分析網(wǎng)絡(luò)連接關(guān)系的模型. 它將模型簡化為4個主要的關(guān)系表: NODE站點表、LINK連接表、PATH路線表和PATH-LINK表,實體-關(guān)系圖如圖1所示. Oracle Spatial也提供了基于Java與路徑分析相關(guān)的API以供開發(fā)者使用. 路網(wǎng)數(shù)據(jù)的查詢和修改不僅可以在數(shù)據(jù)庫中進行操作,還能在NDM編輯器(Network data model editor)中進行可視化查詢和修改,有利于用戶在此基礎(chǔ)上進行二次開發(fā).

圖1 Oracle 空間網(wǎng)絡(luò)數(shù)據(jù)模型實體-關(guān)系圖

表1以NODE_ID為主鍵,用NODE_NAME存儲的每一個公交汽車站和地鐵站的名稱; 由NODE_TYPE區(qū)分該點是公交站(BusStop)還是地鐵站(Subway Stop); ACTIVE是便于在該站點的維修或取消之時方便更改或不參與計算; GEOMETRY存儲每一個站點的幾何信息; SDO_GEOMETRY 是 Oracle Spatial軟件獨有的數(shù)據(jù)類型表達,主要存儲站點的坐標信息.

表1 站點表

表2以LINK_ID為主鍵,使用START_NODE_ID和END_NODE_ID來確定這條連接的方向,LINK_TYPE來區(qū)分連接的類型是地鐵線路上的連接(Subway Link)、公交線上的連接(BusLink)、或是換乘的步行連接(TransferLink). 本模型選用的連接的成本cost是指行駛時間或換乘時間,單位是秒,一般是用該連接的實際距離除以交通工具或步行的速度. 根據(jù)一些參考文獻和實際數(shù)據(jù)采集,本文定義了地鐵速度為每小時60公里,公交車的速度為每小時30公里,換乘的速度相當(dāng)于步行速度,平均每秒1.2米,以此計算出所有連接的時間成本.

表3以PATH_ID為主鍵,并使用PATH_NAME來記錄每一條公交或地鐵線路名稱,如593路或地鐵1號線等,START_NODE_ID和END_NODE_ID確定該線路是上行或下行方向,與NODE_ID關(guān)聯(lián),PATH_TYPE來區(qū)分線路的類型是公交線路(BusPath)還是地鐵線路(SubwayPath),SIMPLE是用于判斷該線路是否是簡單線路.

表2 連接表

表3 線路表

表4是描述線路表和連接表關(guān)系的一個表格,以PATH_ID、LINK_ID和SEQ_NO為組合主鍵,LINK_ID和PATH_ID為表2和表3的主鍵,SEQ_NO代表該連接在該線路中的序列號.

表4 線路-連接表

3 基于時刻表的多模式交通路網(wǎng)模型

3.1 多模式交通路網(wǎng)規(guī)劃

在第二章的建模中,本文規(guī)定了以時間作為成本的計算標準(見表2),而且各個交通模式的站點、連接、線路數(shù)據(jù)等均存儲在同一站點、連接和線路表中,因此所求的最短路徑即找出使用最少的時間到達目的地的路徑,未考慮時刻表時的多模式交通網(wǎng)絡(luò)路徑的規(guī)劃主要是采用Dijkstra算法. 該算法的基本思想是以起始點為中心,然后向外對路徑成本層層迭代,從而得到從起點到其他節(jié)點的最短路徑. 具體表現(xiàn)為: 首先確定起始站點s和終點站點t; 把所有站點分為S組和V組,S組代表已求出的最短路徑的站點集合,V組為尚未確定的站點集合,初始的S組只有起始站點s; 從V組中選取一個距離s最小的一個站點i,將i從V組移到S組; 以i為新考慮的中間點,則站點s→站點i→V組中各個站點的距離將縮短,修改這些距離值,選取當(dāng)前狀態(tài)下距離值最短的站點j移入S組中; 將站點j作為第二個中間點,尋找站點s→站點i→站點j→V組中各個站點的最短距離,重復(fù)上述步驟,直到從V組移入S組的站點為終點站點t為止,該條路徑即為從s站點到t站點的最短路徑.

綜上,此條件下的多模式交通路網(wǎng)模型規(guī)劃的主要實現(xiàn)流程如下:

(1)設(shè)置起始站點s和終點站點t.

(2)采用寬度優(yōu)先搜索算法,快速判斷起始站點s和終點站點t是否在路網(wǎng)中連通. 如果判斷結(jié)果為連通,則進行下一步開始計算最短路徑,反之說明兩點之間不存在連通關(guān)系,退出計算過程.

(3)用上述提及Dijkstra算法,算出從s到t的最短路徑. 值得一提的是,Oracle Spatial提供了 Dijkstra 算法的Java API以供開發(fā)者使用.

(4)對得到的最短路徑進行處理,輸出結(jié)果. 根據(jù)模型的設(shè)計將所得的最短路徑轉(zhuǎn)化為指導(dǎo)用戶換乘的、具有可讀性的規(guī)劃信息,還可以預(yù)估到達目的地的所需時間.

3.2 基于時刻表的多模式交通路網(wǎng)規(guī)劃

在實際日常生活中,并不是每次到達站點時公交車或地鐵都會正好出發(fā),更多時候出行者都需要在原地等待交通工具的到來. 而且某一條線路表面上看雖然空間距離較短,但是由于該線路的發(fā)車間隔時間較長,導(dǎo)致用戶需要等待的時間更多,反而可能會比一條空間距離長但等待時間短的線路更晚到達目的地. 完整的出行時間的計算,應(yīng)該是等待時間、交通工具的行駛時間和換乘時間的總和. 添加了時刻表這一參考因素將等待時間納入模型中,更有利于出行者能夠準確預(yù)測到達目的地的時間,即基于絕對時間[10]的多模式交通網(wǎng)絡(luò)路徑模型.

絕對時間需要時刻表數(shù)據(jù)進行支持,數(shù)據(jù)的存儲結(jié)構(gòu)詳見表5. 該表以 PATH_ID,RUN_ID 和 NODE_ID為組合主鍵. PATH_ID和NODE_ID即為表3和表1中的主鍵,RUN_ID是指不同班次的公交車和地鐵,ARRIVAL_TIME和DEPARTURE_TIME代表該路線到達和離開該站點的時間. ACTIVE字段是用于描述此次班次是否可用,當(dāng)交通工具沒有準時到來時,用戶可以暫時將此字段改變?yōu)?,不參與新的路徑規(guī)劃的計算當(dāng)中,退出程序時再更新回1即可.

表5 時刻表

模型引入了三維時空坐標系來描述交通工具的行駛規(guī)律,如圖2所示,X軸和Y軸構(gòu)成一個平面用于表達位置坐標,點A到F分別代表不同位置的公交站點或地鐵站點; 豎軸為時間坐標,圖中截取了從12:00到12:40的時間段; 每條線路代表不同的班次,線路1a和線路1b表示同一趟線路的兩個不同班次,線路1a由12:00發(fā)車從A站點發(fā)車,12:15到達D站點,線路1b比線路1a晚10分鐘,線路2于12:20從E站點發(fā)車,途徑B、C 站點,于12:40到達F 站點.

圖2 三維時空坐標系下的交通路網(wǎng)模型[11]

假設(shè)某人想從站點A到站點F,于11:55分到達了站點A,他需要在A站點等待5分鐘,乘坐線路1a于12:10分到達站點C下車,在C點等候20分鐘換乘線路2,于12:40到達F點. 因此總的出行時間共為45分鐘,包含了5分鐘的等待時間、20分鐘的行駛時間和20分鐘的換乘時間.

4 實驗與結(jié)果

將武漢市交通數(shù)據(jù)導(dǎo)入到Oracle空間網(wǎng)絡(luò)數(shù)據(jù)模型后,模型中共包含武漢市7152個站點,其中包括7074個公交車站和78個地鐵站(僅考慮武漢市內(nèi)已運營的地鐵1號線、2號線和 4號線); 共包含14432條有向連接,包括13596條公交連接、150條地鐵連接和686條換乘連接(其中規(guī)定只有當(dāng)兩個不在同一條路線上的站點之間距離小于150米時才允許創(chuàng)建換乘連接); 共包含 558條有向行駛線路,包括552條有向公交線路和6條有向地鐵線路. 所構(gòu)建的武漢市多模式交通系統(tǒng)如圖3所示.

圖3 武漢市交通路網(wǎng)

由于公交車路線和地鐵路線的時刻表數(shù)據(jù)量較為龐大,故本文只選取了部分數(shù)據(jù)進行實驗. 路徑規(guī)劃算法由Java語言實現(xiàn),需要用戶輸入起始站點名稱和終點站點名稱,數(shù)據(jù)庫將模糊查詢出與之相對應(yīng)的站點ID,當(dāng)用戶再輸入出發(fā)的時間后,程序便可輸出最優(yōu)路線以及該路線到達的時間. 流程圖見圖4.

以“廣埠屯站-魯磨路地質(zhì)大學(xué)站”和“磨山景區(qū)-積玉橋”兩條線路為例,見表6,未加入時刻表因素前,模型由Dijkstra算法可以得出最短路徑所消耗的時間成本分別為737秒和1932秒,到達時間僅僅是簡單地將時間成本由秒數(shù)轉(zhuǎn)化分鐘. 加入時刻表后,消耗的時間成本不變,但是到達時間和未加入時刻表之前相比均有延后,這是考慮到用戶在原地等候和公交車上車下車、地鐵的站點?？康人ǖ臅r間成本. 而且不同的出行時間也可能會影響到路線的選擇,第一條線路中所示12:19出發(fā)和12:21出發(fā),雖然出發(fā)的時間僅隔了兩分鐘,但是得出的出行路線完全不同,甚至12:21出發(fā)時,74 路雖然 cost更高,但是到達的時間更早; 第二條線路中,不同的出發(fā)時間雖然沒有導(dǎo)致路線的選擇發(fā)生改變,但是預(yù)估的總消耗時間均有變化. 因此,將交通工具的時刻表作為多模式交通網(wǎng)絡(luò)路徑規(guī)劃的一個參考因素是非常有必要的. 該模型路徑規(guī)劃的計算過程在Windows7 64位操作系統(tǒng)下3.00 GHz處理器的環(huán)境中完成,數(shù)據(jù)庫使用的是 Oracle 12c,運行速度良好,實現(xiàn)了基于時刻表的多模式交通路網(wǎng)規(guī)劃.

5 結(jié)論與展望

以武漢市為例,在Oracle空間網(wǎng)絡(luò)數(shù)據(jù)模型上進行多模式交通路網(wǎng)的建模是可行且易于實現(xiàn)的,加入了時刻表因素后的路線規(guī)劃可以根據(jù)不同的出行時間選擇不同的路線,更準確地預(yù)估到達時間.

但是該研究也存在一些不足,由于國內(nèi)時常會有交通堵塞的情況,且擁堵情況也是隨著時間進行波動的,因此公交車的到達時間和離開時間并不能很好地遵守時刻表. 本模型雖能夠使用戶在車輛未準時到達時主觀地將該趟班次不參與新的路徑規(guī)劃的計算中,但若該班次只是短暫延誤,新計算出來的規(guī)劃路線可能仍不是最優(yōu)選擇. 后續(xù)考慮能將本模型與實時交通狀況、公交車GPS定位技術(shù)相結(jié)合,在定位公交車地點后,根據(jù)實時路況或歷史路況記錄,計算出延誤時間,更新時刻表中的數(shù)據(jù),以達到真正的準確預(yù)計和規(guī)劃.

圖4 基于時刻表的最短路徑規(guī)劃流程圖

表6 時刻表對的路徑規(guī)劃的影響

1吳信才,楊林,周順平,等. 支持多模式的復(fù)合交通網(wǎng)絡(luò)模型研究. 武漢大學(xué)學(xué)報·信息科學(xué)版,2008,33(4): 341–346.

2仇寧海,秦勇. 基于多層-多模式交通網(wǎng)絡(luò)的最短路徑分析的研究. 2007第三屆中國智能交通年會論文集. 北京.2007.

3李學(xué)全,劉美嬌. 多模式城市交通網(wǎng)絡(luò)隨機用戶平衡配流模型. 數(shù)學(xué)理論與應(yīng)用,2007,27(2): 101–104.

4熊麗音,陸鋒,陳傳彬. 城市多模式交通網(wǎng)絡(luò)特征連通關(guān)系表達模型. 武漢大學(xué)學(xué)報·信息科學(xué)版,2008,33(4): 393–396.

5四兵鋒,楊小寶,高亮,等. 基于出行需求的城市多模式交通配流模型. 中國公路學(xué)報,2010,23(6): 85–91.

6李想. 考慮換乘的多模式城市交通網(wǎng)絡(luò)配流問題研究[碩士學(xué)位論文]. 成都: 西南交通大學(xué),2015.

7劉新華. 基于時刻表的地鐵動態(tài)配流模型研究[博士學(xué)位論文]. 西安: 長安大學(xué),2013.

8劉志謙,宋瑞. 基于時刻表的公交配流算法研究. 重慶交通大學(xué)學(xué)報 (自然科學(xué)版),2010,29(1): 114–120.

9Spatial O. Oracle Spatial Quadtree Indexing,10g Release,1(10.1). 10g White Paper,2006.

10聞輝,劉岳峰,鄭江華,等. 基于時間鏈的公交網(wǎng)絡(luò)數(shù)據(jù)模型研究. 地理與地理信息科學(xué),2005,21(3): 35–38.

11Thorlacius P. Time-and-space modelling of public transport systems using GIS. Transportr?det og Aalborg Universitet,1998.

Multi-Mode Traffic Network Path Planning Based on Schedule

ZHOU Jia-Li,DENG Yue-Jin

(State Key Laboratory of Information Engineering in Surveying,Mapping and Remote Sensing,Wuhan University,Wuhan 430079,China)

The urban traffic system is gradually changing from a single mode to interconnected multi-mode. In order to express the multi-mode traffic network system more accurately and meet the requirements of personal route planning and time prediction,this paper selects Oracle spatial network data model as the modeling foundation. The model takes Wuhan City as an example,and selects the road network,bus network and railway network to construct a multi-mode traffic network. Also the schedule of bus lines and subway lines is added to allow the travelers to find the quickest path to destination and to estimate the time required for the route.

multi-mode traffic network; path planning; Oracle spatial network data model; schedule; shortest path

周佳麗,鄧躍進.基于時刻表的多模式交通網(wǎng)絡(luò)路徑規(guī)劃.計算機系統(tǒng)應(yīng)用,2017,26(12):160–164. http://www.c-s-a.org.cn/1003-3254/6075.html

國家重點研發(fā)課題(2016YFB0502201)

2017-03-06; 修改時間: 2017-03-23; 采用時間: 2017-03-27