CN113295177B - Dynamic path planning method and system based on real-time road condition information - Google Patents

Abstract

The invention relates to the field of vehicle navigation and path planning, and discloses a dynamic path planning method and a dynamic path planning system based on real-time road condition information. The method is characterized in that in the process of driving a vehicle along a planned navigation route, if a congested road section appears in front of the vehicle, a part of the route connected with the congested road section is replaced as little as possible on the basis of an original route without deviating from the original driving direction, the route can be re-planned to reach a preset destination, and therefore the road traffic congestion condition can be effectively relieved. Meanwhile, when the path is re-planned, the invention does not need to search the path in the network again, but searches in the tree structure mentioned in the invention, which is faster than searching the path in the network, thereby shortening the time spent on searching the path to a great extent. The method is suitable for vehicle navigation, path planning and other conditions, and has important application value in the field of intelligent transportation.

Description

Dynamic route planning method and system based on real-time road condition information

technical field

The invention belongs to the field of vehicle navigation and path planning, and in particular relates to a dynamic path planning method and system based on real-time road condition information.

Background technique

During the process of driving along the planned navigation route, due to the influence of traffic flow, weather, unexpected accidents and other factors, there will be congested sections in the driving path of the car. At this time, reasonable path planning is required to avoid congestion. Most of the existing path planning search on the basis of the global road network, and solve the path optimization problem by using genetic algorithm, A* algorithm, ant colony algorithm, Dijkstra algorithm and so on. Among them, the genetic algorithm refers to finding the optimal path by simulating the selection and genetic mechanism in nature. It has a good global search ability, but when dealing with the driving route problem, there is a phenomenon of path intersection, which leads to suboptimal search results; A* algorithm is a widely used shortest path heuristic search algorithm. The search results of this algorithm are closely related to the heuristic function. Different heuristic functions will lead to different search paths; ant colony algorithm is a modern bionic evolutionary algorithm, which has strong robustness, but it is prone to the defects of slow algorithm convergence and easy to fall into local optimum; Dijkstra algorithm uses It is used to calculate the shortest path from one node to all other nodes. The main feature is that it expands from the starting point to the outer layer until it reaches the end point. It can get the optimal solution of the shortest path, but because it traverses many nodes for calculation, it is inefficient.

In addition, when using the global road network search method for path planning, it is necessary to search on the basis of traversing all the paths in the road network again, and the topological relationship of all road segments needs to be used in the search process to replace the original navigation path. A large part of the path is used, so that the car deviates from the original driving direction, and it also increases the path planning time, which does not meet the timeliness requirements of the car.

SUMMARY OF THE INVENTION

The purpose of the present invention is to provide a dynamic path planning method and system based on real-time road condition information, so as to solve the problem that when a path is re-planned in the prior art, it is necessary to perform a path search in the road network again, resulting in low processing efficiency. question.

In order to realize the above-mentioned tasks, the present invention adopts the following technical solutions:

The dynamic route planning method based on real-time road condition information is used to use the established shortest tree structure road network map to replace the congested road sections in the original route and optimize the candidate replacement route to obtain the optimal replacement route;

The shortest tree structure road network map includes the tree structure of each road segment, and the tree structure of each road segment includes the topology structure of the road segment and the shortest reachable path from each road segment to other road segments after the shortest distance search is performed on the road segment. The shortest distance; the method includes the following steps:

Step 1: Obtain the original planned path and the current position, where the original planned path includes congested road sections;

Step 2: Search the congested road segment tree structure in the shortest tree structure road network map according to the road segment ID of the congested road segment, obtain the adjacent upstream road segments and adjacent downstream road segments of the congested road segment, and assign the topological road segments of the adjacent upstream road segments of the congested road segment As the departure road section, the adjacent downstream road section of the congested road section is used as the end road section, and the adjacent upstream road section and the adjacent downstream road section both belong to the original planned route;

Step 3: Determine whether there is an accessible path that does not pass through the congested section between the current departure road section and the current ending road section, and save the existing accessible path as a candidate replacement path,

Retain the current departure road segment and take the adjacent downstream road segment of the current end road segment as the current end road segment;

Step 4: Judging the current end road section, if the path length between the current end road section and the congested road section is less than or equal to the second path distance threshold, return to step 3, where the second path distance threshold is from The maximum upper limit threshold of the search distance from the congested road section to the downstream section;

