基于“路网数据库”的最佳位置及路径选择研究

刘　佳，刘　琳，陈　伟

(1.中国环境管理干部学院，河北 秦皇岛　066004；2.秦皇岛职业技术学院，河北 秦皇岛　066004)



基于“路网数据库”的最佳位置及路径选择研究

刘佳1，刘琳2，陈伟1

(1.中国环境管理干部学院，河北 秦皇岛066004；2.秦皇岛职业技术学院，河北 秦皇岛066004)

摘要：本文综合“位置查询”及“路径查询”为一体，同步解决最佳位置及路径的查询问题，并在此基础上考虑其合理性，以满足实际路网查询与分析应用的要求。同时针对实际问题，进行实际案例分析，找出了影响效率的指标属性，进而构建了合理性路网最佳位置及路径分析框架，有效地实现最佳位置及路径的选择问题。

关键词：路网；数据库；最佳位置；最优路径

河北省教育厅青年基金项目(基于空间网络的“兴趣集群”的最优选择查询研究，QN2015133)。

1.问题提出

目前，关于空间信息查询的研究越来越多，包括：最近邻查询和它的变体。他们可以应用在餐饮、娱乐、医疗救护、事故救援、区域分析、数量统计等各方面，几乎囊括了生活中的各行各业。尤其在路网上的位置查询服务，应用极广。(最佳路径选择是空间信息查询中的关键技术，是智能交通及路网应用的重要指标。在实时性和有效性上完善路径选择算法，优化查询效率及准确度，提高实际应用价值，建立高效的路网分析策略。)例如：查找最近位置(查找最近的加油站)、查找最合适位置(某个商店开设分店)、查找最优路径(旅游景点的游玩顺序)等。根据实际路网应用问题，最佳位置及路径选择问题毫无疑问地成了目前路网的研究重点。目前常见的路网应用问题有如下两类：

(1)查找最近目标，如：加油站、旅游景点、医院等，现有的系统直接通过距离测算，查找最近的一个。

(2)查找最佳位置，如：在几块候选土地上开发项目，哪个最合适？现有的系统也是直接通过距离量算，对附近周围同类型项目的距离进行分析，然后来选择合适的地方。

然而，多数的路网上的研究大多基于距离量算，如：欧氏距离和路网距离，从它们的分析方式就能够看出其存在选择的盲目性：有的应用不能只靠距离测算，比如上边提到的“查找最近医院”，距离最小了，但是没有相关科室或不是优势专业，这给急病的选择者都带来了不便。而“查找最合适位置”的分析中，同类设施的距离考虑了，但是其服务门类，服务范围等属性数据都对新建设施产生影响，这些属性数据有的时候比距离重要的多，这显然是不合理的。

综上所述，本文基于上述问题，提出选择合理性要求，利用目标的属性数据信息作为评价指标，将“最佳位置和最佳路径”选择综合考虑，在一个模式架构下，解决多个问题。这种方式不仅能够解决目前路网查询的盲目性，还具有以下两个意义：

(1)将最优位置及路径查询由理论过渡到实际的路网应用，为现实的交通应用、选址分析、综合价值计算等提供理论依据。

(2)考虑到实际应用价值，对查询本身进行合理性评估，根据各个查询属性值进行不同的权值设定，使得最终查询结果应用性更强，应用价值更高。

2.国内外研究现状

目前，国内外关于路网信息检索内容主要集中在：最近邻查询、选址分析、索引机制。

(1)最近邻查询：根据实际查询需要，近邻可以是1个，也可以是K个(k个最近的目标点)，以下简称KNN(k-NearestNeighbor)查询。

KNN查询方法以传统的路径选择算法Dijktra算法为代表，在Dijktra算法基础上做些优化选择，其在小数据网中应用较多，但却不能支持大数据的路网，其查询和存储的代价都很高，尤其当数据量很大的时候，这种方法基本就是不可用。

(2)选址分析：也可称为最佳位置查询，以下简称OL(Optimal Locations)查询。

OL查询是对空间信息资源的合理规划，部分文献对最优位置查询也提出了多种方法，但前提是假设现有查询目标存在Lp空间中，这种假设在实际中很受限制，因为空间位置之间的活动常常受其实际路网情况的约束，所以两个位置点之间的距离不是简单的Lp空间距离，故相应的实用价值也随之降低。

(3)索引机制：有效的剪枝策略，能够快速地引导查询算法，避免重复查询。

路网上信息量太大，实施查询都需要创建索引，无论是树结构还是图结构，都可以通过索引有效地实施剪枝策略，过滤不必要的查询，提高查询速度和准确度。

由上述分析可知，近年来路网信息查询一直处在不断地研究过程中，但都是基于距离求得最短路径或多个近邻。随着路网信息的增加，人们获取的信息除了满足距离最短以外，还要考虑信息应用价值和意义。

3.最佳位置及路径查询

3.1 最佳位置查询

最佳位置查询常常涉及设施的选址问题，可用于城市规划、商业选址等。而这样的问题仅仅将距离和关键属性作为检索条件是不足够的，因为不同的用户关注的属性不同，不能一概而论。所以本文将讨论如何给属性数据设置动态权值，用户在应用的时候可以自行选择权值设置，来满足各自的需求。

例如：某个人想开个童装店，想选取一块合适的地方，这个地方应具备以下条件的组合：

(1) 交通便利(方便逛街)

(2) 人口密集(保证基础的销售量)

