交通運輸最短路徑分析系統的設計與實現

張曉楠，任志國，曹一冰，劉瑞雪

(1.信息工程大學 地理空間信息學院，河南 鄭州 450052；2.中華測繪服務公司，北京 100088；3.78155部隊，四川 成都 610036)

交通運輸最短路徑分析系統的設計與實現

張曉楠1，任志國2，曹一冰1，劉瑞雪3

(1.信息工程大學 地理空間信息學院，河南 鄭州 450052；2.中華測繪服務公司，北京 100088；3.78155部隊，四川 成都 610036)

針對目前交通運輸效力發揮不足的問題，研究道路網絡模型構建和道路數據庫設計，探討分析交通運輸最短路徑分析流程，基于Dijkstra算法的基本原理，設計實現交通運輸最短路徑分析系統，從而優化運輸資源配置，實現高質高效的交通運輸。

交通運輸;道路網絡;GIS;最短路徑分析

當前，我國城市交通的發展速度已經遠遠滯后于經濟增長的速度，交通運輸問題涉及和影響到人們生活和經濟的各個方面，成為社會發展中亟待解決的重要問題。但是，交通運輸業的發展需要聚集大量的財力物力，考慮到我國目前尚處于資金短缺這一實際情況，大規模建設新的交通干線，并不實際[1]。因此，有必要立足現有的交通資源，進行運輸的合理規劃與有效配置，最大限度地發揮運輸效力。為了達到這一目標，最短路徑的分析與獲取就成為關鍵所在。這里所指的最短路徑，不僅僅局限于空間意義上的最短距離，還引申為諸如最短時間、最短線路容量、最低耗費成本等度量。如何才能使得運輸貨物經歷最短時間、以最短路徑到達指定的目的地，是交通運輸最短路徑分析的最終目標。本文結合GIS技術，在.NET環境下進行GIS產品的二次開發，實現網絡化環境下交通運輸的最短路徑分析，用戶還可以根據任務的實際情況，查詢和搜索相應的運輸路線。

1 道路網絡模型構建

1.1 道路網絡模型

城市道路交通網錯綜復雜，縱橫交織，由成百上千條道路相連、相交構成。每條道路的地理位置以及道路與道路之間的相互位置關系，都會影響交通運輸網的結構和組成。僅以道路相連的情況來看，一條道路可能就與若干條道路相連，且相連的模式多種多樣。為此，本文抽取交通網中道路之間的交叉口作為單獨分析的對象，然后使用交叉口作為節點將每條道路分割成段，從而避免道路之間復雜多樣的拓撲關系，最終構建基于路段連接的道路網絡模型。基于該模型，整個交通網絡圖由路口交叉節點和路段構成，交叉口節點構成網絡的節點，道路路段構成網絡的弧。

如圖1所示，路網中的節點為道路交叉口，路網中的弧段為與道路交叉口相連的若干條道路路段，二者共同組成了道路交通網的結構。

圖1 道路網絡模型

實施道路的最短路徑分析，離不開道路交通要素之間的拓撲關系。如圖2所示，本文定義了如下拓撲關系來表征GIS地理要素之間的連通性、相鄰性等空間關系。基于該空間關系，各個道路路段之間的連通以及道路交叉口節點與道路路段的關聯得以充分地表達，最短路徑的查找與分析得以順利實施。

圖2 道路網的拓撲關系描述

1.2 道路數據庫設計

城市道路交通網主要由道路路段和路段交叉口兩類要素構成，其中道路路段要素包括：平均車速、雙行、單行、禁行和分時通行等，有快速路、主干道、次干道和支路之分；而路段交叉口要素則包括：等候時間、禁止左轉、禁止右轉等參數[2]。針對道路交通網的復雜性，本文采用道路信息表(見表1)和交叉口信息表(見表2)來描述城市交通道路面貌，以滿足系統進行路徑分析的需要。

表1 道路信息表