If the path length between the current end road segment and the congested road segment is greater than the second path distance threshold, the remaining topological road segments that do not include the original trajectory segment in the current departure road segment are taken as the current departure road segment, and the adjacent downstream segments of the congested road segment are used as the current departure road segment. The road segment is taken as the current end road segment, and returns to step 3 until the remaining topological road segments in the current departure road segment are empty, then update the topological road segment of the adjacent upstream segment of the original trajectory segment included in the current departure road segment to the current departure road segment , take the adjacent downstream section of the congested section as the current end section, and perform step 5;

Step 5: If the distance from the current departure section to the current position is greater than or equal to the first path distance threshold, return to step 3, where the first path distance threshold is the minimum lower limit of the distance between the departure section and the current driving position threshold;

Otherwise, stop the path search and judge, if the candidate replacement path is empty, continue to drive according to the original planned path; if the candidate replacement path is not empty, go to step 6;

Step 6: Obtain the path with the shortest path length between the departure section and the end section in the candidate replacement path, and determine whether the path with the shortest path length includes a new congested section, if there is a new congested section, update the congested section and Take the updated driving trajectory path as the original trajectory path and perform step 2 again; otherwise, the path with the shortest path length is used as the optimal replacement path.

Further, obtaining the shortest tree structure road network map includes the following sub-steps:

Step a: Obtain the road section data of all road sections, the road section data includes the road section ID, the longitude coordinates of the start point of the road section, the latitude coordinates of the start point of the road section, the longitude coordinates of the end point of the road section, the latitude coordinates of the end point of the road section, and the length of the road section. , whether the latitude and longitude coordinates of the end point are the same, and then associate to obtain the topology structure of each road segment;

Step b: Carry out the shortest distance search for each road segment according to the topology structure, obtain the shortest reachable path and shortest distance from each road segment to other road segments, take the starting point and end point of each road segment as the Node node of the tree structure of the road segment, and use The reachable path and the shortest distance of each road segment within the time length of the shortest distance search algorithm establish a tree structure for the Value value of the tree structure of the road segment, obtain the tree structure of all road segments, and take the tree structure of all road segments as the shortest Tree structure road network map.

Further, the first path distance threshold is determined according to the shortest reaction time and the average driving speed of the car, and the second path distance threshold is determined according to the distance between the farthest reachable path from the current road section to the downstream direction connected to it. The time required and the average speed of the car are determined.

Furthermore, the average driving speed is 50km/s, the shortest response time is 40s, and the time required between starting from the current road section and reaching the farthest reachable route in the downstream direction connected to it is 2min.

The dynamic route planning system based on real-time road condition information is used to use the established shortest tree structure road network map to replace the congested road sections in the original route and optimize the candidate replacement route to obtain the optimal replacement route;

The system includes the shortest tree structure road network map of the road section and a replacement path planning module;

The shortest tree structure road network map includes the tree structure of each road segment, and the tree structure of each road segment includes the topology structure of the road segment and the shortest reachable path from each road segment to other road segments after the shortest distance search is performed on the road segment. the shortest distance;

The replacement route planning module includes a plurality of sub-modules, wherein the first sub-module is used to obtain an original planned route and a current position, and the original planned route includes a congested road section;

The second sub-module is used to search the congested road segment tree structure in the shortest tree structure road network map according to the road segment ID of the congested road segment, obtain the adjacent upstream road segment and adjacent downstream road segment of the congested road segment, and assign the adjacent upstream road segment of the congested road segment The topological road section is used as the departure road section, and the adjacent downstream road section of the congested road section is used as the end road section, and the adjacent upstream road sections and adjacent downstream road sections belong to the original planned path;

The third sub-module is used to determine whether there is an accessible route that does not pass through the congested road segment between the current departure road segment and the current end segment, and save the existing reachable route as a candidate replacement route,

Retain the current departure road segment and take the adjacent downstream road segment of the current end road segment as the current end road segment;

The fourth sub-module is used for judging the current end road section, and if the path length between the current end road section and the congested road section is less than or equal to the second path distance threshold, return to execute the third sub-module, wherein the second sub-module is executed. The path distance threshold is the maximum upper limit threshold of the search distance from the congested road section to the downstream road section;

