吳紅波，王英杰，楊肖肖

(1. 陜西理工大學 地理科學系，陜西 漢中 723000；2. 西北大學 陜西省地表系統(tǒng)與環(huán)境承載力重點實驗室，西安 710127；3. 北京交通大學 土木建筑工程學院，北京 100044)

路徑分析是城市交通網(wǎng)絡分析的研究內(nèi)容之一，也是地理信息系統(tǒng)(Geographic Information System，GIS)空間分析功能的組成部分，并在城市道路管理、網(wǎng)絡通信、交通規(guī)劃等方面得到廣泛應用[1].路徑分析的核心是最短路徑、最佳路徑的求解，而路徑優(yōu)化是利用運籌學規(guī)劃模型使道路網(wǎng)絡使用、車輛調(diào)度、貨物配送等的運行效率達到最優(yōu).

地理信息系統(tǒng)是將關(guān)系數(shù)據(jù)庫管理、圖形算法、空間插值、區(qū)劃和網(wǎng)絡分析等功能集成于一體，能有效管理地理空間數(shù)據(jù)，其空間分析可為智慧交通建設提供技術(shù)支持.近年來，隨著網(wǎng)絡信息、物聯(lián)網(wǎng)和移動互聯(lián)技術(shù)的日益發(fā)展，GIS技術(shù)被應用于物流配送、交通規(guī)劃、道路選址、路徑優(yōu)化研究[2]，使得海量地理信息的提取、表現(xiàn)和傳輸任務變得簡單易行.在現(xiàn)實中，最短路徑指的是帶權(quán)圖上的最短路徑問題，不僅是歐氏空間中的距離最短，也可以是時間最短、費用最少、線路使用率最優(yōu)[3].Papinski等[4]考慮距離、行程時間、速度統(tǒng)計、交叉口數(shù)、匝數(shù)、停車標志/停車燈數(shù)量和路線迂回等變量，借助GIS路徑分析工具箱，對比分析時間最短和距離最短的優(yōu)化時間.Yang等[5]基于GIS網(wǎng)絡分析工具模塊,對車輛規(guī)劃路線和固定路線的運輸服務范圍、運營成本、成本效益進行綜合分析.Huang[6]利用GIS網(wǎng)絡分析和層次分析法(Analytic Hierarchy Process，AHP),分析了道路網(wǎng)絡中的每個鏈路的影響因素，結(jié)合危險品運輸車的安全性和運輸成本，通過成本函數(shù)模型,量化出每個運輸路線的適用性.針對小學生從學校到家庭住處的行走路線，Duncan等[7-8]聯(lián)合GPS(Global Positioning System)和GIS技術(shù),分析了選線過程中行駛距離、道路節(jié)點、道路擁堵的影響，幫助人們快速確定最短路徑.關(guān)于最短路徑分析算法研究已有較多報道[9-10]，Bellman算法、Dijkstra算法、Dreyfus算法已成為確定情況下的經(jīng)典算法.而不確定情況下的最短路徑問題，大致分為4個方面[11]：研究路段長度隨機變化的最短路徑；研究不同費用函數(shù)的最短路徑；研究時間獨立情況下的路段長度隨機變化的最短路徑；研究路段長度為區(qū)間范圍的最短路徑.但以上最短路徑分析未考慮城市車輛在實際行駛中對道路選線的不確定因素，為此本文作者在傳統(tǒng)Dijkstra算法優(yōu)化基礎上做進一步研究:首先，借助GIS網(wǎng)絡分析技術(shù),將城市道路網(wǎng)絡轉(zhuǎn)換成有向圖，包含節(jié)點和鏈路；其次，將城市道路網(wǎng)絡節(jié)點和路段上距離或時間阻強(障礙、限速、節(jié)點延遲)作為約束條件；再次，考慮道路類型、節(jié)點停留時間、限速、車輛行駛方向等條件，對比分析從起點到終點的時間或費用；最后，根據(jù)時間成本和距離成本約束因素，分別對無約束條件、障礙路況、限速模式下的最短路線進行了實地驗證，并確定最優(yōu)路線.

