基于城市興趣點(diǎn)的連續(xù)路徑誘導(dǎo)方法

于 堯，楊兆升，2，莫祥倫，林賜云，2

隨著GIS地理信息的不斷完善，路徑導(dǎo)航［1－2］得到了人們越來越多的關(guān)注及應(yīng)用。興趣點(diǎn)信息的完善極大地方便了人們的出行，在出行前即可規(guī)劃好去目的地的最短路徑［3－4］。以一次出行為例，出行者通常需要先到餐館、銀行、商場等多個(gè)地點(diǎn)，最后抵達(dá)目的地。然而現(xiàn)有誘導(dǎo)算法大都以單興趣點(diǎn)為誘導(dǎo)目標(biāo)，忽略了實(shí)際出行中出行者的中途停留需求，無法實(shí)現(xiàn)多個(gè)興趣點(diǎn)的連續(xù)路徑規(guī)劃。

近年來，一些學(xué)者針對連續(xù)行程規(guī)劃問題［5］（STPQ）提出了相關(guān)的近似查詢算法，如Sharifzadeh等［6］提出的最優(yōu)有序路徑算法（OSRLORD）、Lee 等 提 出 的 NS 最 近 鄰 算 法［7］、Terrovitis等［8］提出的a自治最短路徑規(guī)劃和k停頓最短路徑規(guī)劃方法等，這些算法（方法）實(shí)質(zhì)上都可以看成是多興趣點(diǎn)連續(xù)路徑規(guī)劃的特例問題，不具有一般性。Chen等在文獻(xiàn)［9］中闡述了多類別興趣點(diǎn)有序路徑查詢問題，通過約束興趣點(diǎn)訪問順序，得到不同約束規(guī)則下的路徑查詢效果，但其查詢的興趣點(diǎn)數(shù)據(jù)必須與其內(nèi)部的數(shù)據(jù)集構(gòu)成有拓?fù)潢P(guān)系，且提出的算法僅為數(shù)據(jù)查詢機(jī)制，未能與實(shí)際路網(wǎng)地圖匹配。所以如何有效、快速地響應(yīng)用戶對多興趣點(diǎn)的訪問請求，是實(shí)現(xiàn)高效路徑引導(dǎo)服務(wù)的基礎(chǔ)，也是未來幾年內(nèi)路徑誘導(dǎo)領(lǐng)域的研究興趣點(diǎn)。本文依據(jù)城市興趣點(diǎn)認(rèn)知程度，對其進(jìn)行分類，并基于不同出行規(guī)則約束，提出了最近鄰連續(xù)興趣點(diǎn)搜索方法，旨在滿足多出行規(guī)則約束下的訪問需求，豐富了現(xiàn)有路徑誘導(dǎo)方法。

1 POI興趣點(diǎn)分類

城市興趣點(diǎn)（Point of interest，POI）包括餐飲、購物、旅游以及汽車服務(wù)等多種類別。這些興趣點(diǎn)信息已在地理信息服務(wù)中得到了廣泛的應(yīng)用［10－11］。POI信息不但可以幫助用戶快速定位所需位置信息，還可以在導(dǎo)航中利用一定的規(guī)則進(jìn)行推理，得到實(shí)時(shí)位置關(guān)聯(lián)度最高的一系列地標(biāo)［12］，進(jìn)而實(shí)現(xiàn)簡潔、靈活和高效的路徑引導(dǎo)服務(wù)。

Raubal等［13］提出，城市中的任何要素，只要人們對它的認(rèn)知度較高，即可以被看做是熟知的地點(diǎn)。本文將人們?nèi)粘３鲂羞^程中需要經(jīng)常訪問的地點(diǎn)定為POI，并參照文獻(xiàn)［12］，定義各類POI的基本選取范疇，如表1所示。