表2 交叉口信息表

1.3 最短路徑分析

最短路徑分析問題作為圖論問題中的典范，已被應用于計算機科學、運籌學、地理信息系統等眾多學科領域。其根本目的是研究如何安排及籌劃一項網絡工程并且使其運行的效果達到最佳[3]。最短路徑問題最直觀的應用就是在地理信息科學領域，比如制定一項運輸方案，如何使得從A地到B地的運輸費用最低、時間最短、路徑最優。針對最短路徑問題，求解的算法有很多，基本分為靜態最短路徑算法和動態最短路徑算法兩類。其中，靜態最短路徑算法主要應用于外界環境條件保持不變的情況，典型的有Dijkstra算法和A*算法等。動態最短路徑算法主要應用于外界環境不斷發生變化的情況，最為典型的有D*算法。交通運輸區域確定的情況下，可以根據運輸的具體要求來確定所求路徑的目的點，因此可以歸結為單源最短路徑分析問題。Dijkstra算法[4]是典型的單源最短路徑算法，按照路徑長度遞增生成各個節點，計算任意一個節點到其他所有節點的最短路徑。本文基于Dijkstra算法進行系統的開發實踐。

2 交通運輸最短路徑分析系統設計

2.1 系統總體架構

為實現交通運輸指揮的靈活和信息的共享，交通運輸最短路徑分析系統的總體架構如圖3所示。

圖3 系統總體架構

系統分為客戶端和服務器端兩部分，客戶端使用web瀏覽器作為用戶界面，服務器端包括web服務器和GIS服務器，web服務器負責與客戶端之間的通信，GIS服務器負責提供最短路徑分析功能。客戶端發送分析請求給web服務器，web服務器通過代理對象將請求發送至GIS服務器，GIS服務器運行業務邏輯和控制數據訪問，將最終的GIS分析結果返回到客戶端瀏覽器。其中，地理數據庫負責存儲管理基礎地理數據，道路數據庫負責存儲管理交通運輸方面的業務數據(道路、道路交叉口等)。

2.2 系統功能結構

根據交通運輸路徑分析功能需求目標，整個系統分為數據處理、地圖控制、路徑規劃和交通應用4個功能模塊。系統的總體功能結構如圖4所示。

圖4 系統功能結構

1)數據處理：該模塊包括數據入庫、數據拓撲、數據查詢和數據編輯等幾個子模塊。能夠將空間相關信息和道路交通數據導入到數據庫中，并進行有效地組織，完成數據的拓撲、查詢和編輯操作。

2)地圖控制：該模塊實現窗口的顯示控制和圖層的相關操作，能夠對圖層圖形進行平移、縮放、顯示控制等處理，并完成圖層的輸出打印。

3)路徑規劃：該模塊是整個系統的核心模塊。針對具體的運輸任務和實際的應用需求，劃分執行任務的運輸單位，設置每個運輸單位的相關屬性，比如：運輸車隊的車輛總數、車輛的最大載重、最大高度、車隊的行進速度等。在地圖上勾選必經的相關節點(起始點、裝載點、卸載點、終止點等)并執行最短路徑分析，輸出最終的分析結果并生成報表。

4)交通應用：該模塊通過對交通運輸屬性信息、運力統計情況和運輸單位情況進行交互式查詢，選中所需的圖層，根據用戶需要選擇相應的字段，最終以統計圖表和word報表的形式輸出結果。

2.3 交通運輸最短路徑分析流程

在交通運輸的過程中，為了提高送運效率，降低送運成本，需要通過計算起始點與目的點之間的最短路徑來決定最佳的運輸路線。對于運輸單位來說，應該按照任務的要求，沿最短路徑前往運送地點。交通運輸最短路徑分析的流程如圖5所示。

