交通運輸最短路徑分析系統(tǒng)的設(shè)計與實現(xiàn)

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

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

交通運輸最短路徑分析系統(tǒng)的設(shè)計與實現(xiàn)

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

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

針對目前交通運輸效力發(fā)揮不足的問題，研究道路網(wǎng)絡(luò)模型構(gòu)建和道路數(shù)據(jù)庫設(shè)計，探討分析交通運輸最短路徑分析流程，基于Dijkstra算法的基本原理，設(shè)計實現(xiàn)交通運輸最短路徑分析系統(tǒng)，從而優(yōu)化運輸資源配置，實現(xiàn)高質(zhì)高效的交通運輸。

交通運輸;道路網(wǎng)絡(luò);GIS;最短路徑分析

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

1 道路網(wǎng)絡(luò)模型構(gòu)建

1.1 道路網(wǎng)絡(luò)模型

城市道路交通網(wǎng)錯綜復(fù)雜，縱橫交織，由成百上千條道路相連、相交構(gòu)成。每條道路的地理位置以及道路與道路之間的相互位置關(guān)系，都會影響交通運輸網(wǎng)的結(jié)構(gòu)和組成。僅以道路相連的情況來看，一條道路可能就與若干條道路相連，且相連的模式多種多樣。為此，本文抽取交通網(wǎng)中道路之間的交叉口作為單獨分析的對象，然后使用交叉口作為節(jié)點將每條道路分割成段，從而避免道路之間復(fù)雜多樣的拓撲關(guān)系，最終構(gòu)建基于路段連接的道路網(wǎng)絡(luò)模型?；谠撃Ｐ停麄€交通網(wǎng)絡(luò)圖由路口交叉節(jié)點和路段構(gòu)成，交叉口節(jié)點構(gòu)成網(wǎng)絡(luò)的節(jié)點，道路路段構(gòu)成網(wǎng)絡(luò)的弧。

如圖1所示，路網(wǎng)中的節(jié)點為道路交叉口，路網(wǎng)中的弧段為與道路交叉口相連的若干條道路路段，二者共同組成了道路交通網(wǎng)的結(jié)構(gòu)。

圖1 道路網(wǎng)絡(luò)模型

實施道路的最短路徑分析，離不開道路交通要素之間的拓撲關(guān)系。如圖2所示，本文定義了如下拓撲關(guān)系來表征GIS地理要素之間的連通性、相鄰性等空間關(guān)系?；谠摽臻g關(guān)系，各個道路路段之間的連通以及道路交叉口節(jié)點與道路路段的關(guān)聯(lián)得以充分地表達，最短路徑的查找與分析得以順利實施。

圖2 道路網(wǎng)的拓撲關(guān)系描述

1.2 道路數(shù)據(jù)庫設(shè)計

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

表1 道路信息表

表2 交叉口信息表

1.3 最短路徑分析

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

2 交通運輸最短路徑分析系統(tǒng)設(shè)計

2.1 系統(tǒng)總體架構(gòu)

為實現(xiàn)交通運輸指揮的靈活和信息的共享，交通運輸最短路徑分析系統(tǒng)的總體架構(gòu)如圖3所示。

圖3 系統(tǒng)總體架構(gòu)

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

2.2 系統(tǒng)功能結(jié)構(gòu)

根據(jù)交通運輸路徑分析功能需求目標(biāo)，整個系統(tǒng)分為數(shù)據(jù)處理、地圖控制、路徑規(guī)劃和交通應(yīng)用4個功能模塊。系統(tǒng)的總體功能結(jié)構(gòu)如圖4所示。

圖4 系統(tǒng)功能結(jié)構(gòu)

1)數(shù)據(jù)處理：該模塊包括數(shù)據(jù)入庫、數(shù)據(jù)拓撲、數(shù)據(jù)查詢和數(shù)據(jù)編輯等幾個子模塊。能夠?qū)⒖臻g相關(guān)信息和道路交通數(shù)據(jù)導(dǎo)入到數(shù)據(jù)庫中，并進行有效地組織，完成數(shù)據(jù)的拓撲、查詢和編輯操作。

2)地圖控制：該模塊實現(xiàn)窗口的顯示控制和圖層的相關(guān)操作，能夠?qū)D層圖形進行平移、縮放、顯示控制等處理，并完成圖層的輸出打印。

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

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

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

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

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

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

3 交通運輸最短路徑分析系統(tǒng)實現(xiàn)

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

圖6 系統(tǒng)主要類結(jié)構(gòu)圖

圖7 系統(tǒng)分析結(jié)果

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

除此之外，系統(tǒng)設(shè)計時還采取了形態(tài)各異的符號加以標(biāo)識類型各異的節(jié)點，形象直觀地反映了執(zhí)行最短路徑分析時相關(guān)節(jié)點的類型，方便用戶的查詢和使用，如圖8所示。

圖8 不同節(jié)點符號說明

4 結(jié)束語

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

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

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

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

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

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

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

[7]周長發(fā).C#面向?qū)ο缶幊蘙M].北京:電子工業(yè)出版社,2006.

[責(zé)任編輯：劉文霞]

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