定義表1中的12種興趣點(diǎn)分類為 ｛Ci｝ ，每個(gè)Ci都滿足｛｝POIs∈Ci；此外，由于POI數(shù)據(jù)庫中會出現(xiàn)冗余數(shù)據(jù)，如大廈內(nèi)有大型商場，或者重疊的機(jī)關(guān)單位等，所以在路徑計(jì)算前應(yīng)剔除數(shù)據(jù)鏈表中的冗余數(shù)據(jù)，但同時(shí)要保證所刪除的數(shù)據(jù)不屬于用戶查詢興趣點(diǎn)類別中的任意一種，所以本文設(shè)興趣點(diǎn)的數(shù)據(jù)存儲形式為｛Categor y＿Name，Longit ude，Latitude｝，并通過 Mapinf o7.0實(shí)現(xiàn)興趣點(diǎn)與真實(shí)路網(wǎng)的匹配。

表1 POI分類Table 1 POI classification

2 不同約束規(guī)則下連續(xù)興趣點(diǎn)查詢

2.1 最近鄰興趣點(diǎn)路徑搜索

實(shí)際上最近鄰興趣點(diǎn)路徑搜索與數(shù)據(jù)庫中的對象修剪與精煉過程類似［14］。但不同于旅行商問題（TSP）［5，15］，算法并不需要遍歷每一個(gè)地圖上已有的興趣點(diǎn)，而是僅僅計(jì)算用戶事先給定所需訪問的興趣點(diǎn)類別即可。

假設(shè)小A現(xiàn)有一個(gè)出行計(jì)劃，她想到達(dá)車站之前，先去銀行取錢，再分別至商場、加油站以及餐館等4個(gè)地點(diǎn)，那么小A的出行路徑有以下兩種：①出發(fā)點(diǎn)→銀行→餐館→商場→加油站→車站。②出發(fā)點(diǎn)→銀行→商場→餐館→加油站→車站，如圖1所示。

出行用戶可以自己定制訪問的興趣點(diǎn)規(guī)則，如餐館→商場，或者商場→餐館，這時(shí)兩種不同路徑下出行時(shí)間的長短將成為輔助出行者決策的重要依據(jù)。

對于出行起點(diǎn)周邊的最近鄰興趣點(diǎn)信息搜索（Nearest POI Search，NPS），做如下規(guī)定，如圖2所示，圖中的黑色點(diǎn)q代表用戶的出行位置，空心點(diǎn)A、B、C、D、E、F代表路網(wǎng)節(jié)點(diǎn)（如交叉口），三角形P1、P2、P3代表路網(wǎng)中的興趣點(diǎn)信息，數(shù)字代表路段的權(quán)重（本文中選擇距離為權(quán)重系數(shù)）。

圖1 小A的出行路徑選擇Fig.1 Travel route choice

搜索當(dāng)前離q最近興趣點(diǎn)位置的步驟為：首先選取與q點(diǎn)相連接的路網(wǎng)節(jié)點(diǎn)（C、D），并初始化隊(duì)列Q＝ 〈（C，5），（D，7）〉；判斷CD 中是否有P存在，若無，緊鄰q點(diǎn)的節(jié)點(diǎn)C出隊(duì)，節(jié)點(diǎn)A、E進(jìn)隊(duì)列Q 中，Q 更新為Q ＝ 〈（D，7），（A，9），（E，10）〉；由于CA、CE段上沒有P存在，故同節(jié)點(diǎn)C一樣，節(jié)點(diǎn)D出隊(duì)，緊鄰D點(diǎn)的B、F進(jìn)隊(duì)，更新Q，Q＝ 〈（A，9），（E，10）（F，10），（B，15）〉；接下來在BD段上搜索到P 3，計(jì)算q至P 3的距離為9，判斷目前Q中其余節(jié)點(diǎn)至q點(diǎn)的距離可知，沒有小于9的路徑，所以搜索完成，q點(diǎn)至最近興趣點(diǎn)P3的最短距離即為9。

圖2 最近鄰興趣點(diǎn)路徑搜索示意圖Fig.2 Nearest POI search sketch

2.2 基于A＊的連續(xù)搜索算法

