基于不同交通工具多約束條件的最短路徑算法研究

范林林，李　翔，張　晶， 張江水，趙　婷

(1 信息工程大學(xué)，河南 鄭州，450052；2 中國天繪衛(wèi)星中心,北京 102100 )

?

基于不同交通工具多約束條件的最短路徑算法研究

范林林1，李翔1，張晶2， 張江水1，趙婷1

(1 信息工程大學(xué)，河南 鄭州，450052；2 中國天繪衛(wèi)星中心,北京 102100 )

多約束條件下的最短路徑選擇可以滿足用戶的出行需求，然而不同的交通工具在相同起始點下最短路徑選擇存在很大差異。為了滿足多用戶的出行需求，基于不同交通工具的多約束條件，對傳統(tǒng)的Dijkstra算法進(jìn)行改進(jìn)，由傳統(tǒng)的基于單約束條件向多約束條件改進(jìn)，并對最短路徑選擇的準(zhǔn)確程度進(jìn)行優(yōu)化。通過實例，驗證算法的可行性和準(zhǔn)確程度。

最短路徑；多約束條件；Dijkstra算法；多交通工具

最短路徑問題是GIS網(wǎng)絡(luò)分析最基本最關(guān)鍵的問題。所謂最短路徑，不只是指地理意義上的距離最短，在交通網(wǎng)絡(luò)分析中，最短路徑可以擴(kuò)展到其它的度量，如時間、費用等，相應(yīng)地，最短路徑問題就成為最快路徑、最低費用等問題[1]。在分析運(yùn)輸貨流的最小成本、交通網(wǎng)絡(luò)結(jié)構(gòu)、選擇交通運(yùn)輸路線、建造和維護(hù)通訊線路、規(guī)劃城市公共交通網(wǎng)絡(luò)[2]等方面，都有著廣泛的應(yīng)用。

隨著交通網(wǎng)絡(luò)日益復(fù)雜，不同的用戶在出行時選擇的交通工具存在很大差別，在出行過程中，僅僅為用戶提供路程最短路線和時間最短路線或者單一約束條件下的最短路徑選擇路線，已經(jīng)不能滿足各類用戶的需求。因此，為了制定符合不同用戶需求的路徑方案，本文提出基于GIS對道路進(jìn)行不同交通工具在多約束條件下最短路徑算法，可以快速尋找最短路徑，滿足多用戶的不同出行需求。

1　基于不同交通工具約束道路網(wǎng)絡(luò)數(shù)據(jù)模型的建立

1.1車輛和道路屬性表的設(shè)置

本文主要是針對大型卡車、中小型客車、小轎車、出租車以及自行車的最短路徑選擇進(jìn)行研究。所以，針對不同交通工具定義屬性信息字段，如表1所示。

表1　不同交通工具屬性數(shù)據(jù)設(shè)置

將真實世界中的交通網(wǎng)抽象為網(wǎng)絡(luò)數(shù)據(jù)模型，構(gòu)成網(wǎng)絡(luò)的最基本的元素是線性實體以及這些線性實體的交匯點。線性實體通常稱為鏈(Link)，交匯點通常稱為結(jié)點(node)。交通網(wǎng)中的道路被抽象為鏈，將道路交匯點、拐點、收費站以及標(biāo)志性建筑物等抽象為結(jié)點。為了使構(gòu)建的道路網(wǎng)絡(luò)模型更加真實，在繪制道路網(wǎng)時，針對道路圖層的每一條道路設(shè)置其屬性信息字段，如表2所示。

其中，道路的路段ID是由系統(tǒng)自動生成的唯一標(biāo)識號；道路等級是路段所屬道路的等級類型，如1為高速路，2為主干道，3為次干道等。

表2　道路屬性數(shù)據(jù)設(shè)置

1.2基于不同交通工具的道路網(wǎng)模型建立

建立帶多約束條件的道路網(wǎng)模型是求解帶多約束條件的最短路徑問題的基礎(chǔ)，它描述交通網(wǎng)絡(luò)中點、線、面之間的拓?fù)潢P(guān)系以及道路的每條路段的約束條件[3]。首先，遍歷道路圖層，讀取道路的屬性信息，生成弧段表，每段路段的端點信息依次加入到結(jié)點表中，并檢查是否重復(fù)錄入，如果有重復(fù)，則刪除重復(fù)端點，生成結(jié)點表，如圖1所示。

