張曉楠，任志國(guó)，曹一冰，劉瑞雪

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

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

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

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

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

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

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

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

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

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

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

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

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

圖2 道路網(wǎng)的拓?fù)潢P(guān)系描述

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

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

表1 道路信息表

表2 交叉口信息表

1.3 最短路徑分析

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

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

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

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

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

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

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

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

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

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

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

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

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

2.3 交通運(yùn)輸最短路徑分析流程

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

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

圖5 交通運(yùn)輸最短路徑分析流程

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

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

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

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

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

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

圖8 不同節(jié)點(diǎn)符號(hào)說(shuō)明

4 結(jié)束語(yǔ)

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

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

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

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

[4]司連法,王文靜.快速Dijkstra最短路徑優(yōu)化算法的實(shí)現(xiàn)[J].測(cè)繪通報(bào),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]周長(zhǎng)發(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