基于城市兴趣点的连续路径诱导方法

于 尧，杨兆升，2，莫祥伦，林赐云，2

随着GIS地理信息的不断完善，路径导航［1－2］得到了人们越来越多的关注及应用。兴趣点信息的完善极大地方便了人们的出行，在出行前即可规划好去目的地的最短路径［3－4］。以一次出行为例，出行者通常需要先到餐馆、银行、商场等多个地点，最后抵达目的地。然而现有诱导算法大都以单兴趣点为诱导目标，忽略了实际出行中出行者的中途停留需求，无法实现多个兴趣点的连续路径规划。

近年来，一些学者针对连续行程规划问题［5］（STPQ）提出了相关的近似查询算法，如Sharifzadeh等［6］提出的最优有序路径算法（OSRLORD）、Lee 等 提 出 的 NS 最 近 邻 算 法［7］、Terrovitis等［8］提出的a自治最短路径规划和k停顿最短路径规划方法等，这些算法（方法）实质上都可以看成是多兴趣点连续路径规划的特例问题，不具有一般性。Chen等在文献［9］中阐述了多类别兴趣点有序路径查询问题，通过约束兴趣点访问顺序，得到不同约束规则下的路径查询效果，但其查询的兴趣点数据必须与其内部的数据集构成有拓扑关系，且提出的算法仅为数据查询机制，未能与实际路网地图匹配。所以如何有效、快速地响应用户对多兴趣点的访问请求，是实现高效路径引导服务的基础，也是未来几年内路径诱导领域的研究兴趣点。本文依据城市兴趣点认知程度，对其进行分类，并基于不同出行规则约束，提出了最近邻连续兴趣点搜索方法，旨在满足多出行规则约束下的访问需求，丰富了现有路径诱导方法。

1 POI兴趣点分类

城市兴趣点（Point of interest，POI）包括餐饮、购物、旅游以及汽车服务等多种类别。这些兴趣点信息已在地理信息服务中得到了广泛的应用［10－11］。POI信息不但可以帮助用户快速定位所需位置信息，还可以在导航中利用一定的规则进行推理，得到实时位置关联度最高的一系列地标［12］，进而实现简洁、灵活和高效的路径引导服务。

Raubal等［13］提出，城市中的任何要素，只要人们对它的认知度较高，即可以被看做是熟知的地点。本文将人们日常出行过程中需要经常访问的地点定为POI，并参照文献［12］，定义各类POI的基本选取范畴，如表1所示。

定义表1中的12种兴趣点分类为 ｛Ci｝ ，每个Ci都满足｛｝POIs∈Ci；此外，由于POI数据库中会出现冗余数据，如大厦内有大型商场，或者重叠的机关单位等，所以在路径计算前应剔除数据链表中的冗余数据，但同时要保证所删除的数据不属于用户查询兴趣点类别中的任意一种，所以本文设兴趣点的数据存储形式为｛Categor y＿Name，Longit ude，Latitude｝，并通过 Mapinf o7.0实现兴趣点与真实路网的匹配。

表1 POI分类Table 1 POI classification

2 不同约束规则下连续兴趣点查询

2.1 最近邻兴趣点路径搜索

实际上最近邻兴趣点路径搜索与数据库中的对象修剪与精炼过程类似［14］。但不同于旅行商问题（TSP）［5，15］，算法并不需要遍历每一个地图上已有的兴趣点，而是仅仅计算用户事先给定所需访问的兴趣点类别即可。

假设小A现有一个出行计划，她想到达车站之前，先去银行取钱，再分别至商场、加油站以及餐馆等4个地点，那么小A的出行路径有以下两种：①出发点→银行→餐馆→商场→加油站→车站。②出发点→银行→商场→餐馆→加油站→车站，如图1所示。

出行用户可以自己定制访问的兴趣点规则，如餐馆→商场，或者商场→餐馆，这时两种不同路径下出行时间的长短将成为辅助出行者决策的重要依据。

对于出行起点周边的最近邻兴趣点信息搜索（Nearest POI Search，NPS），做如下规定，如图2所示，图中的黑色点q代表用户的出行位置，空心点A、B、C、D、E、F代表路网节点（如交叉口），三角形P1、P2、P3代表路网中的兴趣点信息，数字代表路段的权重（本文中选择距离为权重系数）。

图1 小A的出行路径选择Fig.1 Travel route choice

搜索当前离q最近兴趣点位置的步骤为：首先选取与q点相连接的路网节点（C、D），并初始化队列Q＝ 〈（C，5），（D，7）〉；判断CD 中是否有P存在，若无，紧邻q点的节点C出队，节点A、E进队列Q 中，Q 更新为Q ＝ 〈（D，7），（A，9），（E，10）〉；由于CA、CE段上没有P存在，故同节点C一样，节点D出队，紧邻D点的B、F进队，更新Q，Q＝ 〈（A，9），（E，10）（F，10），（B，15）〉；接下来在BD段上搜索到P 3，计算q至P 3的距离为9，判断目前Q中其余节点至q点的距离可知，没有小于9的路径，所以搜索完成，q点至最近兴趣点P3的最短距离即为9。

图2 最近邻兴趣点路径搜索示意图Fig.2 Nearest POI search sketch

2.2 基于A＊的连续搜索算法

在最近邻兴趣点路径搜索规则的基础上，提出基于A＊的连续搜索算法（A＊-based sequenced search al gorit h m，ASSA），算法考虑了用户设置的终点信息，通过分别计算起点与终点至兴趣点P的最短距离（如式（1）所示），得到总出行费用（距离）最小的路径，避免了非最短路径的出现［16］，如图3所示。

