CN-117523890-B - Urban K shortest path acquisition method considering real-time road conditions

CN117523890BCN 117523890 BCN117523890 BCN 117523890BCN-117523890-B

Abstract

The invention discloses an urban K shortest path acquisition method considering real-time road conditions, which comprises the steps of 1, constructing an urban road network according to the road condition information at the starting moment, 2, defining parameters and initializing, 3, searching the K shortest path from a starting intersection node to an end intersection node at the current time, 4, searching the k+1 shortest path from the starting intersection node to the end intersection node at the current time, and 5, acquiring the K shortest paths from the starting intersection node to the end intersection node at the next time after the road condition is updated according to the real-time road conditions. The method and the device can obtain K optimal travel paths which are more suitable for actual traffic conditions while improving the calculation efficiency, so that stable and efficient operation of social traffic is ensured.

Inventors

DING JIANXUN
SHAN YUNHAN
DUAN RUI
Yang beinuo
CHEN YU
HUANG JUNPENG
WANG YUYUE
WANG HUA
LONG JIANCHENG

Assignees

合肥工业大学

Dates

Publication Date: 20260505
Application Date: 20231124

Claims (3)

1. A city K shortest path acquisition method considering real-time road conditions is characterized by comprising the following steps: step 1, constructing an urban road network; acquiring real-time road network data and obtaining urban road network , Represents a junction node set, an , Represent the first The nodes of the intersections are arranged at the same time, , For the urban road network In the total number of intersection nodes in the network, Representing a set of road segments between intersection nodes, an , Represent the first Individual intersection nodes To the first Individual intersection nodes A directed road section between the two road sections, A set of travel time weights representing road segments between intersection nodes, , Is a directed road section If the running time weight of (1) Individual intersection nodes To the first Individual intersection nodes With directed road sections therebetween Then (1) Individual intersection nodes Is the first Individual intersection nodes Is marked as a subsequent intersection node of (a) First, the Individual intersection nodes Is the first Individual intersection nodes Is marked as the precursor intersection node of (2) And (2) and If at first Individual intersection nodes To the first Individual intersection nodes No directed road section exists between Order in principle Order-making machine Represent the first Individual intersection nodes Precursor intersection node set of (1), let Represent the first Individual intersection nodes Is a set of subsequent intersection nodes; step 2, defining parameters and initializing; Setting the intersection node of the starting point as The junction node of the terminal point is And (2) and Order-making machine Representing intersection nodes from origin To the junction node of the terminal intersection The shortest path number of (1) is given by Representing intersection nodes from origin To the first Individual intersection nodes And (2) the number of viable paths of ; Step 2.1, defining relevant attributes of the feasible paths; Order the Representing intersections from the origin To the first Individual intersection nodes Is the first of (2) Travel time of the feasible path, and ; Order the Representing intersections from the origin Through length of To the (1) Individual intersection nodes Precursor intersection node of (c) Then from the front-driving intersection node To the first Individual intersection nodes Is provided, wherein, Representing intersections from the origin To the precursor intersection node Is the first of (2) Travel time of the feasible path, and , Representing intersection nodes from origin To intersection node And (2) the number of viable paths of When (when) Is the intersection node of the origin, i.e Time, order ; Order the Represents a time minimum and = Wherein, the method comprises the steps of, Representing intersections from the origin To the first Individual intersection nodes Is the first of (2) The travel time of the feasible path; Order the Representing intersections from the origin To the first Individual intersection nodes Is the first of (2) Included in the feasible paths are intersections from the starting points To the first Individual intersection nodes Precursor intersection node of (c) Is the first of (2) Correlation properties of the feasible paths; Order the Representing intersection nodes from origin To the first Individual intersection nodes Attribute tag set of all feasible paths of (1), and The number of attribute tags in (a) is And (2) and ; Order the Arbitrary first of (3) Personal attribute tags Representing intersection nodes from origin To the first Individual intersection nodes Is the first of (2) A set of correlation attributes for the feasible paths, an ; Definition of the definition Is arbitrary first Individual intersection nodes All attribute labels per A set after ascending arrangement; Order the Arbitrary first of (3) Personal attribute tags Representing intersection nodes from origin To the first Individual intersection nodes Is the first of (2) The correlation property of the shortest path, i.e Wherein, the method comprises the steps of, Representing intersections from the origin To the first Individual intersection nodes Is the first of (2) The driving time of the shortest path; representing intersections from the origin Through length of Is routed to the first Individual intersection nodes Precursor intersection node of (c) Then from the front-driving intersection node To the first Individual intersection nodes Is used for the total driving time of the vehicle, Representing intersections from the origin To the precursor intersection node Is the first of (2) Travel time of shortest path, and , Representing intersection nodes from origin To intersection node And (2) the number of viable paths of When (when) Is the intersection node of the origin, i.e Time, order ; Represents a time minimum and = Wherein, the method comprises the steps of, Representing intersections from the origin To the first Individual intersection nodes Is the first of (2) The driving time of the shortest path; representing intersections from the origin To the first Individual intersection nodes Is the first of (2) Included in the shortest path is the intersection from the start point To the first Individual intersection nodes Precursor intersection node of (c) Is the first of (2) Correlation properties of the shortest path; Definition of the definition Is the first A label set to be searched for the shortest path; Definition of the definition Is a step of unit time; initializing the related attributes of the feasible paths; initializing a starting point intersection node Is a label set of (2) All tags in (a) are Any other arbitrary ones Individual intersection nodes Is a label set of (2) All tags in (1) are initialized to ; Junction node of starting point intersection Ordered tag of (2) Add the first Label set to be searched for shortest path ; Defining and initializing a timer as ; Step3, hierarchically calculating the time steps of the unit time A shortest path; Step 3.1 calculating the first Initializing ; Step 3.1.1. Collecting tags to be searched The intersection node corresponding to the label with the minimum time minimum value is recorded as Order-making Representing a node of an origin intersection To intersection node Is the first of (2) The correlation property of the shortest path, i.e The corresponding attribute label is , wherein, Representing intersections from the origin To intersection node Is the first of (2) The driving time of the shortest path; representing intersections from the origin Through length of Is routed to the intersection node Precursor intersection node of (c) Then from the front-driving intersection node To intersection node Is used for the total driving time of the vehicle, Representing intersections from the origin To the precursor intersection node Is the first of (2) Travel time of shortest path, and , Representing intersection nodes from origin To intersection node And (2) the number of viable paths of When (when) Is the intersection node of the origin, i.e Time, order ; Represents a time minimum and = Wherein, the method comprises the steps of, Representing intersections from the origin To intersection node Is the first of (2) The driving time of the shortest path; representing intersections from the origin To intersection node Is the first of (2) Included in the shortest path is the intersection from the start point To intersection node Precursor intersection node of (c) Is the first of (2) Correlation properties of the shortest path; Representing intersection nodes from origin To intersection node And (2) the number of viable paths of ; If it is Or (b) Turning to step 3.1.2, otherwise turning to step 3.2; step 3.1.2 if Executing the step 3.1.2a, otherwise, turning to the step 3.1.3; Step 3.1.2a. Ream Label is attached to Removal of Traversing intersection nodes Subsequent intersection node set of (a) Is provided with a junction node in the middle, for any intersection node And is also provided with Not belonging to intersection nodes from the start To intersection node Is the first of (2) In the short circuit: Order the Representing a node of an origin intersection To intersection node Is the first of (2) Correlation properties of shortest paths, i.e. intersection nodes The corresponding attribute label is , wherein, Representing intersections from the origin To intersection node Is the first of (2) The driving time of the shortest path; representing intersections from the origin Through length of Is routed to the intersection node Precursor intersection node of (c) Then from the front-driving intersection node To intersection node Is used for the total driving time of the vehicle, Representing intersections from the origin To the precursor intersection node Is the first of (2) Travel time of shortest path, and , Representing intersection nodes from origin To intersection node And (2) the number of viable paths of ; Represents a time minimum and = Wherein, the method comprises the steps of, Representing intersections from the origin To intersection node Is the first of (2) The driving time of the shortest path; representing intersections from the origin To intersection node Is the first of (2) Included in the shortest path is the intersection from the start point To intersection node Precursor intersection node of (c) Is the first of (2) A set of correlation attributes for the shortest path; Representing intersection nodes from origin To intersection node And (2) the number of viable paths of ; If present Then pair From the slave Starting the descending sequence of traversal, if Turning to step 3.1.2b, otherwise turning to step 3.1.2c; If present Traversing the intersection node Is the remainder of (2) Ordered tags, if present Personal label Satisfy the following requirements And is also provided with Stopping the traversal for From the slave Starting the descending sequence of traversal, if Turning to step 3.1.2d, otherwise turning to step 3.1.2e; Step 3.1.2b order , And update the time minimum Label is attached to Add the first Label set to be searched for shortest path In the step (2), continuing to search for updating by waiting for the subsequent step, and turning to the step (3.1.2 c); Step 3.1.2c updating preamble tag, i.e. order Re-order Turning to step 4.1, wherein, Representing directed road segments Is a running time weight of (a); step 3.1.2d. Order , And update the time minimum Label is attached to Add the first Label set to be searched for shortest path In the step (2), continuing to search for updating by waiting for the subsequent step, and turning to the step (3.1.2 e); step 3.1.2e order , And update the time minimum Label is attached to Add the first Label set to be searched for shortest path In the step (2), continuing to search for updating in the subsequent step, and turning to the step (4.1); step 3.1.3 order ; Step 3.1.4 traversing intersection nodes And its subsequent intersection node set Is provided with a junction node in the middle, for any intersection node And is also provided with Not belonging to intersection nodes from the start To intersection node Is the first of (2) In the short circuit: Record intersection node Precursor intersection node set of (c) Any intersection node in the network is ; Order the Representing a node of an origin intersection To intersection node Is the first of (2) Correlation properties of shortest paths, i.e. intersection nodes The corresponding attribute label is , wherein, Representing intersections from the origin To intersection node Is the first of (2) The driving time of the shortest path; representing intersections from the origin Through length of Is routed to the intersection node Precursor intersection node of (c) Then from the front-driving intersection node To intersection node Is used for the total driving time of the vehicle, Representing intersections from the origin To the precursor intersection node Is the first of (2) Travel time of shortest path, and , Representing intersection nodes from origin To intersection node And (2) the number of viable paths of ; Represents a time minimum and = Wherein, the method comprises the steps of, Representing intersections from the origin To intersection node Is the first of (2) The driving time of the shortest path; representing intersections from the origin To intersection node Is the first of (2) Included in the shortest path is the intersection from the start point To intersection node Precursor intersection node of (c) Is the first of (2) A set of correlation attributes for the shortest path; Representing intersection nodes from origin To intersection node And (2) the number of viable paths of ; If it is Junction node other than origin And is also provided with Step 3.1.5 is executed, otherwise, step 3.1.4 is returned to for continuous traversal; Step 3.1.5 traversing intersection nodes All precursor intersection nodes of (a) Record so that The smallest intersection node is , wherein, Representing intersections from the origin To intersection node Is the first of (2) The travel time of the shortest path is, Representing directed road segments Is a running time weight of (a); Order the Representing a node of an origin intersection To intersection node Is the first of (2) Correlation properties of shortest paths, i.e. intersection nodes The corresponding attribute label is , wherein, Representing intersections from the origin To intersection node Is the first of (2) The driving time of the shortest path; representing intersections from the origin Through length of Is routed to the intersection node Precursor intersection node of (c) Then from the front-driving intersection node To intersection node Is used for the total driving time of the vehicle, Representing intersections from the origin To the precursor intersection node Is the first of (2) Travel time of shortest path, and , Representing intersection nodes from origin To intersection node And (2) the number of viable paths of ; Represents a time minimum and = Wherein, the method comprises the steps of, Representing intersections from the origin To intersection node Is the first of (2) The driving time of the shortest path; representing intersections from the origin To intersection node Is the first of (2) Included in the shortest path is the intersection from the start point To intersection node Precursor intersection node of (c) Is the first of (2) A set of correlation attributes for the shortest path; Representing intersection nodes from origin To intersection node And (2) the number of viable paths of ; Order the , Turning to step 4.2, wherein, Representing directed road segments Is a running time weight of (a); step 3.2 calculating the first +1 Shortest paths; Will be Assignment of +1 to If (if) Turning to step 6, otherwise, returning to step 3.1; Step 4, updating the first Label set to be searched for shortest path ; Step 4.1, updating the intersection node Is a label of (2) Ordered labels ; Step 4.1.1 if the intersection node Tag value of (2) And is also provided with Then update time minimum Turning to step 4.1.2, otherwise, executing step 4.1.3; Step 4.1.2, the current intersection node Removing the collection If at this time gather If not, the step is switched to the step 3.1.2 to continue traversing, otherwise, the step is switched to the step 3.1.1; Step 4.1.3 if And is also provided with Then update time minimum Then the intersection is connected with Is a label of (2) Adding in Turning to step 4.1.2; If it is And is also provided with Then the label is attached Removal of Turning to step 4.1.2; Step 4.2, updating the intersection node Is a label set of (2) And an ordered tag set ; Step 4.2.1 if the intersection node Tag value of (2) And is also provided with Then update time minimum Turning to step 4.2.2, otherwise, executing step 4.2.3; step 4.2.2, the current intersection node Removing the collection If at this time gather If not, the step is switched to the step 3.1.4 to continue traversing, otherwise, the step is switched to the step 3.1.1; Step 4.2.3 if And is also provided with Then junction node will be Is a label of (2) Adding in Turning to step 4.2.2; If it is And is also provided with Then the label is attached Removal of Turning to step 4.2.2; step 4.3 updating intersection nodes Is a label set of (2) And an ordered tag set ; Step 4.3.1 if the intersection node Tag value of (2) And is also provided with Then update time minimum Turning to step 4.3.2, otherwise, executing step 4.3.3; Step 4.3.2 the current road segment Removing road segment set with changed running time weights If at this time gather If not, go to step 5.3 to continue traversing the next driving time weight change road section, otherwise, go to step 3.1.1; Step 4.3.3 if And is also provided with Then junction node will be Is a label of (2) Adding in Turning to step 4.3.2; If it is And is also provided with Then the label is attached Removal of Turning to step 4.3.2; step 5, detecting real-time road condition and updating A shortest path; Step 5.1 judgment timer Whether or not to reach If yes, empty the timer And executing the step 5.2, otherwise, continuing to time; step 5.2, detecting whether the road network running time weight is changed, if not, returning to the step 5.1, otherwise, recording the running time weight set of the road sections between the intersection nodes after updating as Turning to step 5.3; step 5.3 for road segment Order-making Representing a node of an origin intersection To intersection node Is the first of (2) The correlation property of the shortest path, i.e The corresponding attribute label is , wherein, Representing intersections from the origin To intersection node Is the first of (2) The driving time of the shortest path; representing intersections from the origin Through length of Is routed to the intersection node Precursor intersection node of (c) Then from the front-driving intersection node To intersection node Is used for the total driving time of the vehicle, Representing intersections from the origin To the precursor intersection node Is the first of (2) Travel time of shortest path, and , Representing intersection nodes from origin To intersection node And (2) the number of viable paths of When (when) Is the intersection node of the origin, i.e Time, order ; Represents a time minimum and = Wherein, the method comprises the steps of, Representing intersections from the origin To intersection node Is the first of (2) The driving time of the shortest path; representing intersections from the origin To intersection node Is the first of (2) Included in the shortest path is the intersection from the start point To intersection node Precursor intersection node of (c) Is the first of (2) Correlation properties of the shortest path; Representing intersection nodes from origin To intersection node And (2) the number of viable paths of ; If it meets Go to step 5.3.1, otherwise go to step 5.3.2; step 5.3.1 if Order-making Then let the Otherwise, go to step 5.3 to continue traversing the next driving time weight change road section; step 5.3.2 if Junction node other than origin And is also provided with Traversing intersection nodes All precursor intersection nodes of (a) Record so that The smallest intersection node is Wherein Representing intersections from the origin To intersection node Is the first of (2) The travel time of the shortest path is, Representing directed road segments Updated running time weight, let , Turning to step 5.3, wherein, Representing intersections from the origin To intersection node Is the first of (2) The travel time of the shortest path is, Representing directed road segments The updated on-time weight of the vehicle, Representing intersection nodes from origin To intersection node Is the first of (2) Otherwise, go to step 5.3 to continue traversing the next road section with weight change of running time; step 6, outputting the current time from the starting point to the intersection node To the junction node of the terminal intersection A kind of electronic device Strip shortest path information; According to the junction node of the terminal point Is a label set of (2) In (a) and (b) Tags from destination intersection nodes Is the first of (2) Personal label Initially, go through Backtracking the attribute labels corresponding to the precursor intersection nodes until backtracking to the starting intersection nodes Is a label of (2) Thereby obtaining a slave To the point of Is the first of (2) Short path with running time of Thereby obtaining the slave in unit time step To the point of A kind of electronic device The shortest path and the driving time thereof are switched to step 5 to continue searching for updated road conditions The shortest path is followed.
2. An electronic device comprising a memory and a processor, wherein the memory is configured to store a program that supports the processor to perform the urban K-bar shortest path acquisition method of claim 1, the processor being configured to execute the program stored in the memory.
3. A computer readable storage medium having stored thereon a computer program, characterized in that the computer program when run by a processor performs the steps of the urban K-bar shortest path acquisition method according to claim 1.