圖1　結(jié)點表和弧段表

1.3基于不同交通工具的道路網(wǎng)模型的數(shù)據(jù)結(jié)構(gòu)

本文采用前向星型結(jié)構(gòu)表達(dá)道路網(wǎng)模型的數(shù)據(jù)結(jié)構(gòu)[4]。這種數(shù)據(jù)結(jié)構(gòu)表示方法是使用兩個數(shù)組來表示道路網(wǎng)絡(luò)拓?fù)潢P(guān)系，一個數(shù)組存儲弧段相關(guān)數(shù)據(jù)，另一個數(shù)組存儲結(jié)點相關(guān)數(shù)據(jù)?；《蔚拇鎯橐粭l弧段以兩個結(jié)點表示。結(jié)點數(shù)組是存儲結(jié)點標(biāo)號，以此結(jié)點為起點的第一條弧段在弧段數(shù)組中的位置以及該結(jié)點的出度。通過結(jié)點數(shù)組，可以很容易搜索到與此結(jié)點相連的弧段的位置。圖2為簡化的道路模型，前向星型結(jié)構(gòu)數(shù)據(jù)表示方法如表3和表4所示，表3為存儲結(jié)點相關(guān)數(shù)據(jù)，表4為存儲弧段相關(guān)數(shù)據(jù)。

圖2　簡化的道路模型

結(jié)點ID結(jié)點連接弧段結(jié)點出度111212324432541632731861

表4　弧段數(shù)組

2　基于不同交通工具的最短路徑算法的研究

2.1多約束條件下的最短路徑問題描述

多約束路徑問題是一種在給定的帶有多個約束條件的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中尋找一條或多條滿足限定條件的路徑問題[5]。多約束最短路徑問題是在多約束路徑問題的基礎(chǔ)上給這些約束制定一個綜合評估函數(shù)，在滿足多約束路徑問題的前提下，評估函數(shù)值最小的路徑就是多約束最短路徑[6]。本文主要是研究不同交通工具在起點和目標(biāo)點已知并確定的情況下進(jìn)行多約束條件的最短路徑求解問題。

給定一個有向的多個權(quán)值的道路交通網(wǎng)絡(luò)圖Q=(N，R，W)、起始結(jié)點Ns、目標(biāo)結(jié)點Ne和一個約束向量C，其中N是道路結(jié)點集，R是道路路段集，W是每條路段的約束向量集，每條路段的約束向量C是非負(fù)的。設(shè)vi，vj是結(jié)點集V中兩個相連的結(jié)點，道路邊上有n個約束值，則有wk(vi，vj)≥0，其中k∈[1，n]，尋找從Ns到Ne的路徑P，滿足wk(P)≤ck，k∈[1，n]的問題就叫做多約束路徑問題[7-9]。該問題存在一個或多個解P，設(shè)路徑P的評價函數(shù)為

(1)

設(shè)結(jié)點狀態(tài)S={node，EP，P}，其中S為從起始結(jié)點到當(dāng)前結(jié)點的評價值,

(2)

式中:node是網(wǎng)絡(luò)結(jié)構(gòu)中的結(jié)點;EP是j結(jié)點狀態(tài)對應(yīng)路徑的評價函數(shù);P用來存儲搜索路徑中到達(dá)當(dāng)前結(jié)點的前一個結(jié)點[11]。

2.2道路網(wǎng)中基于不同條件的最優(yōu)路徑權(quán)值設(shè)計

在越來越復(fù)雜的交通模式下，對于不同用戶來說，所選擇的交通工具不同，則相同起始點情況下所選擇的路徑存在很大的差別?，F(xiàn)實生活中，用戶的出行主要考慮的是：出發(fā)點和目標(biāo)點之間基于不同交通工具是否可通行、出發(fā)點與目標(biāo)點之間的距離最短、出發(fā)點與目標(biāo)點之間的時間最短以及出發(fā)點與目標(biāo)點之間的費用最少。

1)不同交通工具通行度：主要是道路的承重、限寬、限高以及大型車輛禁止通行路段，所以道路的權(quán)值取0或者1；其中0表示該路段不可通行，1表示該路段可以通行。

