一种面向多属性的动态组旅行规划方法及装置

1.本技术涉及路径规划技术领域，具体涉及一种面向多属性的动态组旅行规划方法及装置。


背景技术：

2.近年来，随着移动通信技术的迅猛发展和智能移动设备的普及，网络数据信息数量迅速增多，其内容也呈现多样化趋势，日常生活中基于位置的服务层出不穷，人们对基于位置的服务也提出了多元化和个性化的需求。
3.移动应用的广泛使用使得互联网数据的位置感知能力变得更加具体。但在地理社交网络应用中，道路网络的复杂性很大程度上限制了用户的位置信息和兴趣点的可达性。两个兴趣点之间的距离并不取决于二者之间的空间位置，而是由他们之间在道路网络中的最短路径决定。不仅如此，在大数据时代，随着许多新的数据类型被引入，空间查询变得愈加复杂，用户的偏好也难以捉摸。例如，美团、饿了么、大众点评等美食软件上的商家信息除了位置信息外，还包含一些譬如口味、环境和服务等评分信息的文本描述信息。如何在道路网络中找到满足用户需求且综合评分数值较高的路径序列，是目前亟需解决的技术问题。
4.因此，为满足路径规划需求，现提供一种面向多属性的动态组旅行规划技术。


技术实现要素：

