CN-122015885-A - Multi-stage path searching method, device and equipment based on time-varying road conditions

CN122015885ACN 122015885 ACN122015885 ACN 122015885ACN-122015885-A

Abstract

The invention discloses a multi-stage path searching method, device and equipment based on time-varying road conditions, which relate to the technical field of travel path searching of traffic networks. Simulating a real driving process along a candidate path sequence, accumulating time consumption section by section, firstly taking dynamic time variation in driving path search into consideration, and in a parking decision stage, performing spatial indexing with a k-d tree through UTM coordinate conversion, the parking lot is dynamically associated to a road network specific node to form a complete searching strategy from a driving path searching to a parking decision, the distance from an attachment point to the parking lot in the preset range of the attachment point is obtained, driving dynamic time consumption of the distance from the attachment point to the parking lot in the preset range of the attachment point is calculated, the parking decision is internalized into a path searching variable by the process, dynamic time variation in the parking decision is taken into consideration, and therefore efficient searching and matching of multi-stage paths are finally carried out.

Inventors

YE JIANHONG
ZHAN JING
LUO GUANPEI
YU BIN

Assignees

同济大学

Dates

Publication Date: 20260512
Application Date: 20260212

Claims (9)

1. The multi-stage path searching method based on the time-varying road conditions is characterized by comprising the following steps of: acquiring traffic road network map data, parking lot data and travel request data to be traveled; acquiring time consumption when traveling from a traveling starting point to any road network node based on traffic road network diagram data, sequentially accumulating dynamic traveling time consumption of each road section along a path node sequence from the starting point of a traveling request, and acquiring the dynamic traveling time consumption from the traveling starting point to any road network node; converting longitude and latitude of each parking lot in the parking lot data into road network coordinates by utilizing UTM coordinate conversion, inquiring a nearest road network node by utilizing k-d tree space indexes as an attachment point, and acquiring the distance from the attachment point to the parking lot in a preset range of the attachment point; And aiming at each driving path in the candidate set, taking the attachment point corresponding to the driving path as a driving end point, accumulating the driving dynamic time consumption from the starting point to any road network node, the time consumption for the distance from the attachment point to the parking lot, the parking locating time of the parking lot and taking the driving path with the minimum time consumption as the searched path.
2. The method for searching the multi-stage path based on the time-varying road conditions according to claim 1, wherein the obtaining the driving dynamic time consumption from the trip start point to any road network node comprises: The relation between the real-time traffic flow and the passing speed of the road section is quantized by adopting a piecewise function, expressed as: ; Wherein: , In the piecewise function, the direction of decreasing the traffic speed respectively indicates that the road section is in a state of smooth, slightly congested, medium congested and severely congested; For a real-time passing speed v in continuous variation, s represents the total length of the road segment, then: ; ; the intersection steering impedance t ij , which is linked with the passing speed v i 、v j of the input and output road segments, is expressed as follows: t ij = g (v i , v j , ...); The time taken by the ratio of the road length to the real-time passing speed v and the intersection turning impedance t ij are used as dynamic time consumption from the starting point to any road network node.
3. The method for searching a multi-stage path based on time-varying road conditions according to claim 1, wherein the obtaining the distance from the attachment point to the parking lot within the preset range of the attachment point comprises: taking the travel terminal point coordinates as a coordinate set to be queried, and carrying out circular search with a preset radius r in a pre-constructed k-d tree of the parking lot to obtain all parking lot indexes meeting the conditions to form a candidate parking lot set; Converting longitude and latitude of each parking lot in the candidate parking lot set into road network coordinates through UTM coordinates, inquiring and outputting nearest neighbor nodes corresponding to the coordinates in a road network node k-d tree, and marking the nodes as attachment points of the corresponding parking lots; Two key value pairs are added in the external value of the parking lot information table, the number of the attachment point and the route length from the attachment point to the parking lot are recorded respectively, the route length is represented by the Manhattan distance between the two, and the time consumption of the section is obtained based on the conversion of the average speed of the section.
4. The multi-stage path searching method based on time-varying road conditions according to claim 1, wherein the obtaining of the parking time of each parking lot comprises: Setting a vacant rate delta of the vacant number of the vehicle seats to the total number of the vehicle seats and a parking locating time t p , and designing a secondary nonlinear function of the parking locating time t p about the vacant rate delta, wherein the function is expressed as follows: ; Wherein: representing the coefficients; the punishment time t p generated by difficult parking space searching when the empty rate delta is low is used for representing the parking availability of a parking lot, and the parking locating time of each parking lot is dynamically calculated by utilizing a secondary nonlinear function.
5. The multi-stage path searching method based on time-varying road conditions according to claim 1, wherein the obtaining of the driving path with the minimum time consumption comprises: Setting a starting point of path search as a road network node s corresponding to a travel starting point, setting an end point as a road network node t corresponding to an attachment point of a certain parking lot, executing path search from the node s to the node t based on traffic network map data, acquiring a single feasible path, and adding the single feasible path into a candidate path set; For k paths in the candidate path set, acquiring total time consumption based on dynamic road conditions, determining respective time consumption of the k paths according to the total time consumption, arranging the k paths according to the priority from small to large, and returning paths which are ordered according to the priority in the k paths to a traveler.
6. The multi-stage path searching method based on time-varying road conditions according to claim 5, wherein the total time consumption acquisition mode of the driving path is as follows: C=C car,on +C car,of +C foot +t p ; Wherein, C car,on represents the dynamic time consumption from the starting point to any network node, C car,of represents the time consumption from the attachment point to the parking lot, C foot represents the parking and locating time of the parking lot, and t p represents the walking time consumption.
7. A multi-stage path search device based on time-varying road conditions, comprising: the data module is used for acquiring traffic road network map data, parking lot data and travel request data to be traveled; the driving module is used for acquiring driving time consumption in a simulated travel mode in a driving stage of traveling, wherein the driving module is used for acquiring the driving time consumption from a traveling starting point to any road network node based on traffic road network diagram data, accumulating the dynamic driving time consumption of each road section along a path node sequence from the starting point of a traveling request, and acquiring the driving dynamic time consumption from the traveling starting point to any road network node; The parking module is used for converting the longitude and latitude of each parking lot in the parking lot data into road network coordinates by utilizing UTM coordinate conversion, inquiring the nearest road network node by utilizing k-d tree space indexes as an attachment point, and acquiring the distance from the attachment point to the parking lot in a preset range of the attachment point; The path optimization module is used for acquiring a plurality of driving paths from a travel starting point to each parking lot attachment point by adopting a path search algorithm to form a driving path candidate set, taking the attachment point corresponding to the driving path as a driving end point for each driving path in the candidate set, accumulating driving dynamic time consumption from the starting point to any road network node, time consumption for the distance from the attachment point to a parking lot, parking position searching time of the parking lot, and taking the driving path with the minimum time consumption as a searched path.
8. An electronic device is characterized by comprising a memory and a processor; the memory is used for storing a computer program; the processor is configured to implement the steps of the multi-stage path searching method according to any one of claims 1 to 6 based on time-varying road conditions when executing the computer program stored in the memory.
9. A computer readable storage medium for storing a computer program which when executed by a processor implements the steps of a multi-stage path search method based on time-varying road conditions as claimed in any one of claims 1 to 6.

