室內(nèi)外一體化最優(yōu)路徑分析算法實(shí)現(xiàn)

張文元，丁京禎，楊麗娜，楊翔宇

1.華中師范大學(xué) 國(guó)家文化產(chǎn)業(yè)研究中心，武漢 430079

2.中國(guó)科學(xué)院 遙感與數(shù)字地球研究所，北京100864

1 引言

為出行者提供路徑規(guī)劃與導(dǎo)航服務(wù)的各種應(yīng)用層出不窮，但目前大部分應(yīng)用僅限于城市室外交通網(wǎng)絡(luò)。隨著城市化進(jìn)程加速，室內(nèi)空間的開發(fā)與利用得到了增強(qiáng)，公眾在室內(nèi)空間的活動(dòng)范圍和時(shí)間也相應(yīng)增多，如購(gòu)物中心、政務(wù)中心、機(jī)場(chǎng)、火車站、醫(yī)院和博物館等大型公共建筑都是人流密集的區(qū)域。陌生而又錯(cuò)綜復(fù)雜的大型公共建筑加劇了空間認(rèn)知負(fù)擔(dān)，使得人們?cè)谶@些公共場(chǎng)所內(nèi)部的尋路愈加困難[1]。如何將宏觀的室外空間與微觀的室內(nèi)環(huán)境集成在一起進(jìn)行路徑分析，滿足公眾日益強(qiáng)烈的室內(nèi)外一體化路徑查詢需求，并為室內(nèi)空間發(fā)生火災(zāi)等突發(fā)事件的應(yīng)急響應(yīng)提供最佳救援路徑，已經(jīng)成為了智能交通和地理信息科學(xué)領(lǐng)域的一項(xiàng)研究熱點(diǎn)和挑戰(zhàn)，也是當(dāng)前智慧城市建設(shè)的一項(xiàng)重要內(nèi)容。

最優(yōu)路徑分析是GIS（Geographic Information System，地理信息系統(tǒng)）空間分析的重要組成部分，其正確性、靈活性和高效性直接關(guān)系到智能空間信息服務(wù)質(zhì)量。由于室內(nèi)空間涉及多層建筑，室內(nèi)網(wǎng)絡(luò)數(shù)據(jù)要比室外道路網(wǎng)絡(luò)復(fù)雜，傳統(tǒng)的基于室外二維道路網(wǎng)絡(luò)連通模型的路徑分析方法并不直接支持室內(nèi)空間復(fù)雜的三維拓?fù)錁?gòu)建和路徑分析。在室內(nèi)路徑分析方面，已有一些學(xué)者進(jìn)行過(guò)研究。Lee[2]將室內(nèi)空間中的房間、門和樓梯出入口等實(shí)體統(tǒng)一抽象為節(jié)點(diǎn)，節(jié)點(diǎn)之間通過(guò)走廊、電梯或樓梯建立連接關(guān)系，從而構(gòu)建室內(nèi)三維網(wǎng)絡(luò)連通拓?fù)淠Ｐ?，并采用改進(jìn)的Dijkstra算法來(lái)實(shí)現(xiàn)室內(nèi)三維最短路徑分析。Becker等[3]將室內(nèi)空間分為多個(gè)層次，建立多層次拓?fù)淠Ｐ蛠?lái)表達(dá)室內(nèi)空間關(guān)系及拓?fù)浣Y(jié)構(gòu)。Tsiliakou等[4]利用CityEngine構(gòu)建建筑物三維模型，并通過(guò)為矢量線路數(shù)據(jù)集的每個(gè)坐標(biāo)點(diǎn)增加Z值來(lái)建立三維室內(nèi)路徑模型，最后基于ArcGIS軟件自帶的網(wǎng)絡(luò)分析工具實(shí)現(xiàn)了室內(nèi)三維空間的路徑查詢。林浩嘉等[5]根據(jù)多層建筑的三維空間特性，將各樓層路網(wǎng)和樓層之間的連接視為獨(dú)立結(jié)構(gòu)，根據(jù)?？奎c(diǎn)的樓層分布情況逐樓層動(dòng)態(tài)構(gòu)建網(wǎng)絡(luò)模型，提出一種分層結(jié)構(gòu)化的動(dòng)態(tài)網(wǎng)絡(luò)分析方法來(lái)實(shí)現(xiàn)多層建筑的最短路徑規(guī)劃。林巍凌[6]針對(duì)傳統(tǒng)路徑規(guī)劃算法的局限性，提出一種基于Delaunay三角剖分導(dǎo)航網(wǎng)格的A*算法，用于室內(nèi)導(dǎo)航路徑規(guī)劃。該算法雖然能自動(dòng)構(gòu)建室內(nèi)導(dǎo)航網(wǎng)格，但是算法復(fù)雜性高，正確性需要人工驗(yàn)證，而且針對(duì)一些特殊情況難以自動(dòng)處理。劉濤等[7]利用矢量建筑圖自動(dòng)構(gòu)建室內(nèi)建筑、地標(biāo)的可視關(guān)系，以此建立行人導(dǎo)航通行規(guī)則，并利用多目標(biāo)蟻群算法實(shí)現(xiàn)了一種顧及地標(biāo)可視性的室內(nèi)導(dǎo)航路徑優(yōu)化算法。該方法對(duì)初始數(shù)據(jù)要求較高，并且在構(gòu)建拓?fù)渚W(wǎng)絡(luò)時(shí)需要人工定義多種規(guī)則。

