CN-116305754-B - Solution to planning problem of joint path and destination based on distributed solving generalized Nash equilibrium algorithm

CN116305754BCN 116305754 BCN116305754 BCN 116305754BCN-116305754-B

Abstract

The invention discloses a solution to a planning problem of a joint path and a destination based on a distributed solving generalized Nash equilibrium algorithm, which comprises the steps of firstly modeling the planning problem of the joint path and the destination, converting the planning problem into a non-cooperative game model, wherein the model comprises an objective function, global coupling constraint and local constraint of each electric automobile; the game model is converted into the VI problem by using the pseudo gradient, a boundary-based consistency constraint and heterogeneous step length mechanism is introduced, a distributed solving algorithm under complete information is provided according to fixed point iteration and a near-end gradient operator theory, and then global estimation of planning of other users is introduced, so that a distributed solving algorithm under partial information is provided. The method avoids the construction of the double random matrix by the consistency constraint based on the edges, and can ensure the solving precision and meet the requirement of low calculation amount when the game model has more users to participate.

Inventors

LI HUAQING
LI CHUANDONG
WANG HUIWEI
SHI YAWEI
CHEN MENGGANG
JI LIANGHAO
LI SONGYANG
WU SONG
SUN JIAN
XIA DAWEN
DONG TAO
RAN LIANG
ZHENG LIFENG
LI JUN

Assignees

西南大学

Dates

Publication Date: 20260505
Application Date: 20221220

Claims (4)