2)距離最短：當(dāng)選擇距離最短時，道路的權(quán)值直接取路段長度，為

(3)

式中：wij表示兩個結(jié)點vi，vj之間路段的權(quán)值；dij表示兩個結(jié)點vi，vj之間的距離。

3)時間最短：當(dāng)選擇時間最短時，會優(yōu)先選擇高速路以及避開擁堵路段，所以道路的權(quán)值取

(4)

式中：λ1為高速路的比例系數(shù)；λ2為路段擁擠狀況比例系數(shù)。

4)費用最少：當(dāng)選擇費用最少時，會選擇避開收費路段，考慮距離相對較短的路段以減少燃油費用，所以道路的權(quán)值取

(5)

式中：λ1為收費路段的比例系數(shù)；k是不同類型交通工具的收費標(biāo)準(zhǔn)。

2.3改進(jìn)Dijkstra算法應(yīng)用于多約束條件下的最短路徑求解

Dijkstra算法是解決單源點單約束條件下最短路徑問題最經(jīng)典、比較有效的算法[12]，所以通過對Dijkstra經(jīng)典算法的改進(jìn)來實現(xiàn)多約束條件下的最短路徑選擇問題。

根據(jù)抽象的道路網(wǎng)模型，將道路的通行高度(RoadLimitHight)、通行寬度(RoadLimitWidth)、通行重量(RoadLimitWeight)、通行速度(RoadLimitspeed)以及是否允許大型交通工具通行(Prohibited Vehicles)作為約束條件加以約束。為了實現(xiàn)基于某種交通工具的最短路徑查詢，在查詢前，需要設(shè)置該類交通工具的最大通行高度(MaxHight)、最大通行寬度(MaxWidth)、最大通行重量(MaxWeight)、最大通行速度(RoadLimitspeed)以及在某個路段是否允許通行(1/0)。

設(shè)置一個通行函數(shù)F(x)，當(dāng)車輛滿足通行高度、通行寬度、通行重量、通行速度以及允許該類車輛通行的條件時，F(xiàn)(x)的狀態(tài)表現(xiàn)為“true”；當(dāng)車輛對于4項指標(biāo)至少有一項不滿足時，F(xiàn)(x)的狀態(tài)表現(xiàn)為“false”。

F(x)=(RoadLimitHight(x)>MaxHight(x)&&RoadLimitWidth(x)>MaxWidth(x)&&RoadLimitWeight(x)>MaxWeight(x)&&RoadLimitspeed(x)>Maxspeed(x)&&1)

通過判斷F(x)的值，不僅限制了不同類型車輛通行，同時可以減少算法的搜索范圍，提高算法的計算效率。

多約束Dijkstra算法(M-Dijkstra)流程如圖3所示。

圖3　多約束條件下Dijkstra算法改進(jìn)流程

2.4基于不同交通工具的多約束條件下最短路徑算法的實現(xiàn)

基于不同交通工具的最短路徑選擇問題應(yīng)用改進(jìn)Dijkstra算法求解最短路徑的具體實現(xiàn)過程如下：

第一步：選擇出行的交通車輛，根據(jù)系統(tǒng)設(shè)置，會自動為選擇的交通車輛進(jìn)行屬性賦值，包含VehicleMhight(汽車通行的最大高度)、VehicleMwidth(汽車通行的最大寬度)、VehicleMweight(汽車通行的最大重量)、VehicleMspeed(汽車通行的最大速度)以及根據(jù)VehicleID(汽車標(biāo)識)確定所禁止通行的道路路段。

第二步：在地圖上選擇StartPoint(起點)和EndPoint(目標(biāo)點)兩個結(jié)點。

第三步：首先判斷StartPoint和EndPoint是否連通，如果連通，則進(jìn)入下一步，否則，終止。

第四步：根據(jù)確定的StartPoint和EndPoint，用改進(jìn)的Dijkstra算法計算基于不同的交通工具在多約束條件下的最短路徑。

第五步：將計算得到的最短路徑可視化顯示在地圖上(見圖4)。根據(jù)交通工具的不同，選擇不同色彩可視化每一條最短路徑。

3　應(yīng)用案例與分析