盡管對(duì)室內(nèi)路徑分析已有一些研究成果，但是大多需要構(gòu)建特殊的網(wǎng)絡(luò)數(shù)據(jù)模型，并采用改進(jìn)的路徑分析算法來(lái)處理，算法復(fù)雜，面對(duì)大規(guī)模網(wǎng)絡(luò)數(shù)據(jù)的實(shí)時(shí)查詢還存在性能問(wèn)題，并且難以適應(yīng)傳統(tǒng)的室外交通網(wǎng)絡(luò)分析。而如何實(shí)現(xiàn)室外地圖與室內(nèi)通行地圖的無(wú)縫對(duì)接，并提供室內(nèi)外一體化最優(yōu)路徑分析服務(wù)，相關(guān)研究和應(yīng)用非常少。本文針對(duì)室內(nèi)外路網(wǎng)數(shù)據(jù)各自的特點(diǎn)，提出一種室內(nèi)外一體化道路網(wǎng)絡(luò)數(shù)據(jù)模型，并對(duì)開源路徑分析算法庫(kù)pgRouting進(jìn)行擴(kuò)展，實(shí)現(xiàn)了室內(nèi)外一體化最優(yōu)路徑查詢分析和二維可視化展示，方法簡(jiǎn)單高效，普適性強(qiáng)。

2 室內(nèi)外一體化路徑數(shù)據(jù)模型

構(gòu)建具有幾何拓?fù)潢P(guān)系的網(wǎng)絡(luò)數(shù)據(jù)模型是實(shí)現(xiàn)室內(nèi)外一體化最優(yōu)路徑分析算法的基礎(chǔ)?？紤]到目前廣泛采用的導(dǎo)航電子地圖都是二維的，并且在二維平面上顯示路徑簡(jiǎn)潔高效，為了最大限度保持與現(xiàn)行主流交通網(wǎng)絡(luò)數(shù)據(jù)結(jié)及Dijkstra等一些成熟路徑分析算法的兼容，本文設(shè)計(jì)了一種較為通用的室內(nèi)外一體化幾何網(wǎng)絡(luò)數(shù)據(jù)模型。

2.1 室內(nèi)外一體化路徑數(shù)據(jù)模型設(shè)計(jì)

在室內(nèi)導(dǎo)航網(wǎng)絡(luò)模型方面，目前主要有四類[8]：（1）幾何網(wǎng)絡(luò)模型（Geometric Network Model，GNM）；（2）可導(dǎo)航空間模型（Navigable Space Model）；（3）細(xì)分方法模型；（4）規(guī)則格網(wǎng)模型。其中，GNM[9]是對(duì)節(jié)點(diǎn)關(guān)系圖（Node-Relation Graph，NRG）的擴(kuò)展，不僅能夠表達(dá)室內(nèi)三維對(duì)象之間的鄰接、連通和層次等邏輯關(guān)系，而且還能精確表達(dá)其幾何屬性，其結(jié)構(gòu)相對(duì)簡(jiǎn)單，因而廣泛應(yīng)用于室內(nèi)網(wǎng)絡(luò)分析。因此，本文參照文獻(xiàn)[9]提出的GNM及骨架抽取算法來(lái)快速構(gòu)建室內(nèi)對(duì)象的幾何網(wǎng)絡(luò)模型。但與該文獻(xiàn)的3D-GNM不同，為了最大限度保持與現(xiàn)行主流城市交通網(wǎng)絡(luò)數(shù)據(jù)模型的一致性，并兼容Dijkstra等一些成熟的路徑分析算法，本文設(shè)計(jì)了一種樓層數(shù)據(jù)偏移策略，并在此基礎(chǔ)上采用2D-GNM來(lái)表達(dá)室內(nèi)三維空間的路徑幾何網(wǎng)絡(luò)。

首先，根據(jù)所獲取的建筑內(nèi)部平面布局設(shè)計(jì)圖，將走廊、過(guò)道等通行路徑抽象為線要素，用其中軸線表示；將走廊拐角、樓梯出入口、電梯出入口、房間出口等對(duì)象抽象為點(diǎn)要素，這些點(diǎn)要素與線要素相互連接構(gòu)成節(jié)點(diǎn)-邊網(wǎng)絡(luò)圖。在構(gòu)建GNM模型過(guò)程中，走廊和過(guò)道等矢量要素的中軸線參考S-MAT（Straight-Medial Axis Transformation）骨架線提取算法，它是對(duì)傳統(tǒng)泰森多邊形（Voronoi圖）構(gòu)建法和中軸變換（MAT）的改進(jìn)，降低了算法復(fù)雜性，并且可以避免線要素在相交處出現(xiàn)變形等問(wèn)題，如圖1所示。

圖1MAT與S-MAT中軸變換法比較

圖2 展示某個(gè)樓層數(shù)據(jù)經(jīng)過(guò)抽象提取后的GNM模型，紅色虛線表示中軸通行路徑，與中軸線連接的節(jié)點(diǎn)表示路徑上的各類出口和拐點(diǎn)。

圖2 樓層平面通行路徑網(wǎng)絡(luò)數(shù)據(jù)模型示例

