CN112097782B - A Circular Filter Query Method for Optimal Group Order Path Based on Meeting Points - Google Patents

Abstract

The invention provides a round filtering query method of an optimal group order path based on meeting points, which can efficiently process the query of the optimal group order path based on the meeting points in a multi-user query scene and provides a round filtering query method.

Description

Translated fromChinese

一种基于会面点的最优组次序路径圆滤查询方法A Circular Filter Query Method for Optimal Group Order Path Based on Meeting Points

技术领域technical field

本发明涉及路径规划算法领域，更具体地，涉及一种基于会面点的最优组次序路径圆滤查询方法。The present invention relates to the field of path planning algorithms, and more particularly, to an optimal group order path circular filter query method based on meeting points.

背景技术Background technique

随着基于位置的服务成熟，人们可以使用更复杂、更个性化的路经查询服务,最优次序路径查询便是其中的一种。例如，用户u从起点s出发，中途要经过银行、餐馆最终到达目的地点d,满足用户u这种查询需求的最优路径便是最优次序路径。With the maturity of location-based services, people can use more complex and personalized route query services, and optimal order route query is one of them. For example, user u starts from the starting point s, and goes through banks and restaurants on the way to the destination point d. The optimal path that meets the query requirements of user u is the optimal sequence path.

考虑到一种多用户路径查询的场景，例如用户A和用户B，用户A从起点sA出发，要经过银行、超市最终和用户B在餐馆会面，而用户B从起点sB出发时要先到加油站后才能和用户A在餐馆见面,现在需要为用户A和用户B选择最优的会面地点(某个餐馆)并规划满足他们需求的路径使得他们尽早地见面。Consider a scenario of multi-user path query, such as user A and user B, user A starts from the starting point sA, goes through a bank, a supermarket, and finally meets with user B in a restaurant, while user B starts from the starting point sB. Only after the station can we meet user A at the restaurant, now we need to choose the optimal meeting place (a restaurant) for user A and user B and plan a path that meets their needs so that they can meet as soon as possible.

尽管最优次序路径查询能很好解决单个用户的查询需求，但不能直接用于解决这种多用户的路径查询场景。一种方法是依次检查会面的候选点为每个用户执行最优次序路径查询，这样能得到最优的候选点和相应的最优查询路径。Although the optimal order path query can well solve the query requirements of a single user, it cannot be directly used to solve this multi-user path query scenario. One method is to check the candidate points of the meeting in turn and perform the optimal order path query for each user, so that the optimal candidate point and the corresponding optimal query path can be obtained.

尽管这种方法能解决这种多用户的查询场景，但查询效率很低，在目标候选点较大时所需要的查询时间是不可接受的。因此本发明致力于提高这种多用户查询的查询性能及效率。Although this method can solve this multi-user query scenario, the query efficiency is very low, and the query time required is unacceptable when the target candidate points are large. Therefore, the present invention is devoted to improving the query performance and efficiency of such multi-user query.

申请号为201510664696.2的专利说明书中公开了一种路径规划装置及方法，本申请通过浮动车出行经验的路径规划方法，以浮动车GPS数据为基础，研究浮动车司机载客时选择路径的经验和规律，提取浮动车的载客行为路径建立经验路径库，并对路径进行修正和校验，通过给定的起点和终点位置，搜索经验路径库获取合理路径集。然而，该专利无法实现高效处理基于会面点的最优组次序路径查询，为多用户提供最优的候选点及相应的组次序路径。The patent specification with the application number of 201510664696.2 discloses a path planning device and method. The present application uses the path planning method of the floating car travel experience, based on the floating car GPS data, to study the floating car driver's experience and path selection when carrying passengers. According to the rules, the passenger-carrying behavior path of the floating car is extracted to establish an experience path library, and the path is corrected and verified. Through the given start and end positions, the experience path library is searched to obtain a reasonable path set. However, this patent cannot efficiently process the optimal group order path query based on meeting points, and provide optimal candidate points and corresponding group order paths for multiple users.

发明内容SUMMARY OF THE INVENTION