1 路徑分析模型

1.1 Dijkstra算法

Dijkstra算法是1959年由荷蘭計算機科學家Dijkstra提出的圖論中求最短路徑的常用算法[12]，該算法可求得圖中一點到其他任一頂點的最短路徑[13].Dijkstra算法將網(wǎng)絡節(jié)點分成3部分：未標記節(jié)點、臨時標記節(jié)點和永久標記節(jié)點.在網(wǎng)絡圖中，將所有節(jié)點初始化為未標記節(jié)點，在搜索過程中游歷節(jié)點和任一路徑中相連通的節(jié)點為臨時標記節(jié)點，每次循環(huán)都是把從臨時標記節(jié)點中搜索距起源點路徑長度最短的節(jié)點作為永久標記節(jié)點，直至找到目標節(jié)點或者所有的節(jié)點都成為永久標記節(jié)點后才算法結(jié)束.如圖1所示，假設節(jié)點網(wǎng)絡的起源點為節(jié)點0，目標點為節(jié)點4，求節(jié)點0到節(jié)點4最短路徑的距離(各節(jié)點間的長度是假設的).

圖1 路徑的節(jié)點網(wǎng)絡Fig.1 The meshed network of the route

假設每個節(jié)點都有一對標號(wi，pj)，wi是起源點到目標點的最短路徑的長度，wj是從起源點s到任意節(jié)點j的最短路徑長度(從頂點到其本身的最短路徑是零路(沒有弧的路)，其長度等于零),pj為從起源點s到節(jié)點j的最短路徑中j點的前一節(jié)點.求解從起源點i到目標節(jié)點j的最短路徑，基本過程如下：

1)初始化.起源點設置為

①若起源點s最短路徑長度ws=0，ps為空；

②所有其他節(jié)點的路徑長度wi=，pi=s；

③標記起源點s.記所有已標記的節(jié)點k=s，其他節(jié)點設為未標記的.

2)檢驗從所有已標記的節(jié)點k到其直接連接的未標記節(jié)點j的距離，并設置

wj=min{wj，wk+dkj}

(1)

式中：wj是未標記節(jié)點j的最短路徑長度；wk是已標記節(jié)點k的最短路徑長度；dkj是從節(jié)點k到節(jié)點j的直接連接距離.

3)選取下一個點.從所有未標記的節(jié)點wj中，選取最小的一個標記節(jié)點i,即wi=minwj(所有未標記的節(jié)點j)，節(jié)點i就被選為最短路徑中的一點，并設為已標記的點.

4)找到節(jié)點i的前一點.從已標記的節(jié)點中找到直接連接到節(jié)點i的點j′，作為前一點，設置i=j′.

5)標記點i.如果所有節(jié)點已標記，則算法求出最短路徑(見表1);否則，記k=i，轉(zhuǎn)到步驟2)再繼續(xù).

表1 0節(jié)點到4節(jié)點的最短路徑

1.2 算法優(yōu)化

Dijkstra算法優(yōu)化思路如下：首先,從起源點s的臨時集合NBs(與起源點s直接相連的節(jié)點集合)中選擇距離最小的鄰居節(jié)點k作為轉(zhuǎn)接點，同時劃歸到標識集合S(初始時，為S{s})；然后，對k臨時集合與標識集合的差集中節(jié)點的值進行更新，從標識集合S中所有節(jié)點的臨時集合的并集與標識集合的差集(∪NBsS，i∈S)中選擇一個路徑距離值最小的節(jié)點Wk作為下一個轉(zhuǎn)接點，并劃歸到標識集合S中.重復上述過程，直到所有的節(jié)點都被標識過，即|s|=n，算法結(jié)束.

設NBi為節(jié)點i的臨時集合,S為標識集合,wi是從源點s到節(jié)點j的最短路徑長度,Pi是從s到j的最短路徑中j點的前一節(jié)點,dij是節(jié)點i到節(jié)點j的距離.算法過程[14]如下:

