CN112097782B - Optimal group order path circular filtering query method based on meeting point - Google Patents
Optimal group order path circular filtering query method based on meeting point Download PDFInfo
- Publication number
- CN112097782B CN112097782B CN202010673378.3A CN202010673378A CN112097782B CN 112097782 B CN112097782 B CN 112097782B CN 202010673378 A CN202010673378 A CN 202010673378A CN 112097782 B CN112097782 B CN 112097782B
- Authority
- CN
- China
- Prior art keywords
- path
- points
- point
- group
- user
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Active
Links
Images
Classifications
-
- G—PHYSICS
- G01—MEASURING; TESTING
- G01C—MEASURING DISTANCES, LEVELS OR BEARINGS; SURVEYING; NAVIGATION; GYROSCOPIC INSTRUMENTS; PHOTOGRAMMETRY OR VIDEOGRAMMETRY
- G01C21/00—Navigation; Navigational instruments not provided for in groups G01C1/00 - G01C19/00
- G01C21/26—Navigation; Navigational instruments not provided for in groups G01C1/00 - G01C19/00 specially adapted for navigation in a road network
- G01C21/34—Route searching; Route guidance
- G01C21/3446—Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags, using precalculated routes
Landscapes
- Engineering & Computer Science (AREA)
- Radar, Positioning & Navigation (AREA)
- Remote Sensing (AREA)
- Automation & Control Theory (AREA)
- Physics & Mathematics (AREA)
- General Physics & Mathematics (AREA)
- Navigation (AREA)
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
Technical Field
The invention relates to the field of path planning algorithms, in particular to an optimal group order path circular filtering query method based on meeting point.
Background
As location-based services mature, people can use more complex, more personalized route query services, of which the best-order path query is one. For example, the user u starts from the starting point s, goes through a bank and a restaurant, and finally reaches the destination point d, and the optimal path meeting the query requirement of the user u is the optimal sequence path.
Considering a multi-user path query scenario, such as a user a and a user B, the user a starts from a starting point sA, and finally meets the user B at a restaurant through a bank and a supermarket, and the user B starts from a starting point sB and can meet the user a at the restaurant only after arriving at a gas station, it is now necessary to select an optimal meeting place (a certain restaurant) for the user a and the user B and plan a path meeting their needs so that they meet the meeting place as early as possible.
Although the optimal order path query can well solve the query requirement of a single user, the optimal order path query cannot be directly used for solving the path query scenario of multiple users. One method is to sequentially check candidate points for meetings and perform optimal sequence path query for each user, so that optimal candidate points and corresponding optimal query paths can be obtained.
Although this method can solve such a multi-user query scenario, the query efficiency is low, and the query time required when the target candidate point is large is unacceptable. The present invention is therefore directed to improving the query performance and efficiency of such multi-user queries.
The patent specification with the application number of 201510664696.2 discloses a path planning device and a method, and the device and the method are characterized in that the experience and the rule of selecting a path when a driver of a floating car carries passengers are researched by a path planning method of traveling experience of the floating car based on GPS data of the floating car, the passenger carrying behavior path of the floating car is extracted to establish an experience path library, the path is corrected and verified, and a reasonable path set is obtained by searching the experience path library through given starting points and end points. However, the patent cannot realize efficient processing of the optimal group order path query based on meeting points, and provide optimal candidate points and corresponding group order paths for multiple users.
Disclosure of Invention
The invention provides a round filtering query method for 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 and provide optimal candidate points and corresponding group order paths for multiple users.
In order to achieve the technical effects, the technical scheme of the invention is as follows:
an optimal group order path circular filtering query method based on meeting points comprises the following steps:
s1: by using
Selecting an initial meeting point dinitial, where L (u)iD) represents user uiShortest path cost to point d, cdIs 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;
s10: and returning the optimal solution OGR.
Further, in step S2, if the access order of the points of interest is null for each user in the user group, the query path is the shortest path from the starting point to the ending point.
Further, in step S2, if the access order of the points of interest is not null, a point p is selected for each point of interest set in the access orderiLet the departure point go to piIs added to piThe cost to the endpoint is minimal in this set of points of interest.
Further, the process of the minimum path cost in the feasible group of paths obtained by the greedy nearest neighbor search in step S5 is as follows:
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.
Further, the process of updating the OGR in the step S9 is as follows:
and (4) forming the optimal sequence path from each user to d in the user group U into a group, and assigning a variable OGR.
Further, in the step S7, the initialization variable OGR is null.
Further, in the step S7, the initialization variable radius is infinite.
Further, the query path of each user constitutes a feasible group path for the user group.
Further, a starting point and each point of interest p selected in the visiting orderiAnd the endpoints also constitute the query path for the user.
Further, in step S5, the minimum path cost in the feasible group of paths is the minimum filtering radius.
Compared with the prior art, the technical scheme of the invention has the beneficial effects that:
the invention can efficiently process the optimal group sequence path query based on the meeting point in a multi-user query scene, and provides the circular filter query method.
Drawings
FIG. 1 is a schematic diagram of a road network according to an embodiment of the present invention;
the nodes of the road network in fig. 1 comprise: u1 and u2 represent the positions of users u1 and u2, r1 and r2 represent two restaurants, s1, s2 and s3 represent three supermarkets, g1, g2 and g3 represent three gas stations, and d1, d2, d3, d4, d5 and d6 represent candidate meeting points of users u1 and u 2; the line between these nodes represents the edge of two nodes, e.g., gas station g1 and point d6 have one edge, and the number 10 on the edge represents the weight of the edge (g1, d6) as 10.
Detailed Description
The drawings are for illustrative purposes only and are not to be construed as limiting the patent;
for the purpose of better illustrating the embodiments, certain features of the drawings may be omitted, enlarged or reduced, and do not represent the size of an actual product;
it will be understood by those skilled in the art that certain well-known structures in the drawings and descriptions thereof may be omitted.
The technical solution of the present invention is further described below with reference to the accompanying drawings and examples.
An optimal group order path circular filtering query method based on meeting points comprises the following steps:
s1: by using
Selecting an initial meeting point dinitial, where L (u)iD) represents user uiShortest path to point dCost, cdIs 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;
s10: and returning the optimal solution OGR.
In step S2, if the access order of the points of interest is null for each user in the user group, the shortest path from the starting point to the ending point is the query path; if the point of interest access order is not null, a point p is selected for each set of points of interest in the orderiLet the departure point go to piIs added to piThe cost to the endpoint is minimal in this set of points of interest.
The process of the minimum path cost in the feasible group of paths obtained by the 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.
The process of updating the OGR in step S9 is:
and (4) forming the optimal sequence path from each user to d in the user group U into a group, and assigning a variable OGR.
In step S7, initializing variable OGR to null; the initialization variable radius is infinite.
The query path of each user forms a feasible group path of the user group; starting point and each point of interest p selected in the visiting orderiAnd the endpoints also constitute the query path for the user.
In step S5, the minimum path cost in the feasible set of paths is the minimum filtering radius.
As shown in fig. 1, definition 1 (road network RN): road network RN is (V, E). The road network is an undirected graph, wherein V is the point set of RN, E is the edge set of RN, and for the edge E belonging to E, w (E) is the weight of E.
Definition 2 (point of interest POI): the interest points are fixed points of a specific type on the road network, and the interest points with the same type can be regarded as a type of interest points.
For example, the points of interest belonging to the supermarket category in FIG. 1 include { s1, s2, s3}, the points of interest belonging to the gas station category include { g1, g2, g3}, and the points of interest belonging to the restaurant category are { r1, r2 }.
Definition 3 (path Route): defining a path R in a road network<v1,v2,...,vn>Wherein v1, v2, vn is a fixed point in a road network, and edges (vi-1, vi),2<＝i<N belongs to the set of edges of the road network, and the weight of the path R is
Define 4 (optimal order path OSR): given a start point s and an end point d and an interest point sequence C which needs to be sequentially visited, C1, C2.., cm >, if a path R is s, p1, p 2.., pm, d > exists and the interest point class satisfying pi is ci (1< ═ i < ═ m), R is a sequence path SR, and the optimal sequence path is a path with the smallest weight among all sequence paths.
Define 5 (query OGSRMQ based on meeting point optimal group order path): given a set of users U ═ U1, U2.., un } and a set of candidate meeting points D ═ D1,d 2.., dk }, each user ui corresponding to a departure point si and a sequence of points of interest to be visited in turn
The search for a meeting point d and a set of order paths based on the optimal set of order paths for the meeting point enables the set of users to meet the meeting most quickly. The meeting point that satisfies such a query is called the best meeting point, and the corresponding set of order paths is called the best set of order paths.
A specific optimal group order route query example based on meeting points is given below in conjunction with fig. 1:
1. acquiring query parameters: the user group U is { U1, U2}, the target meeting point set D is { D1, D2, D3, D4, D5, D6}, the departure point of the user U1 is U1 and the access sequence of the corresponding interest points is < restaurant, supermarket >, and the departure point of the user U2 is U2 and the access sequence of the corresponding interest points is < gas station, supermarket >;
2. initializing an inquiry result OGR to be null, and radius to be infinite;
3. selecting an initial candidate meeting point as d 1;
4. checking a candidate point d1, obtaining the greedy path of a user u1 as < u1, r1, s1 and d1>, obtaining the greedy path of a user u2 as < u2, g1, s2 and d1>, updating the OGR into the greedy paths of the two users with the cost of 14 and the updating radius of 14;
5. due to max { L (u)1,d6),L(u2,d6) 16 > 14, filter out d 6;
6. updating radius to 12 by the obtained minimum filtering radius of the candidate meeting point d 2;
7. d5 is filtered off;
8. selecting a candidate meeting point d1 because the remaining candidate meeting point set is not empty, checking d1, and calculating the optimal sequence paths of the user u1 and the users u2 to d1 respectively, wherein radius is not updated because the maximum path cost is 14< 12;
9. checking d3 in the same way of the previous step, wherein the optimal sequence path of OGR updated to u1 is < u1, r2, s3, d3> with cost 10 and the optimal sequence path of user u2 is < u2, g3, s3, d3> with cost 9, updating radius to 10 and filtering out d 4;
10. and returning the optimal solution OGR when the residual candidate meeting point set is empty.
The same or similar reference numerals correspond to the same or similar parts;
the positional relationships depicted in the drawings are for illustrative purposes only and are not to be construed as limiting the present patent;
it should be understood that the above-described embodiments of the present invention are merely examples for clearly illustrating the present invention, and are not intended to limit the embodiments of the present invention. Other variations and modifications will be apparent to persons skilled in the art in light of the above description. And are neither required nor exhaustive of all embodiments. Any modification, equivalent replacement, and improvement made within the spirit and principle of the present invention should be included in 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 dinitialWherein L (u)iD) represents user uiShortest path cost to point d, cdIs 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 orderiLet the departure point go to piIs added to piThe 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 areiAnd 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.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202010673378.3A CN112097782B (en) | 2020-07-14 | 2020-07-14 | Optimal group order path circular filtering query method based on meeting point |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202010673378.3A CN112097782B (en) | 2020-07-14 | 2020-07-14 | Optimal group order path circular filtering query method based on meeting point |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN112097782A CN112097782A (en) | 2020-12-18 |
| CN112097782B true CN112097782B (en) | 2022-04-08 |
Family
ID=73750101
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN202010673378.3A Active CN112097782B (en) | 2020-07-14 | 2020-07-14 | Optimal group order path circular filtering query method based on meeting point |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN112097782B (en) |
Family Cites Families (8)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS6232516A (en) * | 1985-08-06 | 1987-02-12 | Shinko Electric Co Ltd | Optimum route searching method for moving robot |
| US8566030B1 (en) * | 2011-05-03 | 2013-10-22 | University Of Southern California | Efficient K-nearest neighbor search in time-dependent spatial networks |
| CN104992044B (en) * | 2015-05-26 | 2018-01-30 | 深圳大学 | Optimal more meeting point method for searching path and device applied to real-time rideshare |
| CN105387864B (en) * | 2015-10-15 | 2021-02-26 | 深圳市城市交通规划设计研究中心股份有限公司 | Path planning device and method |
| CN106446242B (en) * | 2016-10-12 | 2019-10-25 | 太原理工大学 | A kind of efficient multiple-fault diagnosis optimal path inquiry method |
| CN109974732B (en) * | 2019-03-28 | 2022-11-15 | 东北大学 | Top-k multi-request path planning method based on semantic perception |
| CN110031017B (en) * | 2019-04-29 | 2024-06-11 | 辽宁艾特斯智能交通技术有限公司 | Multi-target optimal path planning method for vehicle and machine |
| CN110826761B (en) * | 2019-09-19 | 2023-04-07 | 中山大学 | Optimal group order path query method based on meeting points |
-
2020
- 2020-07-14 CN CN202010673378.3A patent/CN112097782B/en active Active
Also Published As
| Publication number | Publication date |
|---|---|
| CN112097782A (en) | 2020-12-18 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| Aydin et al. | A navigation and reservation based smart parking platform using genetic optimization for smart cities | |
| CN106017490B (en) | A kind of map-indication method, navigation server and navigation system | |
| CN109344529A (en) | A kind of customization public bus network design method based on two-phase heuristic algorithm | |
| US8744770B2 (en) | Path oracles for spatial networks | |
| CN102506849B (en) | Method for optimizing shortest path with restraint | |
| WO2016188151A1 (en) | Searching method and device for optimal route of multiple meeting point applicable for real-time ride-sharing | |
| CN106203725A (en) | Door-to-door trip route scheme personalized recommendation method based on heuristic search | |
| CN106767826A (en) | A kind of indoor method across floor path navigation | |
| CN111272187B (en) | Optimal driving path planning method and system based on improved A-star algorithm | |
| Aissat et al. | A priori approach of real-time ridesharing problem with intermediate meeting locations | |
| US20200349660A1 (en) | Method and an Apparatus for Searching or Comparing Sites Using Routes or Route Lengths Between Sites and Places Within a Transportation System | |
| CN110095134A (en) | It is a kind of using the preference of user as the method and system of the path planning of core and navigation | |
| Khan et al. | Ride-sharing is about agreeing on a destination | |
| Du et al. | GAQ-EBkSP: a DRL-based urban traffic dynamic rerouting framework using fog-cloud architecture | |
| CN112328877B (en) | Skyline inquiry method for multiple users on time-dependent road network | |
| Chou et al. | A clonal selection algorithm for energy-efficient mobile agent itinerary planning in wireless sensor networks | |
| Nannicini et al. | Shortest paths on dynamic graphs | |
| KR102185334B1 (en) | PROCESSING METHOD OF ε-DISTANCE JOIN QUERIES IN ROAD NETWORKS AND DEVICE THAT PROCESSES ε-DISTANCE JOIN QUERIES IN ROAD NETWORKS | |
| US20080133484A1 (en) | Device, Method and Program for Managing Area Information | |
| CN112097782B (en) | Optimal group order path circular filtering query method based on meeting point | |
| CN107677277A (en) | A kind of determining method of path based on dijkstra's algorithm | |
| CN112507047B (en) | Optimal ordered path query method based on interest point preference | |
| CN110826761B (en) | Optimal group order path query method based on meeting points | |
| da Silva et al. | Combining k-means method and complex network analysis to evaluate city mobility | |
| CN113465612B (en) | Parallel path planning method and system based on double-layer index |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| PB01 | Publication | ||
| PB01 | Publication | ||
| SE01 | Entry into force of request for substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| GR01 | Patent grant | ||
| GR01 | Patent grant |