本发明提供一种基于会面点的最优组次序路径圆滤查询方法，该方法能高效处理基于会面点的最优组次序路径查询，为多用户提供最优的候选点及相应的组次序路径。The present invention provides an optimal group order path circular filter query method based on meeting points, which can efficiently process the optimal group order path query based on meeting points, and provides optimal candidate points and corresponding group order paths for multiple users .

为了达到上述技术效果，本发明的技术方案如下：In order to achieve above-mentioned technical effect, technical scheme of the present invention is as follows:

一种基于会面点的最优组次序路径圆滤查询方法，包括以下步骤：An optimal group order path circular filter query method based on meeting points, comprising the following steps:

S1：利用

选出初始会面点dinitial，其中L(u_i,d)代表的是用户u_i到点d的最短路径代价，c_d是候选会面点集，U是用户组；S1: Exploit

Select the initial meeting point dinitial, where L(u_i ,d) represents the shortest path cost from user_ui to point_d , cd is the candidate meeting point set, and U is the user group;

S2：通过贪心最近邻搜索得到可行组路径FGRinitial；S2: Obtain the feasible group path FGRinitial through greedy nearest neighbor search;

S3：赋值变量radius为FGRinitial的代价；S3: The cost of assigning the variable radius to FGRinitial;

S4：过滤掉候选会面点集中满足

条件的候选会面点；S4: Filter out candidate meeting points to focus on satisfying

Conditional candidate meeting points;

S5：更新radius为所有通过贪心最近邻搜索得到的可行组路径中的最小路径代价；S5: Update radius to the minimum path cost among all feasible group paths obtained by greedy nearest neighbor search;

S6：执行S4；S6: execute S4;

S7：初始化变量OGR和radius；S7: Initialize variables OGR and radius;

S8：若还有候选会面点，从中选出一个候选会面点d，否则执行S10；S8: If there are still candidate meeting points, select a candidate meeting point d, otherwise, perform S10;

S9：计算用户组U中每个用户到d的最优次序路径，若最大路径代价小于radius，更新radius以及OGR并执行S4；S9: Calculate the optimal sequence path from each user in the user group U to d, if the maximum path cost is less than radius, update radius and OGR and execute S4;

S10：返回最优解OGR。S10: Return the optimal solution OGR.

进一步地，所述步骤S2中，若对于用户组中的每个用户，若兴趣点访问次序为空时，则其查询路径为出发点到终点最短路径。Further, in the step S2, if for each user in the user group, if the access order of the points of interest is empty, the query path is the shortest path from the starting point to the ending point.

进一步地，所述步骤S2中，若兴趣点访问次序不为空时，为次序中的每个兴趣点集选择一个点p_i，使得出发点到p_i的最短路径代价加上p_i到终点的代价在该兴趣点集中是最小的。Further, in the step S2, if the interest point access order is not empty, select a point p_i for each interest point set in the order, so that the shortest path cost from the starting point to p_i is added to the cost of the shortest path from p_i to the end point. The cost is minimal in this set of interest points.

进一步地，所述步骤S5中通过贪心最近邻搜索得到的可行组路径中的最小路径代价的过程是：Further, the process of the minimum path cost in the feasible group paths obtained by the greedy nearest neighbor search in the step S5 is:

更换步骤S2中FGRinitial的会面点，重新计算其可行组路径的代价，候选会面点集中的所有候选会面点都更换一遍即可得到最小路径代价。Replace the meeting point of FGRinitial in step S2, recalculate the cost of its feasible group path, and replace all candidate meeting points in the candidate meeting point set once to obtain the minimum path cost.

进一步地，所述步骤S9中更新OGR的过程为：Further, the process of updating OGR in the step S9 is:

将用户组U中每个用户到d的最优次序路径组成一个组，赋值给变量OGR。The optimal order path from each user in the user group U to d is formed into a group and assigned to the variable OGR.

进一步地，所述步骤S7中初始化变量OGR为空。Further, in the step S7, the initialization variable OGR is empty.

进一步地，所述步骤S7中初始化变量radius为无限大。Further, in the step S7, the initialization variable radius is infinite.

进一步地，每个用户的查询路径构成了该用户组的可行组路径。Further, the query path of each user constitutes the feasible group path of the user group.