图3中的虚线代表未考虑出行终点D时的出行路径，实线为考虑D点后的出行路径。可以看出，未考虑D情况下的出行距离要远大于后者。

图3 定义规则为Bank-Restaurant下的出行路径对比Fig.3 Comparison of travel routes under Bank-to-Restaur ant r ule

采取与经典启发式算法类似的估价方法，设（s，d）为ASSA算法选定的包含兴趣点pi至兴趣点pj间的行驶路线，令f（l）＝ω（s，pi）＋c（pi，d），其中ω（s，pi）为从起始点s到达兴趣点pi的权值之和，c（pi，d）为兴趣点pi的代价函数，它预测了从pi到目的地d的代价。f（l）的值决定了该兴趣点是否能够被优先查找。

为了减少路网搜索范围，通过出发点O、目的地D以及OD间的欧式距离确定一个椭圆，这个椭圆的焦点即为O、D，这样可以有效减少算法的搜索范围。采用不同形式的数据存储形式，会对算法的执行效能产生较大影响。在路网规模较大时，应采用表形式存储数据，此时遍历效率远高于邻接矩阵的存储形式［17］。在本文中，采用与Dij kstra相似的表形式用以存储路网及兴趣点数据，即初始搜索点将被添加至Sv表中，而L最短路径表为空表状态。设兴趣点访问规则为R，那么算法的时间复杂度即为R2。其算法流程图如图4所示。

3 试验分析

试验平台配置如下：2.8 GHz双核处理器，2 GB内存，操作系统为Windows XP。试验路网选择长春市实际路网，共包括3421个结点以及5771个路段，如图5所示。其中结点的存储形式为｛Node＿ID，Longtitude，Latitude｝，路段的存储形式为｛Edge＿ID，Strat＿Node＿ID，End＿Node＿ID｝。出行起始点采用随机数发生器产生的服从均匀分布的点数据。采用Mapinf o7.0＋Mapx以及Visual C＋＋6.0对所提算法进行编程实现。

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

图5 长春市路网及其兴趣点分布情况Fig.5 POI distribution on ChangChun road-net work

路网中共含有12个兴趣点图层，本文仅取宾馆酒店、大厦、车辆服务、银行、商场、政府、学校以及休闲场所共计8个兴趣点分类中的主要兴趣点，各兴趣点数目如表2所示。通过对比文献［7］中提到的全方位最近邻算法（NS），分别在计算时间和搜索距离两方面分析了不同出行约束条件下两种算法的表现。NS算法［7］是数据遍历算法中较为成熟、广泛使用的一种数据关联搜索算法，具有较高的实用性。为了不失一般性，出行规则选择在银行和大厦，商场和车辆服务（如加油站）等不同兴趣点类别之间随机发生。

表2 不同兴趣点类别包含的兴趣点数Table 2 Number of POIs in different categorization

当出行规则一定时，相比于NS全方位搜索算法，ASSA算法的计算时间明显要优于NS算法，如图6所示。随着兴趣点基数的增加，两种算法的计算时间都有显著增加，以NS算法为例，当兴趣点数为3500个时，算法的计算时间相比500个兴趣点时增加了3倍以上；当出行约束条件增加时，也就是说用户定义的访问规则占全部需访问兴趣点类别的比例增加时，可知虽然NS算法和ASSA算法的计算时间都呈现线性增加，但计算时间要低于R／C＝0.333时的情景，这是因为，约束规则增加，算法所需遍历搜索的数据空间就随之减少，所以算法的执行时间也相应变短。

图6 不同约束条件下ASSA算法与NS算法的计算时间对比Fig.6 Computed ti me comparison bet ween ASSA and NS under t wo different constrained conditions

图7 相同出行规则下ASSA与NS算法的计算性能对比Fig.7 Computed perfor mance comparison bet ween AAS and NS under the same travel rules

由图7可知，用户选择兴趣点数目的多少直接影响着ASSA算法的计算时间和路径搜索距离。随着兴趣点访问类别的增加，可知用户的出行距离也要相应增加，由于算法需要响应这一系列的出行规则，所以其路径搜索距离以及计算时间两项指标都有明显的上升，但ASSA的计算时间仅为0.191 s。相比NS算法，ASSA算法的执行效率要优于其16%以上。

4 结束语

以城市兴趣点信息为基础，提出了基于A＊的连续搜索算法（ASSA），该算法能够快速地响应用户的多兴趣点访问要求，并提供最短行驶路径。通过试验可知，提出的ASSA算法在运行效果上要明显优于NS全方位最近邻算法，并可避免非最短路径的出现。但由于面向多兴趣点信息的位置服务理念提出的较晚，因此对这类算法的研究依然处于起步阶段，考虑的因素还不够全面，实时性等有待进一步提高。

［1］李威武，王慧，钱积新.智能交通系统中路径诱导算法研究进展［J］.浙江大学学报：工学版，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］杨兆升.城市交通流诱导系统理论与模型［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］范志起.半结构化数据索引技术的研究［D］.长春：吉林大学：计算机科学与技术学院，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］于德新，杨兆升，高鹏.动态限制搜索区域的带约束K则最优路径算法［J］.吉林大学学报：工学版，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］郑四发，曹剑东，连小珉.复杂路网下多客户间最短路径的扇面Dijkstra算法［J］.清华大学学报：自然科学版，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.