CN113537722B - Scheduling planning method and application - Google Patents

Abstract

The present application belongs to the technical field of unmanned aerial vehicles, and in particular relates to a dispatching and planning method and its application. The operator can remotely control the drone through the 4G signal and charge it with the help of the base station, but the charging time location and the scheduling of patrol tasks must be considered. The present application provides a scheduling planning method, the method includes obtaining base station location information, constructing a base station Unicom relationship diagram, and rating base stations according to the relationship diagram; establishing a space-time convolutional network model, and obtaining an initial solution of the model; A scheduling plan is obtained according to the rating result and the initial solution. Able to give suitable schedule.

Description

A Scheduling Planning Method and Its Application

technical field

The present application belongs to the technical field of unmanned aerial vehicles, and in particular relates to a dispatching and planning method and its application.

Background technique

Unmanned aircraft, referred to as "UAV", is an unmanned aircraft controlled by radio remote control equipment and its own program control device. There is no cockpit on board, but equipment such as autopilot and program control device are installed. The personnel on the ground, on the ship, or at the remote control station of the parent aircraft track, locate, remote control, telemetry and digital transmission through radar and other equipment. Under the radio control, it can take off like an ordinary aircraft or be launched into the air with a booster rocket, and it can also be taken into the air by the parent aircraft for flight. When recovering, it can automatically land in the same way as the common aircraft landing process, and can also be recovered by remote control with a parachute or a block. Can be used repeatedly. Widely used in aerial reconnaissance, surveillance, communication, anti-submarine, electronic jamming, etc.

UAV patrol is a direction of UAV application in the future. However, the current UAV cannot realize autonomous long-distance patrol. There are two reasons, one is battery life, and the other is the need for operators. The drone can be controlled and charged using 4G signal. The operator can remotely control the drone through the 4G signal and charge it with the help of the base station, but the charging time location and the scheduling of patrol tasks must be considered.

Contents of the invention

1. Technical problems to be solved

Based on the current scheme can only deal with small-scale problems, it is often difficult to obtain results in the face of large-scale problems. In the case of using base stations to provide signals and charging for drones, the number of base stations is huge, and the scale of the problem increases exponentially. The current solution is difficult to meet. In addition, due to the great difference between the base station and the airport, for example, the airport cannot be relocated, but the base station is easy to relocate, so a strong technical flexibility is added, which brings great difficulty to the scheduling problem. Highly flexible scheduling problems are difficult to solve. In view of the above problems, the present application provides a scheduling method and application.

2. Technical solution

In order to achieve the above-mentioned purpose, the present application provides a scheduling planning method, the method includes obtaining base station location information, constructing a base station Unicom relationship diagram, and rating base stations according to the relationship diagram; establishing a space-time convolutional network model, and obtaining The initial solution of the model; obtaining a scheduling plan according to the rating result and the initial solution.

Another implementation manner provided by the present application is: the location information of the base station includes the longitude and the latitude of the base station, and the base stations are divided into tower base stations and pole base stations.

Another implementation mode provided by the present application is: assuming that the distance between the two base stations is smaller than the coverage radius of the base station signal, the two base stations are in direct contact, and a base station topology diagram is prepared according to the direct contact.

Another implementation manner provided by the present application is: the ranking adopts the PageRank algorithm.

Another implementation mode provided by the present application is: the rating includes assigning an initial weight of 1 to each of the base stations, and then assigning each of the weights to the base stations that are directly connected with the base station on average, and the weight of the base stations is also Update the sum of the weights given to it by all base stations that are directly connected with the base station; iterate the above process, and the weight of each base station will eventually converge and tend to be stable; assuming θ is the rating threshold of the base station, and the base station with a weight greater than θ The relevant decision variable is the first decision variable, and the change of the first decision variable can have a greater impact on the performance of the entire scheduling system, and the decision variable related to the base station with weight less than θ is the second decision variable However, it is difficult for the change of θ to have a large impact on the performance of the entire scheduling system; the quantities of the first decision variable and the second decision variable can be adjusted by adjusting the value of θ, and the first decision variable is optimized.

Another embodiment provided by this application is: the spatio-temporal convolutional network model is a network flow model that considers both the time dimension and the space dimension, and a series of sustainable The route of is used to cover the task.