根據實際應用需求，接受運輸任務，明確劃分運輸單位，設置運輸任務及每一運輸單位的相關屬性，具體包括車隊的車輛總數、人員總數、車輛的最大載重量、最大高度、車隊行進速度等，在地圖上勾選必經的相關節點(起始點、裝載點、卸載點、終止點等)并執行最短路徑分析，輸出最終的分析結果并生成報表、輸出報告。

圖5 交通運輸最短路徑分析流程

3 交通運輸最短路徑分析系統實現

根據系統設計方案，采用Microsoft Visual Studio.Net2008(.NET)為平臺，基于某地理信息系統二次開發的工具軟件包和應用開發包，實現交通運輸最短路徑分析系統。該系統中，最短路徑分析組件采用動態鏈接庫形式進行集成，系統工程中各個功能的類結構如圖6所示。

圖6 系統主要類結構圖

圖7 系統分析結果

圖中，CDemo_ShortPathCommand類、CDemo_ShortPathCom類、CDemo_ShortPathTool類以及CDemo_ShortPathUIProcessor類，主要負責整個系統內部命令的處理；CShowNodeDlg類主要用于輔助選點窗口的設置及彈出，顯示最短路徑分析執行前所選節點的類型以及相關備注說明；CAnalyseDlg類用于最短路徑分析窗口的顯示及彈出，設置最短路徑分析的相關參數、執行分析并顯示最終的路線情況。圖7為系統運行后，執行最短路徑分析的可視化結果。

除此之外，系統設計時還采取了形態各異的符號加以標識類型各異的節點，形象直觀地反映了執行最短路徑分析時相關節點的類型，方便用戶的查詢和使用，如圖8所示。

圖8 不同節點符號說明

4 結束語

本文針對交通運輸問題設計的最短路徑分析系統，能夠為運輸單位提供最佳的運輸處理方案和為客戶提供實時貨物送運情況的直觀、可視化查詢功能，充分發揮了GIS為交通運輸服務的優勢。事實上，交通運輸最短路徑分析涉及很多方面內容，在具體的應用實踐中還需要進一步補充和優化。比如擴充算法中的權重值，包括距離、路面情況、交通條件等，實時跟蹤與共享送運車輛的數據、軌跡回放等，都是下一步研究的重點。

[1]胡吉平,魏際剛,王紅梅.基于GIS的交通運輸規劃[J].鐵道學報,2000,22(4):12-15.

[2]李旭華,王建中.基于數據庫的城市道路中最短路徑搜索[J].電腦開發與應用,2005,18(1):14-21.

[3]鄔倫,劉瑜,張晶,等.地理信息系統——原理、方法和應用[M].北京:科學出版社,2001.

[4]司連法,王文靜.快速Dijkstra最短路徑優化算法的實現[J].測繪通報,2005(8):15-18.

[5]JAMES W COOPER.C#Design Patterns[M].BeiJing:Publishing House of Electronics Industry,2003.

[6]華一新,吳升,趙軍喜.地理信息系統原理與技術[M].北京:解放軍出版社,2001.

[7]周長發.C#面向對象編程[M].北京:電子工業出版社,2006.

[責任編輯：劉文霞]

Designandimplementationofthetransportationshortestpathanalysissystem

ZHANG Xiao-nan1,REN Zhi-guo2,CAO Yi-bing1,LIU Rui-xue3

(1.School of Geographic Space Information，Information Engineering University，Zhengzhou 450052,China；2.Chinese Surveying and Mapping Service Corporation，Beijing 100088,China；3.Troops 78155，Chengdu 610036,China)

In view of the insufficient effectiveness of present transportation，it presents a preliminary study of road network model building and road database design，and discusses the process of transportation shortest path analysis.The transportation shortest path analysis system is designed and implemented based on the basic principle of Dijkstra algorithm in order to optimize the resource allocation and realize the high quality and efficiency transportation.

transportation;road network;GIS;shortest path analysis

2012-10-19

張曉楠(1986-)，男，博士研究生.

P208

：A

：1006-7949(2014)01-0025-06