If the path length between the current end road segment and the congested road segment is greater than the second path distance threshold, the remaining topological road segments that do not include the original trajectory segment in the current departure road segment are taken as the current departure road segment, and the adjacent downstream segments of the congested road segment are used as the current departure road segment. The road segment is taken as the current end road segment, and returns to execute the third sub-module until the remaining topological road segments in the current departure road segment are empty, then update the topological road segment of the adjacent upstream road segment of the original trajectory segment included in the current departure road segment to the current one Departure section, take the adjacent downstream section of the congested section as the current end section, and execute the fifth sub-module;

The fifth sub-module is used to judge, if the distance from the current departure road segment to the current position is greater than or equal to the first path distance threshold, then return to execute the third sub-module, wherein the first path distance threshold is the departure road segment to the current driving distance. Minimum lower threshold for distances between locations;

Otherwise, stop the path search and judge, if the candidate replacement path is empty, continue to drive according to the original planned path; if the candidate replacement path is not empty, execute the sixth sub-module;

The sixth sub-module is used to obtain the path with the shortest path length between the departure road segment and the end road segment in the candidate replacement path, and determine whether the path with the shortest path length includes a new congested road segment, and if there is a new congested road segment, update the The road section is congested and the updated driving trajectory path is taken as the original trajectory path and the second sub-module is re-executed; otherwise, the path with the shortest path length is taken as the optimal replacement path. The sixth sub-module is used to obtain the path with the shortest path length between the departure section and the end section of the replacement path, and determine whether the path with the shortest path length includes a new congested section, and if there is a new congested section, update the congested section And re-execute the second sub-module; otherwise, the path with the shortest path length is regarded as the optimal replacement path.

Further, obtaining the shortest tree structure road network map includes the following submodules:

Submodule a is used to obtain the road section data of all road sections, and the road section data includes the road section ID, the longitude coordinates of the start point of the road section, the latitude coordinates of the start point of the road section, the longitude coordinates of the end point of the road section, the latitude coordinates of the end point of the road section and the length of the road section. Correlate according to whether the latitude and longitude coordinates of the starting point and the ending point are the same to obtain the topology structure of each road segment;

Sub-module b is used to search the shortest distance for each road segment according to the topology structure, obtain the shortest reachable path and shortest distance from each road segment to other road segments, and take the starting point and end point of each road segment as the Node node of the road segment tree structure , take the reachable path and the shortest distance of each road segment within the time length of the shortest distance search algorithm as the Value value of the tree structure of the road segment to establish a tree structure, obtain the tree structure of all road segments, and combine the tree structure of all road segments As the shortest tree structure road network map.

Further, the first path distance threshold is determined according to the shortest reaction time and the average driving speed of the car, and the second path distance threshold is determined according to the distance between the farthest reachable path from the current road section to the downstream direction connected to it. The time required and the average speed of the car are determined.

Furthermore, the average driving speed is 50km/s, the shortest response time is 40s, and the time required between starting from the current road section and reaching the farthest reachable route in the downstream direction connected to it is 2min.

Compared with the prior art, the present invention has the following technical characteristics:

(1) The present invention is based on dynamic path planning based on real-time road condition information. When the vehicle is traveling along the planned navigation route, if there is a congested road section in front of the vehicle, the replacement and congestion are as little as possible on the basis of the original path. Part of the path connected to the road segment can complete the re-planning of the path and reach the preset destination without deviating from the original driving direction. This can effectively alleviate road traffic congestion.

(2) The present invention does not need to search the route in the road network again when re-planning the route, but searches in the tree structure mentioned in the present invention, which is faster than the route search in the road network, thereby The time spent on path search can be greatly shortened.

(3) The method of the present invention is suitable for situations such as vehicle navigation and path planning, and has important application value in the field of intelligent transportation.

Description of drawings

Fig. 1 is the effect diagram of the dynamic path planning of real-time road condition information of the present invention;

Figure 2 is a schematic diagram of the road section topology;

3 is a schematic diagram of a tree-shaped data structure;

Fig. 4 is the overall flow chart;

FIG. 5 is a schematic diagram of the embodiment.

Detailed ways

The specific embodiments of the present invention are given below. It should be noted that the present invention is not limited to the following specific embodiments, and all equivalent transformations made on the basis of the technical solutions of the present application all fall into the protection scope of the present invention.

The present invention uses Scala language to implement dynamic path planning based on real-time road condition information, and can re-plan the path in real time according to the congested road sections that appear in the vehicle's driving path, thereby effectively alleviating road traffic congestion and avoiding traffic congestion. time consumed.

