基于交通規則的路網模型建立及最優路徑分析研究

楊英偉，饒鳴，殷忠銀

(重慶數字城市科技有限公司，重慶 400020)

基于交通規則的路網模型建立及最優路徑分析研究

楊英偉?，饒鳴，殷忠銀

(重慶數字城市科技有限公司，重慶 400020)

研究了國內交通規則，建立起了適于最優路徑分析的路網數據模型，利用Dijkstra算法實現了兩點之間最優路徑分析和多點之間最優路徑分析，并闡述了最優路徑分析在實際中的應用及其重要性。

最優路徑；Dijkstra；路網數據模型

隨著社會日益發展，科技不斷進步，城市現代化進程也在加速發展，“衣、食、住、行”中最后這一要素“行”也越受重視與關注。如何降低油耗，減少時間成本成為駕駛員最為關注的問題。最優路徑分析是研究如何在起點到終點間找到一條最優路徑的方法，“最優”既可以指距離最短，也可以指成本最低。國內外學者對此問題做了大量研究，其中以Dijkstra算法最為經典。然而最優路徑分析不但需要高效的算法，同時還需要準確、高效的路網模型做支撐，才能為駕駛員提供最優路徑分析服務。

最優路徑分析本質屬于圖論研究中的一個經典問題，但在實際應用中，需要結合交通規則和道路的實際情況，將其抽象為有實際意義的路網模型，才能應用在實際交通運輸中。本文是在研究了現有最短路徑算法的基礎上，建立了基于交通規則的路網數據模型，實現了最優路徑求解，并描述了其在交通運輸、物流配送等行業中的應用及價值意義。

1 路網模型

1.1 模型

模型是對客觀現實事物的某些特征與內在聯系所作的一種模擬或抽象，為了研究一個過程或事物，可以通過提取在某些特征(形狀或結構等)方面與它相似的“模型”來描述或表示具體事務。路網模型就是現實世界中路網的客觀抽象，真實的反映路網內部結構及關系，以便于在此模型上進行最優路徑分析。

道路采集后是由若干連續的點所組成的多邊線，其模型如圖1所示，其中首尾點稱作“結點”，中間點稱作“接點”?！敖Y點”表示道路的起始點和結束點，道路與道路之間通過結點相連；接點只代表道路的數字化坐標，不具有表達拓撲關系的功能。

圖1 弧段、結點拓撲關系

1.2 路網模型建立

道路建設目的是便于車輛通行，從機械運動學原理上講，車輛可以在道路上隨意行駛。但如果沒有交通規則作為行駛準則，車輛雜亂無章的行駛，很難想象會對社會造成多大的災難，因此國家制定了城市交通規則和相關法律法規，約束駕駛員按交通規則行駛，并在道路路口、路面設置了各種交通標志。路網模型只有嚴格遵照交通規則，才能真實反映現實道路情況，才能在此模型上做最優路徑分析[1]。

為了滿足最優路網分析，我們采用表1所示數據結構來描述一條道路。

道路數據結構 表1

?

其中道路類型包含高速公路、主干道、次干道、支路等四種類型；行駛代價既可表示時間代價，也可表示費用代價。系統設計為開放式系統，針對不同用途選擇不同的影響因子。例如，考慮行駛時間最快，Cost值如下設置:

P表示道路類型權值，其值由統計分析獲得，由于不同城市道路狀況不同，P值也會相應不同，道路類型權值P越小，等里程下耗時越短，在耗時最優路徑分析下被選中的幾率越大；Length表示道路長度，其值除以最長的道路長度MaxLength做均一化變換，以便于分析計算。

圖2是重慶市江北區商圈的道路狀況，是一個較為復雜的路網系統，其中囊括了立體層次、單行、雙行、左轉及掉頭等道路狀況及交通規則，運用上述道路網模型，可抽象為圖3所示的道路網模型。

圖2 現實路網狀態圖

圖3 現實道路網模型

