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

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

?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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)表示方法是使用兩個(gè)數(shù)組來表示道路網(wǎng)絡(luò)拓?fù)潢P(guān)系，一個(gè)數(shù)組存儲(chǔ)弧段相關(guān)數(shù)據(jù)，另一個(gè)數(shù)組存儲(chǔ)結(jié)點(diǎn)相關(guān)數(shù)據(jù)。弧段的存儲(chǔ)為一條弧段以兩個(gè)結(jié)點(diǎn)表示。結(jié)點(diǎn)數(shù)組是存儲(chǔ)結(jié)點(diǎn)標(biāo)號(hào)，以此結(jié)點(diǎn)為起點(diǎn)的第一條弧段在弧段數(shù)組中的位置以及該結(jié)點(diǎn)的出度。通過結(jié)點(diǎn)數(shù)組，可以很容易搜索到與此結(jié)點(diǎn)相連的弧段的位置。圖2為簡(jiǎn)化的道路模型，前向星型結(jié)構(gòu)數(shù)據(jù)表示方法如表3和表4所示，表3為存儲(chǔ)結(jié)點(diǎn)相關(guān)數(shù)據(jù)，表4為存儲(chǔ)弧段相關(guān)數(shù)據(jù)。

圖2　簡(jiǎn)化的道路模型

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

表4　弧段數(shù)組

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

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

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

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

(1)

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

(2)

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

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

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

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

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

(3)

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

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

(4)

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

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

(5)

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

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

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

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

設(shè)置一個(gè)通行函數(shù)F(x)，當(dāng)車輛滿足通行高度、通行寬度、通行重量、通行速度以及允許該類車輛通行的條件時(shí)，F(xiàn)(x)的狀態(tài)表現(xiàn)為“true”；當(dāng)車輛對(duì)于4項(xiàng)指標(biāo)至少有一項(xiàng)不滿足時(shí)，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)的值，不僅限制了不同類型車輛通行，同時(shí)可以減少算法的搜索范圍，提高算法的計(jì)算效率。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.2案例算法效率分析

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

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

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

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

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

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

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

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

[3]張喜.帶路徑約束的最短路徑問題與數(shù)據(jù)流查詢技術(shù)研究[D].長(zhǎng)沙:國(guó)防科學(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ì)算機(jī)應(yīng)用，2008，28(5) :1101-1103.

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

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

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

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

[12] 樂陽(yáng)，龔健雅.Dijkstra最短路徑算法的一種高效率實(shí)現(xiàn)[J].武漢測(cè)繪科技大學(xué)學(xué)報(bào)，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

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

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

P208

A

1006-7949(2016)12-0032-06