进一步地，出发点以及按访问次序选出的每个兴趣点p_i还有终点构成了该用户的查询路径。Further, the starting point, each interest point p_i selected in the order of access, and the end point constitute the query path of the user.

进一步地，步骤S5中，可行组路径中的最小路径代价即是最小过滤半径。Further, in step S5, the minimum path cost in the feasible group paths is the minimum filter radius.

与现有技术相比，本发明技术方案的有益效果是：Compared with the prior art, the beneficial effects of the technical solution of the present invention are:

本发明能高效处理多用户查询场景下基于会面点的最优组次序路径查询，提出了圆滤查询方法，该方法能够求解基于会面点的最优组次序路径查询，并且能快速的求解相应的该查询的最优解。The invention can efficiently process the query of the optimal group order path based on the meeting point in the multi-user query scenario, and proposes a circular filter query method, which can solve the optimal group order path query based on the meeting point, and can quickly solve the corresponding query The optimal solution for this query.

附图说明Description of drawings

图1为本发明实施例中的路网示意图；1 is a schematic diagram of a road network in an embodiment of the present invention;

图1中的路网的节点包括：u1、u2代表用户u1和u2所在位置，r1和r2代表两个餐馆，s1、s2和s3代表三个超市，g1、g2、g3代表三个加油站，d1、d2、d3、d4、d5和d6代表用户u1和u2的候选会面点；这些节点之间的连线代表两个节点的边，例如加油站g1和点d6存在一条边，边上的数字10代表边(g1,d6)的权重是10。The nodes of the road network in Figure 1 include: u1, u2 represent the location of users u1 and u2, r1 and r2 represent two restaurants, s1, s2 and s3 represent three supermarkets, g1, g2, g3 represent three gas stations, d1, d2, d3, d4, d5, and d6 represent candidate meeting points for users u1 and u2; the line between these nodes represents the edge of the two nodes, for example, there is an edge between gas station g1 and point d6, and the numbers on theedge 10 means the weight of edge (g1, d6) is 10.

具体实施方式Detailed ways

附图仅用于示例性说明，不能理解为对本专利的限制；The accompanying drawings are for illustrative purposes only, and should not be construed as limitations on this patent;

为了更好说明本实施例，附图某些部件会有省略、放大或缩小，并不代表实际产品的尺寸；In order to better illustrate this embodiment, some parts of the drawings are omitted, enlarged or reduced, which do not represent the size of the actual product;

对于本领域技术人员来说，附图中某些公知结构及其说明可能省略是可以理解的。It will be understood by those skilled in the art that some well-known structures and their descriptions may be omitted from the drawings.

下面结合附图和实施例对本发明的技术方案做进一步的说明。The technical solutions of the present invention will be further described below with reference to the accompanying drawings and embodiments.

一种基于会面点的最优组次序路径圆滤查询方法，包括以下步骤：An optimal group order path circular filter query method based on meeting points, comprising the following steps:

S1：利用

选出初始会面点dinitial，其中L(u_i,d)代表的是用户u_i到点d的最短路径代价，c_d是候选会面点集，U是用户组；S1: Exploit

Select the initial meeting point dinitial, where L(u_i ,d) represents the shortest path cost from user_ui to point_d , cd is the candidate meeting point set, and U is the user group;

S2：通过贪心最近邻搜索得到可行组路径FGRinitial；S2: Obtain the feasible group path FGRinitial through greedy nearest neighbor search;

S3：赋值变量radius为FGRinitial的代价；S3: The cost of assigning the variable radius to FGRinitial;

S4：过滤掉候选会面点集中满足

条件的候选会面点；S4: Filter out candidate meeting points to focus on satisfying

Conditional candidate meeting points;

S5：更新radius为所有通过贪心最近邻搜索得到的可行组路径中的最小路径代价；S5: Update radius to the minimum path cost among all feasible group paths obtained by greedy nearest neighbor search;

S6：执行S4；S6: execute S4;

S7：初始化变量OGR和radius；S7: Initialize variables OGR and radius;

S8：若还有候选会面点，从中选出一个候选会面点d，否则执行S10；S8: If there are still candidate meeting points, select a candidate meeting point d, otherwise, perform S10;

