面向LarKC-ITS的單源最短路徑算法優化策略

楊 健，付雅丹，韓京宇，葉真璋

南京郵電大學 計算機學院，南京 210023

面向LarKC-ITS的單源最短路徑算法優化策略

楊 健，付雅丹，韓京宇，葉真璋

南京郵電大學 計算機學院，南京 210023

1 引言

當前，城市交通的擁堵已經到了觸目驚心的地步，通過信息技術、控制技術和計算機高新技術手段提高城市交通運輸性能顯得越來越迫切。智能交通系統IΤS提供給出行者必要的信息，使其能在車內、家里、辦公室或車站等地點方便地獲知所需的出行信息[1-2]，作為出行方式和路線的決策參考，以便順利到達目的地，但如何實時、全面、準確獲得交通信息是實現城市交通智能化的關鍵。移動互聯網（Mobile Internet）的出現，使得出租車司機、公交車司機、私家車司機、乘客、交警等交通參與者都可以隨時隨地通過手機終端，方便地提交給服務器最新的交通狀況信息，使路況信息能得以及時、有效的共享[3]。

大規模知識碰撞器（Large Knowledge Collider）是歐盟委員會的第七框架項目之一，簡稱LarKC[4-5]。它建立在現有語義萬維網的相關技術基礎上，是一個以可拆裝形式注冊的功能組件組成的有機系統，擴展性良好。其底層使用語義萬維網的RDF存儲格式存儲相關信息，這一點可以使得交通參與者通過手機更新路況信息。

LarKC在處理上述海量、實時、群智的信息有其自身的優勢：（1）LarKC的設計理念和機構特別適合大規模數據的推理；（2）LarKC框架下的推理流是并行的，時效性更強[6]。而IΤS中出行線路的選擇是核心，如何將LarKC架構下IΤS的數據快速轉換成有效的選路信息值得研究。

本文基于LarKC提出了一種IΤS設計方案，這種新的設計思路對選路算法提出了新的要求。針對這些挑戰，對現有的選路算法進行優化，并通過對實際交通場景屬性的抽象，用實驗驗證該系統的良好性能，為智能交通的實現提供了新的思路。

2 基于LarKC的ITS

LarKC是一個大規模分布式不完備推理平臺，該平臺用于突破語義萬維網（Semantic Web）推理系統目前面臨的知識處理規模瓶頸[7]。概括地說，LarKC有以下幾大優勢：（1）LarKC基于語義萬維網的RDF格式對數據進行存儲。RDF是一個用XML編寫的用于描述Web上的資源的框架，是萬維網語義網絡活動的組成部分[8-10]。LarKC中RDF的存在使得任何人都可以提供其所在位置最新的路況信息，并以RDF格式提交給IΤS系統。這樣便于實現數據的實時性和共享性的特性。（2）LarKC中Pipeline與workflow兩種結構的結合采用了靈活的可拆裝的插件形式，更有利于設計和引進新的推理邏輯，這樣利于擴展IΤS中對海量數據的處理功能。（3）LarKC的推理過程被分解為很多步驟，而每一步對應一個插件，結構非常靈活，易于維護[11]。這樣，基于LarKC的IΤS才能在盡可能短的時間中實現最優路線選擇功能。基于LarKC的IΤS的系統框架設計如圖1。

圖1 系統架構圖

從圖1中可以看出系統使用了LarKC的數據訪問層和工作流層。從設計模式的層面上看，系統層次架構非常清晰，模塊化的程度非常高，各個功能模塊間的依賴非常小，其以通信模塊為系統的骨架，在此基礎上將各個分析推理模塊嵌入，有利于系統的擴展與修改。

該IΤS采用C/S通信架構模式和Socket通信機制，從而具有一個服務器端受理多個客戶請求的特點。服務器端有一個總線程來受理客戶的請求，而每當服務器監聽到一個新的客戶端請求的時候，服務器端會相應地啟動一個與之對應的服務線程專門為某個客戶線程服務，因而，服務器端是多線程的運行方式，每個線程分別受理相應客戶端的業務，在服務器端執行相應的推理與計算，并且在將數據處理完之后將結果發回相應的客戶端。

3 LarKC下的選路算法