在最近鄰興趣點(diǎn)路徑搜索規(guī)則的基礎(chǔ)上，提出基于A＊的連續(xù)搜索算法（A＊-based sequenced search al gorit h m，ASSA），算法考慮了用戶設(shè)置的終點(diǎn)信息，通過分別計(jì)算起點(diǎn)與終點(diǎn)至興趣點(diǎn)P的最短距離（如式（1）所示），得到總出行費(fèi)用（距離）最小的路徑，避免了非最短路徑的出現(xiàn)［16］，如圖3所示。

圖3中的虛線代表未考慮出行終點(diǎn)D時(shí)的出行路徑，實(shí)線為考慮D點(diǎn)后的出行路徑?？梢钥闯觯纯紤]D情況下的出行距離要遠(yuǎn)大于后者。

圖3 定義規(guī)則為Bank-Restaurant下的出行路徑對比Fig.3 Comparison of travel routes under Bank-to-Restaur ant r ule

采取與經(jīng)典啟發(fā)式算法類似的估價(jià)方法，設(shè)（s，d）為ASSA算法選定的包含興趣點(diǎn)pi至興趣點(diǎn)pj間的行駛路線，令f（l）＝ω（s，pi）＋c（pi，d），其中ω（s，pi）為從起始點(diǎn)s到達(dá)興趣點(diǎn)pi的權(quán)值之和，c（pi，d）為興趣點(diǎn)pi的代價(jià)函數(shù)，它預(yù)測了從pi到目的地d的代價(jià)。f（l）的值決定了該興趣點(diǎn)是否能夠被優(yōu)先查找。

為了減少路網(wǎng)搜索范圍，通過出發(fā)點(diǎn)O、目的地D以及OD間的歐式距離確定一個(gè)橢圓，這個(gè)橢圓的焦點(diǎn)即為O、D，這樣可以有效減少算法的搜索范圍。采用不同形式的數(shù)據(jù)存儲形式，會對算法的執(zhí)行效能產(chǎn)生較大影響。在路網(wǎng)規(guī)模較大時(shí)，應(yīng)采用表形式存儲數(shù)據(jù)，此時(shí)遍歷效率遠(yuǎn)高于鄰接矩陣的存儲形式［17］。在本文中，采用與Dij kstra相似的表形式用以存儲路網(wǎng)及興趣點(diǎn)數(shù)據(jù)，即初始搜索點(diǎn)將被添加至Sv表中，而L最短路徑表為空表狀態(tài)。設(shè)興趣點(diǎn)訪問規(guī)則為R，那么算法的時(shí)間復(fù)雜度即為R2。其算法流程圖如圖4所示。

3 試驗(yàn)分析

試驗(yàn)平臺配置如下：2.8 GHz雙核處理器，2 GB內(nèi)存，操作系統(tǒng)為Windows XP。試驗(yàn)路網(wǎng)選擇長春市實(shí)際路網(wǎng)，共包括3421個(gè)結(jié)點(diǎn)以及5771個(gè)路段，如圖5所示。其中結(jié)點(diǎn)的存儲形式為｛Node＿ID，Longtitude，Latitude｝，路段的存儲形式為｛Edge＿ID，Strat＿Node＿ID，End＿Node＿ID｝。出行起始點(diǎn)采用隨機(jī)數(shù)發(fā)生器產(chǎn)生的服從均勻分布的點(diǎn)數(shù)據(jù)。采用Mapinf o7.0＋Mapx以及Visual C＋＋6.0對所提算法進(jìn)行編程實(shí)現(xiàn)。

圖4 ASSA算法流程圖Fig.4 ASSA algorith m flow diagram

圖5 長春市路網(wǎng)及其興趣點(diǎn)分布情況Fig.5 POI distribution on ChangChun road-net work

