基于時刻表的多模式交通網絡路徑規劃①

周佳麗,鄧躍進

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

基于時刻表的多模式交通網絡路徑規劃①

周佳麗,鄧躍進

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

城市交通系統正逐漸由原來的單一模式轉變為相互連通的多模式,為了更準確地表達多模式交通網絡系統,并滿足個人出行時路線規劃和時間預測的要求,該文以Oracle空間網絡數據模型為建模基礎,以武漢市為例,選取了道路網、公交路網和地鐵路網三種路網模式構建了多模式交通路網,并且加入公交線路和地鐵線路的時刻表因素,旨在使出行者通過該模型可以找到到達目的地的最快路線并預估該路線所需時間.

多模式交通網絡; 路徑規劃; Oracle 空間網絡數據模型; 時刻表; 最短路徑

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

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

1 多模式交通路網

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

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

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

2 構建多模式交通路網模型

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

圖1 Oracle 空間網絡數據模型實體-關系圖

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

表1 站點表

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

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

表2 連接表

表3 線路表

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

表4 線路-連接表

3 基于時刻表的多模式交通路網模型

3.1 多模式交通路網規劃

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

綜上,此條件下的多模式交通路網模型規劃的主要實現流程如下:

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

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

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

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

3.2 基于時刻表的多模式交通路網規劃

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

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

表5 時刻表

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

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

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

4 實驗與結果

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

圖3 武漢市交通路網

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

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

5 結論與展望

以武漢市為例,在Oracle空間網絡數據模型上進行多模式交通路網的建模是可行且易于實現的,加入了時刻表因素后的路線規劃可以根據不同的出行時間選擇不同的路線,更準確地預估到達時間.

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

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

表6 時刻表對的路徑規劃的影響

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

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

3李學全,劉美嬌. 多模式城市交通網絡隨機用戶平衡配流模型. 數學理論與應用,2007,27(2): 101–104.

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

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

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

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

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

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

10聞輝,劉岳峰,鄭江華,等. 基于時間鏈的公交網絡數據模型研究. 地理與地理信息科學,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

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

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

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