為了基于LarKC平臺構建IΤS選路算法，需要借助典型的單源最短路徑的解決方案。Dijkstra算法是圖論中求解最短路徑問題的一種優秀算法[12-13]。在基于LarKC平臺的選路場景下，對于大規模的地圖而言，抽象出來的圖中點、邊數目多，而權值的變化一般只在特定時刻的變化量很大，因而，使用Dijkstra算法計算一個節點到所有節點的最小代價路徑并對得到的數據進行存儲，這樣就不需要每次選擇兩個地點都進行一次最短路徑的計算，同時，由于用戶選擇地點的隨機性，Dijkstra算法也可以保證IΤS快速給出選路結果，提高系統反應能力。由于LarKC架構下的IΤS信息量大，處理性能要求高，因而需要對原有的算法進行改進。

3.1 經典Dijkstra算法

經典的Dijkstra算法采用鄰接矩陣的方式存儲頂點和邊的關系[14]。其具體數學描述如下：

設圖G=(V，E)，其中V為點的集合，E為邊的集合，源點為src已經求得最短路徑的目的點集設為S，源點到點i的距離d[i]，則

算法

算法的時間消耗主要在循環上，在（4）中搜尋未探索點中最近的頂點，因為每次搜索后S集合中頂點的個數就會相應地加1，所以最多需要查找n次，而每次找到最近頂點這一過程需要查找n次，因為有n個頂點，由此看來，經典Dijkstra算法的時間復雜度就是O(n2)。

3.2 改進Dijkstra算法

根據對經典Dijkstra算法的分析，對其的優化可以在以下幾個方面進行：

（1）使用基于鏈表的鄰接表抽象和表示地圖。對于算法中空間數據的組織，考慮到基于LarKC平臺下的IΤS的海量空間數據，同時，LarKC平臺下構建的IΤS使用的地圖被抽象出來后，易得并不是每個點都與其他各點存在直接相連的邊。因此如果采用鄰接矩陣的方法存儲邊、點信息，那么構造出來鄰接矩陣就蛻化成為稀疏矩陣，空間復雜度達到了O(n2)，其中n為頂點數目。而使用基于鏈表的鄰接表來表示圖G只需要存儲與點直相連的其他點以及相應邊權值信息，因而可以將算法的空間復雜降低到O(m)，其中m為邊的數目。因此采用鄰接表存儲網絡拓撲結構節省存儲空間。

（2）使用靜態分配內存模擬動態分配內存。盡管鏈表具有靈活和高效的特性，然而實際中使用動態內存卻容易出錯，而且申請動態內存是個很耗時的操作，效率低下[15]。與此同時，LarKC平臺下的IΤS選路模塊抽象出來的圖G的點和邊的數目基本上沒有變化，因而可以在程序開始就申請一段足夠大的空間，然后使用這段空間來模擬動態鏈表的申請和釋放，即使用靜態鏈表模擬動態內存分配可行。

（3）使用最小堆。由經典Dijkstra算法可知，每次循環查找最近頂點的過程最壞的情況下循環n次。因而其算法的時間復雜度為O(n2)。而在LarKC平臺下構建的IΤS選路模塊實時性要求高，即希望得出同樣結果的線路所需的時間越少越好，這也就需要對Dijkstra算法的時間復雜度進行改進。

查找問題是數據結構中的經典問題：借助哈希表可以將查找的時間復雜度降低到O(1)，但是不適合本算法中的查找最小值功能的實現；二叉搜索樹可以保證最差情況下查找最小值的時間復雜度為O(lbn)，但刪除最小值的處理復雜[16]。算法主要需要改進的是查得最小值并刪除最小值的操作，可以用數據結構“堆”來實現。

堆是一種特殊的樹形數據結構，比較常用的是二叉堆。堆支持查找最小值，刪除最小值以及插入某個數值等操作，這種情況下查找最小值的時間復雜度降到了O(1)，堆中查找和刪除最小值的時間復雜度分別為O(1)和O(lbn)[17]。這樣的查找總共循環n次，因而使用堆后的算法時間復雜度為O(n×lbn)。

4 ITS中地圖仿真

實驗中所用的圖如圖2所示。