1. Solution to the problem of joint path and destination planning based on distributed solution generalized Nash equalization algorithm, comprising Vehicle electric car n= {1,..n }, the electric car is also referred to as a user, Road strip And Personal charging station The charging station refers to a parking lot provided with the charging station and also refers to a destination of a user, and is characterized by comprising the following steps: modeling planning problems of joint paths and destinations, and establishing objective functions of each user According to the maximum traffic load of the road and the maximum power supply load of the charging station, global coupling constraint of the planning problem of the joint path and the destination is obtained, and meanwhile, according to probability, each user also needs to meet local constraint of the user; Converting the gaming model described above into a variational inequality problem whose solution has an economical interpretation of no price discrimination while taking all local Lagrangian multipliers When agreement is reached in a steady state, the solution of the variation inequality problem is that of the original game model; For the purpose of Introducing edge-based consistency constraint, designing a distributed solving algorithm under complete information according to the fixed point iteration and the near-end gradient operator theory, and introducing global estimation of planning of other users A partial information lower distributed solving algorithm is provided, which converts a game model into a variation inequality problem and interprets the relation between the solution of the variation inequality problem and the solution of the game model, and specifically comprises the following steps: summarizing the gaming model as another popular gaming model is as follows: Wherein the method comprises the steps of The constraint conditions of the common game model are as follows: wherein Representing a feasible set, defined as: Wherein the method comprises the steps of Representing a user The local constraints to be met are that, Define the global coupling constraint to be satisfied for all users , And The generalized gaming model can be written as: Further, the Karush-Kuhn-Tucker condition of the popular gaming model needs to be satisfied: the pseudo-gradient map of the generalized gaming model is expressed as: The variational inequality problem can be expressed as: Wherein the method comprises the steps of The Karush-Kuhn-Tucker condition for the variational inequality problem needs to be satisfied: By observing Karush-Kuhn-Tucker conditions of the generalized gaming model and the variational inequality problem, we infer that this is true , Any solution to the variation inequality problem is then a solution to the gaming model.
2. The solution to the problem of planning a joint path and destination based on a distributed solution generalized nash equalization algorithm of claim 1, characterized in that said problem of planning a joint path and destination specifically comprises: Each user Determining own planning: , wherein, Representing the user The probability of selecting each road is determined, Representing the user Probability of selecting each charging station; Each user The objective function of (2) is: Wherein the method comprises the steps of Representing deviation from the user The associated costs of habitual selection, Is the user The expected time of travel is set to be the same, Is the user The cost of the service to be expected is, Is a weighting factor representing the time term, each user The definition of the three parts of the objective function of (a) is as follows: (1) Deviating from the user Costs associated with habitual selection Wherein the method comprises the steps of And Respectively represent users Based on its past experience, the probability of the preferred destination and road being selected, And Weight factors representing the two preferences, respectively; (2) Travel time Wherein the method comprises the steps of Is to represent a road The strictly monotonically increasing function of the traffic flow is defined as: Wherein the method comprises the steps of Representing a road The transit time in the event of a non-blocking, And road Is related to the length of the vehicle and the speed limit, Representing a road Is used for the passage capacity of the vehicle, Representing a function of travel time Is used for the control of the control parameters of the (c), Representing a road Is defined as: Wherein the method comprises the steps of Representing the traffic flow of a non-charged car; (3) Cost of service Wherein the method comprises the steps of Representing a user Is used for the energy requirements of the (a) and (b), The parking fee is indicated by the number of the parking fee, A price function representing energy, defined as: Wherein the method comprises the steps of Is the price coefficient of the price of the product, Is a charging station Is provided with a charging capacity of (a), Is a charging station The overall demand for energy is expected to be that, Is the user In the charging station Is a power source requirement of (1); To ensure that the gaming model has GNE, when the user From the starting point Departure to a feasible destination When the probability is User(s) The following constraints must be satisfied: the above constraints can be understood as users Departure from the starting point The probability of (1) being equal to 1, arrive at the first Probability of each charging station being equal to The probability of entering an intersection and leaving an intersection should also be the same, while the user is at the same time Only to a specific set of destinations, i.e Because the charger therein is adapted to its electric car, the user Needs to meet the requirements of Furthermore, the user The sum of the probabilities of going to all charging stations needs to satisfy ; The global coupling constraint of the planning problem of the joint path and destination can be modeled as: Wherein the method comprises the steps of Representing destination Is used for the energy supply of the maximum energy, Representing a road Is set for the vehicle, and the maximum vehicle flow of (1).
3. The solution to the problem of planning of joint paths and destinations based on a distributed solution generalized nash equalization algorithm according to claim 1, characterized in that the distributed solution algorithm under complete information specifically comprises: Definition of the definition And for each edge Introducing operators So that Wherein Is an operator that achieves local lagrangian multiplier arrival consistency, defined as: Will be assembled Is defined as Thus can get the effect At the time, there are , ; Definition of the definition As a means of Of (2), wherein Order-making , , And Therefore Karush-Kuhn-Tucker conditions are as follows: According to Karush-Kuhn-Tucker conditions, the immobilized point iteration is utilized and a near-end gradient operator is applied, and the algorithm is centralized as follows: Wherein the method comprises the steps of , , And three heterogeneous step matrices in the above formula are respectively represented as follows: Decomposing the centralized algorithm to obtain a distributed form of a distributed solving algorithm under complete information, wherein the distributed form is as follows: 。
4. the solution to the problem of planning of joint paths and destinations based on a distributed solution generalized Nash equalization algorithm according to claim 1, characterized in that the distributed solution algorithm under partial information specifically comprises: Considering the more practical application, i.e. that some users cannot know the planning of all other users, an estimate of the planning of other users is introduced for each user: And correspondingly define And therefore, the user Can be written as a local objective function of (2) Local estimations of all users need to be agreed in steady state, i.e ; For each edge Introducing operators So that Wherein the method comprises the steps of Is an operator that implements local estimation consistency, defined as Then will be assembled Is defined as It can be observed that when At the time, there are ; Definition of the definition As a means of Of (2), wherein Order-making machine And ; Introducing two selection matrices And , For screening In (a) and (b) The definition is: Wherein the method comprises the steps of And ; For screening In (a) and (b) The definition is: Thus, there are Order the , , And Can obtain Meanwhile, the pseudo gradient mapping under partial information is as follows: thus Karush-Kuhn-Tucker conditions are as follows: The algorithm is centralized as follows: , , the three heterogeneous step size matrices in the above formula are respectively represented as follows: Decomposing the centralized algorithm to obtain a distributed form of a distributed solving algorithm under partial information, wherein the distributed form is as follows: 。

