本发明属于道路网络中的最短路径查询中索引构建，具体为一种面向道路网络的高效索引构建方法。
背景技术：
1、近年来，随着移动互联网、物联网等技术的发展，数据获取的规模和速度爆炸式增长，与大数据相关的技术成为了当今世界的热点话题。在大数据分析领域，图作为一种有效描述数据关联性的抽象数据结构，扮演着越来越关键的角色，引起学术界、工业界和政府部门的密切关注。特别是在道路网络领域，图数据的分析与处理受到广泛研究，已成功应用于路径规划、交通分析等多个方面，为解决实际交通问题、提升路径规划效率等方面提供了新的研究方向和方法。
2、最短路径问题在道路网络研究中具有重要意义。一个道路网络可以采用图模型g＝(v,e,φ)来表示。在该图中，每个顶点v∈v表示一个路径交叉口，而每条边e∈e则代表两个交叉口之间的道路，边的权重φ(e)用于表示两个交叉口之间的距离。最短路径问题的核心是研究如何在道路网络g中找到从源顶点到目标顶点距离最短的路径。通过这种图模型的建立，能够有效地描述和分析道路网络中的最短路径情况，为解决实际交通和导航问题提供了基础。
3、最短路径问题在道路网络中被广泛应用，主要应用领域包括路径规划和交通管理与优化。一方面，最短路径问题直接影响路径规划服务的效率和准确性。通过确定两点之间最短或成本最低的路径，可以为驾驶员提供最高效的导航，减少出行时间和成本。另一方面，最短路径问题影响了交通管理部门的管理与优化方案。随着城市交通的不断发展，交通需求不断扩大，道路网络也日益复杂，现代城市的交通管理系统离不开最短路径问题。交通管理部门可以通过对道路网络中各个节点间的最短路径分析，更加精确地调配交通流量，从而减少拥堵，提高道路的使用效率，还能减少环境污染，降低交通事故的发生率和节约能源。
4、为了解决最短路径问题，大量基于索引的算法被提出，这些基于索引的算法预先计算顶点间的路径信息，并按照合理的方式组织顶点，在查询时可以减少计算，提高了算法的效率。在已有的大量基于索引解决最短路径问题的算法中，ch(contraction hierarchy)由于其在预处理时间、空间成本和查询处理时间的方面都具有出色的表现而被广泛使用。但是随着大数据的发展，ch的运行效率已经不能满足现有的数据体量。 近年来，随着拼车服务的普及，注册的司机也在快速增长，数据的新增和更新速度也在显著提高。因此，需要对ch的效率进行提升，以适应更大的数据量。
5、基于道路网络的特性，两个地点之间可能存在着如铁路、高速公路等不同的路径，针对多标签道路网络中的最短路径研究也吸引了很多学者的关注。多标签道路网络可以采用图模型g＝(v,e,φ,l)来表示，其中l(e)表示多标签道路网络中每条边的标签集。在多标签道路网络上查询最短路径问题的核心是研究如何在多标签道路网络g中找到源顶点到目标顶点距离最短的路径，且该路径中边的标签均被限制在标签集a中。在多标签道路网络中的最短路径研究中，chlr(contraction hierarchy with label restrictions)继承了ch的思想，将其转化运用在了多标签网络中，引入索引提升了解决最短路径问题的效率。但与ch类似，随着大数据时代的到来，chlr也无法满足于日益提升的数据量及更新速度，无法高效解决最短路径问题，如何高效地解决多标签道路网络中的最短路径问题已经成为一项重要的工作。
技术实现思路
1、本发明的目的在于提出了一种面向道路网络的高效索引构建方法。
2、实现本发明目的的技术方案为：一种面向道路网络的高效索引构建方法，具体步骤为：
3、构建多标签道路网络模型，所述多标签道路网络模型以路径交叉口为顶点，以两个交叉口之间的道路为边，以两个交叉口之间的距离为边的权重，每条边都带有标签，所述标签用于表示道路属性；
4、对所有顶点按顺序编号，按照边的权重逐个遍历多标签道路网络模型中的边进行索引构建。
5、优选地，按照边的权重逐个遍历多标签道路网络模型中的边进行索引构建的具体方法为：
6、步骤2.1：初始时将结果图设置为空，将多标签道路网络模型中的所有边放入待处理边集，所述结果图索引构建后的道路网络图。
7、步骤2.2：按照边的权重对待处理边集中的边进行排序，排序方法为按照权重从小到大排序；将结果图与待处理边集的并集作为全局图；
8、步骤2.3：当待处理边集不为空时，判断结果图中是否有排序最前的边e＝(u,v)的完全依赖边，如果没有，则进行步骤2.3，否则进行步骤2.6；
9、步骤2.4：将排序最前的边加入到结果图中并从待处理边集中删除；
10、步骤2.5：在结果图中遍历刚加入的边中排序在前的顶点v的邻居，找到排序在后的所有顶点w，排序在后的所有顶点w不包括加入的边上的另一顶点u；根据找到的顶点构成的边与刚加入的边的关系，新增或更新索引；
11、遍历结束，返回步骤2.2；
12、步骤2.6：如果结果图中有排序最前的边的完全依赖边，不对该边进行任何操作，直接删除，选择下一排序的边重新进行步骤2.1。
13、优选地，所述索引的权重为(u,v)构成的边与(v,w)构成的边的权重之和，标签为l(u,v)∪l(v,w)。
14、优选地，根据找到的顶点构成的边与刚加入的边的关系，新增或更新索引的具体方法为：
15、判断全局图中u和w之间有没有标签为l(u,v)∪l(v,w)的边，如果没有，直接在u和w之间插入索引；并将索引放入待处理边集中；
16、若全局图中u和w之间存在标签为l(u,v)∪l(v,w)的边且该边权重大于(u,v)构成的边与(v,w)构成的边的权重之和，更新该边权重为两边之和，放入待处理边集中；若全局图中u和w之间存在标签为l(u,v)∪l(v,w)的边且该边权重不大于(u,v)构成的边与(v,w)构成的边的权重之和，则不进行任何操作。
17、优选地，判断结果图中是否有排序最前的边e＝(u,v)的完全依赖边的具体方法为：
18、查找结果图中顶点u和顶点v之间是否存在边e1，使得边e1的标签集合是边e标签集和的子集，若存在满足条件的边，说明结果图中有排序最前的边e＝(u,v)的完全依赖边，反之则无。
19、本发明与现有技术相比，其显著优点为：本发明改变了现有技术必须依照点顺序进行索引构建的模式，减少了索引构建过程中出现冗余索引的数目，极大加快了索引构建的时间；避免了现有技术在索引构建过程中需要不断进行最短路径查询的情况，极大地提升了索引构建的效率。
1.一种面向道路网络的高效索引构建方法，其特征在于，具体步骤为：
2.根据权利要求1所述的面向道路网络的高效索引构建方法，其特征在于，按照边的权重逐个遍历多标签道路网络模型中的边进行索引构建的具体方法为：
3.根据权利要求2所述的面向道路网络的高效索引构建方法，其特征在于，所述索引的权重为(u,v)构成的边与(v,w)构成的边的权重之和，标签为l(u,v)∪l(v,w)。
4.根据权利要求2所述的面向道路网络的高效索引构建方法，其特征在于，根据找到的顶点构成的边与刚加入的边的关系，新增或更新索引的具体方法为：
5.根据权利要求1所述的面向道路网络的高效索引构建方法，其特征在于，判断结果图中是否有排序最前的边e＝(u,v)的完全依赖边的具体方法为：
