CN-121981352-A - Grid-structured charging pile space-time scheduling optimization method based on Dijkstra and Bellman-Ford fusion algorithm

CN121981352ACN 121981352 ACN121981352 ACN 121981352ACN-121981352-A

Abstract

The invention provides a grid-structured charging pile space-time scheduling optimization method based on Dijkstra and Bellman-Ford fusion algorithm, and belongs to the technical field of electric automobile charging. The method comprises the steps of S1, obtaining short-time road network information representing traffic road section traffic states and network construction requirement information representing network construction charging pile operation constraint, S2, conducting time expansion on a time-varying traffic road network according to the short-time road network information and the network construction requirement information, constructing a directed graph model containing time constraint, and predicting path traffic states by taking the current position of an electric automobile as a source node in the directed graph model, and S3, calculating to obtain an optimal space-time path of the network construction requirement constraint based on the directed graph model. The invention can obtain the optimal space-time path under the constraint condition of meeting the network construction requirement, and avoid the problem that the network construction operation requirement is ignored only by the shortest running time, thereby improving the practicality and engineering applicability of the electric automobile dispatching scheme in practical application.

Inventors

WANG LILI
SHI YIN
LIU ZHIJIE
Yong Chengzong
LI HANGFENG
ZHAO YUANLIANG
LIU YINGYING
Hu Houpeng
LIU JIAHAO
YANG HUA
CHANG DONGLING
LONG XIAOLIN
ZHANG DAYONG

Assignees

南方电网贵州电动汽车服务有限公司

Dates

Publication Date: 20260505
Application Date: 20251231

Claims (10)