具有相同結點的道路相連通，雙向行駛道路正向行駛代價和逆向行駛代價均為正值，表示其可通行；單向行駛道路，若行駛方向與數字化方向一致，則正向行駛代價為正，逆向行駛代價為負，表示不能通行。根據道路類型，可由公式(1)計算該道路正向行駛代價和逆向行駛代價。表2列舉了部分道路的數據結構:

部分道路結構 表2

1.3 路網模型特點

上述模型真實反映了客觀世界路網信息，已在系統中驗證使用，具體表現在:

(1)實用性:該模型能真實的反映道路的拓撲關系和通行狀況，為最優路徑分析打下了數據源基礎；

(2)可擴展性:針對不同需要，模型可擴展出更多的道路描述信息；

(3)開放性:最優路徑有多種含義，包括耗時最短或距離最短等情況，系統可自定義Cost字段值，滿足其自身需求。

2 最優路徑分析

最短路徑是指頂點之間路徑最優。抽象到圖論中，路網可以看作是有向圖，圖的頂點表示道路結點，圖的邊表示道路路段，圖的方向表示道路通行方向，邊的長度即可表示道路長度，也可表示道路通行時間，根據不同的要求賦予邊長以不同的含義。最優路徑分析分為兩類，一是指從起點到終點之間路徑最優，另一種是指從起點到多點之間路徑最優，也稱貨郎擔問題。

2.1 兩點之間最優路徑

Dijkstra[2～4]算法是解決最優路徑最經典的算法，其基本思想是:若從點S到點T有一條最短路徑，則該路徑上的任何點到S的距離都是最短的。該算法適用于一個理想的路網圖，在實際路徑分析中，需要結合實際使用方式，經過預處理才能進行路徑分析，分析結果同樣需要經過處理才能呈現給使用者，下面是最優路徑分析的主要步驟:

(1)輸入起點坐標P1和終點坐標P2；

(2)搜索離P1和P2最近的兩條道路L1和L2；

(3)在L1上選擇一個結點，作為模型中的起始點PS，在L2上選擇一個結點，作為模型中的終止結點PE。若L1為雙向行駛，則任意選擇FirstNode或LastNode作為PS，若L1為單向正向行駛，則選擇LastNode作為Ps，若L1為單向反向行駛，則選擇FirstNode作為PS，若L2為雙向行駛，則任意選擇FirstNode或LastNode作為PE，若L2為單向正向行駛，則選擇LastNode作為PE，若L1為單向反向行駛，則選擇FirstNode作為PE；

(4)計算Cost值和ReverseCost值，P權值如表3所示；

道路類型權值 表3

(5)根據PS和PE，利用Dijkstra算法做最優路徑分析，確定兩點之間最佳路徑；

(6)路徑裁剪，Dijkstra算法計算出的最優路徑是從PS到PE之間的最優路徑，需要裁剪道路，找到從P1到P2之間的最優路徑；

(7)輸出。

若只考慮距離最短優先，計算權值P時將式(1)中的P全部置為1；若考慮主干道優先，借用2005年上海市城區典型道路平均速度統計值[5]，P值計算結果如表3所示。圖4和圖5展示了主干道優先和距離優先的兩種最優路徑分析結果，路網數據為全重慶市道路數據，以人和立交作為起點到朝天門，分析耗時在600 ms到1 s之間。

圖4 主干道優先最佳路徑分析結果

圖5 距離最短路徑分析結果

2.2 起點到多點間最優路徑

起點到多點間最優路徑是指從起點出發，選擇一條最優的路徑，經過各目的點一次，且僅經過一次，其實質就是著名的貨郎擔問題[6]。解決辦法有窮舉法、最短路標號法、動態規劃法等。利用上述路網模型，實現主干道優先最佳路徑分析和距離最短路徑分析效果分別如圖6和圖7所示，路徑分析以松橋路和金龍路交叉路口作為起點，分別經過龍華大道與松牌路交叉路口、金龍路與嘉洲路交叉路口、金城國際3個目的點。

圖6 起點到多點間主干道優先最佳路徑分析

圖7 起點到多點間距離最短路徑分析

3 最優路徑分析應用