1)初始化標識集合S={s},wi=dsi(i∈NBs),否則wi=(i?NBs)；Pi=s.

2)若k臨時集合節(jié)點到起源點距離最小dsk=mindsi，則S=S∪{k}，j∈NBs.

3)修改k臨時集合節(jié)點NBk=S中的wi值,wi=min{wi，wk+dki}；若wi值改變，則Pj=k，j∈NBs-S.

4)選定已標記的臨時節(jié)點集合NBi-S(i∈S)中的wi最小值，并將其劃歸到s中,wk=minwi,S=S∪{k}；若|s|=n,節(jié)點已標識，則算法終止，否則轉(zhuǎn)到步驟3).

對于節(jié)點總數(shù)為n的網(wǎng)絡圖，Dijkstra算法求解最短路徑總共需要迭代n-1次，每次迭代都新加一個節(jié)點到臨時節(jié)點集合中，由于第i次迭代時不在臨時節(jié)點集合中的節(jié)點數(shù)為n-i.那么，第i次迭代需對n-i個節(jié)點進行處理的次數(shù)為

(2)

當式(2)中的網(wǎng)絡節(jié)點數(shù)量為n時，路徑求解的時間復雜度為O(n2)，即為網(wǎng)絡圖上從起源點到其余各節(jié)點的最短路徑求解的時間復雜度.隨著節(jié)點總數(shù)n的增大，其計算效率和存儲效率降低.

時間復雜度O(n2)取決于轉(zhuǎn)接點k的臨時集合NBs的元素數(shù)量，那么優(yōu)化算法空間復雜度為O(n×p)，其中p為鄰接矩陣存儲結(jié)構(gòu)N×N下節(jié)點對象所占用的空間，是常量.另外，根據(jù)網(wǎng)絡節(jié)點和路段的個數(shù)，可以求出節(jié)點的平均出度e,即

(3)

式中：m為路段數(shù).

一般在GIS網(wǎng)絡關(guān)系圖中，e∈[1，4]，由于步驟3)、步驟4)都是搜索與Vi(i=l，2，3，…，n)相鄰的節(jié)點操作，時間復雜度均為O(n×e)；步驟4)的時間復雜度為O(m)，即O(n×e).

1.3 模型構(gòu)建

選取漢中市主城區(qū)道路網(wǎng)絡作為研究數(shù)據(jù)，將高速公路、國道、省道、縣道、鐵路、主干道、次干道、鄉(xiāng)鎮(zhèn)道路等矢量要素導入到本地地理數(shù)據(jù)庫.首先，指定參與道路網(wǎng)絡矢量要素的拓撲等級,設置容限值(限速、限行)和轉(zhuǎn)彎模型，建立道路弧線段-節(jié)點拓撲網(wǎng)絡模型；其次，根據(jù)道路網(wǎng)絡節(jié)點-弧線段連通規(guī)則，設定費用變量和約束變量，費用變量為路徑成本費用[15]，約束變量屬性字段為布爾值，即為單行和雙行線；最后，設定道路網(wǎng)絡中路段的行駛方向和節(jié)點延遲.通過網(wǎng)絡拓撲規(guī)則和關(guān)系，建立節(jié)點和路段連接的有向網(wǎng)絡圖，其模型為

(4)

式中：Rw代表道路網(wǎng)絡；N代表節(jié)點集；R代表路段集合，其元素為有序?qū)Α磝,y〉，且表示由節(jié)點x到節(jié)點y存在一條有向通路；LR代表路段的加權(quán)長度，其元素L(x,y)表示有向路段〈x,y〉的加權(quán)長度；lxy為節(jié)點x到節(jié)點y的任一路段長度.