Another implementation manner provided by the present application is: in the spatio-temporal convolutional network model, the decision variable is represented by the time of an arc, and the arc connects some event nodes to form a closed loop.

Another implementation manner provided by the present application is: the initial solution is obtained by using cplex.

The present application also provides an application of a scheduling and planning method, which is characterized in that: the scheduling and planning method is applied to traffic planning, logistics distribution or unmanned aerial vehicle scheduling.

Another implementation manner provided by the present application is: the UAV includes three states, represented by three arcs as patrol arc, charging arc, and transfer arc.

3. Beneficial effect

Compared with the prior art, the beneficial effects of the scheduling method and application provided by this application are:

The scheduling and planning method provided in this application is a method for scheduling and planning a base station-unmanned aerial vehicle system.

The scheduling and planning method provided by this application is for the scheduling of UAV maintenance path problems. According to the endurance capability of UAVs, the maintenance capabilities of airports and the execution of flights, it can give a suitable solution according to the specified flight and UAV. schedule.

The dispatching and planning method provided by this application can provide a feasible solution with excellent performance in a short period of time, has extremely high timeliness, and can adjust the trade-off between the accuracy and timeliness of the solution according to needs.

Description of drawings

Fig. 1 is a schematic flow chart of the dispatching planning method of the present application;

FIG. 2 is a schematic diagram of the principle of the scheduling method of the present application;

FIG. 3 is a schematic diagram of a base station connection diagram of the present application;

FIG. 4 is a schematic diagram of the spatio-temporal convolutional network model of the present application.

Detailed ways

Hereinafter, specific embodiments of the present application will be described in detail with reference to the accompanying drawings. According to these detailed descriptions, those skilled in the art can clearly understand the present application and can implement the present application. Without departing from the principle of the present application, the features in different embodiments can be combined to obtain new implementations, or some features in certain embodiments can be replaced to obtain other preferred implementations.

Referring to Figures 1 to 4, the present application provides a scheduling planning method, the method includes obtaining base station location information, building a base station Unicom relationship diagram, and rating base stations according to the relationship diagram; establishing a space-time convolutional network model, and calculating the The initial solution of the model; obtaining a scheduling plan according to the rating result and the initial solution.

Further, the location information of the base station includes the longitude and latitude of the base station, and the base station is divided into a tower base station and a pole base station.

The location information of the base station is composed of the longitude and latitude of the base station. The types of base stations are divided into tower base stations and pole base stations. The English of the tower base station is Tower-base station, and the English of the pole base station is Pole-base station. Among them, tower base stations usually occupy a large area, and most of them have computer rooms, which can be expanded to a certain scale and installed with equipment that provides power for drones. The pole-type base stations do not necessarily exist in the form of poles. Some are disguised as air conditioners, loudspeakers, etc. and placed on various buildings. Therefore, they cannot be expanded, nor can they provide power for drones. But both pole base stations and tower base stations can provide control signals for drones. Since the signal coverage radius of the base station is limited, and the UAV must be controlled continuously during flight, the UAV cannot fly from one base station to a location more than two meters away from the current base station without the help of a third base station. times the coverage radius of the base station's signal. Therefore, assuming that the distance between two base stations is smaller than the signal coverage radius of the base station, the two base stations have a direct connection, and a topological structure diagram of the base station can be made according to this connection. First give each base station an initial weight of 1, and then assign the weight of each base station to the base station directly connected with this base station, and the weight of this base station is also updated to the weight assigned to it by all the base stations directly connected with this base station Sum. Iterating the above process, the weight of each base station will eventually converge and tend to be stable. According to the core idea of PageRank, at this time, changes in decision variables related to base stations with relatively large weights can have a greater impact on the performance of the entire scheduling system, while changes in decision variables related to base stations with relatively small weights It is difficult to have a large impact on the performance of the entire scheduling system, so concentrating computing resources to optimize these decision variables related to base stations with relatively large weights can improve certain efficiency. Suppose θ is the base station rating threshold, and the decision variable related to the base station whose weight is greater than θ is the first decision variable, then the change of the first decision variable can have a greater impact on the performance of the entire scheduling system, and the weight less than The decision variable related to the base station of θ is the second decision variable, and the change is difficult to cause a large impact on the performance of the entire scheduling system; the number of the first decision variable and the second decision variable can be adjusted by adjusting the value of θ, And optimize the first decision variable.