交通問題是世界各國面臨的共同問題[7]。交通擁擠、繞路等情況造成了巨大的時間浪費，加重了環境污染。由于車輛速度過慢，行駛時間長，尾氣排放增加，使得城市的空氣質量進一步惡化。交通問題也造成了巨大的經濟損失。為了緩解經濟發展帶來的交通運輸發展的壓力，盡量的利用現有的資源，使其發揮最大的作用，各國都加大了對智能交通系統的研究和建設的力度。智能交通系統是現代交通運輸發展的趨勢，智能運輸系統(Intelligent Transport System)的主要思想是將傳統的交通系統看成是人、車、路的統一體[8]，運用計算機、通信、人工智能、傳感器等領域的先進成果來徹底改變目前被動式的交通局面。最優路徑分析可以作為智能交通系統的一部分，輔助系統使用者規劃最優行車路線，減少出行成本。

在物流配送與選址上，怎樣規劃配送貨車的行駛路線，減少配送時間和降低運輸成本，規劃選址地點，成為物流公司主要考慮的問題，隨著現代物流業的發展，在物流管理系統中引入最優路徑分析輔助規劃決策，是提升其競爭力的有力工具。

城市建設往往需要鋪設各種管道、管線，合理規劃最優路線，可以減少管道鋪設材料，可以極大的降低建設成本，節約資源。

4 結論與展望

自駕出行逐漸成為民眾主要的出行方式，如何減少行駛時間與降低駕車成本是駕駛員關注的話題，城市道路建設滯后與日漸增長的車輛矛盾越發突出，需要合理的規劃行車路線，最佳路徑分析作為智能交通系統的一部分，對于路徑規劃起到積極作用。本文在研究了城市交通規則的基礎上，建立了適于最優路徑分析的路網數據模型，并在此基礎上實現了兩種方式的最優路徑分析，并探討了其在實際生產生活中的應用。

路網數據采集包含空間數據采集和屬性數據采集，數據量很大，采集道路數據是一個非常龐大的工程，并且國內道路建設更新速度很快，需要交通主管部門組織一個專業的數據采集隊伍和建立一個長期有效的路網更新機制。路網分析是智能交通系統中一個重要的部分，隨著信息化技術的普及，路網分析會受到越來越多的行業關注和使用。

[1]劉云翔.基于城市道路網的最短路徑分析解決方案[J].小型微型計算機系統，2003，24(7):1390～1393

[2]樂陽，龔鍵.Dijkstra最短路徑算法的一種高效率實現[J].武漢測繪科技大學學報，1999，24(3):209～212

[3]Benjam in Zhan F.Three fastest shortest path algorithms on real road network’s data structures and procedures[J]Journal of Geographic Information and Decision Analysis，1995，1 (1):69～82

[4]Dijkstra E W.A note on two problems in connection with graphs[J].Numeriche Mathematic 1959，1:269～271

[5]王海鯤，陳長虹，黃成等.上海市城區典型道路行駛特征研究[J].交通環保，2005，26(3)

[6]杜均，蔡之華，朱莉.用遺傳算法解貨郎擔問題[J].微型機與應用，2004，23(10)

[7]劉學軍，徐鵬.交通地理信息系統[M].北京:科學出版社，2006

[8]史其信.中國道路交通的現狀與ITS研究展望.第一屆亞太地區ITS會議(東京)，1996.10

Building Road Data Model Based on Traffic Rules and Researching on Shortest Path Analyzing

Yang YingWei，Rao Ming，Ying ZhongYin
(ChongQing Cybercity Sci－tech Company，ChongQing 400020，China)

This paper studies the domestic traffic rules，and builds a road data model in suit for shortest path analyzing.Using Dijikstra，implements the shortest path analyzing between tow points and among multiple points.Finally，this paper describes the application of shortest path analyzing in practice and its importance.

Shortest Path；Dijikstra；Road Data Model

1672－8262(2010)04－58－04

P208

A

2009—12—02

楊英偉(1983—)，男，軟件工程師，現從事WebGIS、地理信息多尺度表達研究。