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

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

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

表1

Table 1

表1(Table 1)

表1 POI分类 Table 1 POI classification 购物场所 商业自营小店、百货商场以及大型超市等 宾馆酒店 提供住宿的宾馆以及星级酒店 车辆服务 汽车维修及加油/气/电站等 政府机关 区级或以上国家行政机关 医院 国家/省级综合医院及专业医院 公园 公共开放的公园及广场 休闲场馆 体育场、歌剧院以及电影院等 餐饮饭店 各档次饭店 学校 各大、中、小院校等 交通枢纽 车站、机场以及港口码头等 大厦 大型写字楼和商务办公楼 名胜古迹 著名景观、古迹以及纪念馆

表1 POI分类 Table 1 POI classification

试验平台配置如下:2.8 GHz双核处理器,2 GB内存,操作系统为WindowsXP。试验路网选择长春市实际路网,共包括3421个结点以及5771个路段,如图5所示。其中结点的存储形式为{Node_ID,Longtitude,Latitude},路段的存储形式为{Edge_ID,Strat_Node_ID,End_Node_ID}。出行起始点采用随机数发生器产生的服从均匀分布的点数据。采用Mapinfo7.0+Mapx以及Visual C++6.0对所提算法进行编程实现。

图5

Fig.5

	Figure Option ViewDownloadNew Window
	图5 长春市路网及其兴趣点分布情况Fig.5 POI distribution on ChangChun road-network

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

表2

Table 2

表2(Table 2)

表2 不同兴趣点类别包含的兴趣点数 Table 2 Number of POIs in different categorization 宾馆酒店 381 购物场所 1075 大厦 38 政府办公 483 车辆服务 407 学校 407 银行 547 休闲场所 724

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

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

图6

Fig.6

	Figure Option ViewDownloadNew Window
	图6 不同约束条件下ASSA算法与NS算法的计算时间对比Fig.6 Computed time comparison between ASSA and NS under two different constrained conditions

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

图7

Fig.7

	Figure Option ViewDownloadNew Window
	图7 相同出行规则下ASSA与NS算法的计算性能对比Fig.7 Computed performance comparison between AAS and NS under the same travel rules

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