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

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

?

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

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

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

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

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

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

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

1　基于不同交通工具約束道路網絡數據模型的建立

1.1車輛和道路屬性表的設置

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

表1　不同交通工具屬性數據設置

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

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

表2　道路屬性數據設置

1.2基于不同交通工具的道路網模型建立

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

圖1　結點表和弧段表

1.3基于不同交通工具的道路網模型的數據結構

本文采用前向星型結構表達道路網模型的數據結構[4]。這種數據結構表示方法是使用兩個數組來表示道路網絡拓撲關系，一個數組存儲弧段相關數據，另一個數組存儲結點相關數據。弧段的存儲為一條弧段以兩個結點表示。結點數組是存儲結點標號，以此結點為起點的第一條弧段在弧段數組中的位置以及該結點的出度。通過結點數組，可以很容易搜索到與此結點相連的弧段的位置。圖2為簡化的道路模型，前向星型結構數據表示方法如表3和表4所示，表3為存儲結點相關數據，表4為存儲弧段相關數據。

圖2　簡化的道路模型

結點ID結點連接弧段結點出度111212324432541632731861

表4　弧段數組

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

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

多約束路徑問題是一種在給定的帶有多個約束條件的網絡拓撲結構中尋找一條或多條滿足限定條件的路徑問題[5]。多約束最短路徑問題是在多約束路徑問題的基礎上給這些約束制定一個綜合評估函數，在滿足多約束路徑問題的前提下，評估函數值最小的路徑就是多約束最短路徑[6]。本文主要是研究不同交通工具在起點和目標點已知并確定的情況下進行多約束條件的最短路徑求解問題。

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

(1)

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

(2)

式中:node是網絡結構中的結點;EP是j結點狀態(tài)對應路徑的評價函數;P用來存儲搜索路徑中到達當前結點的前一個結點[11]。

2.2道路網中基于不同條件的最優(yōu)路徑權值設計

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

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

2)距離最短：當選擇距離最短時，道路的權值直接取路段長度，為

(3)

式中：wij表示兩個結點vi，vj之間路段的權值；dij表示兩個結點vi，vj之間的距離。

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

(4)

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

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

(5)

式中：λ1為收費路段的比例系數；k是不同類型交通工具的收費標準。

2.3改進Dijkstra算法應用于多約束條件下的最短路徑求解

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

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

設置一個通行函數F(x)，當車輛滿足通行高度、通行寬度、通行重量、通行速度以及允許該類車輛通行的條件時，F(x)的狀態(tài)表現為“true”；當車輛對于4項指標至少有一項不滿足時，F(x)的狀態(tài)表現為“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算法改進流程

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

基于不同交通工具的最短路徑選擇問題應用改進Dijkstra算法求解最短路徑的具體實現過程如下：

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

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

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

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

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

3　應用案例與分析

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

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

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

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

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

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

3.2案例算法效率分析

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

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

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

表6　兩種算法的準確度比較

4　結束語

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

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

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

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

[4]秦昆.GIS空間分析理論與方法[M].武漢:武漢大學出版社，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].計算機應用，2008，28(5) :1101-1103.

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

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

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

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

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

[責任編輯：張德福]

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)；國家自然科學基金青年科學基金項目(41401467)；國家自然科學基金面上項目(41471336)；國家自然科學基金資助項目(41271450)

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

P208

A

1006-7949(2016)12-0032-06