1. A network-structured charging pile space-time scheduling optimization method based on Dijkstra and Bellman-Ford fusion algorithm is characterized by comprising the following steps: S1, short-time road network information representing traffic road section traffic state is obtained, and network demand information representing network construction charging pile operation constraint is obtained; S2, according to the short-time road network information and the network construction requirement information, time-varying traffic road networks are subjected to time expansion, a directed graph model containing time constraint is constructed, and in the directed graph model, the current position of the electric automobile is taken as a source node, so that the path traffic state is predicted; And S3, calculating to obtain an optimal space-time path constrained by the networking requirement by adopting a path solving mode of fusing a Dijkstra algorithm and a Bellman-Ford algorithm based on the directed graph model.
2. The method for optimizing space-time scheduling of the network-structured charging pile based on Dijkstra and Bellman-Ford fusion algorithm according to claim 1, wherein the S1 comprises the following steps: S11, short-time road network information comprises traffic nodes, road section information and a weight function representing the change of road section traffic capacity along with time, and network construction demand information comprises demand positions, demand occurrence time, demand discharge capacity, demand power and demand inertia and is used for representing operation constraint of network construction charging piles; S12, traffic nodes and road section information are preset according to the topological structure of an actual traffic network, a weight function representing the change of the traffic capacity of the road section along with time is calculated according to the time as an independent variable and the running time or the traffic capacity of the road section as a dependent variable based on real-time traffic monitoring data and historical traffic flow data.
3. The method for optimizing space-time scheduling of the network-structured charging pile based on Dijkstra and Bellman-Ford fusion algorithm according to claim 2, wherein the S1 further comprises: S13, the required position represents the corresponding position of a power grid node of the grid-structured charging pile in a traffic road network, and the required position is obtained according to the installation geographic position of the charging pile; S14, the demand appearance time represents target time for requiring the EV to reach a demand position and having the capability of participating in network construction operation, and the EV arrival time is set in advance according to a charging pile management side to obtain the demand appearance time; S15, the required inertia represents the virtual inertia requirement of the grid-structured charging pile for accessing the EV in a grid-structured operation mode, and the required inertia is obtained according to the power grid dispatching requirement.
4. The method for optimizing space-time scheduling of the network-structured charging pile based on Dijkstra and Bellman-Ford fusion algorithm according to claim 3, wherein the S2 comprises the following steps: s21, according to the short-time road network information and the network construction requirement information, the time-varying traffic road network is expanded in time, and the method is as follows: each traffic node in the traffic network is discretized into a plurality of space-time nodes with time attributes according to a preset time step, and the passing cost corresponding to the electric automobile entering the road section at different moments is determined based on the time-dependent weight function corresponding to the road section; in the time unfolding process, road sections between adjacent nodes in an original traffic road network are mapped into directed edges connected with different time space nodes, and the directions of the directed edges are jointly determined by the running direction and the time advancing direction of a vehicle, so that a directed graph model containing time constraint is constructed; And taking a space-time node corresponding to the current position of the electric automobile as a source node, and taking the space-time node on different time layers corresponding to the demand position in the networking demand information as a target node set, so that the directed graph model is converted into a single-source shortest path solving form starting from the source node.
5. The method for optimizing space-time scheduling of network-structured charging piles based on Dijkstra and Bellman-Ford fusion algorithm according to claim 4, wherein the step S2 further comprises: S22, constructing a traffic network graph G based on the short-time road network information; ; In the formula, Represented as a set of traffic nodes; Represented as a collection of traffic segments; Expressed as a set of road network weights; A set of weight functions representing the passage cost of road segment (i, j) as a function of time; Based on the node set V and the road segment set L, storing the road network weight set W in an adjacency matrix form to construct an n multiplied by n order adjacency matrix , Is unfolded into ; In the formula, Represented as representing the weights between nodes i and j, The value of 0 indicates that the traffic cost from the node to the node is zero when i and j are equal.
6. The method for optimizing space-time scheduling of the network-structured charging pile based on Dijkstra and Bellman-Ford fusion algorithm according to claim 5, wherein the S2 further comprises: s23, based on the demand position in the networking demand information Time of occurrence of demand And the required inertia The residual energy of the electric automobile is obtained through calculation in the following way ; ; In the formula, Expressed as the total available energy of the electric vehicle, The ratio of the maximum response time required by the electric automobile to the frequency change rate required by the electric automobile to deal with the frequency change of the power grid under the network construction operation is expressed; s24, based on the demand position in the networking demand information And time of occurrence of demand The road section energy consumption value is calculated and obtained by ; ; In the formula, Expressed as the energy consumption rate of the electric vehicle, The distance is expressed as a road section distance, i.e. i and j respectively represent a starting point node and an ending point node of the road section; subsequently calculating the total path energy consumption ; ; When (when) > When this path is not available.
7. The method for optimizing space-time scheduling of the network-structured charging pile based on Dijkstra and Bellman-Ford fusion algorithm according to claim 6, wherein the S3 comprises the following steps: S31, based on a directed graph model, in the directed graph model after time expansion, taking a space-time node corresponding to the current position of the electric vehicle as a source node, adopting a Dijkstra algorithm and a Bellman-Ford algorithm in fusion, taking a space-time node of a demand position corresponding to network demand information as a target node, and carrying out iterative computation on a single-source shortest path to obtain a path distance from the source node to a node j ; ; In the formula, Represented as a path distance value from the source node to node i, Represented as road segments At the time of To the traffic cost of (a).
8. The method for optimizing space-time scheduling of the network-structured charging pile based on Dijkstra and Bellman-Ford fusion algorithm according to claim 7, wherein the S3 further comprises: S32, constructing a front node set S according to the path distance from the source node to the node; ; In the formula, Representing any spatiotemporal nodes in the time-expanded directed graph model, Represented as a lower distance bound during the current path search, Represented as the upper distance bound during the current path search, Represented as the current electric vehicle distance from node v.
9. The method for optimizing space-time scheduling of the network-structured charging pile based on Dijkstra and Bellman-Ford fusion algorithm according to claim 8, wherein the S3 further comprises: s33, based on the directed graph model, performing time expansion on the directed graph model, and when the electric automobile is from space-time nodes Starting via the traffic route Travel to adjacent space-time nodes Satisfies the following conditions When the node i establishes a directed edge to the node j; In the middle of Expressed as the time of the electric automobile Entry road section Corresponding transit time.
10. The method for optimizing space-time scheduling of the network-structured charging pile based on Dijkstra and Bellman-Ford fusion algorithm according to claim 9, wherein the S3 further comprises: s34, when the path distance from the source node to the node j When the target node is unchanged in the continuous multi-round relaxation updating process, judging that the target node reaches the shortest path stable state, and outputting an optimal space-time path determined by the relation of the precursor nodes ; ; The summation represents accumulating the passing cost of the road sections between each adjacent node i and j on the path from the source node to the target node; In the formula, Representing road segments At the time of To the traffic cost of (a).