In this embodiment, a dynamic route planning method based on real-time road condition information is disclosed, which is used to replace the congested road sections in the original route by using the established shortest tree structure road network map and to optimize the candidate replacement route. , to obtain the optimal replacement path;

In the actual operation of the algorithm, not only the congested road section is replaced, but also a part of the road section connected to the congested road section is replaced;

The shortest tree structure road network map includes the tree structure of each road segment, and the tree structure of each road segment includes the topology structure of the road segment and the shortest reachable path from each road segment to other road segments after the shortest distance search is performed on the road segment. The shortest distance; the method includes the following steps:

Step 1: Obtain the original planned path and the current position, where the original planned path includes congested road sections;

Step 2: Search the congested road segment tree structure in the shortest tree structure road network map according to the road segment ID of the congested road segment, obtain the adjacent upstream road segments and adjacent downstream road segments of the congested road segment, and assign the topological road segments of the adjacent upstream road segments of the congested road segment As the departure road section, the adjacent downstream road section of the congested road section is used as the end road section, and the adjacent upstream road section and the adjacent downstream road section both belong to the original planned route;

Step 3: Determine whether there is an accessible path that does not pass through the congested section between the current departure road section and the current ending road section, and save the existing accessible path as a candidate replacement path,

Retain the current departure road segment and take the adjacent downstream road segment of the current end road segment as the current end road segment;

Step 4: Judging the current end road section, if the path length between the current end road section and the congested road section is less than or equal to the second path distance threshold, return to step 3, where the second path distance threshold is from The maximum upper limit threshold of the search distance from the congested road section to the downstream section;

If the path length between the current end road segment and the congested road segment is greater than the second path distance threshold, the remaining topological road segments that do not include the original trajectory segment in the current departure road segment are taken as the current departure road segment, and the adjacent downstream segments of the congested road segment are used as the current departure road segment. The road segment is taken as the current end road segment, and returns to step 3 until the remaining topological road segments in the current departure road segment are empty, then update the topological road segment of the adjacent upstream segment of the original trajectory segment included in the current departure road segment to the current departure road segment , take the adjacent downstream section of the congested section as the current end section, and perform step 5;

Step 5: If the distance from the current departure section to the current position is greater than or equal to the first path distance threshold, return to step 3, where the first path distance threshold is the minimum lower limit of the distance between the departure section and the current driving position threshold;

Otherwise, stop the path search and judge, if the candidate replacement path is empty, continue to drive according to the original planned path; if the candidate replacement path is not empty, go to step 6;

Step 6: Obtain the path with the shortest path length between the departure section and the end section in the candidate replacement path, and determine whether the path with the shortest path length includes a new congested section, if there is a new congested section, update the congested section and Take the updated driving trajectory path as the original trajectory path and perform step 2 again; otherwise, the path with the shortest path length is used as the optimal replacement path.

Specifically, obtaining the shortest tree-structured road network map includes the following sub-steps:

Step a: Obtain the road section data of all road sections, the road section data includes the road section ID, the longitude coordinates of the start point of the road section, the latitude coordinates of the start point of the road section, the longitude coordinates of the end point of the road section, the latitude coordinates of the end point of the road section, and the length of the road section. , whether the latitude and longitude coordinates of the end point are the same, and then associate to obtain the topology structure of each road segment;

Step b: Perform the shortest distance search for each road segment according to the topology, obtain the shortest reachable path and shortest distance from each road segment to other road segments, obtain the shortest reachable path and shortest distance from each road segment to other road segments, and use each The starting point or end point of the road segment is the Node node of the tree structure of the road segment, and the tree structure is established with the reachable path and the shortest distance of each road segment within the time length of the shortest distance search algorithm as the Value value of the tree structure of the road segment, and we get The tree structure of all road segments, the tree structure of all road segments is used as the shortest tree structure road network map.

Specifically, the following methods are used for the shortest distance search for any road segment:

Select a road segment, take the selected road segment as the starting road segment, perform the shortest distance search for the starting road segment according to the topology structure, and obtain the shortest reachable path and shortest distance from each road segment to other road segments,

Specifically, the first path distance threshold is determined according to the shortest reaction time and the average driving speed of the vehicle, and the second path distance threshold is determined according to the distance between the farthest reachable path from the current road section to the downstream direction connected to it. The time required and the average speed of the car are determined.