5.本技术提供一种面向多属性的动态组旅行规划方法及装置，将动态组旅行延伸到真实的道路网路，同时增加兴趣点的多维属性信息，使得动态组旅行规划查询考虑因素更为全面，查询结果更准确可靠。
6.为实现上述目的，本技术提供以下方案。
7.第一方面，本技术提供了一种面向多属性的动态组旅行规划方法，所述方法包括以下步骤：
8.获取路网图以及查询数据；
9.基于所述路网图构建对应的综合索引结构；
10.基于所述查询数据以及各所述兴趣点的文本信息以及有效时间信息，对所述综合索引结构进行剪枝处理，得到第一集合；
11.基于所述查询数据，对所述路网图的搜索空间进行剪枝处理，并与所述第一集合进行交集处理，得到第二集合；
12.基于所述第二集合，获得满足所述查询数据对应的约束条件的兴趣点，记作条件兴趣点；
13.根据所述查询数据的起始位置和目标位置，并基于各所述条件兴趣点，获得多条候选路径；
14.计算多条候选路径的综合排名，并根据综合排名将预设条数的候选路径选定为旅行最佳路径；其中，
15.所述路网图包括多个兴趣点以及对应的路径，各所述兴趣点包括文本信息以及有效时间信息；
16.所述查询数据包括组成员、起始位置、目的位置、查询关键字和时间查询区间。
17.进一步的，所述基于所述路网图构建对应的综合索引结构中，包括以下步骤：
18.对所述路网图进行划分，获得多个子图；
19.计算并存储各所述子图中所述兴趣点的边界的最短路径距离，构建边界距离矩阵；
20.基于各所述兴趣点的文本信息以及有效时间信息，构建对应的关键字反向索引；
21.基于所述子图的名称信息、所述边界距离矩阵、所述关键字反向索引以及对应的所述有效时间信息，构建所述综合索引结构。
22.进一步的，所述基于所述查询数据以及各所述兴趣点的文本信息以及有效时间信息，对所述综合索引结构进行剪枝处理，得到第一集合中包括以下步骤：
23.初始化第一集合和第一队列，所述第一队列用于存放所述综合索引结构的叶子节点，所述第一集合用于存放条件兴趣点；
24.基于所述综合索引结构的根结点，遍历所述根结点的子结点，判断是否满足所述查询数据对应的查询关键字和时间查询区间；
25.若满足则判定是否为非叶结点，若是非叶结点则将对应结点的子结点存储所述第一队列，若不是非叶结点则将对应的结点存入所述第一集合。
26.进一步的，所述基于所述查询数据，对所述路网图的搜索空间进行剪枝处理，并与所述第一集合进行交集处理，得到第二集合中，包括以下步骤：
27.定位查询数据在所述路网图中的区域，并定义一组椭圆区域；
28.初始化第二队列、第二集合、椭圆第一焦点集合以及椭圆第二焦点集合，所述第二队列用于存放一组椭圆区域，所述第二集合用于存放所述条件兴趣点，所述椭圆第一焦点集合用于存放椭圆区域的第一焦点，所述椭圆第二焦点集合用于存放椭圆区域的第二焦点；
29.计算每个椭圆区域的第一焦点，并添加至所述椭圆第一焦点集合；
30.计算每个椭圆区域的第二焦点，并添加至所述椭圆第二焦点集合；
31.基于所述椭圆第一焦点集合和所述椭圆第二焦点集合，计算出每个所述椭圆区域；
32.计算多个所述椭圆区域之间的椭圆交集，将位于所述椭圆交集中的兴趣点添加至所述第二集合中。
33.进一步的，所述基于所述查询数据，对所述路网图的搜索空间进行剪枝处理，并与所述第一集合进行交集处理，得到第二集合中，包括以下步骤：
34.若多个所述椭圆区域之间不存在椭圆交集，则计算获得多个所述椭圆区域之间的质心；
35.识别获得所述质心与其距离最近的所述兴趣点之间的距离，记作第一距离；
36.以所述质心为圆心，以所述第一距离为半径，获得自定义圆形区域；
37.将位于所述自定义圆形区域中的兴趣点添加至所述第二集合中。
38.进一步的，所述方法还包括综合排名函数，所述综合排名函数为：
39.其中，
40.q(v)表示兴趣点v不满足查询约束q；
41.f
t
(q.v)是查询时间与兴趣点v的有效时间重叠率；
42.f
l
(q.v)是路径序列的距离代价；
43.score(q.v)是兴趣点v的综合评分；
44.α、β、γ∈(0，1)且α+β+γ＝1，α、β、γ表示用户的偏好参数，用于调整时间重叠率、距离代价和综合评分在综合排名函数中的权重。
45.进一步的，所述方法还包括综合评分函数，所述综合评分函数为：
46.其中，
47.参数α1、α2表示权重，|u|是小组成员数量，vi.pop是兴趣点vi的流行数值，vi.env是兴趣点vi的环境数值，vi.ser是兴趣点vi的服务数值。
48.进一步的，所述方法还包括有效时间重叠率函数，所述有效时间重叠率函数为：
49.其中，
50.q.t是时间查询区间q的查询时间，v.t是兴趣点v的有效时间，v.st是兴趣点v的有效起始时间；
51.q.et是时间查询区间q的结束时间；
52.tw表示是小组成员可以忍受的等待时间；
53.|q.t∩v.t|≠0表示q.t与v.t之间存在交集；
54.v.st-q.et是v.t与q.et的时间差值。
55.进一步的，所述方法还包括距离代价函数，所述距离代价函数为：
56.其中，
57.dist(si,vc,di)表示用户ui从起点开始，经过兴趣点vc，到达终点的路网距离。
58.第二方面，本技术提供了一种面向多属性的动态组旅行规划装置，所述装置包括：
59.数据获取模块，其用于获取路网图以及查询数据；
60.索引结构构建模块，其用于基于所述路网图构建对应的综合索引结构；
61.第一集合获取模块，其用于基于所述查询数据以及各所述兴趣点的文本信息以及有效时间信息，对所述综合索引结构进行剪枝处理，得到第一集合；
62.第二集合获取模块，其用于基于所述查询数据，对所述路网图的搜索空间进行剪枝处理，并与所述第一集合进行交集处理，得到第二集合；
63.条件兴趣点获取模块，其用于基于所述第二集合，获得满足所述查询数据对应的约束条件的兴趣点，记作条件兴趣点；
64.候选路径获取模块，其用于根据所述查询数据的起始位置和目标位置，并基于各所述条件兴趣点，获得多条候选路径；
65.最佳路径获取模块，其用于计算多条候选路径的综合排名，并根据综合排名将预设条数的候选路径选定为旅行最佳路径；其中，
66.所述路网图包括多个兴趣点以及对应的路径，各所述兴趣点包括文本信息以及有效时间信息；
67.所述查询数据包括组成员、起始位置、目的位置、查询关键字和时间查询区间。
68.进一步的，所述索引结构构建模块还用于对所述路网图进行划分，获得多个子图；
69.所述索引结构构建模块还用于计算并存储各所述子图中所述兴趣点的边界的最短路径距离，构建边界距离矩阵；
70.所述索引结构构建模块还用于基于各所述兴趣点的文本信息以及有效时间信息，构建对应的关键字反向索引；
71.所述索引结构构建模块还用于基于所述子图的名称信息、所述边界距离矩阵、所述关键字反向索引以及对应的所述有效时间信息，构建所述综合索引结构。
72.进一步的，第一集合获取模块还用于初始化第一集合和第一队列，所述第一队列用于存放所述综合索引结构的叶子节点，所述第一集合用于存放条件兴趣点；
73.第一集合获取模块还用于基于所述综合索引结构的根结点，遍历所述根结点的子结点，判断是否满足所述查询数据对应的查询关键字和时间查询区间，若满足则判定是否为非叶结点，若是非叶结点则将对应结点的子结点存储所述第一队列，若不是非叶结点则将对应的结点存入所述第一集合。
74.进一步的，所述第二集合获取模块还用于定位查询数据在所述路网图中的区域，并定义一组椭圆区域；
75.第二集合获取模块还用于初始化第二队列、第二集合、椭圆第一焦点集合以及椭圆第二焦点集合，所述第二队列用于存放一组椭圆区域，所述第二集合用于存放所述条件兴趣点，所述椭圆第一焦点集合用于存放椭圆区域的第一焦点，所述椭圆第二焦点集合用于存放椭圆区域的第二焦点；
76.第二集合获取模块还用于计算每个椭圆区域的第一焦点，并添加至所述椭圆第一焦点集合；
77.第二集合获取模块还用于计算每个椭圆区域的第二焦点，并添加至所述椭圆第二焦点集合；
78.第二集合获取模块还用于基于所述椭圆第一焦点集合和所述椭圆第二焦点集合，计算出每个所述椭圆区域；
79.第二集合获取模块还用于计算多个所述椭圆区域之间的椭圆交集，将位于所述椭圆交集中的兴趣点添加至所述第二集合中。
80.进一步的，第二集合获取模块还用于当多个所述椭圆区域之间不存在椭圆交集
时，则计算获得多个所述椭圆区域之间的质心；
81.第二集合获取模块还用于识别获得所述质心与其距离最近的所述兴趣点之间的距离，记作第一距离；
82.第二集合获取模块还用于以所述质心为圆心，以所述第一距离为半径，获得自定义圆形区域；
83.第二集合获取模块还用于将位于所述自定义圆形区域中的兴趣点添加至所述第二集合中。
84.进一步的，所述装置还包括综合排名函数，所述综合排名函数为：
85.其中，
86.q(v)表示兴趣点v不满足查询约束q；
87.f
t
(q.v)是查询时间与兴趣点v的有效时间重叠率；
88.f
l
(q.v)是路径序列的距离代价；
89.score(q.v)是兴趣点v的综合评分；
90.α、β、γ∈(0，1)且α+β+γ＝1，α、β、γ表示用户的偏好参数，用于调整时间重叠率、距离代价和综合评分在综合排名函数中的权重。
91.进一步的，所述装置还包括综合评分函数，所述综合评分函数为：
92.其中，
93.参数α1、α2表示权重，|u|是小组成员数量，vi.pop是兴趣点vi的流行数值，vi.env是兴趣点vi的环境数值，vi.ser是兴趣点vi的服务数值。
94.进一步的，所述装置还包括有效时间重叠率函数，所述有效时间重叠率函数为：
95.其中，
96.q.t是时间查询区间q的查询时间，v.t是兴趣点v的有效时间，v.st是兴趣点v的有效起始时间；
97.q.et是时间查询区间q的结束时间；
98.tw表示是小组成员可以忍受的等待时间；
99.|q.t∩v.t|≠0表示q.t与v.t之间存在交集；
100.v.st-q.et是v.t与q.et的时间差值。
101.进一步的，所述装置还包括距离代价函数，所述距离代价函数为：
102.其中，
103.dist(si,vc,di)表示用户ui从起点开始，经过兴趣点vc，到达终点的路网距离。
104.本技术提供的技术方案带来的有益效果包括：
105.本技术将动态组旅行延伸到真实的道路网路，同时增加兴趣点的多维属性信息，使得动态组旅行规划查询考虑因素更为全面，查询结果更准确可靠；
106.另外，本技术的技术方案考虑到小组成员偏好及路径距离代价，提出了综合评分函数，鉴于道路网络距离与欧式距离不同，构建综合索引结构来处理道路网络信息，进一步保障查询结果的可靠性和准确性。
附图说明
107.术语解释：
108.mdgtp：multi-attribute dynamic group travel planning，动态组旅行规划；
109.gta：group time algorithm，群时间算法；
110.oea：optimize the ellipse algorithm，椭球算法；
111.kpl：top-k path land；
112.s-gts：straightforward group trip scheduling，直接分组出行计划。
113.为了更清楚地说明本技术实施例中的技术方案，下面将对实施例描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本技术的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。
114.图1为本技术实施例中提供的面向多属性的动态组旅行规划方法的步骤流程图；
115.图2为本技术实施例中提供的面向多属性的动态组旅行规划方法中的路网图示意图；
116.图3为本技术实施例中提供的面向多属性的动态组旅行规划方法中路网图的划分示意图；
117.图4为本技术实施例中提供的面向多属性的动态组旅行规划方法中综合索引tig-tree的示意图；
118.图5为本技术实施例中提供的面向多属性的动态组旅行规划方法中主轴tmax的示意图；
119.图6为本技术实施例中提供的面向多属性的动态组旅行规划方法中椭圆交集区域的示意图；
120.图7为本技术实施例中提供的面向多属性的动态组旅行规划方法中圆形区域的示意图；
121.图8为本技术实施例中提供的面向多属性的动态组旅行规划方法中圆形区域扩展的示意图；
122.图9为本技术实施例中提供的面向多属性的动态组旅行规划方法中组大小n的影
响示意图；
123.图10为本技术实施例中提供的面向多属性的动态组旅行规划方法中查询关键字m的影响示意图；
124.图11为本技术实施例中提供的面向多属性的动态组旅行规划方法中k值的影响示意图；
125.图12为本技术实施例中提供的面向多属性的动态组旅行规划方法中参数α的影响示意图；
126.图13为本技术实施例中提供的面向多属性的动态组旅行规划方法中参数β的影响示意图；
127.图14为本技术实施例中提供的面向多属性的动态组旅行规划方法中参数γ的影响示意图；
128.图15为本技术实施例中提供的面向多属性的动态组旅行规划装置的结构框图。
具体实施方式
129.为使本技术实施例的目的、技术方案和优点更加清楚，下面将结合本技术实施例中的附图，对本技术实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例是本技术的一部分实施例，而不是全部的实施例。基于本技术中的实施例，本领域普通技术人员在没有做出创造性劳动的前提下所获得的所有其他实施例，都属于本技术保护的范围。
130.以下结合附图对本技术的实施例作进一步详细说明。
131.本技术实施例提供一种面向多属性的动态组旅行规划方法及装置，将动态组旅行延伸到真实的道路网路，同时增加兴趣点的多维属性信息，使得动态组旅行规划查询考虑因素更为全面，查询结果更准确可靠。
132.为达到上述技术效果，本技术的总体思路如下：
133.一种面向多属性的动态组旅行规划方法，该方法包括以下步骤：
134.s1、获取路网图以及查询数据；
135.s2、基于路网图构建对应的综合索引结构；
136.s3、基于查询数据以及各兴趣点的文本信息以及有效时间信息，对综合索引结构进行剪枝处理，得到第一集合；
137.s4、基于查询数据，对路网图的搜索空间进行剪枝处理，并与第一集合进行交集处理，得到第二集合；
138.s5、基于第二集合，获得满足查询数据对应的约束条件的兴趣点，记作条件兴趣点；
139.s6、根据查询数据的起始位置和目标位置，并基于各条件兴趣点，获得多条候选路径；
140.s7、计算多条候选路径的综合排名，并根据综合排名将预设条数的候选路径选定为旅行最佳路径；其中，
141.路网图包括多个兴趣点以及对应的路径，各兴趣点包括文本信息以及有效时间信息；
142.查询数据包括组成员、起始位置、目的位置、查询关键字和时间查询区间。
143.以下结合附图对本技术的实施例作进一步详细说明。
144.参见图1所示，本技术实施例提供一种面向多属性的动态组旅行规划方法，该方法包括以下步骤：
145.s1、获取路网图以及查询数据；
146.s2、基于路网图构建对应的综合索引结构；
147.s3、基于查询数据以及各兴趣点的文本信息以及有效时间信息，对综合索引结构进行剪枝处理，得到第一集合；
148.s4、基于查询数据，对路网图的搜索空间进行剪枝处理，并与第一集合进行交集处理，得到第二集合；
149.s5、基于第二集合，获得满足查询数据对应的约束条件的兴趣点，记作条件兴趣点；
150.s6、根据查询数据的起始位置和目标位置，并基于各条件兴趣点，获得多条候选路径；
151.s7、计算多条候选路径的综合排名，并根据综合排名将预设条数的候选路径选定为旅行最佳路径；其中，
152.路网图包括多个兴趣点以及对应的路径，各兴趣点包括文本信息以及有效时间信息；
153.查询数据包括组成员、起始位置、目的位置、查询关键字和时间查询区间。
154.需要说明的是，步骤s7，根据综合排名将预设条数的候选路径选定为旅行最佳路径，假设条数为k条，
155.则是基于综合排名，由高到低，返回k条候选路径，即选定k条候选路径选定为旅行最佳路径。
156.由于查询用户与兴趣点之间的实际距离受到道路网络连通性的限制，本技术实施例增加兴趣点的多维属性信息，例如流行属性、服务属性和环境属性等，提出面向多属性的动态组旅行规划查询mdgtp(multi-attribute dynamic group travel planning)。该查询考虑路径距离代价及小组成员偏好，并在此基础上提出了一个综合评分函数。构建一种新的层次索引结构tig-tree，将空间-文本对象有效地组织起来并快速找到满足查询条件的对象信息。其中，距离矩阵记录数据对象的位置信息，tig-tree每个结点设置了一个n位的二进制数来表示该结点所包含的关键字，以便快速判断该结点是否包含用户所需关键字。同时，基于tig-tree设计gta(group time algorithm)算法对不满足查询条件的空间-文本对象进行剪枝。沿用椭圆性质来缩减搜索区域，考虑到实际路网距离必然大于欧式距离，先初始化椭圆主轴tmax，继而利用椭圆的几何性质提出搜索区域剪枝方法oea(optimize the ellipse algorithm)。设计新的kpl(top-k path land)算法来获得k个满足小组成员需求且综合评分最高的路径序列。实验结果表明，本技术实施例的技术方案能够有效地解决多属性动态组旅行规划问题，对于小组出行具有广泛的应用价值。
157.本技术实施例中，将动态组旅行延伸到真实的道路网路，同时增加兴趣点的多维属性信息，使得动态组旅行规划查询考虑因素更为全面，查询结果更准确可靠；
158.并且，本技术实施例的技术方案考虑到小组成员偏好及路径距离代价，提出了综合评分函数，鉴于道路网络距离与欧式距离不同，构建综合索引结构来处理道路网络信息，
进一步保障查询结果的可靠性和准确性。
159.需要说明的是，本技术实施例运用到路网图，因此，如表1所示，对路网下涉及的一些符号及其定义进行解释说明：
160.表1
[0161][0162]
其中，本技术实施例中提及的兴趣点则是路网图中的顶点。
[0163]
本技术实施例中的路网图，是将道路网络建模为无向加权图g＝(v，e)，其中v是一组顶点集合，e是一组边集合；e中的每条边(u，v)连接两个相邻顶点u、v(u、v∈v)，并与表示距离或旅行时间的非负权重w(u，v)》0相关联；路径pl(v1，vn)＝{v1，v2，
…
，vn}(n≥1)是一个有序的顶点集合，给定顶点u和顶点v之间的路径，用路径距离dist(u，v)表示沿路径的边的权重之和；说明书附图中的图2显示了道路网络的示意图，给定起始点v4和目标v9，pl(v4，v9)＝{v4，v3，v2，v6，v7，v8，v9}，路径距离dist(v4，v9)＝15。
[0164]
本技术实施例中，假定兴趣点位于路网顶点之上，用顶点表示；道路网中有一组顶点v∈v，具有多重属性的空间关键字对象v＝{id，w，t，r}，其中v.id是顶点v的唯一标识，v.w＝{w1，w2，w3……
}是顶点v的关键字集合，v.t表示顶点v的有效时间，v.r表示该兴趣点其他属性信息，v.r中每条数值属性数据表示为v.r＝{pop，env，ser}；如下方表2所示，其为路网中顶点信息。
[0165]
表2
[0166][0167]
本技术实施例在执行动态组旅行规划时，具体情况如下：
[0168]
已知顶点集v和一个面向多属性的动态组旅行规划(mdgtp)查询q＝(u，s，d，p，t，k)；其中，u＝{u1，u2，
…
，un}是小组成员集合，s＝{s1，s2，
…
，sn}表示每个成员ui的起点集，d＝{d1，d2，
…
，dn}表示每个成员ui的终点集，q.p是一组关键字集合，表示成员查询目的，q.t是成员指定的任意查询时间区间如(9，12)；
[0169]
查询q返回k条各个成员从s出发、到d结束且符合q.p和q.t约束条件，综合排名函数crf(q.v)排名最高的最佳路径序列。
[0170]
本技术实施例将动态组旅行延伸到真实的道路网路，同时增加兴趣点的多维属性信息，如流行属性、环境属性和服务属性，提出面向多属性的动态组旅行规划(mdgtp)查询；
[0171]
并且，考虑到小组成员偏好及路径距离代价，提出了综合评分函数，鉴于道路网络距离与欧式距离不同，构建了综合索引tig-tree来处理道路网络信息；
[0172]
其中，距离矩阵记录数据对象的位置信息，使用倒排文件对顶点文本信息进行索引，并为tig-tree每个结点分配一个n位的二进制数，用以表示该结点所包含的关键字；同时，基于tig-tree设计相关剪枝算法gta修剪不符合时间、文本约束条件的顶点；再者，椭圆搜索区域剪枝策略进行改进，初始化主轴tmax，提出oea算法来缩减搜索空间，使其适用于道路网络。此外，基于tig-tree索引算法gta和椭圆剪枝算法oea，提出一种查询处理算法kpl返回k条排名最高的路径序列；通过在真实路网合成的数据集ca和ny对kpl算法与s-gts算法进行对比，验证了申请实施例提出的查询算法kpl在处理返回路径序列是高效可行的。
[0173]
进一步的，所述基于所述路网图构建对应的综合索引结构中，包括以下步骤：
[0174]
对所述路网图进行划分，获得多个子图；
[0175]
计算并存储各所述子图中所述兴趣点的边界的最短路径距离，构建边界距离矩阵；
[0176]
基于各所述兴趣点的文本信息以及有效时间信息，构建对应的关键字反向索引；
[0177]
基于所述子图的名称信息、所述边界距离矩阵、所述关键字反向索引以及对应的所述有效时间信息，构建所述综合索引结构。
[0178]
进一步的，所述基于所述查询数据以及各所述兴趣点的文本信息以及有效时间信息，对所述综合索引结构进行剪枝处理，得到第一集合中包括以下步骤：
[0179]
初始化第一集合和第一队列，所述第一队列用于存放所述综合索引结构的叶子节点，所述第一集合用于存放条件兴趣点；
[0180]
基于所述综合索引结构的根结点，遍历所述根结点的子结点，判断是否满足所述查询数据对应的查询关键字和时间查询区间；
[0181]
若满足则判定是否为非叶结点，若是非叶结点则将对应结点的子结点存储所述第一队列，若不是非叶结点则将对应的结点存入所述第一集合。
[0182]
进一步的，所述基于所述查询数据，对所述路网图的搜索空间进行剪枝处理，并与所述第一集合进行交集处理，得到第二集合中，包括以下步骤：
[0183]
定位查询数据在所述路网图中的区域，并定义一组椭圆区域；
[0184]
初始化第二队列、第二集合、椭圆第一焦点集合以及椭圆第二焦点集合，所述第二队列用于存放一组椭圆区域，所述第二集合用于存放所述条件兴趣点，所述椭圆第一焦点集合用于存放椭圆区域的第一焦点，所述椭圆第二焦点集合用于存放椭圆区域的第二焦点；
[0185]
计算每个椭圆区域的第一焦点，并添加至所述椭圆第一焦点集合；
[0186]
计算每个椭圆区域的第二焦点，并添加至所述椭圆第二焦点集合；
[0187]
基于所述椭圆第一焦点集合和所述椭圆第二焦点集合，计算出每个所述椭圆区域；
[0188]
计算多个所述椭圆区域之间的椭圆交集，将位于所述椭圆交集中的兴趣点添加至所述第二集合中。
[0189]
进一步的，所述基于所述查询数据，对所述路网图的搜索空间进行剪枝处理，并与所述第一集合进行交集处理，得到第二集合中，包括以下步骤：
[0190]
若多个所述椭圆区域之间不存在椭圆交集，则计算获得多个所述椭圆区域之间的质心；
[0191]
识别获得所述质心与其距离最近的所述兴趣点之间的距离，记作第一距离；
[0192]
以所述质心为圆心，以所述第一距离为半径，获得自定义圆形区域；
[0193]
将位于所述自定义圆形区域中的兴趣点添加至所述第二集合中。
[0194]
进一步的，所述方法还包括综合排名函数，所述综合排名函数为：
[0195]
其中，
[0196]
q(v)表示兴趣点v不满足查询约束q；f
t
(q.v)是查询时间与兴趣点v的有效时间重叠率；f
l
(q.v)是路径序列的距离代价；score(q.v)是兴趣点v的综合评分；α、β、γ∈(0，1)且α+β+γ＝1，α、β、γ表示用户的偏好参数，用于调整时间重叠率、距离代价和综合评分在综合排名函数中的权重。
[0197]
其中，若α＝0，则查询不考虑查询和对象之间的文本相关性；
[0198]
α》0时，文本相关性的重要性增加；
[0199]
为了便于解释说明，本技术实施例中忽略了参数α、β、γ，但当参数变化时，所提出的算法仍然适用。
[0200]
进一步的，所述方法还包括综合评分函数，所述综合评分函数为：
[0201]
其中，
[0202]
参数α1、α2表示权重，|u|是小组成员数量，vi.pop是兴趣点vi的流行数值，vi.env是兴趣点vi的环境数值，vi.ser是兴趣点vi的服务数值。
[0203]
进一步的，所述方法还包括有效时间重叠率函数，时间重叠率是根据查询时间与道路网路中数据对象有效时间的交集计算出来，所述有效时间重叠率函数为：
[0204]
其中，
[0205]
q.t是时间查询区间q的查询时间，v.t是兴趣点v的有效时间，v.st是兴趣点v的有效起始时间；q.et是时间查询区间q的结束时间；tw表示是小组成员可以忍受的等待时间；|q.t∩v.t|≠0表示q.t与v.t之间存在交集；v.st-q.et是v.t与q.et的时间差值。
[0206]
进一步的，所述方法还包括距离代价函数，所述距离代价函数为：
[0207]
其中，
[0208]
dist(si,vc,di)表示用户ui从起点开始，经过兴趣点vc，到达终点的路网距离。
[0209]
需要说明的是，本技术实施例在进行规划时，还存在针对搜索区域边界的计算，搜索区域边界的计算需要使用椭圆焦点公式，该公式如下：
[0210]
第一焦点：
[0211]
第二焦点：其中，
[0212]
si表示成员ui的起点位置，di表示成员ui的终点位置，mer是小组成员的数量。
[0213]
另外，初始化椭圆主轴公式：
[0214]
tmax＝dist(si,v1)+dist(v1,v2)+kk+dist(v
n-1
,vn)+dist(vn,di)
ꢀꢀ
(7)；
[0215]
其中，dist(si,v1)是成员ui从起点到第一个顶点的路网距离；dist(v
n-1
,vn)是成员ui在第n-1个顶点到第n个顶点的路网距离；dist(vn,di)成员ui从最后一个顶点到终点的路网距离。
[0216]
再者，椭圆面积范围计算公式为：
[0217]
f(gc,vc)＜tar＜f(gc,tmax) (8)
[0218]
f(gc,vc)是以gc为圆心，半径为dist(gc,vc)的椭圆面积，f(gc,tmax)是以gc为圆心，半径为dist(gc,tmax)的椭圆面积。
[0219]
本技术实施例中的步骤s2和步骤s3具体用于剪枝处理和建立索引，具体情况如下：
[0220]
第一阶段，索引结构tig-tree及相关剪枝算法gta；
[0221]
本技术实施例中由于加快计算两个顶点之间的最短路径距离的速度，以提高mdtgp查询处理的性能；
[0222]
道路网络上最有效的索引技术之一是g-tree，它是一种基于组件的索引结构，能够支持道路网络上基于位置的查询；
[0223]
ir-tree被用于欧氏空间中的空间关键字查询。
[0224]
为此，基于两种索引结构思想，本技术实施例中创建了一种新的索引结构tig-tree用以满足最佳路径查询的需求。
[0225]
图划分是g-tree构造中的一个重要步骤；
[0226]
最佳的方法不仅应该生成大小大致相等的子图，而且应该最小化边界的数量。在本技术实施例中，采用了一种著名的启发式算法，称为多级划分算法；它首先通过粗化顶点和边来缩减图的大小，然后使用传统的图分割算法(例如kernighan-lin算法)在粗化的图上进行分割；最后，它分解子图以生成原始图的分区。
[0227]
遵循g-tree所使用的图形分区技术，图3显示了图2中给出示例路网的图形划分，使用多级划分算法将图划分为大小相等的子图，整个路网被划分为两个子图，分别用g1和g2表示；然后，g1继续被划分为g3和g4两个子图，类似的g2被划分为g5和g6两个子图，直到每个子图的顶点个数小于预设值(一般大于等于2)时停止划分；将两个子图连接起来的顶点称为边界点；图g1由子图g3和g4组成，顶点v1、v6和v
10
构成了g1的边界点；g1和g2共同组合成了g0，g0的边界点由v1、v2、v6、v
10
和v
12
组成。划分之后，标记每个子图的边界，边界是一个子图中将道路网络连接到另一个分区的顶点，基于这些边界，创建距离矩阵；因此，预先计算每个节点中每个边界的最短路径距离，并将其存储在矩阵中。
[0228]
图2的路网示例中一些顶点包含一个或多个关键字，需要对这些关键字进行索引，因此，第一步是对图表中的所有关键字进行排序。然后，对于每个关键字，根据其在每个结点中的存在情况分配一个二进制值。例如，子结点v1同时包含关键字书店和西餐厅，因此v1的反向列表为100001。对于子结点v2，它包含关键字博物馆，因此其反向列表为010000。图4中所有顶点的反向索引如表3示。基于上面的反向索引列表，将每个反向索引附加到叶结点处的相应顶点。对于每个父结点，使用其子结点的逻辑或来计算其反向索引。例如，g3的反向索引是v1、v6、v7的反向索引的逻辑或的结果。100001或101000或001000的结果为101001，因此g3的反转指数为101001；
[0229]
对每个非叶结点应用相同的计算，根节点通常具有索引的所有1。
[0230]
表3关键字反向索引
[0231][0232]
每个顶点所包含的关键字均包含有效时间信息，每个顶点的有效时间均保存在tig-tree的叶子结点中，非叶子结点的有效时间，使用其子结点的逻辑“或”计算。
[0233]
例如，对于非叶子结点g3来说，其子节点v1、v6和v7对应的有效时间分别为(9，13)，(11，17)，(12，21)，通过逻辑“或”运算，得到g3的有效时间为(9，21)。
[0234]
tig-tree整体结构如图4所示：对于tig-tree中的每个非叶结点，包含子图名称、每个子图的边界距离矩阵、关键字反转索引和有效时间(使用其子节点的逻辑或)；
[0235]
对于每个叶结点，它包含路网的顶点、相应顶点的反向列表以及每个顶点的关键字信息及有效时间。
[0236]
另外，算法gta具体流程如下：
[0237]
首先，初始化一个指针gnode、一个集合vk和一个队列gq
init
，其中gq
init
用来存放候选结点，vk用于保存符合约束条件的所有兴趣点集合(第1行)，将关键字q.p转化为二进制，并将git-tree的根结点g0放入队列gq
init
(第2-3行)，当队列gq
init
不为空时，从根结点自上而下地进行处理，遍历根结点的子结点；
[0238]
然后，gnode指向队列gq
init
的头元素，判断gnode是否满足查询关键字和时间约束，若满足，继续判断gnode是否为非叶结点，若是，则将该结点的子结点存入队列gq
init
，否则将该结点存入集合vk。遍历完成后，返回集合vk(第4-11行)。
[0239]
算法gta具体执行情况如下：
[0240][0241]
第二阶段，执行搜索空间的剪枝算法oea：
[0242]
本技术实施例提出了一种新的搜索区域细化技术，该技术的关键思想是基于椭圆定理；较小的搜索区域减少了从数据库检索的顶点的数量，避免了不必要的行程计算，并显著减少了i/o访问和计算开销。
[0243]
已知一个mdgtp查询q＝(u，s，d，p，t，k)以及一个搜索空间，为了计算搜索区域的边界，需计算一组椭圆区域集。椭圆长轴是以第一轮加入的成员取质心cs1，搜寻最近邻且满足第一轮成员要求的顶点v，然后第二轮成员加入时，取顶点v与加入成员的质心为cs2，继续搜寻满足当前成员要求的最近邻顶点v，依次类推，最后得到所有满足条件的顶点集。根据公式(7)求出每个用户的行程距离，取最大的单人距离tmax为椭圆长轴距离，使用tmax作为初始化的椭圆长轴；其次根据第三章椭圆焦点公式分别计算初始成员的起点和终点的质心，即椭圆焦点，主轴为tmax，形成elar1椭圆；然后继续计算在某个顶点新加入成员的起点和终点的质心，形成elari椭圆；最后得到n个椭圆区域，此时若椭圆区域elar1∩elar2∩...∩elarn不为空，则搜索空间区域为所有椭圆的交集区域，若椭圆区域elar1∩elar2∩...∩elarn为空，计算以elar1，elar2...elarn的几何质心tecs1，检索最近的顶点，以g为圆心，半径r＝dist(g，vi)，检索圆内面积是否有满足用户需求的顶点，此时搜索区域取值范围根据公式(8)依次检索，直到圆形区域包含n个椭圆区域的顶点集。
[0244]
以图5为例，有5位小组成员u＝{u1，u2，u3，u4，u5}，小组成员的起点位置集合为s＝{s1，s2，s3，s4，s5}，终点位置集合为d＝{d1，d2，d3，d4，d5}。u1和u3是首发成员，取质心为tecs1，搜寻满足u1和u3条件的第一个最近顶点v3，第二轮u4和u5是第二轮加入的成员，取v3、u4、u5的质心为tecs2，搜索满足当前成员条件的最近邻点v5，u2是最后一轮加入的成员，取v5和u2的质心tecs3，搜寻满足当前成员条件的最近邻点v4。此时找到符合所有用户需求的顶点集为p＝{v3，v4，v5}，根据公式(7)求出tmax。
[0245]
其次根据第三章焦点公式分别计算出椭圆区域elar1，elar2，elar3，若椭圆区域elar1∩elar2∩elar3不为空，如图6所示，此时的搜索区域为三个椭圆的交集；若椭圆区域elar1∩elar2∩elar3为空，如图7所示，计算椭圆区域elar1，elar2，elar3的几何质心为g，检索最近的顶点v4，以g为圆心，半径等于dist(g，v4)，检索该区域是否有满足用户需求的顶点
集，若没有，则继续检索最近的顶点，扩展区域，直到圆形区域覆盖三个椭圆区域终止，如图8所示。
[0246]
oea算法是利用椭圆性质的剪枝算法，具体流程如下：
[0247]
两个队列casp，cadp以及5个集合fscv、fdcv、cvod、vwant、res初始化为空，将集合vpn初始为v。其中，casp和cadp分别用于存放小组成员起点和终点，vpn用来存放椭圆交集内的兴趣点，fscv和fdcv分别存放根据第三章椭圆焦点公式计算的小组成员起点和终点的几何质心，即椭圆焦点(第1行)。将每轮加入行程的成员起点和终点存入casp，cadp(第2行)。当两个队列不为空时，根据焦点公式(5)和(6)计算每一轮次的几何质点，分别存放在fscv和fdcv中，主轴长度为tmax，然后使用ellipticformfind函数形成椭圆区域，如果椭圆区域交集不为空(第8行)，则将该区域内的兴趣点与vwant的交集存入cvod并返回(第9-10行)，如果椭圆区域交集为空，则对vwant中的所有点求其到圆心g点的距离i.d(第12-13行)，并由小到大排序(第14行)，遍历排序后的vwant，以tmax为半径，筛选出圆内所有点，并存储到cvod中返回(第15-18行)。
[0248]
算法oea具体执行情况如下：
[0249][0250][0251]
第三阶段，路网上的动态组旅行规划算法kpl：
[0252]
使用算法gta对关键字进行剪枝，然后调用算法gta，在算法oea里调用算法gta，返回既在细化搜索区域内又满足小组成员约束条件的顶点集，按照关键字排序，得到所有候选路径，根据综合排名函数，返回k条满足用户需求，且综合排名最高的路径序列。
[0253]
kpl算法具体流程如下：初始化一个队列mdct和四个集合pmd，mdclt
cand
、lt及ans，将valuemax初始化为∞，其中，pmd用来存放算法oea剪枝后的顶点，mdct用来存放根据关键字排列后的候选路径，mdclt
cand
用来保存队列mdct出队元素，ans存放筛选后的最优路径(第1行)。调用oea算法，将返回的集合交集存放在pmd，并将pmd中的兴趣点按照关键字排列的候选路径存入mdct(第2-3行)。当mdct不为空时，遍历每条候选路径，根据公式(4)得到每条候选路径的综合排名数值，使用二维数组存储路径序列及数值，valuemax存储最大的crf(第7-8行)。使用二维数组倒序从valuemax脚标取出该crf值的所有路径，直到取满k条路径序列(第9-18行)。
[0254]
算法kpl具体执行情况如下：
[0255][0256][0257]
算法kpl的复杂度分析：
[0258]
在路网上，假设有m个关键字，查询关键字数量为|q.p|，每个顶点分配s个关键字，算法gta为了得到包含有效时间的关键字，需要对不满足条件的顶点剪枝，此时获得满足条件的概率pg是
[0259]
算法oea考虑不同地点的用户，缩减路网区域，若椭圆区域有交集，此时的概率p1为若椭圆无交集，此时最好的概率p2是最坏的概率p3是
算法kpl使用二维数组存储路径序列及数值，若不采用剪枝策略，执行次数为|v|，则算法kpl的时间复杂度为o(|v|)，若采用剪枝策略，细化搜索空间的椭圆有交集时，算法的时间复杂度为o细化搜索空间的椭圆无交集时，此时算法的时间复杂度为最坏的时间复杂度为
[0260]
综上所述，算法kpl采用关键字及空间搜索剪枝策略，遍历了每个满足剪枝需求的顶点n，使得参与计算的顶点远远小于|v|，因此时间复杂度为o(n)。
[0261]
基于本技术实施例的技术方案，给出一种实际操作案例，具体如下：
[0262]
实验使用两个真实路网数据与实验系统随机产生的数据对象合成的ca数据集和ny数据集(如表3所示)来评估提出的kpl算法；ca路网有21048个结点和21693条边，ny有213756个结点和186489条边；两个数据集均使用zipfian分布为每个对象分配2-3个关键字；进而展示kpl算法的性能与s-gts算法进行比较分析。
[0263]
表3实验数据集
[0264][0265][0266]
根据表4中列出的各种参数评估kpl算法的性能；对6个参数进行设置：成员数量n、查询关键字个数m、结果数k、参数α、β、γ。
[0267]
表4参数设置
[0268][0269]
基于本技术实施例的技术方案，实验结果如下：
[0270]
第一，组大小n的影响：说明书附图的图9展示了两种算法的查询处理时间均随组
大小n的增加而增加，这是因为两个数据集的路网距离计算次数随着n的增加而增加；
[0271]
但kpl算法要优于s-gts算法，这是因为s-gts算法是独立计算每个小组成员的行程，从而在数据库中多次访问相同的顶点。另一方面，我们使用基于椭圆的剪枝策略逐步细化搜索区域。
[0272]
第二，查询关键字m的影响：如图10所示，两种算法的查询时间随着查询关键字数量的增加呈线性增长；其原因是，随着查询关键字个数的增加，需要探索更大的搜索空间，需要查询处理的对象数量也随之增多，但kpl算法始终优于s-gts算法，这是因为tig-tree索引结构能够快速找到对应的对象信息，提升了查询效率。
[0273]
第三，返回结果k值的影响：如图11所示，两种算法在两个数据集上的查询时间，实验结果表明，随着k值的增长，两种算法的查询性能都比较稳定；总体而言，kpl算法的查询处理速度比s-gts算法要快一些，这是因为kpl算法同时利用时间和文本信息来修剪不必要的对象，并削减搜索空间的范围。
[0274]
第四，α的影响：参数α表示时间重叠率在查询中具有的权重大小。如图12所示，图12显示了参数α对查询时间的影响。随着α值的变化，kpl算法和s-gts算法的查询时间几乎保持稳定，并且kpl算法始终优于s-gts算法。此外，对于这两种算法，α值的变化并不会影响经过剪枝之后得到的候选对象数量。
[0275]
第五，β的影响：β表示路径序列的距离代价具有的权重。如图13所示，β值的变化对kpl算法和s-gts算法的查询时间几乎没有太大影响，并且kpl算法性能更优。
[0276]
第六，γ的影响：γ表示路径序列的综合评分具有的权重。图14显示了两种算法在两个数据集上的查询性能比较稳定，不会随着γ的增大而增加，但kpl算法要优于s-gts算法。
[0277]
参见图15所示，基于与方法实施例相同的发明构思，本技术实施例提供一种面向多属性的动态组旅行规划装置，该装置包括：
[0278]
数据获取模块，其用于获取路网图以及查询数据；
[0279]
索引结构构建模块，其用于基于所述路网图构建对应的综合索引结构；
[0280]
第一集合获取模块，其用于基于所述查询数据以及各所述兴趣点的文本信息以及有效时间信息，对所述综合索引结构进行剪枝处理，得到第一集合；
[0281]
第二集合获取模块，其用于基于所述查询数据，对所述路网图的搜索空间进行剪枝处理，并与所述第一集合进行交集处理，得到第二集合；
[0282]
条件兴趣点获取模块，其用于基于所述第二集合，获得满足所述查询数据对应的约束条件的兴趣点，记作条件兴趣点；
[0283]
候选路径获取模块，其用于根据所述查询数据的起始位置和目标位置，并基于各所述条件兴趣点，获得多条候选路径；
[0284]
最佳路径获取模块，其用于计算多条候选路径的综合排名，并根据综合排名将预设条数的候选路径选定为旅行最佳路径；其中，
[0285]
所述路网图包括多个兴趣点以及对应的路径，各所述兴趣点包括文本信息以及有效时间信息；
[0286]
所述查询数据包括组成员、起始位置、目的位置、查询关键字和时间查询区间。
[0287]
进一步的，所述索引结构构建模块还用于对所述路网图进行划分，获得多个子图；
[0288]
所述索引结构构建模块还用于计算并存储各所述子图中所述兴趣点的边界的最短路径距离，构建边界距离矩阵；
[0289]
所述索引结构构建模块还用于基于各所述兴趣点的文本信息以及有效时间信息，构建对应的关键字反向索引；
[0290]
所述索引结构构建模块还用于基于所述子图的名称信息、所述边界距离矩阵、所述关键字反向索引以及对应的所述有效时间信息，构建所述综合索引结构。
[0291]
进一步的，第一集合获取模块还用于初始化第一集合和第一队列，所述第一队列用于存放所述综合索引结构的叶子节点，所述第一集合用于存放条件兴趣点；
[0292]
第一集合获取模块还用于基于所述综合索引结构的根结点，遍历所述根结点的子结点，判断是否满足所述查询数据对应的查询关键字和时间查询区间，若满足则判定是否为非叶结点，若是非叶结点则将对应结点的子结点存储所述第一队列，若不是非叶结点则将对应的结点存入所述第一集合。
[0293]
进一步的，所述第二集合获取模块还用于定位查询数据在所述路网图中的区域，并定义一组椭圆区域；
[0294]
第二集合获取模块还用于初始化第二队列、第二集合、椭圆第一焦点集合以及椭圆第二焦点集合，所述第二队列用于存放一组椭圆区域，所述第二集合用于存放所述条件兴趣点，所述椭圆第一焦点集合用于存放椭圆区域的第一焦点，所述椭圆第二焦点集合用于存放椭圆区域的第二焦点；
[0295]
第二集合获取模块还用于计算每个椭圆区域的第一焦点，并添加至所述椭圆第一焦点集合；
[0296]
第二集合获取模块还用于计算每个椭圆区域的第二焦点，并添加至所述椭圆第二焦点集合；
[0297]
第二集合获取模块还用于基于所述椭圆第一焦点集合和所述椭圆第二焦点集合，计算出每个所述椭圆区域；
[0298]
第二集合获取模块还用于计算多个所述椭圆区域之间的椭圆交集，将位于所述椭圆交集中的兴趣点添加至所述第二集合中。
[0299]
进一步的，第二集合获取模块还用于当多个所述椭圆区域之间不存在椭圆交集时，则计算获得多个所述椭圆区域之间的质心；
[0300]
第二集合获取模块还用于识别获得所述质心与其距离最近的所述兴趣点之间的距离，记作第一距离；
[0301]
第二集合获取模块还用于以所述质心为圆心，以所述第一距离为半径，获得自定义圆形区域；
[0302]
第二集合获取模块还用于将位于所述自定义圆形区域中的兴趣点添加至所述第二集合中。
[0303]
进一步的，所述装置还包括综合排名函数，所述综合排名函数详见方法实施例，在此不做赘述。
[0304]
进一步的，所述装置还包括综合评分函数，所述综合评分函数详见方法实施例，在此不做赘述。
[0305]
进一步的，所述装置还包括有效时间重叠率函数，所述有效时间重叠率函数详见
方法实施例，在此不做赘述。
[0306]
进一步的，所述装置还包括距离代价函数，所述距离代价函数详见方法实施例，在此不做赘述。
[0307]
需要说明的是，在本技术中，诸如“第一”和“第二”等之类的关系术语仅仅用来将一个实体或者操作与另一个实体或操作区分开来，而不一定要求或者暗示这些实体或操作之间存在任何这种实际的关系或者顺序。而且，术语“包括”、“包含”或者其任何其他变体意在涵盖非排他性的包含，从而使得包括一系列要素的过程、方法、物品或者设备不仅包括那些要素，而且还包括没有明确列出的其他要素，或者是还包括为这种过程、方法、物品或者设备所固有的要素。在没有更多限制的情况下，由语句“包括一个
……”
限定的要素，并不排除在包括要素的过程、方法、物品或者设备中还存在另外的相同要素。
[0308]
以上仅是本技术的具体实施方式，使本领域技术人员能够理解或实现本技术。对这些实施例的多种修改对本领域的技术人员来说将是显而易见的，本文中所定义的一般原理可以在不脱离本技术的精神或范围的情况下，在其它实施例中实现。因此，本技术将不会被限制于本文所示的这些实施例，而是要符合与本文所申请的原理和新颖特点相一致的最宽的范围。