路段的加權(quán)長度LR是指根據(jù)多目標函數(shù)和規(guī)劃要求，綜合各種動態(tài)和靜態(tài)屬性約束條件后求解的最優(yōu)路徑[16]，而并非路徑的實際距離或者長度.因此，最優(yōu)路徑不僅指一般地理空間意義上的距離最短[17]，還可以引申到時間、費用、線路容量等[18].

1.4 阻強問題

道路網(wǎng)絡既有起點、終點、停靠點、路徑、路障等，又有費用成本、等級、限制和描述符[19].其中，阻強是網(wǎng)絡中的節(jié)點或路段因某些突發(fā)事件(如交通事故)而不可運行時，原來獲得的最優(yōu)路徑需要進行修正，具體步驟如下：

1)修路時，即某個路段不可運行，屬于永久性的.當?shù)缆吩诰S修時，最優(yōu)路徑的距離也隨著維修狀態(tài)而發(fā)生改變.

2)交叉路口出現(xiàn)車禍等情況時，暫時不可通行，即網(wǎng)絡中的節(jié)點不可運行，延長了車輛行駛時間.

任一路徑的綜合路阻C采用加權(quán)求和法計算[20]，有

(5)

式中：Ci為第i路段的綜合路阻；Dij為第i路段中的路阻因素分值；aj為第j路阻因素權(quán)重.

任一路段路阻因素分值Dij的計算采用上限測度，計算公式為

Dij=dij/dj，max

(6)

式中：Dij為第i路段j路阻因素分值；dij為路阻因素的實際值；dj，max為第j路阻因素的最大實際值.

2 結(jié)果與討論

2.1 無約束條件下的最優(yōu)路徑

假設漢中站為初始源點，陜西理工大學南校區(qū)南門為目標節(jié)點，在任意路口可以調(diào)頭，計算漢中站—陜西理工大學南校區(qū)南門的距離和時間最優(yōu)路徑.如圖2(a)所示，在車輛行駛速度理想的狀態(tài)下，從漢中站到陜西理工大學南校區(qū)南門的距離最短路線長為4 377.8 m，所用時間成本為10.7 min，而在時間約束模式下的路線距離為4 384.9 m，行駛時長最小為9.7 min，如圖2(b)所示.在實際行駛中，路線選擇受駕駛員對時間最短和距離最短的偏好影響.

(a)距離最短路徑

(b)時間最短路徑圖2 路徑選擇Fig.2 Route choice

2.2 障礙路況下的最優(yōu)路徑

假設在繁雜路口、事故現(xiàn)場、醫(yī)院等位置節(jié)點車流量大，設置臨時障礙點，短時間內(nèi)車輛禁止通過，計算距離最短和時間最短路徑.如圖3所示，在障礙路況下，車輛行駛的最短距離為4 610.3 m，時間成本為10.7 min;最短行駛時間為10.2 min，行駛距離為4 630.6 m，二者在時間和距離成本上相差不大.這表明,從漢中站到陜西理工大學南校區(qū)南門時，最優(yōu)路徑的選擇受行駛距離或行駛時間成本的影響甚微，不起決定性作用，可在時間成本和距離成本模式下自主選擇.

(a)距離最短路徑

(b)時間最短路徑圖3 障礙路況下路徑選擇Fig.3 Route choice under the barrier

2.3 限速限行模式下的最優(yōu)路徑

基于道路網(wǎng)絡等級、路段限速模式下，駕駛員在主觀意愿上會優(yōu)先選擇省道、國道、城市主干道，其次選擇城市次干道、鄉(xiāng)鎮(zhèn)道路.假設主干道限速30 km/h、次干道限速25 km/h、省道限速35 km/h，計算出在限速模式下的最優(yōu)路徑.在限速模式下，距離最短路徑需要行駛4 455.3 m，行駛時間成本為13.2 min(見圖4(a))，比無約束模式下的時間最短路徑多行駛2.3 min.限速模式下的最短時間為10.5 min，行駛距離為4 739.4 m(見圖4(b))，與最短距離路徑模式相比，時間成本降低了，距離成本增加了361.5 m.在道路通行能力有限情況下，尤其在上下班高峰期，實際的行駛時間與最優(yōu)路徑的行駛時間存在較大差異.而交通路況在非高峰時段，最優(yōu)路徑與實際行駛時間和距離成本較為接近.

