CN110826761B - Optimal group order path query method based on meeting points - Google Patents
Optimal group order path query method based on meeting points Download PDFInfo
- Publication number
- CN110826761B CN110826761B CN201910884212.3A CN201910884212A CN110826761B CN 110826761 B CN110826761 B CN 110826761B CN 201910884212 A CN201910884212 A CN 201910884212A CN 110826761 B CN110826761 B CN 110826761B
- Authority
- CN
- China
- Prior art keywords
- optimal
- query
- path
- algorithm
- points
- 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
- G06—COMPUTING; CALCULATING OR COUNTING
- G06Q—INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR
- G06Q10/00—Administration; Management
- G06Q10/04—Forecasting or optimisation specially adapted for administrative or management purposes, e.g. linear programming or "cutting stock problem"
- G06Q10/047—Optimisation of routes or paths, e.g. travelling salesman problem
-
- Y—GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
- Y02—TECHNOLOGIES OR APPLICATIONS FOR MITIGATION OR ADAPTATION AGAINST CLIMATE CHANGE
- Y02D—CLIMATE CHANGE MITIGATION TECHNOLOGIES IN INFORMATION AND COMMUNICATION TECHNOLOGIES [ICT], I.E. INFORMATION AND COMMUNICATION TECHNOLOGIES AIMING AT THE REDUCTION OF THEIR OWN ENERGY USE
- Y02D10/00—Energy efficient computing, e.g. low power processors, power management or thermal management
Landscapes
- Business, Economics & Management (AREA)
- Human Resources & Organizations (AREA)
- Engineering & Computer Science (AREA)
- Strategic Management (AREA)
- Economics (AREA)
- Marketing (AREA)
- Game Theory and Decision Science (AREA)
- Entrepreneurship & Innovation (AREA)
- Development Economics (AREA)
- Operations Research (AREA)
- Quality & Reliability (AREA)
- Tourism & Hospitality (AREA)
- Physics & Mathematics (AREA)
- General Business, Economics & Management (AREA)
- General Physics & Mathematics (AREA)
- Theoretical Computer Science (AREA)
- Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
Abstract
The invention discloses an optimal group order path query method based on meeting points, and belongs to the technical field of path planning. The invention can efficiently process the optimal group sequence path query based on meeting points in a multi-user query scene, provides an OGSRM algorithm framework, can solve the optimal group sequence path based on the meeting points and can also quickly solve a corresponding high-quality approximate solution, and in addition, the framework has high flexibility and can use different candidate point heuristic functions, an optimal sequence path algorithm and an approximate optimal sequence path algorithm.
Description
Technical Field
The invention relates to the technical field of path planning, in particular to an optimal group order path query method based on meeting points.
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.
Disclosure of Invention
The optimal group order path query method based on the meeting point is high in query efficiency.
In order to achieve the technical effects, the technical scheme of the invention is as follows:
an optimal group order path query method based on meeting points comprises the following steps:
s1: initializing OGSRM algorithm frame parameters lambda, mu, h, ALGO-OSR and ALGO-AOSR;
s2: initializing the optimal set of order path variables routes to null;
s3: calculating heuristic function values of all meeting candidate points by using h and arranging the candidate points in an ascending order according to the heuristic function values;
s4: sequentially checking each candidate point d according to the candidate point arrangement sequence generated in the S3, if the lambda times of the heuristic function values of d are greater than or equal to the maximum value of the path in the current routes or all the candidate points are checked completely, turning to the S6, and otherwise, continuing to execute the S4 after executing the S5;
s5: the first mu x 100% of users use ALGO-OSR algorithm to query, the rest users use ALGO-AOSR algorithm to query, and if the maximum value in the paths of the user group in the query result is smaller than the maximum value in the paths of the routes, the routes is updated to be the current query result;
s6: the optimal group order path routes is returned.
Further, the specific process for initializing the framework parameters of the OGSRM algorithm in step S1 is as follows:
the stop parameter λ is set to be greater than or equal to 1.0; accurately limiting the value of the parameter mu to be 0 to 1, wherein the larger the value is, the more accurate the result is; the heuristic function h of the candidate point comprises SP (service provider) -the maximum value of the shortest paths from the starting point of all query users to the candidate point, L2 OSR-the maximum value of the Euclidean optimal sequence paths obtained by all the query users or other heuristic functions; .
Further, in the specific process of initializing OGSRM algorithm frame parameters in the step S1, ALGO-OSR is set as any optimal order path query algorithm; ALGO-AOSR is set as any approximate optimal order path query algorithm.
Further, the candidate point heuristic function value calculating process in step S3 is:
if the parameter h is SP, the shortest path distance from the user to the candidate point is calculated for each user, and the maximum value in all the users is taken as the heuristic function value of the candidate point.
Further, if the parameter h is L2OSR, calculating the Euclidean optimal sequence path distance from each user to the candidate point, and selecting the maximum value as a heuristic function value of the candidate point.
Further, the heuristic function value calculation process of candidate points in step S3 is:
if h is other heuristic functions, the function value from each user to the candidate point is calculated in the same way, the calculation mode is defined by h, and the maximum value is taken as the heuristic function value of the candidate point.
Compared with the prior art, the technical scheme of the invention has the beneficial effects that:
1. the invention provides an OGSRM algorithm framework which can efficiently process optimal group order path query based on meeting points;
2. the OGSRM algorithm framework can not only provide the optimal solution of the optimal group order path based on the meeting point, but also can quickly provide a high-quality approximate solution;
3. the OGSRM algorithm framework has strong flexibility, and different candidate point heuristic functions, an optimal sequence path algorithm and an approximate optimal sequence path algorithm can be used.
Drawings
Fig. 1 is a schematic diagram of an optimal path query process in the embodiment of the present invention.
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.
Example 1
An optimal group order path query method based on meeting points comprises the following steps:
s1: initializing OGSRM algorithm frame parameters lambda, mu, h, ALGO-OSR and ALGO-AOSR;
s2: initializing the optimal set of order path variables routes to null;
s3: calculating heuristic function values of all meeting candidate points by using h, and arranging the candidate points in an ascending order according to the heuristic function values;
s4: sequentially checking each candidate point d according to the candidate point arrangement sequence generated in the S3, if the lambda times of the heuristic function value of d is larger than or equal to the maximum value of the path in the current routes or all the candidate points are checked completely, turning to the S6, and if not, continuing to execute the S4 after executing the S5;
s5: the first mu x 100% of users use ALGO-OSR algorithm to inquire, the rest users use ALGO-AOSR algorithm to inquire, and if the maximum value in the paths of the user group in the result obtained by inquiry is smaller than the maximum value in the paths of the routes, the routes is updated to be the current inquiry result;
s6: the optimal group order path routes is returned.
The specific process for initializing the frame parameters of the OGSRM algorithm in the step S1 is as follows:
the stop parameter λ is set to be greater than or equal to 1.0; the value of the accurate limiting parameter mu is 0 to 1, and the larger the value is, the more accurate the result is; the heuristic function h of the candidate point comprises SP, the maximum value of the shortest paths from the starting points of all query users to the candidate point, L2OSR, the maximum value of the Euclidean optimal sequence paths obtained by all the query users or other heuristic functions; .
In the specific process of initializing OGSRM algorithm frame parameters in the step S1, setting ALGO-OSR as a path query algorithm in any optimal sequence; ALGO-AOSR is set as any approximate optimal order path query algorithm.
In step S3, the heuristic function value calculation process of the candidate points is as follows:
if the parameter h is SP, the shortest path distance from the user to the candidate point is calculated for each user, and the maximum value in all the users is taken as the heuristic function value of the candidate point.
And if the parameter h is L2OSR, calculating the Euclidean optimal sequence path distance from each user to the candidate point, and selecting the maximum value as a heuristic function value of the candidate point.
If h is other heuristic function, the function value from each user to the candidate point is calculated in the same way, the calculation mode is defined by h, and the maximum value is taken as the heuristic function value of the candidate point.
Example 2
As shown in fig. 1, definition 1 (road network RN): road network RN = (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 represented as 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.
In FIG. 1, the points of interest belonging to the supermarket category 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 =ina network<v1,v2,...,vn>Wherein v1, v2, vn is a fixed point in the road network, edge (vi-1, vi), 2<＝i<Where n belongs to an edge set of a road network, and the weight of a route R is w (R) = n
Define 4 (optimal order path OSR): given a start point s and an end point d and an interest point order C = < C1, C2,. And cm > that needs to be visited in sequence, if a path R = < s, p1, p2,. And pm, d > exists and the interest point category satisfying pi is ci (1 < = i < = m), then R is an order path SR, and the optimal order path is the path with the smallest weight among all order 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, D2.,. Dk }, each user ui corresponds to a departure point si and a point of interest order that needs to be visited in turn
Based on the optimal group order path query of the meeting pointA meeting point d and a set of order paths enable the set of users to meet 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:
acquiring query parameters: a user group U = { U1, U2}, a target meeting point set D = { D1, D2, D3, D4, D5, D6}, the departure point of the user U1 is U1 and the corresponding access sequence of the interest points is < restaurant, supermarket >, and the departure point of the user U2 is U2 and the corresponding access sequence of the interest points is < gas station, supermarket >;
initialization parameters λ =1.0, μ =1.0, h = sp, ALGO-OSR is PNE (an OSR algorithm), ALGO-AOSR is null (here, it is not necessary to use an approximate OSR algorithm);
initializing a query result routes to be null;
calculating heuristic function values of candidate points, obtaining h (d 1) =2,h (d 2) =3,h (d 3) =9,h (d 4) =10, h (d 5) =13, h (d 6) =16, and determining the candidate points checked by the OGSRM algorithm framework as d1, d2, d3, d4, d5 and d6 in sequence;
checking the candidate point d1, solving the cost of the optimal sequence path of the user u1 being < u1, r1, s1, d1> as 14, solving the cost of the optimal sequence path of the user u2 being < u2, g1, s2, d1> as 11, and updating routes;
checking a candidate point d2, obtaining that the cost of the optimal sequence path of the user u1 is < u1, r1, s1, d2> is 12 because 1.0 × h (d 2) =3< -14, obtaining that the cost of the optimal sequence path of the user u2 is < u2, g1, s2, d2> is 12, and updating routes because the maximum value in the sequence paths of the current group is 12 less than 14;
checking the candidate point d3, and as with the process 6, updating routes to u1 with the cost of < u1, r2, s3, d3> being 10 and the cost of < u2, g3, s3, d3> being 9;
when the candidate point d4 is checked, since 1.0 × h (d 4) =10 ≧ 10, the checking process ends, and the OGSRM algorithm framework returns the optimal group order paths.
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. This need not be, nor should it be 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 (5)
1. An optimal group order path query method based on meeting points is characterized by comprising the following steps:
step S1: initializing OGSRM algorithm frame parameters lambda, mu, h, ALGO-OSR and ALGO-AOSR, wherein lambda is a stopping parameter, mu is an accurate limiting parameter, h is a heuristic function of candidate points, ALGO-OSR is a path query algorithm in any optimal order, and ALGO-AOSR is a path query algorithm approximate to any optimal order;
step S2: initializing the optimal set of order path variables routes to null;
and step S3: calculating heuristic function values of all meeting candidate points by using h and arranging the candidate points in an ascending order according to the heuristic function values;
and step S4: sequentially checking each candidate point d according to the candidate point arrangement sequence generated in the S3, if the lambda times of the heuristic function values of d are greater than or equal to the maximum value of the path in the current routes or all the candidate points are checked completely, turning to the S6, and otherwise, continuing to execute the S4 after executing the S5;
step S5: the first mu x 100% of users use ALGO-OSR algorithm to query, the rest users use ALGO-AOSR algorithm to query, and if the maximum value in the paths of the user group in the query result is smaller than the maximum value in the paths of the routes, the routes is updated to be the current query result;
step S6: the optimal group order path routes is returned.
2. The optimal group order path query method based on meeting points as claimed in claim 1, wherein the specific process of OGSRM algorithm frame parameter initialization in step S1 is:
the stop parameter λ is set to be greater than or equal to 1.0; accurately limiting the value of the parameter mu to be 0 to 1, wherein the larger the value is, the more accurate the result is; the heuristic function h of the candidate point comprises SP, the maximum value of the shortest paths from the starting point of all query users to the candidate point, L2OSR, the maximum value of the Euclidean optimal sequence paths obtained by all the query users or other heuristic functions.
3. The optimal group ordered path query method based on meeting points as claimed in claim 1, wherein in the specific process of OGSRM algorithm frame parameter initialization in step S1, ALGO-OSR is set as any optimal ordered path query algorithm; ALGO-AOSR is set as any approximate optimal order path query algorithm.
4. The method as claimed in claim 3, wherein the step S3 of calculating the heuristic function values of candidate points comprises:
if the parameter h is SP, the shortest path distance from the user to the candidate point is calculated for each user, and the maximum value in all the users is taken as the heuristic function value of the candidate point.
5. The optimal group sequential path query method based on meeting points as claimed in claim 4, wherein if the parameter h is L2OSR, calculating Euclidean optimal sequential path distance from each user to the candidate points, and selecting the maximum value as a heuristic function value of the candidate points.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201910884212.3A CN110826761B (en) | 2019-09-19 | 2019-09-19 | Optimal group order path query method based on meeting points |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201910884212.3A CN110826761B (en) | 2019-09-19 | 2019-09-19 | Optimal group order path query method based on meeting points |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN110826761A CN110826761A (en) | 2020-02-21 |
| CN110826761B true CN110826761B (en) | 2023-04-07 |
Family
ID=69548059
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN201910884212.3A Active CN110826761B (en) | 2019-09-19 | 2019-09-19 | Optimal group order path query method based on meeting points |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN110826761B (en) |
Families Citing this family (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN112097782B (en) * | 2020-07-14 | 2022-04-08 | 中山大学 | Optimal group order path circular filtering query method based on meeting point |
Citations (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN101833699A (en) * | 2009-03-12 | 2010-09-15 | 北京博懋易通科技有限公司 | Heuristic route segment path-finding method for ship route design |
| CN104236569A (en) * | 2013-06-21 | 2014-12-24 | 株式会社日立制作所 | Method and device for determining optimal meeting point |
| CN105956167A (en) * | 2016-05-19 | 2016-09-21 | 北京理工大学 | Dinner party place intelligent recommendation method and system |
| CN106845630A (en) * | 2017-02-23 | 2017-06-13 | 中国人民解放军国防科学技术大学 | Unordered process must be through the shortest path acquisition methods and device of point |
Family Cites Families (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US9689695B2 (en) * | 2014-09-19 | 2017-06-27 | Empire Technology Development Llc | Meeting point determination for group members |
| US10697789B2 (en) * | 2017-05-23 | 2020-06-30 | Uatc, Llc | Individualized risk routing for human drivers |
-
2019
- 2019-09-19 CN CN201910884212.3A patent/CN110826761B/en active Active
Patent Citations (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN101833699A (en) * | 2009-03-12 | 2010-09-15 | 北京博懋易通科技有限公司 | Heuristic route segment path-finding method for ship route design |
| CN104236569A (en) * | 2013-06-21 | 2014-12-24 | 株式会社日立制作所 | Method and device for determining optimal meeting point |
| CN105956167A (en) * | 2016-05-19 | 2016-09-21 | 北京理工大学 | Dinner party place intelligent recommendation method and system |
| CN106845630A (en) * | 2017-02-23 | 2017-06-13 | 中国人民解放军国防科学技术大学 | Unordered process must be through the shortest path acquisition methods and device of point |
Non-Patent Citations (1)
| Title |
|---|
| 基于多点协作的团队出行路径优化算法;邱吉刚 等;《计算机应用》;20150731;第35卷(第7期);第2093-2095页 * |
Also Published As
| Publication number | Publication date |
|---|---|
| CN110826761A (en) | 2020-02-21 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN105430706B (en) | A kind of wireless sensor network routing optimization method based on improvement particle swarm algorithm | |
| CN107018031B (en) | Rapid optimization method for Internet of vehicles based on fog calculation | |
| CN102506849B (en) | Method for optimizing shortest path with restraint | |
| CN109102124B (en) | Dynamic multi-target multi-path induction method and system based on decomposition and storage medium | |
| EP3112808B1 (en) | Route search apparatus, route search method, and program | |
| CN106767826A (en) | A kind of indoor method across floor path navigation | |
| CN108038576A (en) | Based on the logistics distribution routing resource and system for improving dijkstra's algorithm | |
| CN109656264A (en) | For being generated to the method implemented by computer and system in the path 3D in landing site for aircraft | |
| CN107332770B (en) | Method for selecting routing path of necessary routing point | |
| CN109995580B (en) | VN mapping method based on GA _ PSO hybrid algorithm in 5G network slice | |
| CN105335524B (en) | A kind of graph search method applied to extensive irregular eutectic data | |
| Liu et al. | Effects of information heterogeneity in Bayesian routing games | |
| CN102916879A (en) | Rapid route convergence method | |
| CN112819211A (en) | Multi-region scheduling route planning method based on ant colony iterative algorithm | |
| CN110826761B (en) | Optimal group order path query method based on meeting points | |
| CN108647837A (en) | Consider the inert network traffic flow prediction technique of traveler Path selection | |
| CN111476389A (en) | Method and device for pre-estimating order receiving waiting time | |
| KR20110116568A (en) | Routing method based on spanning tree in wireless sensor and actor network | |
| CN111915078A (en) | Data-driven flexible cigarette distribution line planning method and system | |
| CN110487293A (en) | A kind of efficient and privacy paths planning method based on extensive road network | |
| CN112507047B (en) | Optimal ordered path query method based on interest point preference | |
| Celsi et al. | On the many-to-many carpooling problem in the context of multi-modal trip planning | |
| CN112097782B (en) | Optimal group order path circular filtering query method based on meeting point | |
| CN110472789A (en) | A kind of logistics distribution shortest path first solved based on Grobner bases | |
| Yousefi et al. | The optimal routing of cars in the car navigation system by taking the combination of divide and conquer method and ant colony algorithm into consideration |
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 |