Further, the spatio-temporal convolutional network model is a network flow model that considers the time dimension and the space dimension at the same time. By constructing one or more closed loops in the time dimension and the space dimension, a series of sustainable routes are derived. Using the routes to Tasks are covered.

Further, in the spatio-temporal convolutional network model, the decision variable is represented by the time of an arc, and the arc connects some event nodes to form a closed loop.

Further, the initial solution is obtained by using cplex.

The present application also provides an application of a dispatching planning method, which is applied to traffic planning, logistics distribution or UAV scheduling.

Further, the UAV includes three states, represented by three arcs as patrol arc, charging arc, and transfer arc.

Example

Drones are widely used in rescue and patrol. This study proposes a drone-based patrol system scheme, which uses a communication base station to remotely control the drone through mobile signals and provide charging services. This study introduces the corresponding UAV routing problem and considers how to perform patrol tasks, assign facilities, and schedule recharging activities according to the given location and type. A mixed integer programming model and a heuristic method are proposed.

Get base station location

The location of the base station is an important factor in determining the path of the drone, so the location of the base station is the most basic data of all data, including longitude and latitude.

Get base station type

The type of base station determines the operations that the base station can complete. The types of base stations are divided into tower base station and pole base station. The English of tower base station is Tower-base station, and the English of pole base station is Pole-base station. Among them, tower base stations usually occupy a large area, and most of them have computer rooms, which can be expanded to a certain scale and installed with equipment that provides power for drones. The pole-type base stations do not necessarily exist in the form of poles. Some are disguised as air conditioners, loudspeakers, etc. and placed on various buildings. Therefore, they cannot be expanded, nor can they provide power for drones. But both pole base stations and tower base stations can provide control signals for drones.

Rating base stations

Base stations at different locations have different influences on the overall schedule, so it is necessary to determine which base stations are important to the overall schedule and which are not. This application uses the PageRank method to rate base stations and follows two criteria:

1) Base stations that can directly affect multiple variables have a great impact on the overall schedule

2) Base stations that can indirectly affect multiple variables have a large impact on the overall schedule

design network

This application uses a network flow model that considers both time and space dimensions to model the problem. The details are shown in Figure 4:

Each base station is represented by a time axis. The time flow of the time axis is from top to right. Generally, for the convenience of calculation, the starting point of the time axis is set to zero, and the end point of the time axis can be infinite or finite. , but even if the length of the time axis is infinite, since the endurance time of the UAV is limited, the parameters of the time dimension of the task in the entire network model will not exceed the endurance time of the UAV. In practice, the timeline represented by each base station is continuous, but for the convenience of calculation, it is sometimes possible to use discrete nodes to simplify the timeline without significantly reducing the accuracy of the model. Each time point on each timeline is a potential event, and the start or end of a certain state of the drone can be regarded as an event. Each event node has a flow balance, that is, the amount flowing into the node is equal to the amount flowing out of the node. It can be vividly understood that drones will not disappear out of thin air. The UAV has three states, which are described by three arcs, patrol arc, charging arc, and transfer arc. The time direction of the state arc of patrolling and transfer is the same as that of the time line, and the time direction of the charging arc is opposite to the time direction of the time axis. In this way, the power of the drone has a great correlation with the position of the time dimension where the drone is located. Some arcs connect some nodes to form a closed loop, and a patrol schedule that can be continuously executed can be obtained. An example is shown in Figure 4.

gives the initial solution

According to Figure 4, a mathematical model will be established. All arcs are considered as a decision variable. Each decision variable represents the time of this arc, and the corresponding operation, whether there is a drone to complete it, and no one. number of machines. For example, a patrol arc issued from time zero and area1 represents the patrol starting from time zero, and the value of the corresponding variable represents the number of drones performing this task. If the value of this variable is 2, Then there are two drones to perform this task, if the value of the variable is 0, no drone will perform this task. According to the above description, the decision variable should be a non-negative integer variable. After establishing the mathematical model, bring in the relevant data and change the objective function to optimize the number of charging stations instead of the total cost. At this time, because the objective function is relatively simple, the solver can give a better solution in a relatively short period of time. solution. Taking this solution as the initial solution, the next step can be solved.