(3) 周边有童装店(在童装店一条街上最好，有对比往往更好销货)

(4) 小区为近5年内新建小区(青年人多，有小孩)

(4)周边有时尚女装店(通常都是妈妈给孩子买衣服)

P=1×0.3+1×0.3+1×0.2+0×0.1+0×0.1=0.8

最终的值越接近于1，越符合要求。为方便理解，本方法将条件f做了0或1的设置，而现实中，它的取值范围应该更宽，而不仅仅是两个值，比如仍然是上述案例：

(1) 交通便利程度不同，取值也不同，可以查询点为始点，对周边最近交通站点做距离计算，计算值作为条件基础值。

(2) 人口密度也可以划分不同范围，根据年龄、消费水平等属性数据做基础参考值，综合形成条件基础值。

(3) 现有的童装店应该如何分布，对于商业区，应该聚集分布较好，即某个范围内存在的越多越好，越能吸引更多人；反之，如果是居民区，消费范围固定，那就不宜过多，否则利益被分割。所以，根据实际需求情况决定该条件的基础值。

(4) 选择小区周边，那么一定重点考虑父母年龄阶段，才能保证童装有基础的需求。

(5) 周边的辅助条件虽然不是重点，但是在某些条件下起到很好地促进作用。时尚女装是年轻妈妈的最爱，如果它与童装店邻接，那么妈妈们逛完女装店会不自觉地逛童装，而不一定是需要了才去，这样更能增加消费。

所以，对于公式P=∑f×q，其f与q的条件基础值由用户自行设定，那样更符合实际需要。

3.2 最佳路径选择

目前多数的空间路径选择都是基于“最短路径” 的思想，而最短路径多基于欧式空间量算的较多。在路网的应用上，实际的最短路径与欧式量算的可能刚好相反。同理，最短路径也仅仅考虑距离因素，忽视了其目标的有效性。最简单的例子：跑高速的车需要加油了，按照最短路径找到的地方没有该车对应的油号，甚至是什么油号的也没有了，这种情况很糟糕，却是实际存在的。所以， 我们提出了最佳路径的选择。

最佳路径即无论从距离、时间、有效性等方面均能满足查询用户的要求。

例如：去某个城市旅游，想查询一条“理想” 的游玩路径，其“理想”表现在：

(1) 最大合理化利用时间，保证每个景点在指定的时间内玩好。

(2) 路径上有餐饮、休息场所。

(3) 不会特别疲惫。

根据上述条件，在选择路径中提取指标为<景点游玩时间、餐饮、酒店>，并将游玩条件根据指标项，分解如下：

(1) 按照人一天正常的游玩时间计算：游玩4-5个小时，加上路程时间1-2个小时，不会太疲惫。

(2) 如果景点小，则可分成两部分，但应该在休息处附近，方便中午休息。如果景点大，则设置全天，午餐选择景点自助更划算。

(3) 如果在一个城市游玩，那么住宿点可以根据景点位置固定1-2个，然后设置路线。

根据上述指标，将住宿点作为查询点，找到目标的最佳位置(按照3.1中方法)，再将最佳位置组成路线，形成最佳路径。不同用户的指标项不同，所以同样的旅游城市，同样的景点，针对用户的最佳路径也会不同。用户可以将历史数据作为参考，调整重组条件，形成自己的最佳路径。

4. 结论

最佳位置及路径查询与我们的生活息息相关，甚至无处不在，它符合实际应用，使得查询变得“合理化”、“智能化”、“个性化”，从几个角度降低了各自的应用成本。同时，它也使实际应用达到合理调配资源的作用。

参考文献：

[1]Sankaranarayanan, J., Samet, H., Alborzi, H.: Path oracles for spatial networks. PVLDB 2(1), 1210-1221 (2009)

[2]Bin Yao, Xiaokui Xiao, Feifei Li, YifanWu, Dynamic Monitoring of Optimal Locations in Road Network Databases.(VLDB),pp:1-23(2013)

[3]Ruicheng Zhong, Guoliang Li, Kian-Lee Tan,Lizhu ZhouG-tree:An Efficient Index for KNN Search on Road Networks(CIKM),pp:39-48(2013)

[4]李艳红,黄群,蒋宏,李国徽.路网中空间关键字连续范围查询算法研究,计算机科学，2014，41(7)

The Optimum Location and Path Selection Research Based on "Road Network Database"

LIU Jia1，LIU Lin2，CHEN Wei1

(1.Environmental Management College of China, Qinhuangdao 066004, China;

2. Qinhuangdao Institute of Technology, Qinhuangdao 066004, China)

Abstract:This paper integrates the "location query" and "path query, synchronously solves the problem of optimum location and the path query, and on this basis, considers the rationality, to meet the requirements of the actual road network query and analytical application, rather than just the distance analysis. Based on the practical problems, this paper, through practical case analysis, finds out the index attributes of query efficiency, then builds the reasonable optimum location and path analysis framework of road network, effectively achieving the optimum location and path selection questions.

Key words:road network; database; optimum location; optimal path

作者简介：刘佳(1980- )，女，在读博士，中国环境管理干部学院教务科研处副教授，研究方向：数据库查询技术。

基金项目：河北省教育厅青年基金项目(基于“路网数据库”的最佳位置及路径选择研究，QN20141059)。

收稿日期：2015-10-08

中图分类号：U12

文献标识码：A

文章编号：1671-3974(2015)04-0062-03