在實際生活中，由于用戶需求的復(fù)雜性，導(dǎo)致用戶在選擇交通工具時的多樣性。由于不同的交通工具在選擇最短路徑問題上存在著很大的差異，根據(jù)不同的需求，在選擇不同交通工具的基礎(chǔ)上，為不同的用戶規(guī)劃出合理的通行方案。例如，在城市交通中，居民社區(qū)、步行街道以及一些狹窄的街道等都是小型交通工具以上車輛禁止通行的；在高速路上，物資器材的運(yùn)輸路線要考慮收費站問題、隧道限高問題以及道路橋梁的承重問題等。所以，針對用戶出行問題，為不同的用戶提供合適的交通工具最短路線是一個值得研究的問題。在本文中，基于不同交通工具選擇最短路徑問題轉(zhuǎn)化為多約束條件下的最短路徑選擇問題。

3.1不同交通工具的多約束條件下最短路徑案例

本文實驗所采用的數(shù)據(jù)是美國舊金山這一城市地區(qū)的道路網(wǎng)絡(luò)數(shù)據(jù)。通過交通網(wǎng)絡(luò)案例來討論改進(jìn)的Dijkstra算法在不同交通工具選擇最短路徑時的應(yīng)用。為了更好地證明Dijkstra算法的可行性，對道路模型進(jìn)行簡化處理，在道路路段上設(shè)置3個約束條件，分別是：收費系數(shù)、路段長度和能否允許大型車輛通行，以實現(xiàn)費用最少為目標(biāo)的最優(yōu)路徑選擇。其中：① 收費系數(shù)與交通工具的類型有關(guān)，所以，當(dāng)選取不同的交通工具時，道路的約束條件會發(fā)生變化，不妨設(shè)收費系數(shù)為K。② 路段長度會影響交通工具的燃油量，進(jìn)而影響消耗金額，不妨設(shè)每升汽油的單價為m，m>5，則在路段上不同交通工具由路段長度影響的金額描述為M=k×m×dij。③自行車不允許在高速路上行駛。

圖4　對基于不同交通工具在多約束條件下的最短路徑算法的可視化表達(dá)

通過對道路添加約束條件，分別得到大型卡車(big car)、中小型客車(small car)、私家車(home car)和自行車輛(bike)的基于相同起止結(jié)點的路線選擇。通過對不同交通工具在相同起止結(jié)點下的高速收費系數(shù)、全程費用、全程行駛距離以及全程行駛時間進(jìn)行描述，結(jié)果如表5所示。

表5　不同交通工具的多約束條件下的路徑規(guī)劃結(jié)果

3.2案例算法效率分析

基于不同交通工具的多約束條件下的最短路徑選擇采用的算法是對經(jīng)典的Dijkstra算法進(jìn)行改進(jìn)，由原來算法中的單個約束條件增加為改進(jìn)后的多個約束條件，對改進(jìn)算法后得到的結(jié)果、經(jīng)典算法得到的結(jié)果以及實際結(jié)果進(jìn)行對比分析，其中，根據(jù)統(tǒng)計不同車輛在相應(yīng)路段的行駛時間得出的平均值作為該實驗的實際結(jié)果與算法得到的結(jié)果進(jìn)行比較。對比結(jié)果如表6所示。

經(jīng)上述結(jié)果分析，本文得出如下結(jié)論：在道路連通的情況下，改進(jìn)的Dijkstra算法可以基于不同的交

通工具在多約束條件下解決最短路徑選擇問題。通過比較實際情況的行駛時間和基于改進(jìn)的算法求解出的行駛時間得到的準(zhǔn)確度，得出改進(jìn)后的Dijkstra算法具備良好的尋找最短路徑的能力，改進(jìn)與實際的百分比越高說明改進(jìn)的算法基于不同交通工具的準(zhǔn)確性越高，所以根據(jù)改進(jìn)與實際的百分比得出改進(jìn)的算法對私家車、自行車、中小型客車的適用性較強(qiáng)，對大型卡車的適用性相對較弱一些。通過比較改進(jìn)算法得到最短路徑的行駛時間和經(jīng)典算法得到的最短路徑的行駛時間進(jìn)行對比，得出增加多個約束條件可以提高最短路徑選擇結(jié)果的準(zhǔn)確性。

表6　兩種算法的準(zhǔn)確度比較