give the final solution

In the final solution, the initial solution has been obtained with cplex, and the ratings of the areas where different base stations are located are also obtained. According to the rating, some areas that need to be focused on optimization can be identified, that is, areas with relatively high ratings. According to the rating, the operation in the area whose rating is lower than a certain threshold is set to be equal to the initial solution, and then solve it with cplex, which can obtain a solution with performance similar to or even better than the long-term accurate solution in a very short period of time. Since the initial solution is feasible, after setting some operations to be equal to the initial solution, the problem must also be feasible. After all, there is at least the feasible solution of the initial solution. And different thresholds will lead to different solution time and performance of the scheme. A higher threshold will lead to a shorter solution time and some decline in the performance of the scheme. If the performance of the scheme is to be improved, the threshold needs to be lowered, then increase the solution time.

According to the space-time convolutional network model, if one or more closed loops conforming to the balance of inflow and outflow are obtained, it means that a patrol schedule that can be continuously executed is obtained. If all patrol tasks are covered by a series of closed loops that meet the balance of inflow and outflow, it means that a patrol schedule that can be continuously executed to meet the patrol requirements is obtained.

This application relates to a model framework for mathematical modeling of scheduling problems; an existing spatio-temporal network convolution model is a network model that considers both time and space dimensions, by constructing one or more A closed loop can be derived to derive a series of sustainable routes, and using these routes to cover tasks can achieve very good results.

This application also involves a rating algorithm for reducing the scale of the problem; all variables are optimized indiscriminately, which is a waste of computing power. Therefore, it is not important to figure out which variables can play a key role and which variables are optimized. The optimization of the process is very helpful. Based on the actual network topology, this application uses an algorithm similar to the PageRank algorithm to rate all variables. Variables with high ratings are more important for formulating patrol plans. In this way, the key variables in the problem can be identified.

Although the present application has been described above with reference to specific embodiments, those skilled in the art should understand that many modifications can be made to the configurations and details disclosed in the present application within the principles and scope disclosed in the present application. The protection scope of the present application is determined by the appended claims, and the claims are intended to cover all modifications included in the equivalent literal meaning or scope of the technical features in the claims.

Claims (7)

1. A scheduling method, characterized in that: the method includes obtaining base station location information, constructing a base station Unicom relationship diagram, and rating the base stations according to the relationship diagram; establishing a space-time convolutional network model, and obtaining the model Initial solution; Obtain a scheduling plan according to the rating result and the initial solution; The rating uses the PageRank algorithm; The rating includes giving each of the base stations an initial weight of 1, and then assigning each of the weights to each of the base stations on average The base station has directly connected base stations, and the weight of the base station is also updated as the sum of the weights given to it by all the base stations directly connected with the base station; iterating the above process, the weight of each base station will eventually converge and tend to be stable ; θ is the base station rating threshold, and the decision variable related to the base station with a weight greater than θ is the first decision variable, then the change of the first decision variable can have a greater impact on the performance of the entire scheduling system, and the weight less than The decision variable related to the base station of θ is the second decision variable, and the change of the second decision variable is difficult to cause a large impact on the performance of the entire scheduling system; the number of the first decision variable and the second decision variable can be adjusted by The value of θ is adjusted, and the first decision variable is optimized. 2. The method according to claim 1, wherein the location information of the base station includes the longitude and the latitude of the base station, and the base stations are divided into tower base stations and pole base stations. 3. the method for claim 1 is characterized in that: when two described base station distances are less than the coverage radius of described base station signal, then two described base stations are direct connection, make base station topological structure according to described direct connection picture. 4. The method according to claim 1, wherein the space-time convolutional network model is a network flow model considering both the time dimension and the space dimension, and by constructing one or more closed loops in the time dimension and the space dimension, the derived A series of sustainable routes with which tasks are covered. 5. The method according to claim 4, wherein in the spatio-temporal convolutional network model, the decision variable is represented by the time of an arc, and the arc connects some event nodes to form a closed loop. 6. The method according to claim 1, characterized in that: the initial solution is obtained by cplex. 7. An application of a dispatching and planning method, characterized in that: the dispatching and planning method according to any one of claims 1 to 5 is applied to traffic planning, logistics delivery or UAV scheduling.