路網(wǎng)中共含有12個(gè)興趣點(diǎn)圖層，本文僅取賓館酒店、大廈、車輛服務(wù)、銀行、商場、政府、學(xué)校以及休閑場所共計(jì)8個(gè)興趣點(diǎn)分類中的主要興趣點(diǎn)，各興趣點(diǎn)數(shù)目如表2所示。通過對比文獻(xiàn)［7］中提到的全方位最近鄰算法（NS），分別在計(jì)算時(shí)間和搜索距離兩方面分析了不同出行約束條件下兩種算法的表現(xiàn)。NS算法［7］是數(shù)據(jù)遍歷算法中較為成熟、廣泛使用的一種數(shù)據(jù)關(guān)聯(lián)搜索算法，具有較高的實(shí)用性。為了不失一般性，出行規(guī)則選擇在銀行和大廈，商場和車輛服務(wù)（如加油站）等不同興趣點(diǎn)類別之間隨機(jī)發(fā)生。

表2 不同興趣點(diǎn)類別包含的興趣點(diǎn)數(shù)Table 2 Number of POIs in different categorization

當(dāng)出行規(guī)則一定時(shí)，相比于NS全方位搜索算法，ASSA算法的計(jì)算時(shí)間明顯要優(yōu)于NS算法，如圖6所示。隨著興趣點(diǎn)基數(shù)的增加，兩種算法的計(jì)算時(shí)間都有顯著增加，以NS算法為例，當(dāng)興趣點(diǎn)數(shù)為3500個(gè)時(shí)，算法的計(jì)算時(shí)間相比500個(gè)興趣點(diǎn)時(shí)增加了3倍以上；當(dāng)出行約束條件增加時(shí)，也就是說用戶定義的訪問規(guī)則占全部需訪問興趣點(diǎn)類別的比例增加時(shí)，可知雖然NS算法和ASSA算法的計(jì)算時(shí)間都呈現(xiàn)線性增加，但計(jì)算時(shí)間要低于R／C＝0.333時(shí)的情景，這是因?yàn)?，約束規(guī)則增加，算法所需遍歷搜索的數(shù)據(jù)空間就隨之減少，所以算法的執(zhí)行時(shí)間也相應(yīng)變短。

圖6 不同約束條件下ASSA算法與NS算法的計(jì)算時(shí)間對比Fig.6 Computed ti me comparison bet ween ASSA and NS under t wo different constrained conditions

圖7 相同出行規(guī)則下ASSA與NS算法的計(jì)算性能對比Fig.7 Computed perfor mance comparison bet ween AAS and NS under the same travel rules

由圖7可知，用戶選擇興趣點(diǎn)數(shù)目的多少直接影響著ASSA算法的計(jì)算時(shí)間和路徑搜索距離。隨著興趣點(diǎn)訪問類別的增加，可知用戶的出行距離也要相應(yīng)增加，由于算法需要響應(yīng)這一系列的出行規(guī)則，所以其路徑搜索距離以及計(jì)算時(shí)間兩項(xiàng)指標(biāo)都有明顯的上升，但ASSA的計(jì)算時(shí)間僅為0.191 s。相比NS算法，ASSA算法的執(zhí)行效率要優(yōu)于其16%以上。

4 結(jié)束語

以城市興趣點(diǎn)信息為基礎(chǔ)，提出了基于A＊的連續(xù)搜索算法（ASSA），該算法能夠快速地響應(yīng)用戶的多興趣點(diǎn)訪問要求，并提供最短行駛路徑。通過試驗(yàn)可知，提出的ASSA算法在運(yùn)行效果上要明顯優(yōu)于NS全方位最近鄰算法，并可避免非最短路徑的出現(xiàn)。但由于面向多興趣點(diǎn)信息的位置服務(wù)理念提出的較晚，因此對這類算法的研究依然處于起步階段，考慮的因素還不夠全面，實(shí)時(shí)性等有待進(jìn)一步提高。

［1］李威武，王慧，錢積新.智能交通系統(tǒng)中路徑誘導(dǎo)算法研究進(jìn)展［J］.浙江大學(xué)學(xué)報(bào)：工學(xué)版，2005，39（6）：819-825.Li Wei-wu，Wang Hui，Qian Ji-xin.New trends in route guidance algorith m research of intelligent transportation system［J］.Jour nal of Zhejiang University（Engineering Science），2005，39（6）：819-825.