(a)距離最短路徑

(b)時間最短路徑圖4 限速模式下路徑選擇Fig.4 Route choice under the speed binit mode

優(yōu)化后的Dijkstra算法和傳統(tǒng)Dijkstra算法，在計算路徑的運行時間和距離最短時，主要取決于行駛路線的節(jié)點數(shù)量.時間最短和距離最短路徑的求解有不同之處，主要表現(xiàn)在有向圖中每條路段上障礙點、行駛方向、限速的設置.假設每個限速路段節(jié)點的延時時間為30 s，非限速路段的節(jié)點處延時25 s，行駛過程中通過的紅綠燈最少，計算出時間最短路徑為18.4 min，比限速模式下時間最短路徑的時間成本多5.2 min，如圖5所示.

圖5 節(jié)點延時條件下的距離最短路徑Fig.5 The shortest route of distance under the node delay conditions

2.4 選線結(jié)果對比

為檢驗優(yōu)化路線的行駛理論時長和實際行駛時長(見表2)，與優(yōu)化路線的行駛時長相比，實際行駛時間用時較長，最小時長差值為1.2 min，最大時長差值2.9 min.在城市道路網(wǎng)絡不限速、不限等級的情況下，時間最短路徑的行駛距離(線2)比距離最短路徑的行駛距離(線1)多行駛了7.4 m，以行駛距離增加和道路等級降低來換取行駛時長最小化.在障礙路況模式下，線4時間行駛時長比線3的實際行駛時長多了1.0 min，行駛中的駕駛員對障礙點和路況不熟悉，實際行駛時長比模型輸出的理論行駛時長多用了2.9 min.在限速模式下，線5中城市車輛的行駛時長實際值受限于道路擁堵、通行能力、路況信息等條件，比線6實際行駛時長多了1.2 min，與行駛理論時長多了2.3 min.而在路口節(jié)點處延時30 s的情況下，實際行駛距離較為合理，實際行駛時長較大.因此，節(jié)點延時、障礙路況、限速限行是影響城市車輛選線的主要因素，最優(yōu)路徑中節(jié)點數(shù)量對行駛時長和行駛距離起到主導作用.

表2 基于Dijkstra算法優(yōu)化的車輛選線與實際行駛時間對比Tab.2 Comparison of actual driving time and vehicle routing results after the optimization of Dijkstra algorithm

3 結(jié)論

1)通過對傳統(tǒng)Dijkstra算法的優(yōu)化，利用GIS網(wǎng)絡分析工具，對城市車輛選線進行求解，獲得了不同約束條件下的時間和距離最優(yōu)路徑，并給出最短路徑長度和行駛時間.在理想情況下，GIS網(wǎng)絡分析工具能夠精準模擬復雜的道路網(wǎng)絡，使模型中的選線結(jié)果與實際選線結(jié)果較為一致.

2)Dijkstra算法優(yōu)化可減少路徑分析過程中的節(jié)點訪問時間，降低時間復雜度，縮短已標識節(jié)點外的大量節(jié)點的計算時長.但是，最優(yōu)路徑的成本仍取決于路徑節(jié)點數(shù)、路段阻強和限速條件.

3)在道路網(wǎng)絡中指定起源節(jié)點和目標點，分別求出在距離、時間成本的限制下的最優(yōu)路徑.但是針對城市公共交通工具的進出站、路段限行、道路擁堵等路況條件，需要采用相應的路徑優(yōu)化措施.Dijkstra算法優(yōu)化傾向于選擇主干道、無障礙路、次干道，在駕駛員主觀和客觀因素(如司機態(tài)度、偶然事件、擁堵路段、節(jié)點訪問次序、交通臨時管制)方面還有待進一步研究.