單個(gè)樓層路徑網(wǎng)絡(luò)模型構(gòu)建完成之后，再將電梯或樓梯等樓層實(shí)際連接物抽象為線要素，與樓層平面圖中的電梯或樓梯出入口等點(diǎn)要素連接，從而構(gòu)建室內(nèi)垂直方向的通行拓?fù)渚W(wǎng)絡(luò)。但是，如何使用2D-GNM對(duì)室內(nèi)多層路網(wǎng)模型進(jìn)行合理的可視化表達(dá)也是一大挑戰(zhàn)。為此，本文設(shè)計(jì)了一種數(shù)據(jù)偏移策略，對(duì)室內(nèi)不同樓層的數(shù)據(jù)進(jìn)行地理偏移處理，即：針對(duì)同一樓宇1樓以上的各個(gè)樓層平面圖數(shù)據(jù)，利用如下公式將每個(gè)數(shù)據(jù)點(diǎn)的二維坐標(biāo)(x,y)沿Y軸方向進(jìn)行平移變換，形成新的坐標(biāo) (x′,y′)：

其中，f代表樓層號(hào)，f∈[1,N],N為建筑物樓層數(shù)。d代表樓層之間的間隔長(zhǎng)度（層高），單位為m。s代表縮放因子，目的是使得偏移后的第i層與i-1層數(shù)據(jù)沒(méi)有重疊。

基于該策略，f=1時(shí)，表示建筑物1樓平面數(shù)據(jù)不進(jìn)行偏移處理，直接在該建筑物外部輪廓范圍內(nèi)顯示。f＞1時(shí)，位于2樓及以上樓層的平面數(shù)據(jù)橫坐標(biāo)不變，縱坐標(biāo)偏移量隨樓層數(shù)的增加而逐步增大，從而使得多層建筑的室內(nèi)地圖數(shù)據(jù)呈現(xiàn)出立體表達(dá)的可視化效果。經(jīng)過(guò)偏移處理后，不僅每個(gè)樓層平面上要素之間的拓?fù)潢P(guān)系保持不變，而且銜接不同樓層的垂直空間拓?fù)潢P(guān)系一目了然，如圖3所示。

圖3 經(jīng)過(guò)坐標(biāo)偏移處理的室內(nèi)多層路網(wǎng)數(shù)據(jù)模型示意圖

此外，設(shè)計(jì)的坐標(biāo)變換程序包含正變換和逆變換兩個(gè)函數(shù)，利用正變換進(jìn)行偏移可滿足路徑分析和可視化表達(dá)需要，而通過(guò)逆變換將偏移后的坐標(biāo)還原為真實(shí)坐標(biāo)，可滿足導(dǎo)航定位和真實(shí)路徑方向描述的需求。2DGNM模型中的每條邊和每個(gè)點(diǎn)除了具有空間位置幾何特征、平面方向和垂直方向相互連通的拓?fù)潢P(guān)系外，還包括名稱、類型、所在樓層、所在建筑物和權(quán)重等語(yǔ)義信息。

基于2D-GNM的室內(nèi)多層路網(wǎng)模型構(gòu)建完成之后，為了支持室內(nèi)外一體化的路徑分析，需將室內(nèi)多層路網(wǎng)數(shù)據(jù)在地面一樓的出入口與外部道路網(wǎng)絡(luò)數(shù)據(jù)進(jìn)行連接，即可形成一套完整的室內(nèi)外一體化路徑幾何網(wǎng)絡(luò)數(shù)據(jù)模型。該模型不僅支持利用現(xiàn)有的二維網(wǎng)絡(luò)圖搜索算法進(jìn)行路徑分析，而且滿足室內(nèi)三維數(shù)據(jù)在二維空間的近似表達(dá)。

2.2 網(wǎng)絡(luò)通行成本

網(wǎng)絡(luò)通行成本是計(jì)算交通幾何網(wǎng)絡(luò)模型中兩點(diǎn)之間最優(yōu)通行路徑的關(guān)鍵。針對(duì)室內(nèi)外一體化路徑分析，本文主要考慮距離（Length）和時(shí)間（WalkTime）兩類通行成本。其中，對(duì)于網(wǎng)絡(luò)中的室外路徑以及室內(nèi)水平方向上的邊要素，根據(jù)其幾何長(zhǎng)度賦予距離成本；而室內(nèi)垂直方向的電梯或樓梯等邊要素，則需要根據(jù)樓層之間的高度和樓梯的實(shí)際量算長(zhǎng)度來(lái)分別為其設(shè)置距離成本。對(duì)于時(shí)間成本，依據(jù)網(wǎng)絡(luò)邊要素的距離以及不同道路類型上的平均步行速度來(lái)計(jì)算。本文結(jié)合相關(guān)文獻(xiàn)給出的參考數(shù)據(jù)[10-11]，考慮4種不同道路類型的步行平均速度V ：（1）室外道路，設(shè)定Vout=1.4 m/s；（2）室內(nèi)走廊等水平通行路徑，Vhor=1.2 m/s；（3）室內(nèi)連接不同樓層的樓梯，設(shè)定上行Vstair=0.9 m/s，下行Vsatir=2.0 m/s；（4）室內(nèi)垂直電梯，設(shè)定電梯運(yùn)行的平均速度Vlift=2.5 m/s（考慮等候時(shí)間）。確定了網(wǎng)絡(luò)中每條邊要素的距離成本和道路類型之后，可以依據(jù)如下公式自動(dòng)計(jì)算網(wǎng)絡(luò)中各條邊的時(shí)間成本：

式中Te代表邊要素步行時(shí)間，Le代表邊長(zhǎng)度，Ve代表該邊要素的步行速度。