Specifically, the average driving speed is 50km/s, the shortest response time is 40s, and the time required between starting from the current road section and reaching the farthest reachable route in the downstream direction connected to it is 2min.

Specifically, the topology structure of each road segment includes a road segment ID and road segment topology information, and the road segment topology information includes: the longitude coordinates of the start point of the road segment, the latitude coordinates of the start point of the road segment, the set of road segment IDs directly connected to the start point of the road segment, and the longitude coordinates of the end point of the road segment. , the latitude coordinates of the end point of the road segment, the set of road segment IDs directly connected to the end point of the road segment, and the length of the road segment.

Specifically, the topology structure of the road segment during storage is a Map structure, and the topology information structure of the road segment is as follows:

Specifically, the method of establishing the topology structure of the road segment is as follows:

Starting from the first row of data, take out the RoadId as a Key and add it to the Map structure, take out the longitude and latitude coordinates of the starting point and add them to the road segment topology information, and then compare with the starting point and end point longitude and latitude coordinates of other road segment data in turn. The RoadId of the road segment data is added to the set of road segment IDs directly connected to the starting point of the current road segment, and then the latitude and longitude coordinates of the end point are taken out, and then compared with the start point and end point latitude and longitude coordinates of other road segment data. Add it into the set of road segment IDs directly connected to the end point of the current road segment, then calculate the distance of the great circle of the earth with the latitude and longitude of the starting point and end point, add it into the Distance field, and then take out the second row of data and do the above operations until all the road segment data are The topology that makes up the road segment ends.

Specifically, the length of time required between starting from the current road section and reaching the farthest reachable path in the downstream direction connected to it is 2 minutes. The method is performed on a dataset that saves the reachable paths in the downstream direction connected by the current road segment within 2 minutes. In order to save search time, this part of the data set can be obtained by offline calculation, and the shortest path and shortest distance between each road segment and all road segments less than 1667m are calculated in advance through the shortest distance search algorithm. 1667m is the farthest distance that the car can reach from the current road section in the downstream direction connected to it within the 2min driving time under the condition of the specified speed of 50km/s.

Since the shortest tree-structured road network map is a dataset of accessible paths in the downstream direction connected to the current road segment within 2 minutes, this method is performed on the dataset that saves the accessible paths in the downstream direction connected to the current road segment within 2 minutes. , so take Threshold2 as 1667m, and 1667m is the furthest distance that can be reached in the downstream direction from the current road section within 2 minutes while traveling at a speed of 50km/h. Take Threshold1 as 560m, and 560m is the longest distance the car can reach in the downstream direction from the current position in the reaction time of 40s and the specified speed is 50km/s. If it is less than Threshold1, the car The driver has no time to react to go to the new planned route.

Specifically, two tree structures are constructed for each road segment, corresponding to the start point and the end point of the road segment respectively. The tree structure of the road segment is represented by the Node node, and the Node node is as follows

Among them, RoadId represents the number of the current road segment, ChildMap(Current ChildRoadId, CurrentNode) represents the sub-road segment ID of the node and the Node node of the sub-road segment, and Value(Distance, Path) contains the shortest distance and connectivity from the initial road segment to the current sub-road segment. path.

Specifically, the tree structure of the road segment is established as follows:

Starting from the initial road segment, take out the RoadId as the Key and add it to the Node node, then add the current sub-road segment ID of the sub-road segment connected to the initial road segment and the Node node of the current sub-road segment into the road segment tree structure, through the road segment in step a The topology structure of , and the shortest reachable path and shortest distance in step b are assigned to Value and saved in the road segment tree structure. Repeat the above steps until all sub-sections and corresponding Node nodes of the current section are added. A schematic diagram of the tree structure of the road section is shown in Figure 3.

This embodiment also discloses a dynamic route planning system based on real-time road condition information, which is used to replace the congested road sections in the original route and optimize the candidate replacement route by using the established shortest tree structure road network map. , to obtain the optimal replacement path;

The system includes the shortest tree structure road network map of the road section and a replacement path planning module;

The shortest tree structure road network map includes the tree structure of each road segment, and the tree structure of each road segment includes the topology structure of the road segment and the shortest reachable path from each road segment to other road segments after the shortest distance search is performed on the road segment. the shortest distance;

The replacement route planning module includes a plurality of sub-modules, wherein the first sub-module is used to obtain an original planned route and a current position, and the original planned route includes a congested road section;

