楊英偉，饒鳴，殷忠銀

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

基于交通規(guī)則的路網(wǎng)模型建立及最優(yōu)路徑分析研究

楊英偉?，饒鳴，殷忠銀

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

研究了國內(nèi)交通規(guī)則，建立起了適于最優(yōu)路徑分析的路網(wǎng)數(shù)據(jù)模型，利用Dijkstra算法實現(xiàn)了兩點之間最優(yōu)路徑分析和多點之間最優(yōu)路徑分析，并闡述了最優(yōu)路徑分析在實際中的應用及其重要性。

最優(yōu)路徑；Dijkstra；路網(wǎng)數(shù)據(jù)模型

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

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

1 路網(wǎng)模型

1.1 模型

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

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

圖1 弧段、結(jié)點拓撲關系

1.2 路網(wǎng)模型建立

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

為了滿足最優(yōu)路網(wǎng)分析，我們采用表1所示數(shù)據(jù)結(jié)構(gòu)來描述一條道路。

道路數(shù)據(jù)結(jié)構(gòu) 表1

?

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

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

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

圖2 現(xiàn)實路網(wǎng)狀態(tài)圖

圖3 現(xiàn)實道路網(wǎng)模型

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

部分道路結(jié)構(gòu) 表2

1.3 路網(wǎng)模型特點

上述模型真實反映了客觀世界路網(wǎng)信息，已在系統(tǒng)中驗證使用，具體表現(xiàn)在:

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

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

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

2 最優(yōu)路徑分析

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

2.1 兩點之間最優(yōu)路徑

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

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

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

(3)在L1上選擇一個結(jié)點，作為模型中的起始點PS，在L2上選擇一個結(jié)點，作為模型中的終止結(jié)點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)根據(jù)PS和PE，利用Dijkstra算法做最優(yōu)路徑分析，確定兩點之間最佳路徑；

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

(7)輸出。

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

圖4 主干道優(yōu)先最佳路徑分析結(jié)果

圖5 距離最短路徑分析結(jié)果

2.2 起點到多點間最優(yōu)路徑

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

圖6 起點到多點間主干道優(yōu)先最佳路徑分析

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

3 最優(yōu)路徑分析應用

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

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

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

4 結(jié)論與展望

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

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

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

[2]樂陽，龔鍵.Dijkstra最短路徑算法的一種高效率實現(xiàn)[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]王海鯤，陳長虹，黃成等.上海市城區(qū)典型道路行駛特征研究[J].交通環(huán)保，2005，26(3)

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

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

[8]史其信.中國道路交通的現(xiàn)狀與ITS研究展望.第一屆亞太地區(qū)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—)，男，軟件工程師，現(xiàn)從事WebGIS、地理信息多尺度表達研究。