Description

Grid-structured charging pile space-time scheduling optimization method based on Dijkstra and Bellman-Ford fusion algorithm Technical Field The invention relates to the technical field of electric automobile charging, in particular to a grid-structured charging pile space-time scheduling optimization method based on Dijkstra and Bellman-Ford fusion algorithm. Background With the rapid popularization of new energy automobiles, the conservation amount of electric automobiles in traffic systems continues to increase, the functions of the electric automobiles in urban traffic traveling and energy systems are increasingly prominent, and especially in the background of novel power systems, the grid-structured charging piles are used as key equipment with electric energy bi-directional flow capacity and virtual inertia supporting capacity and become an important component for supporting safe and stable operation of a power grid. Regarding space-time scheduling of EV and charging pile at present, a prediction and dynamic function road condition method is mostly adopted, a day-ahead prediction is adopted on the load condition so as to know a plan in time in advance, a dynamic function is adopted on the traffic road condition and the road condition change under each road section every time is predicted, the method is limited to the planned scheduling, the method is not suitable for emergency scenes, an algorithm for real-time solving is needed in the emergency scenes, namely, the emergency occurrence moment is taken as a time starting point, the current position of a vehicle is taken as a space starting point, however, the current Dijkstra algorithm is taken as the most accurate optimal path algorithm, the solving speed is logically limited, and when the data quantity is too large, the solving speed is difficult to meet the time requirement. Disclosure of Invention In order to overcome the defects, the invention provides a grid-structured charging pile space-time scheduling optimization method based on Dijkstra and Bellman-Ford fusion algorithm, which solves the technical problems or at least partially solves the problems. The invention is realized in the following way: The invention provides a grid-structured charging pile space-time scheduling optimization method based on Dijkstra and Bellman-Ford fusion algorithm, which is characterized by comprising the following steps of: S1, short-time road network information representing traffic road section traffic state is obtained, and network demand information representing network construction charging pile operation constraint is obtained; S2, according to the short-time road network information and the network construction requirement information, time-varying traffic road networks are subjected to time expansion, a directed graph model containing time constraint is constructed, and in the directed graph model, the current position of the electric automobile is taken as a source node, so that the path traffic state is predicted; And S3, calculating to obtain an optimal space-time path constrained by the networking requirement by adopting a path solving mode of fusing a Dijkstra algorithm and a Bellman-Ford algorithm based on the directed graph model. In a preferred embodiment, the step S1 includes: S11, short-time road network information comprises traffic nodes, road section information and a weight function representing the change of road section traffic capacity along with time, and network construction demand information comprises demand positions, demand occurrence time, demand discharge capacity, demand power and demand inertia and is used for representing operation constraint of network construction charging piles; S12, traffic nodes and road section information are preset according to the topological structure of an actual traffic network, a weight function representing the change of the traffic capacity of the road section along with time is calculated according to the time as an independent variable and the running time or the traffic capacity of the road section as a dependent variable based on real-time traffic monitoring data and historical traffic flow data. In a preferred embodiment, the step S1 further includes: S13, the required position represents the corresponding position of a power grid node of the grid-structured charging pile in a traffic road network, and the required position is obtained according to the installation geographic position of the charging pile; S14, the demand appearance time represents target time for requiring the EV to reach a demand position and having the capability of participating in network construction operation, and the EV arrival time is set in advance according to a charging pile management side to obtain the demand appearance time; S15, the required inertia represents the virtual inertia requirement of the grid-structured charging pile for accessing the EV in a grid-structured operation mode, and the required inertia