這樣，計(jì)算網(wǎng)絡(luò)上任意兩點(diǎn)間最快通行路徑就轉(zhuǎn)化為求解網(wǎng)絡(luò)上累計(jì)時(shí)間成本最小的路徑問(wèn)題，公式如下：

式中，T表示總通行時(shí)間，i為結(jié)果路徑上的每一條邊，Lout為室外道路的長(zhǎng)度，Lhor代表室內(nèi)水平路徑的長(zhǎng)度，Lver代表室內(nèi)垂直路徑的長(zhǎng)度，如電梯或樓梯，Vver代表室內(nèi)垂直路徑的速度，Vver=Vstair或Vver=Vlift。

以圖4所示的上下兩層樓部分路徑網(wǎng)絡(luò)為例，從1樓到2樓乘坐電梯上下行的時(shí)間成本均為1.2 s，而步行上樓需要20 s，步行下樓成本為8 s。在計(jì)算跨樓層的最快路徑時(shí)，會(huì)優(yōu)先選擇乘坐電梯。

圖4 室內(nèi)不同樓層幾何網(wǎng)絡(luò)時(shí)間成本示意圖

2.3 幾何網(wǎng)絡(luò)模型數(shù)據(jù)存儲(chǔ)

針對(duì)制作完成的室內(nèi)外一體化路徑幾何網(wǎng)絡(luò)模型數(shù)據(jù)，本文采用鄰接表數(shù)據(jù)結(jié)構(gòu)在開源對(duì)象關(guān)系型數(shù)據(jù)庫(kù)系統(tǒng)PostgreSQL[12]進(jìn)行存儲(chǔ)和管理。鄰接表采用鏈?zhǔn)浇Y(jié)構(gòu)存儲(chǔ)網(wǎng)絡(luò)拓?fù)?，相?duì)于鄰接矩陣優(yōu)化了存儲(chǔ)空間，降低了空間復(fù)雜度，是交通網(wǎng)絡(luò)表達(dá)中一種高效的數(shù)據(jù)結(jié)構(gòu)[13]。PostgreSQL中主要存儲(chǔ)路網(wǎng)模型邊數(shù)據(jù)表（route）和對(duì)應(yīng)的節(jié)點(diǎn)數(shù)據(jù)表（route_vertices_pgr）。其中，route表邏輯結(jié)構(gòu)設(shè)計(jì)如表1，除了基本屬性外，還包括RouteType、IsInside、BuildingID和FloorID等擴(kuò)展語(yǔ)義屬性，滿足網(wǎng)絡(luò)成本計(jì)算、坐標(biāo)偏移、路徑方向描述和分段可視化等需要。route表的Source和Target字段存儲(chǔ)邊要素的起點(diǎn)和終點(diǎn)編號(hào)，關(guān)聯(lián)route_vertices_pgr表的ID（主鍵）字段，以此表達(dá)網(wǎng)絡(luò)拓?fù)潢P(guān)系。這種存儲(chǔ)方式將路徑網(wǎng)絡(luò)模型中的空間數(shù)據(jù)、屬性數(shù)據(jù)和拓?fù)鋽?shù)據(jù)進(jìn)行了有機(jī)關(guān)聯(lián)，并且采用拓?fù)溧徑颖泶鎯?chǔ)結(jié)構(gòu)的空間復(fù)雜度僅為O(e+n)，e和n分別表示邊和節(jié)點(diǎn)數(shù)量，即使邊信息表屬性較多對(duì)存儲(chǔ)空間也沒(méi)有影響，可以適應(yīng)大規(guī)模交通網(wǎng)絡(luò)。

3 基于開源pgRouting的最優(yōu)路徑分析算法

計(jì)算二維平面網(wǎng)絡(luò)中兩點(diǎn)之間的最優(yōu)路徑可以歸結(jié)為圖論中求解帶權(quán)有向圖的最短路徑問(wèn)題，Dijkstra算法[14]、A*算法[15]、遺傳算法[16]和禁忌搜索算法[17]等一些經(jīng)典的圖搜索算法可用來(lái)解決該問(wèn)題。本文主要基于經(jīng)典的Dijkstra算法理論和開源路徑分析算法庫(kù)pgRouting[18]實(shí)現(xiàn)室內(nèi)外一體化最優(yōu)路徑分析。

3.1 Dijkstra算法思想

Dijkstra算法是目前公認(rèn)的求解單源最短路徑問(wèn)題的最佳算法[19]，也是許多GIS系統(tǒng)解決最短路徑問(wèn)題的理論基礎(chǔ)，例如ArcGIS的Network Analysis模塊就使用了該算法。

Dijkstra算法思想為：設(shè)G=(V,E)是一個(gè)帶權(quán)有向圖，V表示所有頂點(diǎn)集合，E表示所有邊集合，E中的每一條邊E(i)是由V中的兩個(gè)點(diǎn)所形成的有序元素對(duì)。假設(shè)(u,v)表示從頂點(diǎn)u到v有路徑相連，w(u,v)代表從頂點(diǎn)u到頂點(diǎn)v的權(quán)重。Dijkstra算法要求圖中不存在負(fù)權(quán)邊，因而邊的權(quán)重函數(shù)定義為w:E→[0,∞]。G中任意兩點(diǎn)間路徑的權(quán)重就是該路徑上所有邊的權(quán)重總和。把G中頂點(diǎn)集合V分成兩組，第一組為已求出最短路徑的頂點(diǎn)集合，用S表示，初始時(shí)S中只有一個(gè)源點(diǎn)v。第二組為其余未確定最短路徑的頂點(diǎn)集合，用U表示。Dijkstra算法的關(guān)鍵部分是從U中不斷地找出到源點(diǎn)v距離最近的點(diǎn)，并把該點(diǎn)加入到S集合中，同時(shí)更新U中其余點(diǎn)到起始點(diǎn)的最短路徑距離。按最短路徑長(zhǎng)度的遞增次序依次把U中的頂點(diǎn)加入S中，并總保持從源點(diǎn)v到S中各頂點(diǎn)的最短路徑長(zhǎng)度不大于從源點(diǎn)v到U中任何頂點(diǎn)的最短路徑長(zhǎng)度，直到全部頂點(diǎn)都加入到S中，算法結(jié)束。