4　結(jié)束語

隨著經(jīng)濟(jì)的快速發(fā)展，用戶對于采用不同交通工具所選擇的路徑規(guī)劃需求也在不斷提升，本文的目的在于為不同需求的用戶提供最合理的路線。分別獲取不同交通工具的屬性信息以及道路的屬性信息，對道路建立道路網(wǎng)模型，并對經(jīng)典的Dijkstra算法通過增加多個約束條件進(jìn)行改進(jìn)，應(yīng)用改進(jìn)的Dijkstra算法求解基于不同交通工具的多約束條件下的最短路徑問題；最后，通過對兩種算法之間以及改進(jìn)算法結(jié)果與實際結(jié)果的比較，說明改進(jìn)的算法不僅具有良好的尋找最短路徑的能力，同時也在原來算法的基礎(chǔ)上提高結(jié)果的準(zhǔn)確性。本文不僅為廣大不同需求的用戶在使用不同交通工具選擇最短路徑時提供合理的路徑規(guī)劃，也為Dijkstra算法的應(yīng)用開拓更廣闊的發(fā)展空間。

[1]郭仁忠.空間分析[M].北京:高等教育出版社，2001.

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

[3]張喜.帶路徑約束的最短路徑問題與數(shù)據(jù)流查詢技術(shù)研究[D].長沙:國防科學(xué)技術(shù)大學(xué)，2007.

[4]秦昆.GIS空間分析理論與方法[M].武漢:武漢大學(xué)出版社，2010.

[5]LI Y，HANGNS J，HOLTE R.Fast exact multi-constraint shortest path algorithms[C]. IEEE Communications Society subject matter experts for publication in the ICC 2007 Proceedings，123-130.

[6]JAFFE J M. Algorithms for finding paths with multiple constraints [J]. Networks，1984，14:95-116.

[7]鄒永貴，魏來.帶多約束條件的最優(yōu)路徑選擇算法研究[J].計算機(jī)應(yīng)用，2008，28(5) :1101-1103.

[8]王歡，張雁，陳旭.基于開源pgRouting的WebGIS最短路徑算法實現(xiàn)研究[J].測繪與空間地理信息，2015,38(2)：81-84.

[9]吳超輝，滑騰飛，周永望.基于ESPO算法的裝甲部隊城市道路機(jī)動路徑選擇[J].測繪與空間地理信息，2015,38(3)：4-6.

[10] 廖建軍.基于道路交通網(wǎng)絡(luò)的多約束最優(yōu)路徑算法研究[D].南京:南京理工大學(xué)，2009.

[11] 王海梅.基于GIS的最優(yōu)路徑算法研究與實現(xiàn)[D].南京:南京理工大學(xué)，2008.

[12] 樂陽，龔健雅.Dijkstra最短路徑算法的一種高效率實現(xiàn)[J].武漢測繪科技大學(xué)學(xué)報，1999，24(3) :209-212.

[責(zé)任編輯：張德福]

Research on the shortest path selection based on differenttransportation under multiple constraints

Fan Linlin1, LI Xiang1, ZHANG Jing2, ZHANG Jiangshui1, ZHAO Ting1

(1.Information Engineering University, Zhengzhou 450052, China; 2.China Tianhui Satellite Center, Beijing 102100, China)

The shortest path selection under the multiple constraints can meet user’s requirements. However, there is a big difference among different means of transportation in the same starting point for the shortest path selection. In order to satisfy the user’s travel demand, in this paper, the traditional Dijkstra algorithm is improved, which applies the shortest path query with different traffic tools under multiple constraint condition. In the process of the algorithm improved, the accuracy of the shortest path selection is optimized. An example shows the final visual result can verify the feasibility and the accuracy of this algorithm.

shortest path; multiple constraint condition; Dijkstra algorithm; multiple transportation vehicle

10.19349/j.cnki.issn1006-7949.2016.12.007

2015-07-22

國家科技支撐計劃資助項目(2012BAK12B02)；國家自然科學(xué)基金青年科學(xué)基金項目(41401467)；國家自然科學(xué)基金面上項目(41471336)；國家自然科學(xué)基金資助項目(41271450)

范林林(1991—)，女，碩士研究生.

P208

A

1006-7949(2016)12-0032-06