CN119573763A - A pathfinding method, system and computer program product based on iterative path rights - Google Patents
A pathfinding method, system and computer program product based on iterative path rights Download PDFInfo
- Publication number
- CN119573763A CN119573763A CN202510130890.6A CN202510130890A CN119573763A CN 119573763 A CN119573763 A CN 119573763A CN 202510130890 A CN202510130890 A CN 202510130890A CN 119573763 A CN119573763 A CN 119573763A
- Authority
- CN
- China
- Prior art keywords
- road
- node
- iterative
- current
- road network
- 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.)
- Pending
Links
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/3453—Special cost functions, i.e. other than distance or default speed limit of road segments
- G01C21/3492—Special cost functions, i.e. other than distance or default speed limit of road segments employing speed data or traffic data, e.g. real-time or historical
Landscapes
- Engineering & Computer Science (AREA)
- Radar, Positioning & Navigation (AREA)
- Remote Sensing (AREA)
- Automation & Control Theory (AREA)
- Physics & Mathematics (AREA)
- General Physics & Mathematics (AREA)
- Traffic Control Systems (AREA)
Abstract
The invention discloses a road searching method, a system and a computer program product based on iterative road weights, wherein the method comprises the steps of obtaining road network data; the method comprises the steps of constructing a road network architecture comprising road network nodes and road segments according to road network data, setting node attributes and road segment attributes according to the road network data, calculating road weights based on priority queues and iteration expansion according to the road network architecture, and obtaining an optimal shortest path from a starting node to a target node. According to the technical scheme, the shortest paths are calculated by setting the road weight and the vehicle passing type in an iterative manner, the optimal vehicle is selected to execute the task more quickly, the shortest paths of all vehicles running can be calculated in a very short time, the calculation efficiency is greatly improved, the calculation amount can be reduced, the iteration efficiency is improved by setting the evaluation function for the nodes, the node processing efficiency can be improved by using parallel calculation, the calculation speed is improved, and the path planning result is obtained more quickly.
Description
Technical Field
The present invention relates to the field of path planning, and in particular, to a path finding method, system and computer program product based on iterative path rights.
Background
The traditional path finding algorithm comprises an A-type algorithm, a Dijkstra algorithm and the like, has respective defects when calculating the shortest path, for example, the shortest path cannot be distinguished for various vehicle types, the path weights cannot be additionally set, part of performance is sacrificed to ensure accuracy, the efficiency for a sparse graph is lower, and the like. Therefore, a routing algorithm suitable for various vehicle types, high efficiency and high robustness is urgently needed.
Disclosure of Invention
In view of the above-mentioned shortcomings of the prior art, the present invention provides a road searching method based on iterative road weights, which can calculate the shortest path of all vehicles in a very short time by setting road weights and vehicle passing types and iteratively expanding and calculating the shortest path.
In order to achieve the above purpose, the embodiment of the present invention adopts the following technical scheme:
A way finding method based on iterative road weight comprises the following steps:
Acquiring road network data;
Constructing a road network architecture comprising road network nodes and road sections according to the road network data;
setting node attributes and road section attributes including road weights according to road network data;
Calculating road weights based on the priority queues and the iteration expansion according to the road network architecture, the node attributes and the road section attributes, and obtaining an optimal shortest path from the initial node to the target node;
and carrying out normalization calculation on road related factors including road section distance, number of lanes, congestion condition and road speed limit, and synthesizing the road related factors into road weights.
According to one aspect of the invention, the road network data comprises road network node information and road network segment information, and the obtaining the road network data comprises the steps of utilizing a multi-source sensor to collect the road network data and obtaining the road network node information and the road network segment information.
According to one aspect of the invention, the node attribute comprises a node name, a distance from the node to the starting node, whether the node is accessed, a road segment set to which the node belongs and a precursor node, and the road segment attribute further comprises a road segment source node, a road segment terminal node and a vehicle type through which the road segment can pass.
According to one aspect of the present invention, the calculating the road weight based on the priority queue and the iterative expansion according to the road network architecture, the node attribute and the road segment attribute, and obtaining the optimal shortest path from the start node to the target node includes:
acquiring a starting node, a target node and a user vehicle type;
setting a priority queue based on thread security;
performing initialization operation;
Repeating iterative expansion calculation road weight until calculation is completed, and obtaining an optimal shortest path set;
and inverting the shortest path segment set to obtain an optimal shortest path from the initial node to the target node.
In accordance with one aspect of the invention, the performing an initialization operation includes:
initializing a graph, adding all nodes and road segment sets, and setting the distance a between all nodes and a starting node to be infinity;
initializing a queue to be an empty queue;
Initializing a starting node, and setting the distance from the starting node to be 0;
Resetting all nodes to an unaccessed state;
the starting node is added to the queue.
According to one aspect of the present invention, the repeatedly iterating and expanding the calculation path weights until the calculation is completed, and obtaining the optimal shortest path set includes:
The current node in the queue is dequeued and is set to be in an accessed state;
selecting one of the road sections connected with the current node as the current road section, and skipping the current road section if the terminal node of the current road section is in the accessed state;
If the user vehicle type is not matched with the vehicle type which can be passed by the current road section, skipping the current road section;
acquiring an iteration distance b from a final node to a starting node of a current road section according to the road weight of the current road section;
If b < a, updating a to b, and updating a precursor node of the current road section terminal node to be the current node;
If the current road section terminal node is not in the queue, adding the current road section terminal node into the queue;
selecting the next road section connected with the current node as the current road section, and repeatedly calculating the steps until all road sections connected with the current node are traversed and calculated;
repeating the steps of iterative computation until the current node dequeued in the queue is the target node, and ending the iterative computation process.
According to one aspect of the present invention, the routing method based on iterative routing rights further includes:
setting an evaluation function for the node, and obtaining a node evaluation score;
acquiring the priority of all the road sections connected with the current node according to the node evaluation score;
and selecting the current road section according to the priority.
According to one aspect of the present invention, the routing method based on iterative routing rights further includes:
And parallelizing and processing the road sections connected with the current node.
A routing system based on iterative road weights, a routing method based on iterative road weights as described above, comprising:
the acquisition module is used for acquiring road network data;
The road network construction module is used for constructing a road network framework comprising road network nodes and road sections according to the road network data;
the road network setting module is used for setting node attributes and road section attributes according to the road network data;
and the iterative calculation module is used for calculating the road weight based on the priority queue and the iterative expansion according to the road network architecture, the node attribute and the road section attribute, and obtaining the optimal shortest path from the initial node to the target node.
A computer program product comprising a computer program which when executed implements the steps of an iterative road-finding method as described above.
The implementation of the invention has the advantages that:
The invention provides a road searching method based on iterative road weights, which comprises the steps of iteratively expanding and calculating shortest paths through setting road weights and vehicle passing types, more rapidly selecting optimal vehicles to execute tasks, calculating the running shortest paths of all vehicles in extremely short time, greatly improving calculation efficiency, reducing calculation amount and improving iteration efficiency through setting evaluation functions for nodes, improving node processing efficiency through parallel calculation, improving calculation speed and more rapidly obtaining path planning results.
Drawings
In order to more clearly illustrate the technical solutions of the embodiments of the present invention, the drawings that are needed in the embodiments will be briefly described below, and it is obvious that the drawings in the following description are only some embodiments of the present invention, and other drawings may be obtained according to these drawings without inventive effort for a person skilled in the art.
Fig. 1 is a flowchart of a way finding method based on iterative road weights according to an embodiment of the present invention.
Detailed Description
The following description of the embodiments of the present invention will be made clearly and completely with reference to the accompanying drawings, in which it is apparent that the embodiments described are only some embodiments of the present invention, but not all embodiments. All other embodiments, which can be made by those skilled in the art based on the embodiments of the invention without making any inventive effort, are intended to be within the scope of the invention.
Example 1
As shown in fig. 1, a routing method based on iterative road weights includes the following steps:
S1, road network data are acquired.
The road network data comprises road network node information and road network segment information.
In practical applications, road network nodes generally refer to intersections where two or more roads in a road network cross, boundary sections where geometric elements of the roads change significantly, and junctions (e.g. cities and towns) where multiple roads meet. In the road network model, a node is also understood as an intersection, a highway entrance, a starting point, an ending point, etc., and a point where a road characteristic changes or a steering operation is possible.
The road network node has various attributes, which have important significance in analysis and path planning of the traffic network, and mainly comprises the following components:
(1) Node identification-each node has a unique identification in the national road network, which facilitates accurate identification of each node in data processing and path planning.
(2) The node coordinates (longitude and latitude) are longitude and latitude information of the position of the node, and are basic data of navigation and positioning.
(3) The node type is that the node can be a main node or a sub node and is classified according to the position and importance of the node in the road network.
(4) Intersection information, including intersection forms, traffic light information, guideboard information and the like, which are critical to path planning and traffic management.
(5) And (3) connecting the road segments, namely listing all the road segments connected with the node, and numbering and type information of the road segments.
(6) And the condition of the adjacent node, namely, the information describing other nodes adjacent to the node, is helpful for knowing the overall structure and connectivity of the road network.
In practical applications, a road network segment refers to a road segment between two nodes in a network, and is generally composed of a plurality of adjacent nodes and connecting lines between the adjacent nodes. These road segments form the basic skeleton of the traffic network and are the infrastructure for vehicles and pedestrians to pass through.
Road network segments have various attributes reflecting the basic characteristics and traffic conditions of the segments, including mainly:
(1) Road segment ID-each road segment has a unique identification in the road network, which facilitates accurate identification of each road segment in data processing and path planning.
(2) Road segment length-the physical length of a road segment is typically in meters or kilometers.
(3) The number of traffic lanes is the number of traffic lanes on the road section and reflects the traffic capacity of the road section.
(4) Road attributes including road name, road type (e.g., expressway, national road, province road, county road, etc.), road width, lane number information, speed limit value, etc.
(5) Road characteristics such as road width, lane division, machine (vehicle lane) non (vehicle lane) division information, road technical grade, type of vehicles allowed to pass by the road, and the like.
(6) Traffic characteristics, namely traffic impedance of a road segment, i.e. a quantitative indicator of how hard a vehicle is to travel along the road segment, may generally be measured by using travel time, travel cost or some combination of the two as a measure, which can reflect traffic congestion conditions.
(7) And connecting node information, namely listing all nodes connected with the road section, and identifying and position information of the nodes.
The acquisition of the road network data comprises the steps of acquiring the road network data by utilizing a multi-source sensor and acquiring road network node information and road network segment information.
In practical applications, road network data may be collected by using vehicle-mounted sensors, such as GPS locators, cameras, laser radars (LiDAR), etc., which may be mounted on vehicles to collect road information in real time as the vehicles travel. Secondly, ground sensors can also be used for monitoring road network conditions and collecting road network data, such as geomagnetic sensors, pressure sensors and the like, and the devices are usually deployed at specific positions of roads and used for monitoring parameters such as traffic flow, vehicle speed and the like. In addition, a remote sensing sensor, such as a satellite image sensor, can be used for shooting the ground in a large range and high precision from high altitude to acquire road information.
The mode of data collection of the sensor comprises real-time collection and timing collection. The road network data which changes at any time, such as traffic state, needs to be collected in real time, and certain road information which needs to be updated regularly, such as road maintenance, traffic sign replacement, and the like, can be updated in a periodical collection mode.
S2, constructing a road network architecture comprising road network nodes and road sections according to the road network data.
In practical applications, the road network architecture may be implemented by adopting data types such as adjacency matrix, adjacency table, graph object-oriented graph database, and the like. The adjacency matrix is suitable for a graph with a small number of vertexes and is dense, and the adjacency table is suitable for a graph with a large number of vertexes and is sparse. The object-oriented representation of the graph can use classes and objects to represent vertices and edges, and attributes and methods can be added conveniently, which is more intuitive and flexible. For large complex graph structures, specialized graph databases (e.g., neo4 j) may be used for storage and querying, which provide efficient graph traversal and querying functions.
And S3, setting node attributes and road section attributes according to the road network data.
The node attributes comprise a node name, a distance between the node and a starting node, whether the node is accessed, a road section set to which the node belongs and a precursor node, and the road section attributes comprise a road section source node, a road section terminal node, road rights and a vehicle type through which a road section can pass.
In practical application, road related factors such as road section distance, number of traffic lanes, congestion condition, road speed limit and the like can be normalized and calculated to be synthesized into road weights as comprehensive factors influencing vehicle running time.
And S4, calculating the road weight based on the priority queue and the iteration expansion according to the road network architecture, the node attribute and the road section attribute, and obtaining the optimal shortest path from the initial node to the target node.
The step S4 includes:
s41, acquiring a starting node, a target node and a user vehicle type.
The starting node and the target node are the starting address and the target address of the vehicle running.
S42, setting a priority queue based on thread safety.
The priority queue is used for storing nodes needing to perform calculation operations, and one node is fetched from the priority queue at a time to perform calculation operations.
S43, performing initialization operation.
Step S43 includes:
1. initializing a graph, adding all nodes and road segment sets, and setting the distance a between all nodes and a starting node to be infinity.
Note that the distance referred to herein is not simply a measure of the length of the journey, but rather a measure of the time it takes for the vehicle to travel.
2. The initialization queue is an empty queue.
3. Initializing a starting node, and setting the distance from the starting node to be 0.
4. Reset all nodes to the unaccessed state.
5. The starting node is added to the queue.
The next step is to perform iterative computation, i.e. from the start node.
And S44, repeatedly iterating and expanding the calculation route weight until the calculation is completed, and obtaining the optimal shortest path segment set.
Step S44 includes:
1. the current node in the queue is dequeued and placed in the accessed state.
The current node is the node which should be accessed most preferentially in the priority queue. When iterative computation, the computation is started from the initial node.
2. And selecting one of the road sections connected with the current node as the current road section, and skipping the current road section if the final node of the current road section is in the accessed state.
3. If the user vehicle type does not match the vehicle type that the current road segment can pass, the current road segment is skipped.
4. And acquiring the iteration distance b from the final node to the initial node of the current road section according to the road weight of the current road section.
In practical application, the road weight is the distance measurement of the current road section, and b=the distance from the current node to the starting node+the road weight of the current road section.
5. If b < a, updating a to b, and updating the precursor node of the current road segment end node to be the current node.
A is the distance between the current road segment end node and the starting node which is recorded and saved before,
6. And if the current road segment terminal node is not in the queue, adding the current road segment terminal node into the queue.
7. And selecting the next road section connected with the current node as the current road section, and repeatedly calculating the steps 2-6 until all road sections connected with the current node are traversed and calculated.
8. And (3) repeating the steps 1-7 for iterative computation until the current node dequeued in the queue is the target node, and ending the iterative computation process.
And finally, backtracking from the target node, and obtaining the optimal shortest path set from the target node to the initial node according to the precursor nodes of each road section.
S45, inverting the shortest path set to obtain an optimal shortest path from the initial node to the target node.
In practical application, different road sections can be set in road sections operated by agv by adopting the method, different vehicles can be passed through, 10000 nodes take less than 1ms, and the operation is very efficient.
Preferably, the method further comprises:
setting an evaluation function for the node, and obtaining a node evaluation score;
acquiring the priority of all the road sections connected with the current node according to the node evaluation score;
and selecting the current road section according to the priority.
In practical application, the importance of each node or the distance from the target node can be evaluated by using an evaluation function, the evaluation score can be obtained, the priority of the road section can be set and adjusted according to the evaluation score, and the access sequence of the nodes can be adjusted. The node can be directly abandoned to be accessed if the evaluation score is lower than a certain threshold value, so that the iteration times can be reduced. When the road network is extremely complex, the calculation amount can be greatly reduced, the iteration efficiency is improved, and the shortest path is obtained more quickly.
The evaluation function can be constructed by adopting a logistic regression mode, a fully-connected neural network model and the like, and the model is trained by utilizing historical data and past experience. And when iterative computation is carried out, computing the evaluation score of the node according to the road network data and the node attribute data.
The method has the advantages that the shortest paths are calculated through setting the road weight and the vehicle passing type in an iterative expansion mode, the optimal vehicle is selected to execute tasks more quickly, the shortest paths of all vehicles in operation can be calculated in a very short time, the calculation efficiency is greatly improved, the calculation amount can be reduced, and the iteration efficiency is improved through setting the evaluation function for the nodes.
Example two
As shown in fig. 1, a routing method based on iterative road weights includes the following steps:
S1, road network data are acquired.
The road network data comprises road network node information and road network segment information.
In practical applications, road network nodes generally refer to intersections where two or more roads in a road network cross, boundary sections where geometric elements of the roads change significantly, and junctions (e.g. cities and towns) where multiple roads meet. In the road network model, a node is also understood as an intersection, a highway entrance, a starting point, an ending point, etc., and a point where a road characteristic changes or a steering operation is possible.
The road network node has various attributes, which have important significance in analysis and path planning of the traffic network, and mainly comprises the following components:
(1) Node identification-each node has a unique identification in the national road network, which facilitates accurate identification of each node in data processing and path planning.
(2) The node coordinates (longitude and latitude) are longitude and latitude information of the position of the node, and are basic data of navigation and positioning.
(3) The node type is that the node can be a main node or a sub node and is classified according to the position and importance of the node in the road network.
(4) Intersection information, including intersection forms, traffic light information, guideboard information and the like, which are critical to path planning and traffic management.
(5) And (3) connecting the road segments, namely listing all the road segments connected with the node, and numbering and type information of the road segments.
(6) And the condition of the adjacent node, namely, the information describing other nodes adjacent to the node, is helpful for knowing the overall structure and connectivity of the road network.
In practical applications, a road network segment refers to a road segment between two nodes in a network, and is generally composed of a plurality of adjacent nodes and connecting lines between the adjacent nodes. These road segments form the basic skeleton of the traffic network and are the infrastructure for vehicles and pedestrians to pass through.
Road network segments have various attributes reflecting the basic characteristics and traffic conditions of the segments, including mainly:
(1) Road segment ID-each road segment has a unique identification in the road network, which facilitates accurate identification of each road segment in data processing and path planning.
(2) Road segment length-the physical length of a road segment is typically in meters or kilometers.
(3) The number of traffic lanes is the number of traffic lanes on the road section and reflects the traffic capacity of the road section.
(4) Road attributes including road name, road type (e.g., expressway, national road, province road, county road, etc.), road width, lane number information, speed limit value, etc.
(5) Road characteristics such as road width, lane division, machine (vehicle lane) non (vehicle lane) division information, road technical grade, type of vehicles allowed to pass by the road, and the like.
(6) Traffic characteristics, namely traffic impedance of a road segment, i.e. a quantitative indicator of how hard a vehicle is to travel along the road segment, may generally be measured by using travel time, travel cost or some combination of the two as a measure, which can reflect traffic congestion conditions.
(7) And connecting node information, namely listing all nodes connected with the road section, and identifying and position information of the nodes.
The acquisition of the road network data comprises the steps of acquiring the road network data by utilizing a multi-source sensor and acquiring road network node information and road network segment information.
In practical applications, road network data may be collected by using vehicle-mounted sensors, such as GPS locators, cameras, laser radars (LiDAR), etc., which may be mounted on vehicles to collect road information in real time as the vehicles travel. Secondly, ground sensors can also be used for monitoring road network conditions and collecting road network data, such as geomagnetic sensors, pressure sensors and the like, and the devices are usually deployed at specific positions of roads and used for monitoring parameters such as traffic flow, vehicle speed and the like. In addition, a remote sensing sensor, such as a satellite image sensor, can be used for shooting the ground in a large range and high precision from high altitude to acquire road information.
The mode of data collection of the sensor comprises real-time collection and timing collection. The road network data which changes at any time, such as traffic state, needs to be collected in real time, and certain road information which needs to be updated regularly, such as road maintenance, traffic sign replacement, and the like, can be updated in a periodical collection mode.
S2, constructing a road network architecture comprising road network nodes and road sections according to the road network data.
In practical applications, the road network architecture may be implemented by adopting data types such as adjacency matrix, adjacency table, graph object-oriented graph database, and the like. The adjacency matrix is suitable for a graph with a small number of vertexes and is dense, and the adjacency table is suitable for a graph with a large number of vertexes and is sparse. The object-oriented representation of the graph can use classes and objects to represent vertices and edges, and attributes and methods can be added conveniently, which is more intuitive and flexible. For large complex graph structures, specialized graph databases (e.g., neo4 j) may be used for storage and querying, which provide efficient graph traversal and querying functions.
And S3, setting node attributes and road section attributes according to the road network data.
The node attributes comprise a node name, a distance between the node and a starting node, whether the node is accessed, a road section set to which the node belongs and a precursor node, and the road section attributes comprise a road section source node, a road section terminal node, road rights and a vehicle type through which a road section can pass.
In practical application, road related factors such as road section distance, number of traffic lanes, congestion condition, road speed limit and the like can be normalized and calculated to be synthesized into road weights as comprehensive factors influencing vehicle running time.
And S4, calculating the road weight based on the priority queue and the iteration expansion according to the road network architecture, the node attribute and the road section attribute, and obtaining the optimal shortest path from the initial node to the target node.
The step S4 includes:
s41, acquiring a starting node, a target node and a user vehicle type.
The starting node and the target node are the starting address and the target address of the vehicle running.
S42, setting a priority queue based on thread safety.
The priority queue is used for storing nodes needing to perform calculation operations, and one node is fetched from the priority queue at a time to perform calculation operations.
S43, performing initialization operation.
Step S43 includes:
1. initializing a graph, adding all nodes and road segment sets, and setting the distance a between all nodes and a starting node to be infinity.
Note that the distance referred to herein is not simply a measure of the length of the journey, but rather a measure of the time it takes for the vehicle to travel.
2. The initialization queue is an empty queue.
3. Initializing a starting node, and setting the distance from the starting node to be 0.
4. Reset all nodes to the unaccessed state.
5. The starting node is added to the queue.
The next step is to perform iterative computation, i.e. from the start node.
And S44, repeatedly iterating and expanding the calculation route weight until the calculation is completed, and obtaining the optimal shortest path segment set.
Step S44 includes:
1. the current node in the queue is dequeued and placed in the accessed state.
The current node is the node which should be accessed most preferentially in the priority queue. When iterative computation, the computation is started from the initial node.
2. And selecting one of the road sections connected with the current node as the current road section, and skipping the current road section if the final node of the current road section is in the accessed state.
3. If the user vehicle type does not match the vehicle type that the current road segment can pass, the current road segment is skipped.
4. And acquiring the iteration distance b from the final node to the initial node of the current road section according to the road weight of the current road section.
In practical application, the road weight is the distance measurement of the current road section, and b=the distance from the current node to the starting node+the road weight of the current road section.
5. If b < a, updating a to b, and updating the precursor node of the current road segment end node to be the current node.
A is the distance between the current road segment end node and the starting node which is recorded and saved before,
6. And if the current road segment terminal node is not in the queue, adding the current road segment terminal node into the queue.
7. And selecting the next road section connected with the current node as the current road section, and repeatedly calculating the steps 2-6 until all road sections connected with the current node are traversed and calculated.
8. And (3) repeating the steps 1-7 for iterative computation until the current node dequeued in the queue is the target node, and ending the iterative computation process.
And finally, backtracking from the target node, and obtaining the optimal shortest path set from the target node to the initial node according to the precursor nodes of each road section.
S45, inverting the shortest path set to obtain an optimal shortest path from the initial node to the target node.
In practical application, different road sections can be set in road sections operated by agv by adopting the method, different vehicles can be passed through, 10000 nodes take less than 1ms, and the operation is very efficient.
Preferably, the routing method based on the iterative routing right further comprises:
And parallelizing and processing the road sections connected with the current node.
In practical application, the parallel computation can be used for improving the node processing efficiency, improving the computation speed and obtaining the path planning result more quickly.
Example III
A way-finding system based on iterative road weights, based on the way-finding method based on iterative road weights according to the first or second embodiment, comprises:
the acquisition module is used for acquiring road network data;
The road network construction module is used for constructing a road network framework comprising road network nodes and road sections according to the road network data;
the road network setting module is used for setting node attributes and road section attributes according to the road network data;
and the iterative calculation module is used for calculating the road weight based on the priority queue and the iterative expansion according to the road network architecture, the node attribute and the road section attribute, and obtaining the optimal shortest path from the initial node to the target node.
Example IV
A computer program product comprising a computer program which when executed performs the steps of the iterative road-finding method of one or both embodiments.
Example five
A readable storage medium having stored thereon a computer program according to the fourth embodiment, which when executed performs the steps of the iterative road-right based road-finding method according to the first or second embodiment.
The foregoing is merely illustrative of the present invention, and the present invention is not limited thereto, and any changes or substitutions easily contemplated by those skilled in the art within the technical scope of the present invention should be included in the scope of the present invention. Therefore, the protection scope of the present invention shall be subject to the protection scope of the claims.
Claims (10)
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202510130890.6A CN119573763A (en) | 2025-02-06 | 2025-02-06 | A pathfinding method, system and computer program product based on iterative path rights |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202510130890.6A CN119573763A (en) | 2025-02-06 | 2025-02-06 | A pathfinding method, system and computer program product based on iterative path rights |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| CN119573763A true CN119573763A (en) | 2025-03-07 |
Family
ID=94815894
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN202510130890.6A Pending CN119573763A (en) | 2025-02-06 | 2025-02-06 | A pathfinding method, system and computer program product based on iterative path rights |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN119573763A (en) |
Citations (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN117723079A (en) * | 2023-12-04 | 2024-03-19 | 青岛蚂蚁机器人有限责任公司 | AGV global path planning method based on improved A star algorithm |
| CN118190006A (en) * | 2024-03-26 | 2024-06-14 | 海南港航物流有限公司 | Path planning method and system based on geographic information knowledge graph |
| CN119245675A (en) * | 2024-09-05 | 2025-01-03 | 深圳市智汇奇策科技有限公司 | A logistics park vehicle path planning method and system |
-
2025
- 2025-02-06 CN CN202510130890.6A patent/CN119573763A/en active Pending
Patent Citations (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN117723079A (en) * | 2023-12-04 | 2024-03-19 | 青岛蚂蚁机器人有限责任公司 | AGV global path planning method based on improved A star algorithm |
| CN118190006A (en) * | 2024-03-26 | 2024-06-14 | 海南港航物流有限公司 | Path planning method and system based on geographic information knowledge graph |
| CN119245675A (en) * | 2024-09-05 | 2025-01-03 | 深圳市智汇奇策科技有限公司 | A logistics park vehicle path planning method and system |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| Ahmed et al. | A comparison and evaluation of map construction algorithms using vehicle tracking data | |
| US11015941B2 (en) | Method and apparatus for path based map matching | |
| US10762776B2 (en) | Method, apparatus, and computer program product for determining vehicle lane speed patterns based on received probe data | |
| Wang et al. | Crowdatlas: Self-updating maps for cloud and personal use | |
| US9384394B2 (en) | Method for generating accurate lane level maps | |
| US11755553B2 (en) | Traffic-aware route decoding using a probabilistic encoding data structure | |
| CN100578152C (en) | A Heuristic Path Matching Method for Large-Scale Floating Car Data | |
| US10119824B2 (en) | Method and apparatus for updating road map geometry based on probe data | |
| US11162797B2 (en) | Map matching method and apparatus | |
| US11353328B2 (en) | Navigation system, apparatus and method for associating a probe point with a road segment | |
| US11602974B2 (en) | System and method for generating map data associated with road objects | |
| Demiryurek et al. | A case for time-dependent shortest path computation in spatial networks | |
| CN111307167A (en) | Method and system for route generation through an area | |
| US11435202B2 (en) | Trajectory sampling using spatial familiarity | |
| US9983016B2 (en) | Predicting short term travel behavior with unknown destination | |
| US11262209B2 (en) | Methods and systems for road work extension identification | |
| Bellini et al. | Real-time traffic estimation of unmonitored roads | |
| US10928211B2 (en) | Method and apparatus for selectively qualifying trajectories in regards to a determination of travel time for a maneuver | |
| US9810539B2 (en) | Method, apparatus, and computer program product for correlating probe data with map data | |
| US20210270629A1 (en) | Method and apparatus for selecting a path to a destination | |
| CN119573763A (en) | A pathfinding method, system and computer program product based on iterative path rights | |
| US20230135578A1 (en) | Method and apparatus for generating structured trajectories from geospatial observations | |
| EP3617651B1 (en) | Use of a geographic database comprising lane level information for traffic parameter prediction | |
| US20250207938A1 (en) | Method, apparatus, and computer program product for identifying turning circles and generating turning circles in map data | |
| Chen et al. | Map-matching based on driver behavior model and massive trajectories |
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 |