3.2 pgRouting最短路徑算法

pgRouting是對(duì)PostGIS/PostgreSQL地理空間數(shù)據(jù)庫(kù)進(jìn)行擴(kuò)展的一個(gè)開源C語(yǔ)言類庫(kù)，支持Dijkstra算法、A*算法、Johnson和Floyd-Warshall等多種最短路徑分析算法。pgRouting最短路徑核心算法基于Boost Graph Library[20]（簡(jiǎn)稱BGL）實(shí)現(xiàn)，利用BGL提供的斐波那契堆（Fibonacci Heap）數(shù)據(jù)結(jié)構(gòu)，將Dijkstra算法的時(shí)間復(fù)雜度從傳統(tǒng)的降低到代表節(jié)點(diǎn)數(shù)量，|E|代表邊數(shù)量，大大提高了搜索效率。

表1 route表邏輯結(jié)構(gòu)設(shè)計(jì)

針對(duì)導(dǎo)入PostgreSQL的室內(nèi)外一體化路徑邊數(shù)據(jù)（route），調(diào)用pgRouting內(nèi)置的pgr_createTopology函數(shù)自動(dòng)構(gòu)建網(wǎng)絡(luò)拓?fù)湫畔ⅲ⑸蛇厡?duì)應(yīng)的節(jié)點(diǎn)信息表（route_vertices_pgr），同時(shí)填充route表每條記錄的source和target字段值，從而構(gòu)建網(wǎng)絡(luò)拓?fù)潢P(guān)系。拓?fù)潢P(guān)系創(chuàng)建成功后，便可使用pgr_dijkstra等函數(shù)來(lái)查詢兩點(diǎn)之間的最短路徑。

3.3 pgRouting最短路徑算法擴(kuò)展

3.3.1 創(chuàng)建兩點(diǎn)間最優(yōu)路徑分析函數(shù)

pgr_dijkstra（sql，source，target，directed，has_rcost）函數(shù)默認(rèn)需要輸入source和target，但在真實(shí)應(yīng)用場(chǎng)景中，用戶根本不知道起止點(diǎn)的ID。為了能夠支持通過(guò)地圖界面交互、興趣點(diǎn)選擇或者當(dāng)前GPS定位坐標(biāo)來(lái)查詢兩點(diǎn)之間最優(yōu)路徑，本文對(duì)pgr_dijkstra函數(shù)進(jìn)行擴(kuò)展。具體做法是在PostgreSQL數(shù)據(jù)庫(kù)創(chuàng)建自定義函數(shù)pgr_fromAtoB，包含6個(gè)輸入?yún)?shù)：路線表名稱（table）、起點(diǎn)坐標(biāo)(x1,y1)、終點(diǎn)坐標(biāo)(x2,y2)和查詢類型（queryType，0表示距離最短，1表示時(shí)間最少）。輸出參數(shù)為查詢結(jié)果對(duì)應(yīng)的路段序號(hào)（seq）、唯一編號(hào)（gid）、名稱（name）、成本（cost）、幾何形狀（geom）和方位角（heading）。

由于用戶交互選擇的輸入點(diǎn)不一定是線路上的節(jié)點(diǎn)，函數(shù)實(shí)現(xiàn)過(guò)程中，會(huì)首先根據(jù)輸入點(diǎn)坐標(biāo)從route_vertices_pgr表查找離該點(diǎn)最近的線路節(jié)點(diǎn)。借助PostGIS 2.0為幾何對(duì)象提供的K-Nearest Neighbour（KNN）索引，在SQL語(yǔ)句中使用<->操作符就可以使用KNN算法快速檢索出離輸入點(diǎn)(x,y)最近的線路節(jié)點(diǎn)，SQL示例為：SELECT id FROM route_vertices_pgr ORDER BY the_geom <->ST_GeometryFromText（''POINT（x，y）''，4326） LIMIT 1。其中，4326 表示W(wǎng)GS1984地理坐標(biāo)系編號(hào)，limit 1表示只輸出距離最近的那個(gè)節(jié)點(diǎn)。

3.3.2 擴(kuò)展路徑方向描述信息

pgr_dijkstra函數(shù)返回結(jié)果pgr_costResult[]是一個(gè)包含{seq,nodeID,edgeID,cost}屬性的數(shù)組，只有路段序號(hào)、節(jié)點(diǎn)編號(hào)、邊編號(hào)和成本4個(gè)基本屬性，能夠據(jù)此繪制結(jié)果線路的幾何形狀，但是沒(méi)有路徑方向語(yǔ)義信息。方向描述是路徑導(dǎo)航的一項(xiàng)重要信息，為了彌補(bǔ)pgRouting在這方面的不足，在上一節(jié)自定義函數(shù)pgr_fromAtoB中增加了heading參數(shù)輸出，依據(jù)路徑中每段線路的起點(diǎn)和終點(diǎn)來(lái)計(jì)算其方位角。設(shè)某段路徑的起止點(diǎn)分別為A(x1,y1)和B(x2,y2)，則其方位角計(jì)算通用公式為：