Description

Urban K shortest path acquisition method considering real-time road conditions Technical Field The invention belongs to the field of navigation optimization of urban road networks, and particularly relates to a method for acquiring urban K shortest paths by considering real-time road conditions. Background With the development of social economy, the use amount of traffic navigation users based on the Internet is continuously increased, more and more travelers hope to select an optimal path according to own demands, so that congestion can be avoided as much as possible, the traffic navigation users smoothly and conveniently reach a destination, but the urban traffic situation is gradually complicated, and therefore, the requirements on a path navigation algorithm are also higher and higher. On the basis of ensuring the solving efficiency and the optimal path quality, K shortest path selections are provided, and the method is one of the practical demands of current navigation users. However, the existing K shortest path planning algorithm has the defects that firstly, the shortest path algorithm is called for multiple times or the whole network is updated to calculate a deviated path set, a large amount of repeated calculation exists, the result of previous calculation is not well utilized, so that the calculation efficiency is low in a large-scale network, the waste of calculation resources is caused, the concept of real-time navigation is not suitable, the running efficiency of urban traffic is reduced, and secondly, a more definite connection is rarely established with the future real-time road condition, and the navigation result is not necessarily close to the actual situation. Disclosure of Invention The invention aims to solve the defects of the prior art, and provides the urban K shortest path acquisition method considering real-time road conditions, so that K optimal travel paths which are more suitable for actual traffic conditions can be obtained while the calculation efficiency is improved, and the stable and efficient operation of social traffic is ensured. In order to achieve the aim of the invention, the invention adopts the following technical scheme: the invention relates to a method for acquiring urban K shortest paths by considering real-time road conditions, which is characterized by comprising the following steps: step 1, constructing an urban road network; Acquiring real-time road network data and obtaining a city road network g= (V, a, W), wherein V represents an intersection node set, v= { V 1,v2,v3,…,vi,…,vN},vi represents an ith intersection node, i=1, 2,3,..n, N is the total number of intersection nodes in the city road network G, a represents a road segment set between intersection nodes, a= { (V i,vj)|i,j＝1,2,3,…,N},(vi,vj) represents a directed road segment between the ith intersection node V i and the jth intersection node V j, W represents a road segment travel time weight set between intersection nodes, w= { W (V i,vj)|i,j＝1,2,3,…,N},w(vi,vj) is a road segment travel time weight of the directed road segment (V i,vj), and if a directed road segment (V i,vj) exists between the ith intersection node V i and the jth intersection node V j, the kth intersection node V j is a succeeding intersection node of the ith intersection node V i, and is recorded as a following intersection node of the ith intersection node V iThe i-th intersection node v i is the precursor intersection node of the j-th intersection node v j, and is marked asAnd omega ij >0, if no directed road segment (v i,vj) exists between the ith intersection node v i and the jth intersection node v j, let w ij = +++; let pred (v i) represent the precursor intersection node set of the ith intersection node v i, let succ (v i) represent the successor intersection node set of the ith intersection node v i; step 2, defining parameters and initializing; Setting a starting point intersection node as V start, a destination intersection node as V end and V start,vend epsilon V, letting K represent the shortest path number from the starting point intersection node V start to the destination intersection node V end, letting l (V i) represent the feasible path number from the starting point intersection node V start to the ith intersection node V i and l (V i) is less than or equal to K; step 2.1, defining relevant attributes of the feasible paths; Let g l(vi) denote the travel time of the first feasible path from the origin intersection v start to the i-th intersection node v i, and l≤l (v i); let rhs l(vi) denote the transit length from the origin intersection v startThe feasible path of (a) reaches the precursor intersection node of the ith intersection node v iThen from the front-driving intersection nodeTotal travel time to the i-th intersection node v i, wherein,Representing the intersection from the origin v start to the precursor intersection nodeTravel time of the a-th feasible path, andRepresenting the intersection from th