技术特征：
1.一种面向多属性的动态组旅行规划方法，其特征在于，所述方法包括以下步骤：获取路网图以及查询数据；基于所述路网图构建对应的综合索引结构；基于所述查询数据以及各所述兴趣点的文本信息以及有效时间信息，对所述综合索引结构进行剪枝处理，得到第一集合；基于所述查询数据，对所述路网图的搜索空间进行剪枝处理，并与所述第一集合进行交集处理，得到第二集合；基于所述第二集合，获得满足所述查询数据对应的约束条件的兴趣点，记作条件兴趣点；根据所述查询数据的起始位置和目标位置，并基于各所述条件兴趣点，获得多条候选路径；计算多条候选路径的综合排名，并根据所述综合排名将预设条数的候选路径选定为旅行最佳路径；其中，所述路网图包括多个兴趣点以及对应的路径，各所述兴趣点包括文本信息以及有效时间信息；所述查询数据包括组成员、起始位置、目的位置、查询关键字和时间查询区间。2.如权利要求1所述的面向多属性的动态组旅行规划方法，其特征在于，所述基于所述路网图构建对应的综合索引结构中，包括以下步骤：对所述路网图进行划分，获得多个子图；计算并存储各所述子图中所述兴趣点的边界的最短路径距离，构建边界距离矩阵；基于各所述兴趣点的文本信息以及有效时间信息，构建对应的关键字反向索引；基于所述子图的名称信息、所述边界距离矩阵、所述关键字反向索引以及对应的所述有效时间信息，构建所述综合索引结构。3.如权利要求1所述的面向多属性的动态组旅行规划方法，其特征在于，所述基于所述查询数据以及各所述兴趣点的文本信息以及有效时间信息，对所述综合索引结构进行剪枝处理，得到第一集合中包括以下步骤：初始化第一集合和第一队列，所述第一队列用于存放所述综合索引结构的叶子节点，所述第一集合用于存放条件兴趣点；基于所述综合索引结构的根结点，遍历所述根结点的子结点，判断是否满足所述查询数据对应的查询关键字和时间查询区间；若满足则判定是否为非叶结点，若是非叶结点则将对应结点的子结点存储所述第一队列，若不是非叶结点则将对应的结点存入所述第一集合。4.如权利要求1所述的面向多属性的动态组旅行规划方法，其特征在于，所述基于所述查询数据，对所述路网图的搜索空间进行剪枝处理，并与所述第一集合进行交集处理，得到第二集合中，包括以下步骤：定位查询数据在所述路网图中的区域，并定义一组椭圆区域；初始化第二队列、第二集合、椭圆第一焦点集合以及椭圆第二焦点集合，所述第二队列用于存放一组椭圆区域，所述第二集合用于存放所述条件兴趣点，所述椭圆第一焦点集合用于存放椭圆区域的第一焦点，所述椭圆第二焦点集合用于存放椭圆区域的第二焦点；
计算每个椭圆区域的第一焦点，并添加至所述椭圆第一焦点集合；计算每个椭圆区域的第二焦点，并添加至所述椭圆第二焦点集合；基于所述椭圆第一焦点集合和所述椭圆第二焦点集合，计算出每个所述椭圆区域；计算多个所述椭圆区域之间的椭圆交集，将位于所述椭圆交集中的兴趣点添加至所述第二集合中。5.如权利要求4所述的面向多属性的动态组旅行规划方法，其特征在于，所述基于所述查询数据，对所述路网图的搜索空间进行剪枝处理，并与所述第一集合进行交集处理，得到第二集合中，包括以下步骤：若多个所述椭圆区域之间不存在椭圆交集，则计算获得多个所述椭圆区域之间的质心；识别获得所述质心与其距离最近的所述兴趣点之间的距离，记作第一距离；以所述质心为圆心，以所述第一距离为半径，获得自定义圆形区域；将位于所述自定义圆形区域中的兴趣点添加至所述第二集合中。6.如权利要求1所述的面向多属性的动态组旅行规划方法，其特征在于，所述方法还包括综合排名函数，所述综合排名函数为：其中，表示兴趣点v不满足查询约束q；f
t
(q.v)是查询时间与兴趣点v的有效时间重叠率；f
l
(q.v)是路径序列的距离代价；score(q.v)是兴趣点v的综合评分；α、β、γ∈(0，1)且α+β+γ＝1，α、β、γ表示用户的偏好参数，用于调整时间重叠率、距离代价和综合评分在综合排名函数中的权重。7.如权利要求6所述的面向多属性的动态组旅行规划方法，其特征在于，所述方法还包括综合评分函数，所述综合评分函数为：其中，参数α1、α2表示权重，|u|是小组成员数量，v
i
.pop是兴趣点v
i
的流行数值，v
i
.env是兴趣点v
i
的环境数值，v
i
.ser是兴趣点v
i
的服务数值。8.如权利要求6所述的面向多属性的动态组旅行规划方法，其特征在于，所述方法还包括有效时间重叠率函数，所述有效时间重叠率函数为：其中，
q.t是时间查询区间q的查询时间，v.t是兴趣点v的有效时间，v.st是兴趣点v的有效起始时间；q.et是时间查询区间q的结束时间；t
w
表示是小组成员可以忍受的等待时间；|q.t∩v.t|≠0表示q.t与v.t之间存在交集；v.st-q.et是v.t与q.et的时间差值。9.如权利要求1所述的面向多属性的动态组旅行规划方法，其特征在于，所述方法还包括距离代价函数，所述距离代价函数为：其中，dist(s
i
,v
c
,d
i
)表示用户u
i
从起点开始，经过兴趣点v
c
，到达终点的路网距离。10.一种面向多属性的动态组旅行规划装置，其特征在于，所述装置包括：数据获取模块，其用于获取路网图以及查询数据；索引结构构建模块，其用于基于所述路网图构建对应的综合索引结构；第一集合获取模块，其用于基于所述查询数据以及各所述兴趣点的文本信息以及有效时间信息，对所述综合索引结构进行剪枝处理，得到第一集合；第二集合获取模块，其用于基于所述查询数据，对所述路网图的搜索空间进行剪枝处理，并与所述第一集合进行交集处理，得到第二集合；条件兴趣点获取模块，其用于基于所述第二集合，获得满足所述查询数据对应的约束条件的兴趣点，记作条件兴趣点；候选路径获取模块，其用于根据所述查询数据的起始位置和目标位置，并基于各所述条件兴趣点，获得多条候选路径；最佳路径获取模块，其用于计算多条候选路径的综合排名，并根据综合排名将预设条数的候选路径选定为旅行最佳路径；其中，所述路网图包括多个兴趣点以及对应的路径，各所述兴趣点包括文本信息以及有效时间信息；所述查询数据包括组成员、起始位置、目的位置、查询关键字和时间查询区间。

技术总结
本申请涉及一种面向多属性的动态组旅行规划方法及装置，涉及路径规划技术领域，该方法包括以下步骤：获取路网图以及查询数据；构建对应的综合索引结构；对综合索引结构进行剪枝处理，得到第一集合；对路网图的搜索空间进行剪枝处理，并与所述第一集合进行交集处理，得到第二集合；基于第二集合，获得满足查询数据对应的约束条件的兴趣点；根据查询数据的起始位置和目标位置，并基于各条件兴趣点，获得多条候选路径；计算多条候选路径的综合排名，并根据综合排名将预设条数的候选路径选定为旅行最佳路径。本申请将动态组旅行延伸到真实的道路网路，同时增加兴趣点的多维属性信息，使得动态组旅行规划查询考虑因素更为全面，查询结果更准确可靠。询结果更准确可靠。询结果更准确可靠。


技术研发人员：杜小坤 欧昱宏 李艳红 涂锐
受保护的技术使用者：中南民族大学
技术研发日：2023.06.30
技术公布日：2023/10/8