［2］Li Y F，Le J，Danny M，et al.Mapping oversized and over weight tr uck r outes with pr ocedure based on geographic infor mation systems［J］.Transportation Research Record，2012，12（2219）：8-16.

［3］楊兆升.城市交通流誘導(dǎo)系統(tǒng)理論與模型［M］.北京：人民交通出版社，2000.

［4］Xing S H，Shahabi C.Scalable shortest paths browsing on land surface［C］∥GIS：Proceedings of the ACM Inter national Sy mposiu m on Advances in Geographic Infor mation Systems，2010：89-98.

［5］Alba Martínez M A，Cor deau J F，Dell＇Amico M，et al.A branch-and-cut algorithm for the double traveling salesman problem with multiple stacks［J］.Infor ms Jour nal on Co mputing，2013，25（1）：41-55.

［6］Sharifzadeh M，Kolahdouzan M，Shahabi C.The optimal sequenced route query［J］.The VLDB Journal，2008，17（4）：765-787.

［7］Lee K C K，Lee W C，Leong H V.Nearest surrounder queries［C］∥IEEE Transactions on Knowledge and Data Engineering，2010，22（10）：1444-1458.

［8］Terrovitis M，Bakiras S，Papadias D，et al.Constrained shortest path computation［C］∥Proceeding of the 9th Inter national Sy mposiu m on Spatial and Temporal Databases，2005：181-199.

［9］Chen H Q，Ku W S，Sun M T，et al.The multi-r ule partial sequenced route quer y［C］∥GIS：Proceedings of the ACM Inter national Sy mposiu m on Advances in Geographic Infor mation Systems，2008：65-74.

［10］Taniar D，Safar M，Tran Q T，et al.Spatial net wor k RNN queries in GIS［J］.Computer Journal，2011，54（4）：617-627.

［11］Montalto F A，Bartrand T A，Wald man A M，et al.Decentralised green infrastr uct ure：The i mportance of stakeholder behaviour in deter mining spatial and temporal outcomes［J］.Structure and Infrastructure Engineering，2013，9（12）：1187-1205.

［12］Zhao W，Li Q，Li B.Extracting hierarchical landmar ks fro m ur ban POI data［J］.Jour nal of Remote Sensing，2011，15（5）：973-988.

［13］Raubal M，Winter S.Enriching wayfinding instr uctions with local land mar ks［J］.Geographic Infor mation Science Lecture Notes in Computer Science，2002，2478：243-259.

［14］范志起.半結(jié)構(gòu)化數(shù)據(jù)索引技術(shù)的研究［D］.長春：吉林大學(xué)：計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，2011.Fan Zhi-qi.Research on the index technology of semi-structured data［D］.Changchun：College of Co mputer Science and Technology，Jilin University，2011.

［15］Engebretsen L，Kar pinski M.TSP with bounded metrics［J］.Jour nal of Co mputer and System Sciences，2006，72（4）：509-546.

［16］于德新，楊兆升，高鵬.動態(tài)限制搜索區(qū)域的帶約束K則最優(yōu)路徑算法［J］.吉林大學(xué)學(xué)報(bào)：工學(xué)版，2009，39（增刊2）：172-176.Yu De-xin，Yang Zhao-sheng，Gao Peng.Constrained K-shortest pat hs algorith m within dynamic restricted searching area［J］.Jour nal of Jilin University（Engineering and Technology Edition），2009，39（Sup.2）：172-176.

［17］鄭四發(fā)，曹劍東，連小珉.復(fù)雜路網(wǎng)下多客戶間最短路徑的扇面Dijkstra算法［J］.清華大學(xué)學(xué)報(bào)：自然科學(xué)版，2009，49（11）：1834-1837.Zheng Si-fa，Cao Jian-dong，Lian Xiao-min.Sector Dijkstra algorith m for shortest routes bet ween customers in co mplex road net wor ks［J］.Jour nal of Tsinghua University，2009，49（11）：1834-1837.