Δy＞0且Δx=0時(shí)，α=0°

Δx＞0且Δy=0時(shí)，α=90°

Δy<0且Δx=0時(shí)，α=180°

Δx<0且Δy=0時(shí)，α=270°

獲取了每條線路的方位角之后，就可以根據(jù)相鄰兩段線路的方位角之差(Δα)來(lái)確定轉(zhuǎn)彎方向。為了避免Δα 出現(xiàn)負(fù)值，當(dāng) Δα<0時(shí)，設(shè)置 Δα=Δα+360°，使得Δα∈[0°,360°)。本文根據(jù) Δα 取值范圍定義8種轉(zhuǎn)彎方向描述信息，如表2所示。這8條規(guī)則分別對(duì)應(yīng)圖5標(biāo)記的8個(gè)區(qū)域。

表2 路徑轉(zhuǎn)彎規(guī)則定義

圖5 路徑轉(zhuǎn)彎規(guī)則定義示意圖

在確定轉(zhuǎn)彎方向的同時(shí)，還要考慮線路合并問(wèn)題。對(duì)于相鄰兩條線路R1和R2，若R1.name=R2.name，且 Δα(R1,R2)∈[0,20)或 [340,360)范圍，表示在同一道路上繼續(xù)直行，則將其合并為一條線路Rnew，設(shè)置Rnew.length=R1.length+R2.length,Rnew.walktime=R1.walktime+R2.walktime。最后，將獲得的轉(zhuǎn)彎信息和線路名稱、線路長(zhǎng)度和步行時(shí)間等信息共同構(gòu)成結(jié)果路徑的方向描述信息，封裝成Direction類對(duì)象。經(jīng)過(guò)合并處理后僅保留路徑中的起點(diǎn)、拐點(diǎn)和終點(diǎn)，簡(jiǎn)化了路徑結(jié)果坐標(biāo)點(diǎn)數(shù)量，可以節(jié)約內(nèi)存和網(wǎng)絡(luò)傳輸開銷，提高客戶端繪制效率。

以圖6標(biāo)識(shí)的4段線路為例，參照上述轉(zhuǎn)彎規(guī)則和路徑合并處理規(guī)則，就可以將北京路兩段線路（2，3）和（3，4）合并為（2，4），僅存儲(chǔ)（1，2，4，5）等節(jié)點(diǎn)。最終轉(zhuǎn)彎語(yǔ)義描述為：沿南京路向正北方向行駛，然后右轉(zhuǎn)進(jìn)入北京路，再左轉(zhuǎn)進(jìn)入陜西路。

圖6 依據(jù)方位角確定路徑方向描述示意圖

4 算法實(shí)驗(yàn)及結(jié)果分析

4.1 系統(tǒng)架構(gòu)

為了驗(yàn)證室內(nèi)外一體化幾何網(wǎng)絡(luò)模型和pgRouting擴(kuò)展路徑分析算法的有效性，作者以開源GeoServer[21]（version 2.11.0）為WebGIS服務(wù)器，OpenLayers（version 4.2.0）API[22]為地圖查詢客戶端組件，pgRouting（version 2.2.2）為路徑分析核心類庫(kù)，使用Java和JavaScript開發(fā)了室內(nèi)外一體化最優(yōu)路徑查詢?cè)拖到y(tǒng)。

基于本系統(tǒng)的最優(yōu)路徑分析實(shí)現(xiàn)流程如圖7所示。

圖7 室內(nèi)外一體化最優(yōu)路徑分析系統(tǒng)實(shí)現(xiàn)流程

用戶通過(guò)Web瀏覽器訪問(wèn)OpenLayers地圖服務(wù)，然后與地圖交互確定路徑分析的起點(diǎn)和目標(biāo)點(diǎn)坐標(biāo)，再由OpenLayers請(qǐng)求GeoServer服務(wù)器上的路徑分析WMS服務(wù)。此時(shí)，GeoServer在后臺(tái)調(diào)用本文擴(kuò)展的pgr_fromAtoB函數(shù)查詢滿足條件的路徑網(wǎng)絡(luò)數(shù)據(jù)，最后將查詢到的最優(yōu)路徑結(jié)果圖片返回OpenLayers客戶端，對(duì)應(yīng)的路徑方面描述信息則利用相關(guān)SQL語(yǔ)句在PostgreSQL數(shù)據(jù)庫(kù)查詢，并通過(guò)JSON（Java Script Object Notation）數(shù)據(jù)格式返回客戶端進(jìn)行解析和顯示。