The second sub-module is used to search the congested road segment tree structure in the shortest tree structure road network map according to the road segment ID of the congested road segment, obtain the adjacent upstream road segment and adjacent downstream road segment of the congested road segment, and assign the adjacent upstream road segment of the congested road segment The topological road section is used as the departure road section, and the adjacent downstream road section of the congested road section is used as the end road section, and the adjacent upstream road sections and adjacent downstream road sections belong to the original planned path;

The third sub-module is used to determine whether there is an accessible route that does not pass through the congested road segment between the current departure road segment and the current end segment, and save the existing reachable route as a candidate replacement route,

Retain the current departure road segment and take the adjacent downstream road segment of the current end road segment as the current end road segment;

The fourth sub-module is used for judging the current end road section, and if the path length between the current end road section and the congested road section is less than or equal to the second path distance threshold, return to execute the third sub-module, wherein the second sub-module is executed. The path distance threshold is the maximum upper limit threshold of the search distance from the congested road section to the downstream road section;

If the path length between the current end road segment and the congested road segment is greater than the second path distance threshold, the remaining topological road segments that do not include the original trajectory segment in the current departure road segment are taken as the current departure road segment, and the adjacent downstream segments of the congested road segment are used as the current departure road segment. The road segment is taken as the current end road segment, and returns to execute the third sub-module until the remaining topological road segments in the current departure road segment are empty, then update the topological road segment of the adjacent upstream road segment of the original trajectory segment included in the current departure road segment to the current one Departure section, take the adjacent downstream section of the congested section as the current end section, and execute the fifth sub-module;

The fifth sub-module is used to judge, if the distance from the current departure road segment to the current position is greater than or equal to the first path distance threshold, then return to execute the third sub-module, wherein the first path distance threshold is the departure road segment to the current driving distance. Minimum lower threshold for distances between locations;

Otherwise, stop the path search and judge, if the candidate replacement path is empty, continue to drive according to the original planned path; if the candidate replacement path is not empty, execute the sixth sub-module;

The sixth sub-module is used to obtain the path with the shortest path length between the departure road segment and the end road segment in the candidate replacement path, and determine whether the path with the shortest path length includes a new congested road segment, and if there is a new congested road segment, update the The road section is congested and the updated driving trajectory path is taken as the original trajectory path and the second sub-module is re-executed; otherwise, the path with the shortest path length is taken as the optimal replacement path. The sixth sub-module is used to obtain the path with the shortest path length between the departure section and the end section of the replacement path, and determine whether the path with the shortest path length includes a new congested section, and if there is a new congested section, update the congested section And re-execute the second sub-module; otherwise, the path with the shortest path length is regarded as the optimal replacement path.

Further, obtaining the shortest tree structure road network map includes the following submodules:

Submodule a is used to obtain the road section data of all road sections, and the road section data includes the road section ID, the longitude coordinates of the start point of the road section, the latitude coordinates of the start point of the road section, the longitude coordinates of the end point of the road section, the latitude coordinates of the end point of the road section and the length of the road section. Correlate according to whether the latitude and longitude coordinates of the starting point and the ending point are the same to obtain the topology structure of each road segment;

Sub-module b is used to search for the shortest distance of each road segment, and obtain the shortest reachable path and shortest distance from each road segment to other road segments. The reachable path and the shortest distance of each road segment within the time length of the shortest distance search algorithm are used to establish a tree structure for the Value value of the tree structure of the road segment, and the tree structure of all road segments is obtained, and the tree structure of all road segments is regarded as the shortest tree. road network map.

Example 1

This embodiment discloses a dynamic path planning method based on real-time road condition information, which traverses the connected road segment with the starting point or the end point of the road segment from the topology structure of the previous road segment adjacent to the congested road segment, and calculates the starting point or end point of the road segment. The connected road segment is used as the departure road segment, and the sub-road segment of the next road segment adjacent to the congested road segment is used as the end road segment to find a connecting path. On the basis of the foregoing embodiments, the following technical features are also disclosed:

The original path between the starting point and the target point is obtained as:

51483708242->51483708239->51483700698->51483708176->51483708175->51483705267->51483705268->51483700685->51483700666 (51483708175)

The topology of road section 51483708176 is shown in Figure 2 below. The downstream section 51483708177 connected to the topology of section 51483708176 is the departure section, and the sub-section 51483705268 of the next section adjacent to the congested section 51483708175 is the end section. A connected path of 51483708175.