S9：计算用户组U中每个用户到d的最优次序路径，若最大路径代价小于radius，更新radius以及OGR并执行S4；S9: Calculate the optimal sequence path from each user in the user group U to d, if the maximum path cost is less than radius, update radius and OGR and execute S4;

S10：返回最优解OGR。S10: Return the optimal solution OGR.

步骤S2中，若对于用户组中的每个用户，若兴趣点访问次序为空时，则其查询路径为出发点到终点最短路径；若兴趣点访问次序不为空时，为次序中的每个兴趣点集选择一个点p_i，使得出发点到p_i的最短路径代价加上p_i到终点的代价在该兴趣点集中是最小的。In step S2, if for each user in the user group, if the point of interest access order is empty, then its query path is the shortest path from the starting point to the end point; if the point of interest access order is not empty, it is each in the order. The set of interest points selects a point_pi such that the shortest path cost from the starting point to_pi plus the cost of_pi to the end point is the smallest in the set of interest points.

步骤S5中通过贪心最近邻搜索得到的可行组路径中的最小路径代价的过程是：The process of obtaining the minimum path cost in the feasible group paths through the greedy nearest neighbor search in step S5 is:

更换步骤S2中FGRinitial的会面点，重新计算其可行组路径的代价，候选会面点集中的所有候选会面点都更换一遍即可得到最小路径代价。Replace the meeting point of FGRinitial in step S2, recalculate the cost of its feasible group path, and replace all candidate meeting points in the candidate meeting point set once to obtain the minimum path cost.

步骤S9中更新OGR的过程为：The process of updating the OGR in step S9 is as follows:

将用户组U中每个用户到d的最优次序路径组成一个组，赋值给变量OGR。The optimal order path from each user in the user group U to d is formed into a group and assigned to the variable OGR.

步骤S7中初始化变量OGR为空；初始化变量radius为无限大。In step S7, the initialization variable OGR is empty; the initialization variable radius is infinite.

每个用户的查询路径构成了该用户组的可行组路径；出发点以及按访问次序选出的每个兴趣点p_i还有终点构成了该用户的查询路径。The query path of each user constitutes the feasible group path of the user group; the starting point, each point of interest_pi selected according to the access order, and the end point constitute the query path of the user.

步骤S5中，可行组路径中的最小路径代价即是最小过滤半径。In step S5, the minimum path cost in the feasible set of paths is the minimum filter radius.

如图1所示，定义1(路网RN)：路网RN＝(V，E)。路网是一个无向图，其中V是RN的点集，E是RN的边集，对于边e属于E，w(e)表示为e的权重。As shown in FIG. 1, definition 1 (road network RN): road network RN=(V, E). The road network is an undirected graph, where V is the point set of RN, E is the edge set of RN, and for edge e belongs to E, w(e) is expressed as the weight of e.

定义2(兴趣点POI)：兴趣点是路网上一种特定类型的定点，具有相同类型的兴趣点可以看成一类兴趣点。Definition 2 (POI): POI is a specific type of fixed point on the road network, and POIs with the same type can be regarded as a type of POI.

例如，图1中属于超市类别的兴趣点包括{s1,s2,s3},属于加油站类别的兴趣点包括{g1,g2,g3},而属于餐馆类别的兴趣点是{r1,r2}。For example, in Figure 1, the POIs belonging to the supermarket category include {s1, s2, s3}, the POIs belonging to the gas station category include {g1, g2, g3}, and the POIs belonging to the restaurant category are {r1, r2}.

定义3(路径Route)：定义路网中的路径R＝<v1,v2,...,vn>,其中v1,v2,...,vn为路网中的定点，边(vi-1,vi),2<＝i<＝n属于路网的边集,路径R的权重为

Definition 3 (Route Route): Define the route R=<v1,v2,...,vn> in the road network, where v1,v2,...,vn are the fixed points in the road network, the edge (vi-1, vi), 2<=i<=n belongs to the edge set of the road network, and the weight of the path R is