在PostgreSQL中實(shí)現(xiàn)自定義函數(shù)pgr_fromAtoB的核心SQL語(yǔ)句為：SELECT gid，name，geom，a.cost，a.source，a.target FROM pgr_dijkstra（‘SELECT gid as id，source，target，length AS cost FROM route’，source，target，false，false） a，route WHERE id2=gid ORDER BY seq。該查詢將pgr_dijkstra得到的初級(jí)結(jié)果與原始線路表進(jìn)行關(guān)聯(lián)，可以獲取結(jié)果線路上更多屬性信息，便于路徑方向語(yǔ)義信息獲取。在此基礎(chǔ)上，利用GeoServer配置路徑查詢WMS服務(wù)的關(guān)鍵SQL語(yǔ)句為：SELECT ST_MakeLine（route.geom） FROM（SELECTgeom FROM pgr_fromAtoB（‘route’，%x1%，%y1%，%x2%，%y2%，%queryType%）ORDER BY seq）AS route。將客戶端請(qǐng)求的起止點(diǎn)坐標(biāo)和查詢類型作為GeoServer WMS服務(wù)請(qǐng)求參數(shù)，即可計(jì)算出最優(yōu)路徑，并返回線路結(jié)果幾何對(duì)象。路徑方向描述則利用Java Servlet這種數(shù)據(jù)庫(kù)和應(yīng)用程序之間的中間層實(shí)現(xiàn)，部署在Tomcat服務(wù)器下，并在OpenLayers客戶端利用AJAX（Asynchronous JavaScript and XML）技術(shù)來(lái)實(shí)時(shí)獲得方向描述語(yǔ)義信息。

4.2 實(shí)驗(yàn)數(shù)據(jù)描述

采用天津市主城區(qū)的道路網(wǎng)絡(luò)及部分建筑室內(nèi)路徑數(shù)據(jù)作為測(cè)試數(shù)據(jù)，其中，城市道路交通網(wǎng)絡(luò)數(shù)據(jù)從OpenStreetMap開源網(wǎng)站下載，利用開源工具osm2pgsql將其導(dǎo)入PostgreSQL；兩幢建筑物的室內(nèi)幾何網(wǎng)絡(luò)模型數(shù)據(jù)基于各樓層平面設(shè)計(jì)圖（AutoCAD數(shù)據(jù)）在ArcGIS 10.2軟件中制作而成，并利用PostGIS 2.0提供的ShapeFile and DBF Loader Exporter工具將其導(dǎo)入PostgreSQL。第1幢建筑共5層，包含3部電梯和3座樓梯；另一幢3層建筑包含2部電梯和2座樓梯。在PostgreSQL中構(gòu)建拓?fù)潢P(guān)系后的幾何網(wǎng)絡(luò)模型共包含32 906條邊和30 019個(gè)節(jié)點(diǎn)。其中，室外道路32 234條，室內(nèi)路徑672條。

除了道路線要素和對(duì)應(yīng)的節(jié)點(diǎn)外，為了能夠直觀展示樓宇內(nèi)部結(jié)構(gòu)，本文將連通室內(nèi)路徑的房門、樓梯出入口、電梯出入口、緊急通道出口等興趣點(diǎn)數(shù)據(jù)（poi）、室內(nèi)房間布局輪廓線數(shù)據(jù)（room_line）、建筑物輪廓（building_polygon）等輔助矢量數(shù)據(jù)也一并導(dǎo)入PostgreSQL，并通過(guò)GeoServer發(fā)布圖層服務(wù)。兩幢建筑室內(nèi)空間數(shù)據(jù)及部分室外連通路徑的空間分布如圖8所示。

4.3 實(shí)驗(yàn)結(jié)果及分析

利用本系統(tǒng)提供的坐標(biāo)點(diǎn)選擇工具從室外道路上選擇一個(gè)點(diǎn)作為起始點(diǎn)（五角星標(biāo)識(shí)），再?gòu)哪炒苯ㄖ亩亲呃壬线x擇一個(gè)目標(biāo)點(diǎn)，按照“距離最短”方式進(jìn)行查詢，其結(jié)果如圖9所示（紅色加粗折線標(biāo)識(shí)）。

圖8 室內(nèi)外一體化道路網(wǎng)絡(luò)模型數(shù)據(jù)示例

圖9 室內(nèi)外一體化路徑分析結(jié)果展示

圖10 室內(nèi)外一體化路徑分析結(jié)果展示

接下來(lái)分別從兩幢建筑的2樓走廊選取一個(gè)點(diǎn)作為起始點(diǎn)和目標(biāo)點(diǎn)，按照“時(shí)間最少”方式進(jìn)行查詢，其結(jié)果如圖10所示，地圖右上方顯示詳細(xì)的路徑方向描述信息。由于乘坐電梯的時(shí)間成本比樓梯步行成本要小，因此算法會(huì)優(yōu)先選擇乘坐電梯上下樓。針對(duì)起止點(diǎn)都在室內(nèi)的查詢，本文采用3種方式優(yōu)化查詢結(jié)果地圖展示：（1）當(dāng)起點(diǎn)和終點(diǎn)在同一樓宇的同一樓層時(shí)，系統(tǒng)只顯示該樓層的平面布局圖并標(biāo)識(shí)結(jié)果路徑；（2）當(dāng)起點(diǎn)和終點(diǎn)在同一樓宇的不同樓層時(shí)，系統(tǒng)只顯示該樓宇這些樓層之間的整合圖并標(biāo)識(shí)結(jié)果路徑；（3）當(dāng)起點(diǎn)和終點(diǎn)位于不同樓宇內(nèi)部時(shí)，系統(tǒng)默認(rèn)展示這兩棟樓宇的室內(nèi)整合圖和室外連接路徑部分。此外，系統(tǒng)還提供“室外路徑”、“起點(diǎn)室內(nèi)路徑”和“終點(diǎn)室內(nèi)路徑”等選項(xiàng)，可分別展示路徑結(jié)果的不同細(xì)節(jié)。