51483708242->51483708239->51483700698->51483708176->51483708177->51483708167->51483705268->51483700685->51483700666

A schematic diagram of the above embodiment is shown in FIG. 5 .

Claims (6)

1. The dynamic path planning method based on the real-time road condition information is characterized by being used for replacing a congested road section in an original path and optimizing alternate paths by adopting a built shortest tree-shaped structure road network map to obtain an optimal alternate path;

the shortest tree-structure road network map comprises a tree structure of each road section, and the tree structure of each road section comprises a topological structure of the road section and the shortest reachable path and shortest distance from each road section to other road sections after the shortest distance search is carried out on the road section; the method comprises the following steps:

step 1: acquiring an original planned path and a current position, wherein the original planned path comprises a congestion road section;

step 2: searching a tree structure of the congested road section in a shortest tree structure road network map according to the road section ID of the congested road section, obtaining an adjacent upstream road section and an adjacent downstream road section of the congested road section, taking a topological road section of the adjacent upstream road section of the congested road section as a starting road section, and taking the adjacent downstream road section of the congested road section as an ending road section, wherein the adjacent upstream road section and the adjacent downstream road section both belong to an original planning path;

and step 3: judging whether an reachable path which does not pass through the congested road section exists between the current departure road section and the current ending road section, saving the existing reachable path as a candidate alternative path,

reserving the current starting road section and taking the adjacent downstream road section of the current ending road section as the current ending road section;

and 4, step 4: judging the current ending road section, and returning to the step 3 if the path length between the current ending road section and the congested road section is less than or equal to a second path distance threshold, wherein the second path distance threshold is a maximum upper limit threshold of a searching distance from the congested road section to a downstream road section;

if the path length from the current ending road section to the congested road section is greater than the second path distance threshold, taking the remaining topological road section which does not contain the original track road section in the current starting road section as the current starting road section, taking the adjacent downstream road section of the congested road section as the current ending road section, returning to the step 3, updating the topological road section of the adjacent upstream road section of the original track road section contained in the current starting road section into the current starting road section until the remaining topological road section in the current starting road section is empty, taking the adjacent downstream road section of the congested road section as the current ending road section, and executing the step 5;

and 5: if the distance from the current departure road section to the current position is greater than or equal to a first path distance threshold value, returning to execute the step 3, wherein the first path distance threshold value is a minimum lower limit threshold value of the distance from the departure road section to the current driving position;

otherwise, stopping path searching and judging, and if the alternate alternative path is empty, continuing to drive according to the original planned path; if the alternate path is not empty, executing step 6;

step 6: acquiring a path with the shortest path length between a starting section and an ending section in the candidate replacement paths, judging whether the path with the shortest path length contains a new congestion section, if the new congestion section exists, updating the congestion section, taking the updated traveling track path as an original track path, and executing the step 2 again; otherwise, taking the path with the shortest path length as the optimal replacement path;

the method for establishing the shortest tree structure road network map comprises the following substeps:

step a: acquiring road section data of all road sections, wherein the road section data comprises road section IDs, road section starting point longitude coordinates, road section starting point latitude coordinates, road section finishing point longitude coordinates, road section finishing point latitude coordinates and road section lengths, and the road section data of all the road sections are associated according to whether the starting point longitude coordinates and the finishing point longitude coordinates are the same or not to acquire a topological structure of each road section;

step b: and searching each road section according to the shortest distance according to a topological structure to obtain the shortest reachable path and the shortest distance from each road section to other road sections, taking the starting point and the end point of each road section as Node nodes of the tree structure of the road section, taking the reachable path and the shortest distance of each road section in the time length of the shortest distance searching algorithm as Value values of the tree structure of the road section to establish a tree structure, obtaining the tree structures of all the road sections, and taking the tree structures of all the road sections as a road network map with the shortest tree structure.

2. The method as claimed in claim 1, wherein the first path distance threshold is determined according to a shortest response time and an average traveling speed of the car, and the second path distance threshold is determined according to a time required for the car to travel from the current road section to the farthest reachable path in a downstream direction connected to the current road section and the average traveling speed of the car.

3. The dynamic path planning method according to claim 2, wherein the average driving speed is 50km/s, the shortest response time is 40s, and the time required from the current road section to the farthest reachable path in the downstream direction connected thereto is 2 min.