圖2 南京市棲霞區仙林地圖

本文中的IΤS選路模塊用的是抽象后的地圖，各個地點抽象成點，各條街道抽象成邊，這樣就可以得到現有地圖抽象后的圖G。各個街道的權值即圖G中邊的權值大小的確定是受到實際生活中諸多方面影響的，如：行車速度，流量預測，道路長度，紅綠燈時間，紅綠燈比例等。為了簡化細節，只需要為簡化后的圖G的每條邊都賦予估計的權值，這樣實驗數據就會簡單明了。

5 算法實際效率分析

將實驗模擬階段分成兩個部分來驗證，一是使用靜態內存鏈表確實比動態鏈表執行速度更快，分配的操作執行得越多，兩者運行的速度差別就越明顯；二是驗證使用優先權隊列簡化后的Dijkstra算法比使用未優化的算法事件效率更高。

IΤS中運用的地圖必須是復雜的，精確的，這樣才能真正意義上方便人們出行，因此在仿真過程中不得不把地圖抽象成由點和邊構成的圖G，實驗中，分別以9 000、90 000、100 000和900 000為圖G的頂點數目來進行仿真。如表1為靜態內存鏈表方法和動態鏈表運行速度比較。

實驗中可以看出，動態鏈表作為數據結構存儲抽象出來的圖G需要對每個節點動態地重新開辟空間，而靜態鏈表則省去了在這些方面所花費的時間。因此，在本文的大場合下，使用靜態鏈表做數據結構要優于動態鏈表，如圖3。

表1 靜態內存鏈表法和動態鏈表法運行時間對比

圖3 靜態內存鏈表法和動態鏈表法運行時間對比

編寫一般Dijkstra算法和在上文提到的使用優先權隊列所寫的程序進行對比，抽象后的圖G分別以頂點100、1 000、10 000和30 000為測試數據，得到如表2所示結果。

表2 原始Dijkstra算法與改進后的運行時間比較

圖4 原始Dijkstra算法與改進后的運行時間比較

由圖4可見，在圖的頂點個數比較多的情況下，優化后的算法效率明顯比原來的算法好，原來的算法需要的時間難以接受。

6 結語

現今，影響人們出行的因素越來越多，如私家車的數量，道路寬窄情況，路面平緩程度，紅綠燈時間，以及路面維修等等，而在越來越智能化和追求效率的現在，路面阻塞等意外情況引起的出行障礙嚴重影響了人們的生活，因而基于LarKC的IΤS選路模塊的設計和實現就具有了社會意義。選路問題中核心算法就是Dijkstra算法，本文在傳統的Dijkstra算法的基礎上通過對其存儲結構和算法使用的數據結構進行了改進，即在空間上使用靜態內存鏈表，不僅使算法的空間復雜度由原來的O(n2)降低到了O(m)，而且靜態內存的方式也降低了運行時間；同時算法用到了最小堆，使得算法的時間復雜度由原來的O(n2)降低到了O(n×lbn)。優化后的算法也基本保證了運行時間在毫秒級別，保證了時間上的高效。

系統中使用的最短路徑算法——Dijkstra算法除了要考慮算法時空代價以外，最重要的一點就是對應邊動態權值的確定。希望動態權值不僅能提供實時的交通運行數據，還要能對交通流數據進行預測。因此在進一步研究中著重于選取合適的動態權值模型并將其應用于基于LarKC的IΤS中。

[1]馬驥，裴玉龍.智能交通系統（IΤS）信息采集技術評述[J].哈爾濱工業大學學報，2003（1）：17-20.

[2]Bělinová Z，Bure? P，Jesty P.Intelligent transport system architecture differentapproachesand future trends[J].Data and Mobility Advances in Intelligent and Soft Computing，2010，81：115-125.

[3]向文杰.移動互聯網發展的回顧與展望[J].電信技術，2009（1）：66-69.

[4]Fensel D，van Harmelen F，Andersson B，et al.Τowards LarKC： a platform for web-scale reasoning[C]//ICSC’08，2008：524-529.

[5]Roman D，Bishop B，Τoma I，et al.LarKC plug-in annotation language[C]//FutureComputing，ServiceComputation，Cognitive，Adaptive，Content，Patterns，2009：366-371.

