基于路网的支配路径查询研究
发布时间：2021-07-06 17:11
随着道路网络与移动通讯的迅猛发展,基于位置的服务在人们生活中发挥着重要作用。而路径规划一直是基于位置的服务与在线地图服务应用中基础而且重要的问题,为人们出行提供了重要参考。随着城镇化水平不断提高,道路网络规模不断增长,面对处理大型复杂道路网络和时间依赖道路网络的挑战时,传统的路径查询算法因其局限性而不能满足大数据时代的需求。因此,需要设计高效算法来解决路网中的路径查询问题。本文在两种道路网络情况下对支配路径查询进行研究:基于静态路网的支配路径查询问题研究和基于时间依赖路网的多约束支配路径查询研究。同时随着用户个性化需求的增加,用户不再满足于现有在线地图路径规划的单一维度路径查询,因而本文研究的问题同时考虑路径花费与结点分数两个维度,寻找不受其他路径支配的支配路径集合。首先,本文研究静态路网中的多偏好顺序路径Skyline查询。分析现有的构造权重Voronoi图的算法在预处理和查询过程存在的局限性。为了提高查询效率,提出基于过程支配的精确算法,定义未完成路径间的支配关系,对查询进行路径花费的花费上界预算,并提出增加剪枝策略。通过以终点为导向的消耗估计策略,进一步减小搜索空间。同时在保证算...
【文章来源】：沈阳建筑大学辽宁省
【文章页数】：65 页
【学位级别】：硕士
【部分图文】：
图２．２?９个结点的标准Ｖｏｒｏｎｏｉ图??Ｆｉｇ．?２．２?Ｔｈｅ?ｓｔａｎｄａｒｄ?Ｖｏｒｏｎｏｉ?ｄｉａｇｒａｍ?ｏｆ?９?ｖｅｔｅｃｓ??１１??
式化定义ＭＰＳＲＳ问题；然后介绍问题相关定义并介绍现有算法并给出解决该问题的算??法：最后通过在真实路网上进行实验，证明所提算法有效性和高效性。??３．１问题描述??多偏好顺序路径?Ｓｋｙｌｉｎｅ?查询（Ｍｕｌｔｉ－Ｐｒｅｆｅｒｅｎｃｅ?Ｓｅｑｕｅｎｃｅ?Ｒｏｕｔｅ?Ｓｋｙｌｉｎｅ?ｑｕｅｒｙ），简??称为ＭＰＳＲＳ查询问题［｜２】。给定二维道路网络图Ｇ，起始结点ｓ和终止结点用户的??偏好设罝尸，一组顺序关键字序列义。ＭＰＳＲＳ查询寻找一组从起始结点ｓ出发，途经指??定顺序关键字的类别中一个兴趣点，在终止结点ｄ结束的Ｓｋｙｌｉｎｅ路径集合＼，使得任??意路径的路程花费ｖｖ（Ａ）和路径的用户指定偏好总花费〇〇／？）两个维度不受任??何其他可行路径兒支配，？?ｇｐ：对于任意／？＇，。??
ａ＞？＞６??时，可得ＰＫ，，?匕，因此，当％＝？时，关键字结点ｖ，被选择。??１８ｋｍ?１４￥?１７ｋｍ?７５５?；?Ｉ８ｋｍ?Ｊ３￥?????▲．?．［１．馨■?．?■０＾２?漏４??????｜．．．．．．．．Ｕｋｎｖｌ７ｉ．．．．．．．．．．｜．．．．．．Ｔ４Ｍ＇＼８￥＼．．．．．??＾?ＨＩ｜?Ｈ???????Ｓ??１６ｋｉｎ?１３￥?１６ｌｄｎ?Ｊ?ＳＳ?＼?Ｔ＾ｎ?１４￥＇?｝??ｒ．?？?ｇ．＾Ａ?ｍ；Ｂ?????图３．２预处理阶段示例图??Ｆｉｇ．?３．２?Ｐｒｅｐｒｏｃｅｓｓｉｎｇ?ｓｔａｇｅ?ｅｘａｍｐｌｅ??基于上述引理，本文不再需要多次迭代选择关键字结点，例如迭代１００次。相反，??本文只需要比较消耗函数％两个极端值，当％＝?１和％＝?０时的优先级分数／和。??如果％?＝?１和％＝?０时均选择了?Ｖ，结点则无需再进行其他迭代，例如：如图３．２所示，??当％＝?１时餐馆类别选择的是＆结点（１３＜１５），当％＞＝０时餐馆类别选择的仍是／＊２结??点（１６＜１７），因此本文不需要洱在丨０，?１］再进行迭代来寻找一个优先级分数更低的结点??了。选择了?Ｘ键字结点即组成了证据路径。??（２）查询处理阶段??预处理阶段是选择山关键字结点，形成了证据路径，但是具有相同证据路径的路径??集合也会具冇不同的路程消耗。为了提高遍历效率，快速形成路Ｎ中真实路径从而得到??查询处理阶段需要查询Ｓｋｙｌｉｎｅ路径集合，木文提出快速选择组成路径的路Ｎ中其它结??点的距离估箅方法：从△？到△／的Ｍ近一次旅行中添加关键字结点的最近邻结点。对于真??实的静态路Ｈ，在每次迭代
【参考文献】：
期刊论文
[1]面向时间依赖路网的空间索引方法[J]. 李佳佳,臧寅旭,刘向宇,夏秀峰,朱睿. 计算机工程. 2019(05)
[2]基于A*算法的最短路径寻优数学方法研究[J]. 张婷娟. 科技通报. 2015(06)
[3]基于分层的改进A算法在路径规划中的应用[J]. 钱红昇,葛文锋,钟鸣,葛铭. 计算机工程与应用. 2014(07)
博士论文
[1]大规模图上的最短路径问题研究[D]. 张钟.中国科学技术大学 2014
本文编号：3268641
【文章来源】：沈阳建筑大学辽宁省
【文章页数】：65 页
【学位级别】：硕士
【部分图文】：
图２．２?９个结点的标准Ｖｏｒｏｎｏｉ图??Ｆｉｇ．?２．２?Ｔｈｅ?ｓｔａｎｄａｒｄ?Ｖｏｒｏｎｏｉ?ｄｉａｇｒａｍ?ｏｆ?９?ｖｅｔｅｃｓ??１１??
式化定义ＭＰＳＲＳ问题；然后介绍问题相关定义并介绍现有算法并给出解决该问题的算??法：最后通过在真实路网上进行实验，证明所提算法有效性和高效性。??３．１问题描述??多偏好顺序路径?Ｓｋｙｌｉｎｅ?查询（Ｍｕｌｔｉ－Ｐｒｅｆｅｒｅｎｃｅ?Ｓｅｑｕｅｎｃｅ?Ｒｏｕｔｅ?Ｓｋｙｌｉｎｅ?ｑｕｅｒｙ），简??称为ＭＰＳＲＳ查询问题［｜２】。给定二维道路网络图Ｇ，起始结点ｓ和终止结点用户的??偏好设罝尸，一组顺序关键字序列义。ＭＰＳＲＳ查询寻找一组从起始结点ｓ出发，途经指??定顺序关键字的类别中一个兴趣点，在终止结点ｄ结束的Ｓｋｙｌｉｎｅ路径集合＼，使得任??意路径的路程花费ｖｖ（Ａ）和路径的用户指定偏好总花费〇〇／？）两个维度不受任??何其他可行路径兒支配，？?ｇｐ：对于任意／？＇，。??
ａ＞？＞６??时，可得ＰＫ，，?匕，因此，当％＝？时，关键字结点ｖ，被选择。??１８ｋｍ?１４￥?１７ｋｍ?７５５?；?Ｉ８ｋｍ?Ｊ３￥?????▲．?．［１．馨■?．?■０＾２?漏４??????｜．．．．．．．．Ｕｋｎｖｌ７ｉ．．．．．．．．．．｜．．．．．．Ｔ４Ｍ＇＼８￥＼．．．．．??＾?ＨＩ｜?Ｈ???????Ｓ??１６ｋｉｎ?１３￥?１６ｌｄｎ?Ｊ?ＳＳ?＼?Ｔ＾ｎ?１４￥＇?｝??ｒ．?？?ｇ．＾Ａ?ｍ；Ｂ?????图３．２预处理阶段示例图??Ｆｉｇ．?３．２?Ｐｒｅｐｒｏｃｅｓｓｉｎｇ?ｓｔａｇｅ?ｅｘａｍｐｌｅ??基于上述引理，本文不再需要多次迭代选择关键字结点，例如迭代１００次。相反，??本文只需要比较消耗函数％两个极端值，当％＝?１和％＝?０时的优先级分数／和。??如果％?＝?１和％＝?０时均选择了?Ｖ，结点则无需再进行其他迭代，例如：如图３．２所示，??当％＝?１时餐馆类别选择的是＆结点（１３＜１５），当％＞＝０时餐馆类别选择的仍是／＊２结??点（１６＜１７），因此本文不需要洱在丨０，?１］再进行迭代来寻找一个优先级分数更低的结点??了。选择了?Ｘ键字结点即组成了证据路径。??（２）查询处理阶段??预处理阶段是选择山关键字结点，形成了证据路径，但是具有相同证据路径的路径??集合也会具冇不同的路程消耗。为了提高遍历效率，快速形成路Ｎ中真实路径从而得到??查询处理阶段需要查询Ｓｋｙｌｉｎｅ路径集合，木文提出快速选择组成路径的路Ｎ中其它结??点的距离估箅方法：从△？到△／的Ｍ近一次旅行中添加关键字结点的最近邻结点。对于真??实的静态路Ｈ，在每次迭代
【参考文献】：
期刊论文
[1]面向时间依赖路网的空间索引方法[J]. 李佳佳,臧寅旭,刘向宇,夏秀峰,朱睿. 计算机工程. 2019(05)
[2]基于A*算法的最短路径寻优数学方法研究[J]. 张婷娟. 科技通报. 2015(06)
[3]基于分层的改进A算法在路径规划中的应用[J]. 钱红昇,葛文锋,钟鸣,葛铭. 计算机工程与应用. 2014(07)
博士论文
[1]大规模图上的最短路径问题研究[D]. 张钟.中国科学技术大学 2014
本文编号：3268641
本文链接：https://www.wllwen.com/kejilunwen/ruanjiangongchenglunwen/3268641.html
