【优秀论文】基于路网的路径查询问题的研究

2基于路网的路径查询问题的研究1引言11研究背景随着经济和技术的飞速发展，越来越多的人们购置私家车作为交通工具。这大大提高了人们出行的自主性和舒适度。人们不再局限于公共交通的时间和空间限制，可以自由选择出行时间和路线。与此同时道路设施也在迅猛发展中，用以保障人们出行的畅通并且为人们出行提供多重选择。庞大繁复的城市道路系统和多变的路况情况使得地图应用成为人们日常生活中非常重要的服务与应用。在地图服务中，不同的用户对于路径有着不同的要求。随着路径查询问题研究的不断深入，解决各种路径查询问题的新算法不断涌现。在线地图应用和基于位置的服务（LBSLOCATIONBASEDSERVICES）的迅猛发展，使得地图上的信息进一步丰富。人们可以通过移动设备的GPS定位对生活中的建筑和商店信息加入到地图应用中，如百度旅游，大众点评网等等。这些基于用户的兴趣点信息（POIPOINTOFINTEREST）的丰富使得之前一度被忽略的基于关键字的路径查询问题再次获得了研究者的青睐，有了进一步的进展。这种查询与普通路径查询的不同在于用户可以通过关键字说明他们对于路径的兴趣点。基于关键字的路径查询问题不断细化出各种变种，解决各种变种问题的新算法也层出不穷。然而，城市交通的发展中的一个新的问题是由于汽车的井喷式增长城市的交通拥堵情况日益严重，人们常常并不能根据地图应用规划的最短路径按时到达指定终点，大大降低了人们的出行舒适度。智能交通（ITSINTELLIGENTTRANSPORTSYSTEM）被公认为是解决交通拥堵问题的重要手段。目前大部分大中城市在高速路段的各个路段设有线圈测速以及事件记录装置。基于这些历史数据有越来越多的研究致力于改善人们的出行质量。研究包括对车辆进行实时导航，为用户进行出行前的路径查询和对路径的时间进行估计预测等等。12研究内容基于关键字的路径查询问题研究的经典问题为空间数据库中的TPQ问题（TRIPPLANQUERY）。在TPQ问题（TRIPPLANQUERY）中，用户可以指定一组关键字，TPQ搜索从起始点到终点最短的覆盖所有关键字的路径。这是一个NP难问题。OSR（OPTIMALSEQUENCEDROUTE）查询用以找到一条以某一顺序经过某些给定节点的路径，这条路径使他行走的距离或者花费的时间最短。和TPQ问题同时的MTNN（MULTITYPENEARESTNEIGHBOR）查询提出了解决问题解决的精确算法。基于OSR查询的MSPSR（MULTIRULEPARTIALSEQUENCEDROUTE）查询可以个性化指定一些顺序的要求，如先经过加油站再经过咖啡馆和电影院而不要求经过咖啡馆和电影院的顺序。考虑到用户输入关键字有时与相应POI上的关键字不同的情况，文献提出了MARK（MULTIAPPROPRIATEKEYWORD）查询。文献提出的KOR（KEYWORDAWAREOPTIMALROUTE）查询可以找到一条覆盖用户指定关键字，满足预算条件（比如，时间，花费）并使得总共的受欢迎程度最高。SKYLINE查询是找到至少有一个属性优于其他所有元素的SKYLINE对象。即SKYLINE查询是找到不能被其他对象支配的对象。这在数据库中有着广泛的应用。如，BRANCHANDBOUNDSKYLINE算法是一个SKYLINE查询中的渐进最优算法。文献研究了如何找到不被到查询起点的距离和到已有路径的迂回路径长度支配的兴趣点。文献提出了两个空间SKYLINE查询算法，基于R树的BS和基于VORONOI图的VS。MPP（MULTIPREFERENCEPATHPLANNING）问题是基于路网的路径SKYLINE查询，属性包括距离，行驶时间，路过的交通灯等等。在路网上的多目标优化路径查询研究中，优化目标为边上的不同参数，如花费，长度，时间和可信度等等。MSPP（MULTIOBJECTIVESHORTESTPATHPROBLEM）研究路网上不被支配的路径，也称为PARETOPATH。意为对于查询结果的对象如果不降低其中一个对象的任何一个参数那么就不能得到另外一个处于查询结果的对象。这被证明在最坏情况下可能有指数级个数的解。标号算法研究了这个问题的精确全集解。算法基于路段排名和MOTE算法。MSPP是一个总和最优或者最小值最大的优化问题。智能交通系统包括车辆控制系统、交通监控系统、运营车辆高度管理系统和旅行信息系统等。研究包括基于实时数据和定位的车辆导航、基于历史数据和实时数据通过预测的车辆导航、基于动态网络的最短路径算法的改进与近似。基于实时数据和定位的车辆导航通过汽车定位、实时路况信息和用户输入的终点给出一条最短路径。文献基于历史数据进行多步时间预测和动态DIJKSTRA最短路径算法求得由起始位置到终点的动态最短路径，并且在车辆行进过程中对路径进行修正。13本文工作本文从两个方面进行研究即基于关键字的支配路径查询问题的研究和基于短时交通预测的动态路径查询问题的研究本文提出一种带关键字的、多查询点的空间査询,叫带关键字的聚集路径查询,是一类空间关键字的匹配查询。本文分布从多路径与树结构的角度出发定义了该查询。与其他空间关键字查询不一样,该查询关注多用户的行程规划。带关键字的聚柴路径查询问题是NPHARD。为了获取查询结果,本文提出一种基于树状索引的精确算法。该精确算法需要重复进行查找分配和任务完成两个阶段的工作。查找分配阶段的主要工作有三点获取聚集点、确定候选任务点集合、给查询点分配任务。查找分配阶段首选通过增量式算法按序获取聚集点,避免访问不必要的点。为了减少任务点集的大小,算法使用了椭圆范围查询确定候选点。本文根据最小包围矩形与椭圆的关系改进了椭圆范围查询的算法。接下来,算法开始迭代式给查询点分配相应的任务。为了加快査询处理,查找分配阶段始终维护着结果的上下界。到任务完成阶段时,精确算法使用一种启发式的算法,利用最小堆维护拓展的路径。通过动态规划的方法维护一张路径的表格,算法减少了最小堆的大小并且过滤了不必要的路径。利用空间换取时间的方法,算法保存得到的最优路径以减少重复的查询。接下来,本文验证了精确算法的正确性。对于查询点或者关键字个数庞大的情况下,精确算法难以在可接受时间内返回结果。针对这种情况,本文提出了查询的近似算法。基于中心分配的算法考虑到用户聚集的地点通常距离其中心点很近,可以在中心点附近顺便完成任务。该算法主要使用基础的查询算法,因此速度非常快。而扩展树算法则基于查询的另外一种关于树的定义方式,在结果偏差率中有较稳定的表现。为了避免聚集点选错后影响结果偏差率,本文还分别对两个近似算法进行拓展。最后,本文使用了真实数据集验证了算法的效率。14文章结构本文一共分成6章,内容与章节安排如下第1章“引言”,该部分介绍空间关键字查询的背景知识,还有空间关键字查询的研究内容,并介绍了本文的主要工作内容。第2章“相关工作”,该部分首先介绍了传统的数据库的主要索引技术,例如RTREE、KDTREE,和一些预处理技术,比如VORONOI图、TEDI树,还有传统空间查询,比如最近查询、聚集最近邻查询等。接下来,该部分介绍了空间关键字查询的索引技术,如R2TREE、IRTREE等,还有一些空间关键字匹配查询还有排序查询。第3章“背景知识”,该部分首先引入了多关键的路径查询,说明了研究精确关键字匹配的目的所在。接着正式介绍了本文所研究的主要问题带关键字的聚集路径查询问题,给出了该问题的两种定义方式,最后证明了该问题是NPHARD的。第6章“总结与展望”,该部分总结了本文的主要工作与成果,并给出了下一步的主要工作。2支配路径查询问题研究21相关工作在基于关键字的路径查询问题的变种中，研究比较成熟的主要有TPQ、OSR、KOR等问题，这些变种的定义与性质不尽相同，适用的算法也不一样。下面分别论述TPQ、OSR和KOR问题以及解决每类变种的算法。211TPQ问题概述在TPQ问题（TRIPPLANQUERY）中，用户可以指定一组关键字，TPQ搜索从起始点到终点最短的覆盖所有关键字的路径。TPQ的概念最早诞生于空间数据库领域。近几十年，空间数据库受到各大数据库生产厂商与科研机构的追捧，大量科研人员对其进行了深入研究。在这一研究热潮中，大量新的数据模型、空间索引技术和查询处理基础等新技术不断涌现。然而，这些新的索引以及查询技术往往仅限于简单的维度，大部分都可以视为最近邻查询或者其变种，这些技术无法满足新的现实空间模型以及新型空间数据库发展的需求。TPQ即诞生于此背景之下。TPQ概念如下假定一个数据库存储的是各种空间对象的位置信息，这些位置信息都取自一个固定的类别集合C。指定空间中的任意两点（起点S和终点T）、类别集合C的一个子集R，TPQ的目标是查询自起点S出发，经过R集合中的所有点并最终到达终点T的最优路径。比如复旦大学的一名学生计划从复旦大学张江校区去往复旦大学杨浦校区，他希望途中经过一个理发店理发、一个餐馆吃饭和一个书店买书。针对这一特定场景，TPQ会输出起点为复旦大学张江校区，终点为复旦大学杨浦校区，途经理发店、餐馆和书店的最优路径。当然，最优不同最优路径标准的不同可能会导致最终输出路径的不同，比如最短距离路径或者最短时间路径。TPQ查询问题可以被视为旅行售货员（TSP）问题的一般化。由于TSP问题是NP难的，TSP问题又可以规约为TPQ查询问题，所以TPQ查询问题也是NP难的。TSP问题向TPQ查询问题规约的过程如下假定每个类别只包含唯一的一个点，TSP问题约定遍历所有的点，由于每个类别只包含一个点，此时TSP问题等价于约定遍历所有的类别，显然满足TPQ问题的约定条件，TSP问题是TPQ问题的特例。TPQ问题类似连续最近邻查询问题，然而，用于解决连续最近邻查询问题的算法并不能产生很好的TPQ路径。专门处理TPQ问题的算法研究工作非常必要。由于TPQ查询问题是NP难的，不存在多项式复杂度之内的算法，有效地解决TPQ查询问题主要依靠近似算法，近似比率的依据主要是类别的数量M和类别的最大维度P，因此TPQ查询问题的近似算法主要包括基于类别数量M的近似算法和机遇类别最大维度P的近似算法。基于类别数量M的近似算法主要有最近邻算法（ANN）和最小距离算法（AMD）。最近邻算法的思想非常简单，从起点开始，每次访问距离当前已经访问节点最近的类别中的邻居节点，并且保证该最近邻居节点尚未被访问。形式化定义如下给定部分路径TK,KDISTUCOSTU,K,T，则修改DISTKDISTUCOSTU,K,T目标节点E加入到S集合了么从获得最短路径算法结束，找到动态最短路径否是动态分时段的DIJKSTRA算法流程图中S表示集合变量，具体指包含最优路径的节点集合；SV是表示节点V是否已找到最短路径的布尔标识，SVTRUE表示已经找到了开始节点到节点V的最短路径，SVFALSE表示还没有找到开始节点到节点V的最短路径；DISTV表示起点到节点V的最优路径所耗费的时间。动态分时段的DIJKSTRA算法可以根据车辆的路段位置进行不同时段的动态路径查询，最终找出最短路径。然而，由于时段跨度往往比较大，该算法无法应对时间敏感的突发事件，比如天气突变、交通事故等，在这种情况下使用该算法得到的最短路径不是实际情况下的最短路径，因为此时它没有放映突发事件对最终路径的影响，因此该算法在突发事件频发的路段中应用价值有限。3122小间隔时段动态路径查询算法小间隔时段的路况信息具有连续性，此时可认为某一路段的行驶时间是固定的，因此可以在小间隔时段内调用静态DIJKSTRA算法来进行路径查询，当下一个时段到来时，该路段的行驶时间发生变化，依据变化之后的数据重新利用静态DIJKSTRA算法来进行路径查询。小间隔时段动态路径查询算法通常将时段长度设置为5分钟到15分钟之间，此时的时段长度适中，交通信息反馈比较及时，最终得到的规划路径也比较准确。小间隔时段动态路径查询算法有效利用了实时的交通信息，可以有效应对突发天气、交通事故等因素，因此在突发事故比较多的路段实用价值比较高。然而，小间隔时段动态路径查询算法利用实时数据，由于实时数据存在延时、衰减等破坏数据完整新的缺点，小间隔时段动态路径查询算法也存在其局限性。其一为实时采集的数据的延时导致最新的交通信息并没有反映在当前路径查询算法找到的路径中，此时地路径具有时滞性，对于实时性要求比较高的用户来说，具有时滞性的路径的实用价值不大。其二为小间隔时段动态路径查询算法只依赖于当前数据进行路径查询，不考虑未来若干时间段之内的交通信息，容易导致最终规划出得路径偏离最优路径。比如根据当前信息，1小时之后到达的路段的路况良好，然而当车辆在1小时之后行驶至该路段时，可能由于上下班高峰等因素此路段已经非常拥堵，此时规划出得路径不符合用户的预期。其三为在交通比较繁忙的时段，路况信息的波动比较大，每个小时段规划出得路径都不同。用户期望获得是变动较小的最优路径，频繁变动的规划路径可能会给用户带来困扰，最终耗尽他们的耐心。3123TDSPP问题动态路径查询算法的第三种类型是时间依赖网络中的最短路径问题，该模型最早由COOKE,HALSEY在1966年提出。在时间依赖的网络模型中，网络中依赖时间而变化的一些特性是可以预期的。时间依赖网络模型最初被用来解决根据当前路网数据规划的最短路径没有考虑可预期的路况数据变化问题，比如高峰时段等。在时间依赖网络最短路径查询模型中，通过某一路段的时间是从该路段出发的时段的函数，并且所有这些函数都是已知的。时间依赖最短路径查询的具体流程是在当前时刻，对路网中所有路段进行多步预测，确定之后每个路段的具体行程时间，将路网建模为基于预测行程时间的时间依赖网络。普适的时间依赖最短路径是NP难的，不存在多项式时间复杂度之内的求解算法，因此实际应用中价值有限。然而，通过重新限制其前置条件，可以保证在多项式时间之内求解该问题，而前置条件也符合实际情况。比如通过限制通过顺序将时间依赖网络建模为FIFO网络，即先进先出网络，FIFO符合现实路网的通过顺序。在FIFO网络中，时间依赖最短路径呈现出很多有用的性质，利用这些性质可以设计多项式时间复杂度的求解算法。BRIANCDEANY研究了FIFO时间依赖网络的性质并率先提出了多项式时间复杂度的求解算法。将实际路网建模为时间依赖网络，之后进行最短路径查询，这是求解动态路径查询问题的有效方法，也是实际路径导航系统普遍使用的方法。该方法充分整合了第一类动态路径查询算法和第二类动态路径查询算法，有效利用历史数据和实时数据，通过对未来若干时段进行预测，可以应对道路占有率突然升高等突发状况。不同于小间隔时段动态路径查询算法，时间依赖最短路径算法预测得到的未来若干时段的路况信息波动不大，最终规划得到的最短路径也不会频繁变动，不会给用户造成困扰。然而，基于多步预测的时间依赖最短路径算法存在如下局限其一，也是最重要的一点是当预测的跨度很大时，预测的精度下降很快，依据预测的路况数据规划的最短路径也越偏离实际最短路径；其二为多步预测的最佳预测步长比较模糊，不存在一致的最佳步长，每个实际路网的最佳步长也能都不同，这给选择步长带来了挑战。选择合理的步长，必须通过实际路网中的不断迭代尝试，而大型路网的迭代尝试是非常耗时的。其三是历史数据的选取标准不明确。同当前时刻较近的历史数据对未来时段交通情况的关联性较大，同当前时刻较远的历史数据对未来时段交通情况的关联性较小，考虑所有历史数据涉及的数据量太大，无法在可以接受的时间内规划出合理的路径。考虑最近的历史数据可能会造成最终路径被若干数据支配，影响最终规划路径的准确性。313其他相关工作32算法设计321基于改进K近邻的短时交通预测算法基于改进K近邻的短时交通预测算法是非参数回归预测算法的一种，通过选择同当前观测的状态向量最相似的K个邻居状态向量来预测未来的路段行驶速度和通过时间。传统的基于K近邻的短时交通预测根据当前的实时速度和历史速度进行比较，从相似度较高的历史数据中的下一时刻的数据预测当前时间下一时刻的交通情况。而我们考虑到在不能获知实时速度而历史数据丰富时的，考虑到交通的规律性，我们从出行时的日期，时刻，星期，天气角度，对任意时刻的交通情况进行预测。3211算法框架具体而言，基于改进K近邻的短时交通预测算法包含5个组成部分（1）构建历史数据库。（2）确定状态向量。（3）确定预测函数。（4）从历史数据库搜索当前状态向量的K个最近邻居。（5）根据K个最近邻居，利用预测函数预测行驶速度和通过时间。基于改进K近邻的短时交通预测算法的具体流程如下图构建历史数据库历史数据预处理形成历史数据库当前数据K个近邻数据预测结果近邻匹配预测算法采用改进K近邻的短时交通预测算法进行交通预测的基础是数据属性丰富且有大量真实有效的历史数据。历史数据应该包含影响交通情况的各个属性如天气、日期、时刻等等的因素从而实时数据可以根据当前的情况找到和历史数据相似度最高的数据。大量真实有效的数据是当前数据在历史数据中有相似项的保证。然而，一方面庞大的历史数据需要合理的设计历史数据库，从而减少数据冗余、提高查询速度。另一方面历史数据中存在着测量误差、记录丢失和干扰数据等等情况，在历史数据库形成前我们需要对原始数据进行数据清洗，降低误差，提高预测准确度。3212状态向量定义状态向量确定了当前数据特征从而可以在历史数据库找到相似数据。在没有实时交通流速情况下，我们可以根据交通情况的规律性和复杂性，通过对状态向量选择可以将人们主观的结论和历史数据结合起来，对短时交通进行预测。根据HTTP/TRPAUTONAVICOM/TRAFFIC/可知，城市交通拥堵问题严重且规律性明显，同时影响不同城市的特征差异很大，如北京的交通受到会议活动影响较大。哈尔滨的城市交通季节特征明显。上海由于气候平稳、无特殊道路交通事件，所以没有和北京哈尔滨相似的特征。但是上海地区晴雨天交通差别明显，高峰时段交通拥堵情况显著，节假日部分交通路段与平时差距较大。在此，我们选择上海作为研究城市，根据上海的交通规律制定相应的状态向量。因此选取日期，时间，星期，天气组成状态向量。即,HHXDTWTD其中，表示路径查询当天的日期。表示历史数据对应的日期。表示TDT当前时间。表示当前的星期，如星期一，星期六。表示路径查询当天的W天气，如晴，雨。分别表示历史数据对应的时间、星期和天气。,HHT3213距离度量准则距离度量准则用来衡量当前采集数据同历史数据库中得数据的匹配程度，通过距离函数来实现。对于给定的域，上的距离函数为映射XDXR对于域中的所有，距离函数需要满足如下条件X,XYZD（1）非负性，即。0D（2）当且仅当。,（3）对称性，即。,XY（4）三角不等式。,ZDYZ常用的距离函数有曼哈顿距离和欧拉距离，这两种距离函数在我们设计的状态向量下不能直接使用。我们使用1/21234IHHHDTWDW3214预测算法经过上述的近邻匹配机制，假设在历史数据库中找到K个近邻，实际数据和这K个近邻的距离为，这些近邻所对应的时刻的流量为。预测算法包括等权重和带权重的预测算法。其中等权重的预测算法为1IKHIV这里并没有考虑当前观测值和历史数据库中不同近邻距离的不同，仅仅将各个近邻对于的流量取简单算数平均作为当前时刻的预测值。带权重的预算算法为1I1,IKIHKIIDV其中，带权重的预测算法认为与当前观测的实时数据距离较小的历史数据库中的数据系列相似度较大，从而在预测算法中，这些距离近的近邻对预测值的权重较大。所以，通过对距离取倒数来确定权值。本文采用带权重的预测算法进行预测。322基于A的动态路径查询算法3221A算法A算法是一种在在图中的节点之间寻找最短路径的高效算法。在静态网络中，A算法的性能很高，如果可以保证启发式估价函数对每个节点的估值不高于其实际值，A算法确定可以找到一条最短路径。A算法最早由PETERHART,NILSNILSSON和BERTRAMRAPHAEL于1968年提出，最初是作为EDSGERDIJKSTRA于1959年提出的DIJKSTRA算法的一种推广，通过启发式搜索来提高算法效率。由于A算法的高效率和精度，A算法被广泛应用于游戏路径查询中，如在线游戏的BOT移动计算和NPC移动计算等。对于图G中给定的两个节点S和T，A算法通过启发式搜索来找到一条起自节点S止于节点T的最短路径，其启发式搜索策略其实是一种最佳优先搜索策略。在A算法遍历图G寻找节点S和T之间的最短路径过程中，它通过合理的估价函数来保证搜索向着最佳的方向进行，同时维护一个优先队列来存储可能组成最短路径的其他节点。对于图G中给定的节点X，A算法利用一个启发式的估价函数FX来决定节点X在图中的遍历次序，估价函数FX由两部分组成（1）已遍历路径的耗费函数，表示从开始节点到当前节点X的路径耗费，通常标记为GX。（2）未遍历路径的耗费函数，表示从当前节点X到终点的路径耗费估值，通常标记为FX。估价函数FXGXDX。未遍历路径的耗费函数FX需要满足一定的启发式条件，即对当前节点到终点的路径耗费估值不可以超过当前节点到终点的实际路径耗费。因此，在求解图中得最短路径问题中，HX可以表示当前节点到终点的直线距离，因为直线距离是两个节点之间的最短距离。同传统的搜索算法相同，A算法也是首先访问最可能形成最短路径的节点。A算法不同于一般贪心最佳优先算法，它不仅考虑为访问的节点路径距离，也考虑已经访问的节点路径距离，而一般贪心最佳优先算法不考虑已经访问的节点路径距离。从起点开始，A算法维持一个优先队列来存储有机会被访问的节点。对于优先队列中的任意节点X,估价函数值FX的值越小，节点的优先级越高，被访问的次序越靠前。在算法的每一次迭代过程中，选取优先队列中具有最小估价函数值FX的节点X作为当前扩展节点，更新图中X得邻接节点的F值和G值，并把节点X的这些邻接节点加入到优先队列中。A算法在终点的估价值F小于任何优先队列中的节点的估价值或者优先队列为空时终止。目前为止的算法仅仅求出了从起点到终点的最短路径的长度。为了在求得最短路径长度的同时求出具体的最短路径，修改算法存储当前遍历节点的上一节点。算法运行结束后，终点指向其上一节点，反向遍历直到遍历到起点即可构建出最短路径。A算法的流程如下（1）将起点S置于优先队列，并计算起点S的估价函数FS。（2）选择优先队列中具有最小估价函数值FX的节点X作为下一个扩展节点。（3）如果第（2）步选择的扩展节点X为终点，找到最短路径，算法终止。（4）如果第（2）步选择的扩展节点X不是终点，将节点X移出优先队列，更新节点X的邻接节点的F值和G值，并把未在优先队列中的X的邻接节点加入到优先队列之中。对于已经在优先队列之中的X的邻接节点，如果其最新的估价函数值F小于当前值，则更新其其值为最新的F值和G值。3222DA算法动态下界323算法框架输入起点、终点，出发时刻初始化状态向量，初始化优先队列优先队列是否为空取队列中优先级最高的元素，并更新所取的元素是不是终点找到最快路径，算法结束用K近邻回归该节点到其邻接节点路段的行驶速度，并计算时间预估邻接节点到终点需要的时间，更新邻接节点的优先级否否是找到最快路径，算法结束是33实验评估4总结与展望41本文总结由于智能设备的普及与基于位置的社交网站的兴盛,空间关键字匹配查询在现实生活中具有很大的价值,广泛地应用于旅游行程规划、商铺开设规划等问题。而带关键字的聚集路径查询有效地解决多个用户聚会的选址与行程规划等问题，本文为该查询提供了有效的解决方法。首先,本文给出了带关键字的聚集路径查询的具体定义,两个定义分别从路径集合与树的观点出发。引入了多关键字的路径查询来说明该问题的是NPH