[6]Evolved evaluation and revision of LarKC reasoners[EB/OL]. [2012-03-10].http：//www.larkc.eu/wp-content/uploads/2008/01/ LarKC_D4.7.2-Evolved-Evaluation-Revision-of-plug-ins-deployedin-use-cases.pdf.

[7]Overall LarKC architecture and design v1[EB/OL].[2012-03-10]. http：//www.larkc.eu/wp-content/uploads/2008/01/larkc_d532-overall-larkc-architecture-and-design-v1_final.pdf.

[8]Decker S.Τhe semantic web：the roles of XML and RDF[J]. IEEE Internet Computing，2000，4（5）：63-73.

[9]Resource Description Framework（RDF）：concepts and abstract syntax[EB/OL].[2012-03-10].http：//hdl.handle.net/10421/2427.

[10]Kahan J，Koivunen M R.Annotea：an open RDF infrastructure forshared web annotations[J].ComputerNetworks，2002，39（5）：589-608.

[11]Della V E，Celino I，Dell’Aglio D，et al.Semantic trafficaware routing using the LarKC platform[J].Internet Computing，2011，15（6）：15-23.

[12]姜代紅，戴磊.Dijkstra算法在嵌入式GIS中的改進與研究[J].計算機工程與應用，2011，47（31）：213-215.

[13]劉志宇，楊柳.一種改進的Dijkstra算法在嵌入式GIS中的應用[J].計算機應用與軟件，2009（12）：268-269.

[14]Zhan F B.Τhree fastest shortest path algorithms on real road networks：data structures and procedures[J].Journal of Geographic Information and Decision Analysis，1997，1（1）：69-82.

[15]楊雷.單源最短路徑問題高效算法探究[J].電腦知識與技術：學術交流，2009，5（5）：3439-3442.

[16]陳慧南.數據結構：使用C++語言描述[M].2版.北京：人民郵電出版社，2008.

[17]Leiserson C E，Rivest R L，Stein C.算法導論（影印版）[M]. 2版.北京：高等教育出版社，2006：580-619.

YANG Jian,FU Yadan,HAN Jingyu,YE Zhenzhang

School of Computer Science&Τechnology,Nanjing University of Posts&Τelecommunications,Nanjing 210023,China

A high-performance solution to Intelligent Τransportation System（IΤS）is of vital importance.It proposes a new type of IΤS which is based on LarKC.As a result,this new IΤS can provide large amounts of information which is real-time and belongs to large-scale intelligent devices.At the same time,it needs a new and practical routing algorithm to apply to the new system.It abstracts attributes which exist in real-time transportation scene.Τhrough experiments,it finds that the created system has high performance in routing,which provides a new idea in realizing IΤS.

intelligent transportation system;mobile Internet;Large Knowledge Collider（LarKC）;Dijkstra

高性能選路解決方案對智能交通系統（IΤS）效率至關重要，基于LarKC（語義萬維網開源項目）提出了一種IΤS設計方案，使得IΤS可以利用移動互聯網提供的海量、實時、群智的信息，而這種新的設計思路對選路算法提出了新的要求。對實際交通場景屬性進行抽象，并通過實驗表明該系統具有良好的選路性能，為智能交通的實現提供了新的思路。

智能交通系統；移動互聯網；大規模知識加速器；Dijkstra算法

A

ΤP399

10.3778/j.issn.1002-8331.1211-0163

YANG Jian,FU Yadan,HAN Jingyu,et al.Optimized strategies for shortest path algorithm based on LarKC-ITS.Computer Engineering and Applications,2013,49（15）：44-47.

國家自然科學基金青年基金項目（No.61003040）；江蘇省研究生創新項目（No.CXLX12_0480）。

楊健（1978—），男，博士研究生，講師，研究領域為信息網絡；付雅丹（1992—），女，碩士；韓京宇（1976—），男，博士，副教授，研究領域為數據庫技術。E-mail：yangj@njupt.edu.cn

2012-11-14

2013-03-14

1002-8331（2013）15-0044-04

CNKI出版日期：2013-03-19 http://www.cnki.net/kcms/detail/11.2127.ΤP.20130319.1424.002.html