定义4(最优次序路径OSR)：给定一个起点s和终点d和需要依次访问的兴趣点次序C＝<c1,c2,...,cm>,如果一条路径R＝<s,p1,p2,...,pm,d>存在且满足pi的兴趣点类别为ci(1<＝i<＝m),则R为一条次序路径SR，最优次序路径为所有次序路径中权重最小的一条路径。Definition 4 (Optimal Order Path OSR): Given a starting point s and an ending point d and the order of interest points that need to be visited sequentially C=<c1, c2,...,cm>, if a path R=<s, p1, p2, . a path.

定义5(基于会面点最优组次序路径查询OGSRMQ)：给定一组用户U＝{u1,u2,...,un}和候选会面点集D＝{d1,d2,...,dk},每个用户ui都对应一个出发点si和一个需要依次访问的兴趣点次序

基于会面点最优组次序路径查询得到一个会面点d和一组次序路径使得这组用户能够最快的会面。满足这种查询的会面点称为最佳会面点，所对应的那一组次序路径称为最优组次序路径。Definition 5 (Query OGSRMQ based on the optimal group order path of meeting points): Given a set of users U={u1,u2,...,un} and a set of candidate meeting points D={d1,d2,...,dk }, each user ui corresponds to a starting point si and an order of interest points that need to be accessed in turn

A meeting point d and a set of sequence paths are obtained based on the optimal group sequence path query of meeting points, so that this group of users can meet the fastest. The meeting point that satisfies this query is called the best meeting point, and the corresponding group of order paths is called the optimal group order path.

下面结合图1给出一个具体的基于会面点的最优组次序路经查询实例：A specific example of the optimal group order path query based on meeting points is given below in conjunction with Figure 1:

1、获取查询参数：用户组U＝{u1,u2},目标会面点集D＝{d1,d2,d3,d4,d5,d6},用户u1的出发点为u1及对应的兴趣点访问次序为<餐馆，超市>,而用户u2的出发点为u2及对应的兴趣点访问次序为<加油站，超市>；1. Obtain query parameters: user group U={u1, u2}, target meeting point set D={d1, d2, d3, d4, d5, d6}, the starting point of user u1 is u1 and the access order of the corresponding points of interest is <restaurant, supermarket>, and the starting point of user u2 is u2 and the corresponding POI access order is <gas station, supermarket>;

2、初始化查询结果OGR为空，radius为无限大；2. The initial query result OGR is empty, and the radius is infinite;

3、选出初始候选会面点为d1；3. Select the initial candidate meeting point as d1;

4、检查候选点d1,求得用户u1的贪心路径为<u1,r1,s1,d1>，求得用户u2的贪心路径为<u2,g1,s2,d1>，更新OGR为两个用户的贪心路径，代价为14，更新radius为14；4. Check the candidate point d1, obtain the greedy path of user u1 as <u1,r1,s1,d1>, obtain the greedy path of user u2 as <u2,g1,s2,d1>, and update the OGR to the two users Greedy path, the cost is 14, and the update radius is 14;

5、由于max{L(u₁,d₆),L(u₂,d₆)}＝16＞14，过滤掉d6；5. Since max{L(u₁ , d₆ ), L(u₂ , d₆ )}=16>14, filter out d6;

6、通过候选会面点d2的得到最小过滤半径，更新radius为12；6. Obtain the minimum filter radius from the candidate meeting point d2, and update the radius to 12;

7、过滤掉d5；7. Filter out d5;

8、由于剩余候选会面点集非空，选出候选会面点d1,检查d1,分别计算用户u1以及用户u2到d1的最优次序路径，由于其最大路径代价为14<12，radius不更新；8. Since the remaining candidate meeting point set is not empty, select the candidate meeting point d1, check d1, and calculate the optimal order path of user u1 and user u2 to d1 respectively. Since the maximum path cost is 14<12, the radius is not updated;

9、以上一步的同样方式检查d3，OGR更新为u1的最优次序路径为<u1,r2,s3,d3>代价为10和用户u2的最优次序路径为<u2,g3,s3,d3>代价为9,更新radius为10并过滤掉d4；9. Check d3 in the same way as the previous step, OGR is updated to the optimal order path of u1 is <u1, r2, s3, d3> cost is 10 and the optimal order path of user u2 is <u2, g3, s3, d3> The cost is 9, the update radius is 10 and d4 is filtered out;