為了驗(yàn)證最優(yōu)路徑分析結(jié)果的正確性，將該實(shí)驗(yàn)數(shù)據(jù)以及與圖10相同的起止點(diǎn)在ArcGIS 10.2桌面軟件ArcMap中進(jìn)行路徑分析（設(shè)置網(wǎng)絡(luò)阻抗為L(zhǎng)ength字段），所得結(jié)果如圖11所示。可以看出，本文結(jié)果與ArcGIS軟件計(jì)算結(jié)果完全一致。選擇任意的起止點(diǎn)進(jìn)行大量的對(duì)比測(cè)試，發(fā)現(xiàn)結(jié)果均相同，說(shuō)明本方法計(jì)算結(jié)果可靠。

圖11 ArcGIS最優(yōu)路徑分析結(jié)果

實(shí)驗(yàn)所用臺(tái)式計(jì)算機(jī)配置為Intel?CoreTMi7-6700 CPU@3.4 GHz雙核，16 GB內(nèi)存，Windows 10 64位操作系統(tǒng)，選擇5組代表室內(nèi)外不同道路上的點(diǎn)作為輸入，分別對(duì)應(yīng)于5組不同的室內(nèi)外一體化路徑分析結(jié)果規(guī)模（路徑邊數(shù)量等），以線路長(zhǎng)度作為網(wǎng)絡(luò)成本，測(cè)試算法的執(zhí)行效率，所得結(jié)果見表3。5組查詢結(jié)果耗時(shí)均在60 ms以內(nèi)，平均耗時(shí)為50.4 ms，并且查詢效率與結(jié)果路徑邊數(shù)量和總長(zhǎng)度關(guān)系不大。

表3 不同查詢規(guī)模的效率對(duì)比

本文使用的Dijkstra算法也與pgRouting庫(kù)內(nèi)置的其他最短路徑分析算法進(jìn)行了效率對(duì)比。由于Johnson和Floyd-Warshall是全源最短路徑算法，使用全部測(cè)試數(shù)據(jù)耗時(shí)非常長(zhǎng)，因此僅選取包含圖8所示的部分路徑（679條邊）作為測(cè)試數(shù)據(jù)。針對(duì)Dijkstra和A*算法，起始點(diǎn)與目標(biāo)點(diǎn)對(duì)應(yīng)的source=30，target=238，4種算法結(jié)果見表4。

表4 不同最短路徑算法效率對(duì)比

可以看出，在單源最短路徑方面，A*算法比Dijkstra算法效率高，因?yàn)锳*算法采用啟發(fā)式搜索，通過(guò)估價(jià)函數(shù)進(jìn)行有選擇的遍歷，優(yōu)于Dijkstra算法的盲目搜索。但是，在大量測(cè)試過(guò)程中，選擇某些起止點(diǎn)，使用Dijkstra算法能求解出最短路徑，而A*算法無(wú)查詢結(jié)果，不能保證獲得最優(yōu)解。Floyd-Warshall和Johnson這兩種算法[23]需要計(jì)算所有節(jié)點(diǎn)之間的全源最短路徑矩陣，效率非常低，因?yàn)镕loyd-Warshall算法時(shí)間復(fù)雜度是O(|V|3)，Johnson算法時(shí)間復(fù)雜度為O(|E||V|+|V|2lg|V|)。并且隨著V和E元素的增多，這兩種算法與Dijkstra算法的效率差別會(huì)更加明顯。

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

本文提出了一種能夠兼容Dijkstra等成熟路徑分析算法的室內(nèi)外一體化幾何網(wǎng)絡(luò)路徑模型，在該模型中設(shè)計(jì)了一種樓層坐標(biāo)偏移策略，既能滿足室內(nèi)垂直方向網(wǎng)絡(luò)拓?fù)潢P(guān)系的構(gòu)建，又能實(shí)現(xiàn)三維空間下的室內(nèi)多層路網(wǎng)數(shù)據(jù)二維可視化表達(dá)。對(duì)開源pgRouting庫(kù)提供的高效Dijkstra算法進(jìn)行擴(kuò)展，能快速查找出離輸入點(diǎn)最近的線路節(jié)點(diǎn)，從而實(shí)現(xiàn)任意兩點(diǎn)間最短或最快路徑查詢，并返回結(jié)果路徑的空間位置和轉(zhuǎn)彎方向語(yǔ)義描述信息。使用大規(guī)模室內(nèi)外一體化道路網(wǎng)絡(luò)數(shù)據(jù)在開發(fā)的原型系統(tǒng)中進(jìn)行實(shí)驗(yàn)，經(jīng)大量測(cè)試均能快速準(zhǔn)確查詢出兩點(diǎn)間最優(yōu)路徑結(jié)。本文提出的室內(nèi)外一體化道路網(wǎng)絡(luò)數(shù)據(jù)模型和基于開源軟件的最優(yōu)路徑分析解決方案具有普適性，能夠滿足室外、室內(nèi)、室內(nèi)外一體化等多種環(huán)境下的最優(yōu)路徑分析，方法簡(jiǎn)單高效，通用性強(qiáng)。今后擬考慮室外汽車行駛速度、道路擁堵程度等多種網(wǎng)絡(luò)成本，并實(shí)現(xiàn)動(dòng)態(tài)最優(yōu)路徑規(guī)劃，更好地滿足公眾的室內(nèi)外一體化路徑導(dǎo)航需求。