Description

Solution to planning problem of joint path and destination based on distributed solving generalized Nash equilibrium algorithm Technical Field The invention relates to the technical field of information processing, in particular to a solution to a planning problem of a joint path and a destination based on a generalized Nash equilibrium algorithm. Background With the advent of new technologies such as various types of map software applications, users can access real-time information to select routes and destinations. Studies have shown that users play a positive role in the infrastructure and therefore, if the state of the traffic network changes, users will react quickly to such changes and change their decisions. A decision-making problem arises when the user selects routes and destinations based on their own preferences and data provided by the online platform (e.g., road congestion and destination congestion). The competitive nature of such decision-making problems becomes apparent when a user is willing to reach a destination with the lowest congestion (e.g., a charging station) in the shortest time. This situation arises from population migration, supermarket selection, on-demand autonomous travel, public parking and Electric Vehicle (EV) charging station selection, etc., where congestion may affect electricity rates and waiting times. Obviously, routing and destination planning are not two disjoint decision variables, as the choice of destination (e.g. charging station) would limit routing and vice versa. On the other hand, with the increasing number of electric vehicles and the limited number of public charging facilities with limited electric resources, the operation of traffic networks and charging stations face some challenges. In this case, when the user is willing to drive to the nearest station, the power demand of some stations may be significantly increased. Because of limited resources and facilities, it is necessary to study and control this effect. The solutions of the prior researches cannot reach the required solving precision when more electric automobiles exist, and a large amount of calculation is needed. Game theory is a tool for researching the behaviors of a plurality of decision makers, and has wide application in the fields of sociology, economy, engineering and the like. In practical problems, the objective functions of the individuals (or decision makers) often restrict each other (e.g., there is a competing relationship), and the decision variables of the individuals are coupled to each other due to the limitation of network bandwidth, scarce resources, or supply-demand balance. In fact, an important research branch of game theory is to provide theoretical basis for various coupling and collision and generated phenomena, and provide effective analysis and prediction to design a learning algorithm capable of achieving equilibrium. Therefore, the game theory is introduced into the multi-agent system, the problem that a plurality of entities existing in a large number in actual life are prevented from colliding in mutual restriction and competition relation to finally reach relative balance can be solved by utilizing a unique game theory system, and the thinking of students on system algorithm design is greatly developed while the system performance is effectively improved. The solution of the game problem (i.e. non-cooperative game) is generally referred to as nash balancing, which can be colloquially interpreted as that all players have reached their own relatively optimal strategy under the condition of determining the states of the rest of the players, i.e. if unilaterally changing their own strategy results in a decrease of the income. However, in many applications, the feasible action sets of all participants are coupled together by global shared affine constraints due to constraints of network resources and the like. That is, for each participant, the set of possible actions depends on the actions of the other participants. In this case, the solution of the non-cooperative game is called generalized Nash equilibrium. Disclosure of Invention In order to solve the problems, the invention discloses a solution to the problem of planning the joint path and the destination based on a distributed solving generalized Nash equilibrium algorithm. The invention adopts the following technical scheme: Solution to planning problem of joint path and destination based on distributed solving generalized Nash equilibrium algorithm, and is assumed to comprise Vehicle electric car n= {1,..once, N }, in the assumed scenario, because the electric car is driven by the user, the electric car also refers to the user,Road stripAndPersonal charging stationThe charging station refers to a parking lot equipped with the charging station, and also refers to a destination of a user, that is, in this assumed situation, the charging peg is equivalent to the destination, and includes the following steps: m