Description

Multi-stage path searching method, device and equipment based on time-varying road conditions Technical Field The invention relates to the technical field of travel path searching of traffic networks, in particular to a multi-stage path searching method, device, equipment and medium based on time-varying road conditions. Background In recent years, with the improvement of integration and intellectualization of traffic systems, driving navigation service and path search serving as a core support technology thereof are widely applied, and the path search serving as a core of the navigation service directly influences travel efficiency and user experience. In the prior art, a passive response strategy of 'instant road condition inquiry and post correction' is frequently adopted in driving navigation travel path searching, wherein the strategy is to conduct path planning based on instant road conditions at the departure time and to conduct passive correction according to the latest road conditions during driving, and when a parking lot is selected, a shortest travel path to the vicinity of a destination is planned first, and then an available parking lot is searched around the end point of the path. However, when the travel path is searched, the means at the present stage only takes the traffic state at the departure time as a single basis of the whole travel planning, ignores the evolution rule of road conditions in the travel time dimension, is difficult to capture and respond to the dynamic change, so that the planned optimal path is often based on the premise of error or outdated, the vehicle is easy to sink into a congested road section, the travel path planning and a parking lot are selected as two independent links, the cost coupling and the mutual restriction relation between the stages are manually ignored by the splitting decision mode, and finally, the efficient searching and matching of the multi-stage path are difficult to accurately perform in a dynamic and real urban traffic environment. Disclosure of Invention The embodiment of the invention provides a multi-stage path searching method, device and equipment based on time-varying road conditions, which can solve the problems in the prior art. The embodiment of the invention provides a multi-stage path searching method based on time-varying road conditions, which comprises the following steps: acquiring traffic road network map data, parking lot data and travel request data to be traveled; acquiring time consumption when traveling from a traveling starting point to any road network node based on traffic road network diagram data, sequentially accumulating dynamic traveling time consumption of each road section along a path node sequence from the starting point of a traveling request, and acquiring the dynamic traveling time consumption from the traveling starting point to any road network node; converting longitude and latitude of each parking lot in the parking lot data into road network coordinates by utilizing UTM coordinate conversion, inquiring a nearest road network node by utilizing k-d tree space indexes as an attachment point, and acquiring the distance from the attachment point to the parking lot in a preset range of the attachment point; And aiming at each driving path in the candidate set, taking the attachment point corresponding to the driving path as a driving end point, accumulating the driving dynamic time consumption from the starting point to any road network node, the time consumption for the distance from the attachment point to the parking lot, the parking locating time of the parking lot and taking the driving path with the minimum time consumption as the searched path. Preferably, the obtaining the driving dynamic time consumption from the trip start point to any one of the network nodes includes: The relation between the real-time traffic flow and the passing speed of the road section is quantized by adopting a piecewise function, expressed as: ; Wherein: , In the piecewise function, the direction of decreasing the traffic speed respectively indicates that the road section is in a state of smooth, slightly congested, medium congested and severely congested; For a real-time passing speed v in continuous variation, s represents the total length of the road segment, then: ; ; the intersection steering impedance t ij, which is linked with the passing speed v i、vj of the input and output road segments, is expressed as follows: tij=g(vi,vj, ...); The time taken by the ratio of the road length to the real-time passing speed v and the intersection turning impedance t ij are used as dynamic time consumption from the starting point to any road network node. Preferably, the obtaining the distance from the attachment point to the parking lot within the preset range of the attachment point includes: taking the travel terminal point coordinates as a coordinate set to be queried, and carrying out circular search with a preset radius r in