10、剩余候选会面点集为空，返回最优解OGR。10. The remaining candidate meeting point set is empty, and the optimal solution OGR is returned.

相同或相似的标号对应相同或相似的部件；The same or similar reference numbers correspond to the same or similar parts;

附图中描述位置关系的用于仅用于示例性说明，不能理解为对本专利的限制；The positional relationship described in the accompanying drawings is only for exemplary illustration, and should not be construed as a limitation on this patent;

显然，本发明的上述实施例仅仅是为清楚地说明本发明所作的举例，而并非是对本发明的实施方式的限定。对于所属领域的普通技术人员来说，在上述说明的基础上还可以做出其它不同形式的变化或变动。这里无需也无法对所有的实施方式予以穷举。凡在本发明的精神和原则之内所作的任何修改、等同替换和改进等，均应包含在本发明权利要求的保护范围之内。Obviously, the above-mentioned embodiments of the present invention are only examples for clearly illustrating the present invention, and are not intended to limit the embodiments of the present invention. For those of ordinary skill in the art, changes or modifications in other different forms can also be made on the basis of the above description. There is no need and cannot be exhaustive of all implementations here. Any modifications, equivalent replacements and improvements made within the spirit and principle of the present invention shall be included within the protection scope of the claims of the present invention.

Claims (9)

1. A round filtering query method for an optimal group order path based on meeting points is characterized by comprising the following steps:

s1: by using

Selecting an initial meeting point d_initialWherein L (u)_iD) represents user u_iShortest path cost to point d, c_dIs a candidate meeting point set, U is a user group;

s2: obtaining a feasible group path FGRinitial through greedy nearest neighbor search;

s3: assigning a variable radius as the cost of FGRinitial;

s4: filtering out candidate meeting point centralized satisfaction

Candidate meeting points of the condition;

s5: updating radius to be the minimum path cost in all feasible group paths obtained by greedy nearest neighbor search;

s6: execution of S4;

s7: initializing variables OGR and radius;

s8: if there are still candidate meeting points, selecting a candidate meeting point d, otherwise executing S10;

s9: calculating the optimal sequence path from each user to d in the user group U, if the maximum path cost is less than radius, updating radius and OGR and executing S4, wherein the process of updating OGR is as follows:

forming an optimal sequence path from each user to d in the user group U into a group, and assigning a variable OGR;

s10: and returning the optimal solution OGR.

2. The method for round filtering search of optimal group order path based on meeting points as claimed in claim 1, wherein in step S2, if the visit order of the points of interest is null for each user in the user group, the search path is the shortest path from the starting point to the ending point.

3. The method for round-filtering query on optimal set of order paths based on meeting points as claimed in claim 2, wherein in step S2, if the visiting order of the points of interest is not empty, a point p is selected for each point of interest set in the order_iLet the departure point go to p_iIs added to p_iThe cost to the endpoint is minimal in this set of points of interest.

4. The optimal group order path round filter query method based on rendezvous points as claimed in claim 3, wherein the process of minimum path cost in feasible group paths obtained through greedy nearest neighbor search in step S5 is:

and replacing the meeting point of FGRinitial in the step S2, recalculating the cost of the feasible group path, and replacing all candidate meeting points in the candidate meeting point set once to obtain the minimum path cost.

5. The method for round filter query based on optimal group order path of meeting points as claimed in claim 4, wherein the initialization variable OGR in step S7 is null.

6. The method for optimal set of order path round filter query based on meeting points as claimed in claim 5, wherein the initialization variable radius in step S7 is infinite.

7. The method of claim 6, wherein the query path of each user constitutes a feasible group path of the user group.

8. The method of claim 7, wherein the starting point and each of the points of interest p selected in the visiting order are_iAnd the endpoints also constitute the query path for the user.

9. The method for round-filtering query on optimal set of order paths based on rendezvous points according to any one of claims 1 to 8, wherein in step S5, the minimum path cost in the feasible set of paths is the minimum filtering radius.

Images