4. The dynamic path planning system based on the real-time road condition information is characterized by being used for replacing a congested road section in an original path and optimizing alternate paths by adopting an established shortest tree-structure road network map to obtain an optimal alternate path;

the system comprises a road network map with a shortest road section tree structure and a planning module of an alternative path;

the shortest tree-structure road network map comprises a tree structure of each road section, and the tree structure of each road section comprises a topological structure of the road section and the shortest reachable path and shortest distance from each road section to other road sections after the shortest distance search is carried out on the road section;

the alternative path planning module comprises a plurality of sub-modules, wherein a first sub-module is used for acquiring an original planned path and a current position, and the original planned path comprises a congested road section;

the second submodule is used for searching the tree structure of the congested road section in the shortest tree structure road network map according to the road section ID of the congested road section, obtaining an adjacent upstream road section and an adjacent downstream road section of the congested road section, taking a topological road section of the adjacent upstream road section of the congested road section as a starting road section, and taking the adjacent downstream road section of the congested road section as an ending road section, wherein the adjacent upstream road section and the adjacent downstream road section both belong to an original planning path;

the third sub-module is used for judging whether an reachable path which does not pass through the congested road section exists between the current departure road section and the current ending road section or not, saving the reachable path as a candidate alternative path,

reserving the current starting road section and taking the adjacent downstream road section of the current ending road section as the current ending road section;

the fourth submodule is used for judging the current ending road section, and returning to execute the third submodule if the path length between the current ending road section and the congested road section is less than or equal to a second path distance threshold, wherein the second path distance threshold is a maximum upper limit threshold of the searching distance from the congested road section to the downstream road section;

if the path length from the current ending road section to the congested road section is greater than the second path distance threshold, taking a residual topology road section which does not contain the original track road section in the current starting road section as the current starting road section, taking an adjacent downstream road section of the congested road section as the current ending road section, returning to execute the third submodule until the residual topology road section in the current starting road section is empty, updating the topology road section of the adjacent upstream road section of the original track road section contained in the current starting road section into the current starting road section, taking the adjacent downstream road section of the congested road section as the current ending road section, and executing the fifth submodule;

the fifth submodule is used for judging, and if the distance from the current departure road section to the current position is greater than or equal to a first path distance threshold value, returning to execute the third submodule, wherein the first path distance threshold value is a minimum lower limit threshold value of the distance from the departure road section to the current driving position;

otherwise, stopping path searching and judging, and if the alternate alternative path is empty, continuing to drive according to the original planned path; if the alternate alternative path is not empty, executing a sixth sub-module;

the sixth submodule is used for acquiring a path with the shortest path length between a starting section and an ending section in the alternate paths, judging whether the path with the shortest path length contains a new congestion section, if the new congestion section exists, updating the congestion section, taking the updated driving track path as an original track path, and executing the second submodule again; otherwise, taking the path with the shortest path length as an optimal replacement path;

the method for establishing the shortest tree structure road network map comprises the following sub-modules:

the sub-module a is used for obtaining road section data of all road sections, wherein the road section data comprises road section IDs, road section starting point longitude coordinates, road section starting point latitude coordinates, road section ending point longitude coordinates, road section ending point latitude coordinates and road section lengths, and the road section data of all the road sections are associated according to whether the starting point longitude coordinates and the ending point longitude coordinates are the same or not to obtain a topological structure of each road section;

the submodule b is used for searching the shortest distance of each road section according to the topological structure to obtain the shortest reachable path and the shortest distance from each road section to other road sections, the starting point and the end point of each road section are taken as Node nodes of the tree structure of the road section, the reachable path and the shortest distance of each road section in the time length of the shortest distance searching algorithm are taken as Value values of the tree structure of the road section to establish a tree structure, the tree structures of all the road sections are obtained, and the tree structures of all the road sections are taken as the road network map with the shortest tree structure.

5. The system according to claim 4, wherein the first distance threshold is determined according to a shortest response time and an average driving speed of the vehicle, and the second distance threshold is determined according to a time required between a departure from a current road section and a farthest reachable route in a downstream direction connected thereto and the average driving speed of the vehicle.

6. The dynamic path planning system according to claim 5, wherein the average driving speed is 50km/s, the shortest response time is 40s, and the time required from the current road section to the farthest reachable path in the downstream direction connected thereto is 2 min.

Images