CN115204466A - International airline route planning method with traffic limitation - Google Patents

Abstract

The invention discloses a method for planning an international airline route with traffic limitation, which comprises the following steps: 1) Loading the whole network route data to generate a route network diagram; 2) Cutting the navigation line network graph to obtain a directed graph G = { V, E }, wherein V is a set of all nodes in the directed graph G, and E is a set of all navigation sides in the directed graph G; 3) Calculating the shortest distance from the starting point to all the nodes under the condition without limit, calculating the shortest distance from all the nodes to the end point under the condition without limit, and 4) calculating the edge weight of each height layer at each navigation side; 5) Selecting the average value of the edge weights of all height layers at each navigation side as the estimated weight of the navigation side; 6) Determining a horizontal airway satisfying airway restrictions; 7) Determining a vertical airway; 8) And outputting an optimization result. The invention can automatically plan the optimal airway according to the optimization target selected by the user, airway restriction, meteorological wind temperature and other conditions.

Description

An international route planning method with traffic restrictions

technical field

The invention relates to the technical field of civil aviation operation command and dispatch and release, in particular to an international route planning method with passage restrictions.

Background technique

Before carrying out a civil flight, airline dispatchers must perform various complex operations based on meteorological conditions, aeronautical information, airport and alternate conditions, pilotage and navigation rules, aircraft capacity and equipment, and aircraft performance limitations. Restrictions and laws and regulations, determine the actual flight profile, calculate and determine the payload that can be carried, determine the amount of fuel and flight time required for this flight. The above route planning is one of the core technologies of the flight planning system. Through the flight planning system, airlines make computer flight plans and dispatch and release work for each flight to standardize operation management, improve work efficiency, control flight operation risks, and save flights. Operating costs, to achieve increased operating benefits.

At present, the methods of route planning are mainly divided into two categories. The first category is the Optimal Control Theory Approach. The optimal path is obtained without considering the restrictions of the route, and then the rules are checked. If the optimal path is found In violation of the relevant route restriction rules, the route is corrected to meet the restrictions on the basis of this route. The navigation distance, navigation time, fuel consumption and navigation cost of the corrected route and the obtained optimal route may deviate greatly. Therefore, once the optimal route If the route violates the relevant route restriction rules, the actual result quality of route planning cannot be guaranteed. The second category is the Network Optimization Approach. The route side of the network uses a fixed estimated weight value to calculate the optimal path. However, in this method, the weight, wind direction, temperature, etc. of the aircraft have a greater impact on fuel consumption, speed, and cost. The optimization results The error is large.

SUMMARY OF THE INVENTION

The purpose of the present invention is to provide an international route planning method with traffic restrictions, which can automatically plan the best route according to the optimization target selected by the user, route restrictions and meteorological wind temperature and other conditions.

A route planning method for an international route with a passage restriction, comprising the following steps:

1) Load the entire network route data to generate the route network map;

2) According to the set departure airport and landing airport, the airline network map is cut, and the airline network map is compressed to obtain a directed graph G={V, E} for optimization, where V is a directed graph The set of all nodes, E is the set of all route edges;

3) Using the Dijkstra algorithm, calculate the shortest distance from the starting point to all nodes without restrictions and establish a shortest path dictionary MINDict _D , calculate the shortest distance from all nodes to the end point without restrictions and establish a shortest path dictionary MINDict _A , used to estimate the weight of the route edge and used for the subsequent A* algorithm to estimate the estimated distance from the current point to the end point;

4) According to the set optimization target and the data including wind temperature, wind speed and heading angle, calculate the edge weight of each level of each route side;

5) Select the average of the edge weights of all levels on each route side as the estimated weight of the route side;

6) Using the A* algorithm to determine a horizontal route that satisfies the route constraints;

7) Determine the vertical route according to the obtained horizontal route;

8) Output optimization results;

In order to achieve the purpose of controlling airway congestion and other purposes, the air traffic control agency will issue some restrictions on the direction and flow of the airway. Some restrictions need to be combined with the waypoints/routes/airspace passed in the previous sequence to determine whether the conditions are met. Such restrictions cannot be preprocessed in advance. When filtering, it must be checked while planning. It is conservatively estimated that there are currently about 100,000 global air route restrictions. By sorting out these restrictions, they can generally be divided into three types:

(1) Not available - not available: when condition X is true, Y must be false;

(2) Compulsory-must go through: when condition X is false, Y must be true;

(3) Only available-only available: only when condition X is true, Y can be true; where condition X and condition Y may pass through a certain waypoint, a combination of waypoints, a certain route, For a part of a route or a certain airspace, the (3) type can be converted into when the condition X is false, Y must be false, so the present invention classifies the route restriction rules as: (1) Not available - not available, ( 2) Compulsory - must go through;

The A*(A-Star) algorithm is the most effective direct search method for solving the shortest path in the static road network, and it is also an effective algorithm for solving many search problems. The closer the distance estimate in the algorithm is to the actual value, the faster the final search will be. The present invention adopts the improved A* algorithm, and its evaluation function is:

f(n)=g(n)+h(n); where f(n) is the cost estimate for each possible node, which consists of two parts, where g(n) is the actual cost from the starting point to the current node, h(n) is the cost estimate from the current node to the destination, and the shortest distance from each route node to the destination airport is pre-calculated without restriction as h(n), and each node retains multiple expansion paths, And when there are route-related restrictions, h(n) is adjusted to be the shortest path through all the necessary nodes.

The present invention also has the following preferred designs:

In the step 6), the determination process of the horizontal route that meets the route restriction is as follows:

(1) Establish an open list and a close list, all of which are initialized to empty, and initialize the state of all nodes to open;

(2) Initialize two rule sets R _na and R _cmp , where R _na is the (1) Notavailable type rule involved in the optimization scope, and R _cmp is the (2) Compulsory type rule involved in the optimization scope;

(3) Add the starting point S to the open list, and use a five-dimensional label to represent the node {pre-node, cost, weight, time, C _n }, which respectively represent the pre-order node, the cost estimate, and the weight of the aircraft after passing the point. , time and the set of nodes that must be passed through, where pre-node and C _n are initialized to be empty, cost is initialized to the corresponding shortest distance without restriction in MINDict _A , weight is initialized to the take-off weight of the aircraft, and time is initialized to the flight take-off time. If the list is empty, or K shortest paths from the start point to the end point have been found, the program terminates, where K can be valued according to experience;

(4) If the open list is not empty, find the node n with the smallest cost from the open list, that is, the node n with the smallest value of f(n) for path expansion;

(5) Delete node n from the open list. If the state of node n in the close list is close, skip the node and select the next node. Otherwise, check the rules of the corresponding path. If it does not violate the rules, it will The path of the node is added to the close list. If the number of nodes in the close list reaches K after the node n is placed, the state of the node will be changed to close. If the node n is the end point, a path from the start point to the end point will be found. The value of K is set according to experience to ensure feasible and better results;

(6) Traverse node m with outgoing edges from node n. If m is not close, calculate its cost f(m). Since the weight of the aircraft arriving at the starting point of each edge has a great influence on the fuel consumption, cost and time of the edge, the expansion When an edge is reached, the weight of the edge to be extended is recalculated from the starting point based on the actual weight of the aircraft when it reaches the edge, and the MINDict _D is updated and the weight of the aircraft after passing through the edge is recorded. For the current expansion node, check whether the conditions in R _cmp are triggered, If it is, check whether there is a mandatory node specified by the restriction in the must-pass node set, if so, ignore it, otherwise the update must go through the set C _m , if the must-pass set C _m is empty, h(m)=current node to The unrestricted shortest path distance of the target point, otherwise h(m) is the shortest path from the current point to the end point through the must-pass point, that is, the unrestricted shortest path distance from the current node to the starting point in the must-travel set + the must-travel set The unrestricted shortest path distance between the midpoint and the point + the unrestricted shortest path distance between the set end point and the target point, update the cost f(m) of the current expansion node and add it to the open list;

The weight of each route edge is jointly determined by the estimated weight of the shortest path without restriction in the reverse direction and the shortest path with restrictions from the start point to the point in the forward direction, so it is called the bidirectional dynamic estimation weight;

(7) Repeat steps (4) to (6) until the shortest path to the target point is obtained or the open list is empty.

In order to narrow the optimization scope, use the actual route historical data of the route to be optimized within two years to mine and cut the route map, and compress the route network map. The compression method of the route network map in step 2) is as follows: 1 node, if the node is not a node in any path-related restriction conditions and restricted objects, delete the node, and connect the predecessor node and successor node of the node to generate a virtual edge, and the weight of the virtual edge is the node. The sum of the weights of the two route edges with the predecessor node, the node and the successor node.

In order to narrow the optimization range and improve the optimization efficiency, the present invention performs the following filtering processing on the nodes and route edges in the directed graph G:

a) If the node is not a node in any path-related restriction conditions and restricted objects and satisfies NM>C(N+M), where N is the in-degree of the node, M is the out-degree of the node, and C is a given parameter, delete the node, and connect the predecessor node and successor node of the node to generate a virtual edge;

b) If there is another path shorter than the virtual edge between two nodes connected by any virtual edge, delete the virtual edge with the longer path;

c) Rules that have nothing to do with passing waypoints, routes, airspace or the time to reach a certain waypoint, route or airspace and which can be directly filtered by the departure and landing time of the flight are called static rules. The aircraft type, departure airport, and arrival airport preprocess the static rules, filter out the corresponding waypoints, routes and airspaces, and do not generate corresponding nodes and route edges in the directed graph G.

When planning international routes, the global route network is huge. Through the clipping of the route map, the compression of the route network map, and the preprocessing of the static rules, the optimization scope is narrowed and the nodes that are not necessarily on the shortest route due to limitations are eliminated, which effectively improves the optimization. speed.

The route optimization objectives include four types: the shortest distance, the most time-saving, the most fuel-efficient and the most cost-effective. The present invention calculates the edge weights of each flight route and each level for different optimization objectives:

If the optimization objective is the shortest distance, the distance to the ground on the side of the route is used as the weight of the edge;

If the optimization goal is the most time-saving, the time when the aircraft passes the airway edge is used as the edge weight;

If the optimization goal is the most fuel-efficient, the fuel consumption of the aircraft passing the route is used as the edge weight;

If the optimization objective is the most cost-saving, the cost of the aircraft passing the airway side is used as the edge weight.

As a feasible implementation manner: the time when the aircraft passes the airway side is obtained through the following process:

查找所述最短路径字典MINDict_A得到所有节点到终点的最短距离

则飞机经过每个节点的估计重量

其中fc为单位距离油耗，

为该点到目标机场的最短距离，W_ZFW为飞机无油重；Estimate the weight of the plane when it passes through each node, and look up the shortest path dictionary MINDict _D to get the shortest distance between the starting point and all nodes

Find the shortest path dictionary MINDict _A to get the shortest distance from all nodes to the end point

then the estimated weight of the aircraft passing through each node

where fc is the fuel consumption per unit distance,

is the shortest distance from this point to the target airport, W _ZFW is the weight of the aircraft without oil;

其中t为单位距离耗时，

为该点距离起点的距离，T_dep为起飞时间；Estimate the time when the plane passes each point:

where t is the unit distance time,

is the distance from the point to the starting point, and T _dep is the take-off time;

According to the airspeed, wind speed, heading angle composite ground speed:

其中v_a为飞机速度，v_w为风速，θ为风与航线的夹角；

where v _a is the aircraft speed, v _w is the wind speed, and θ is the angle between the wind and the route;

其中L_e为该航路边的长度。the time for the aircraft to pass the airway

where _Le is the length of the airway side.

As a feasible implementation manner, the fuel consumption of the route side is: F _e =T _e *FF _e , where FF _e is the fuel flow corresponding to the route side, and T _e is the time for the aircraft to pass the route side.

其中

为燃油相关成本、

为时间相关成本、

为航路相关成本。As a feasible implementation manner, the cost of the wayside is:

in

for fuel-related costs,

for time-related costs,

for the route-related costs.

The optimization of the vertical route of the present invention adopts a greedy algorithm, and selects the altitude with the lowest cost among the multiple altitude layers as the flight height of the aircraft for iterative calculation. When the calculated landing weight of the aircraft and the input standard landing weight are within 10KG. The iteration ends.

The planning method of the present invention adds a constraint that the height difference between adjacent airways does not exceed a threshold value in the cruise phase, so as to avoid jumps in the altitude during the cruise phase.

The present invention has the following beneficial effects:

1. Through the improved A* algorithm, the present invention provides a civil aviation route optimization method for bidirectional dynamic estimation weights that satisfies complex route restrictions, and can expand multiple optimal paths under route-related restrictions to avoid encountering unrestricted routes. When the optimal path violates the rules, the quality of the correction path result cannot be guaranteed.

2. The present invention cuts the route map, compresses the route network map, and preprocesses the static rules, narrows the optimization scope and eliminates the nodes that are no longer on the shortest route due to the limitation problem, thereby effectively improving the optimization speed.

3. The present invention is aimed at the optimization goals of the shortest distance, the most time-saving, the most fuel-saving and the most cost-saving, and the weights of the airway sides are respectively estimated, and the influence of the aircraft weight, wind direction, temperature, and speed cost is considered, and the error of the optimization result is reduced. .

Description of drawings

Fig. 1 is the flow chart of a kind of international route planning method of the present invention with the restriction of passage;

Fig. 2 is the cropping schematic diagram of the route network diagram in the embodiment;

FIG. 3 is a schematic diagram of a route planning result in an embodiment.

Detailed ways

The technical solutions of the present invention are described in detail below with reference to the accompanying drawings and embodiments, so that those skilled in the art can better understand and implement the technical solutions of the present invention.

An international route planning method with traffic restrictions, as shown in Figure 1, includes the following steps:

1) Load the entire network route data to generate the route network map.

2) According to the set departure airport and landing airport, the airline network map is cut, and the airline network map is compressed to obtain a directed graph G={V, E} for optimization, where V is a directed graph The set of all nodes, E is the set of all route edges.

In this embodiment, the actual route historical data within two years of the route to be optimized is used for mining and the route map is trimmed. The trimming method is shown in Figure 2. The departure airport and the landing airport are the center of the circle, and the route network within the radius R is the optimization range. Only the airway edges within this range are considered to effectively reduce the calculation scale, where R=r ₁ *|F ₁ F ₂ |+375*1852, _r1 is 0.0045. To ensure that the ellipse range is not too small, the minimum value of R is 400 nautical miles and the maximum value is 1000 nautical miles.

The ellipse is the trajectory of the moving point E where the sum of the distances from the start point F1 and the end point F2 is equal to a constant (greater than |F1F2|), and F1 and F2 are the two foci of the ellipse. Its mathematical expression is: |EF1|+|EF2|=2a(2a>|F1F2|).

In this embodiment, 2a=|F ₁ F ₂ |+2R.

The route network graph is compressed. The compression method is as follows: For a node with an in-out degree of 1, if the node is not a node in any path-related restriction conditions and restricted objects, delete the node and connect the predecessor of the node. The virtual edge is generated by the node and the successor node, and the weight of the virtual edge is the sum of the weights of the two route edges of the node and the predecessor node and the node and the successor node.

As a preferred embodiment: in order to narrow the optimization scope and improve the optimization efficiency, the following filtering processing is performed for the nodes and route edges in the directed graph G:

a) If the node is not a node in any path-related restriction conditions and restricted objects and satisfies NM>C(N+M) (where N is the in-degree of the node, M is the out-degree of the node, and C is the given parameter), delete the node, and connect the predecessor node and successor node of the node to generate a virtual edge;

b) If there is another path shorter than the virtual edge between two nodes connected by any virtual edge, delete the virtual edge with the longer path;

c) Rules that have nothing to do with passing waypoints, routes, airspace or the time to reach a certain waypoint, route or airspace and which can be directly filtered by the departure and landing time of the flight are called static rules. The aircraft type, departure airport, and arrival airport preprocess the static rules, filter out the corresponding waypoints, routes and airspaces, and do not generate corresponding nodes and route edges in the directed graph G. The static rules are filtered from the notification data. After filtering, the notification data is a kind of restricted data in route planning. It is mainly used to describe the available status of restricted objects such as waypoints, route edges, and airspaces. The restriction types are usually time and edge height restrictions, and such restrictions are not subject to pre-order The influence of the route can be preprocessed to narrow the optimization scope.

3) Using the Dijkstra algorithm, calculate the shortest distance from the starting point to all nodes without restrictions and establish a shortest path dictionary MINDict _D , calculate the shortest distance from all nodes to the end point without restrictions and establish a shortest path dictionary MINDict _A , used to estimate the weight of the route edge and used for the subsequent A* algorithm to estimate the estimated distance from the current point to the end point.

In this embodiment, the calculation steps of MINDict _D are as follows:

1) Declare an array dis to save the shortest distance from the source point to each vertex and a collection T of vertices that have found the shortest path;

2) The path weight of the source point s is assigned as 0 (dis[s]=0). If there is an edge (s,m) that s can reach directly to the vertex v, then let dis[m]=w(s,m ), where w(s,m) is the weight of the edge (s,m). At the same time, the path length of all other vertices (that is, vertices that s cannot reach directly) is set to +∞. Initially, the set T has only vertex s;

3) Select the minimum value from the dis array, then the value is the shortest path from the source point s to the vertex corresponding to the value, and this point is added to the set T;

4) Check whether the newly added vertex can reach other vertices and judge whether the length of the path to other points through the vertex is shorter than that of the source point directly. If so, replace the values of these vertices in dis;

5) Find the minimum value from dis and repeat 3) and 4) until the set T contains the target point,

Similarly, MINDict _A can be obtained.

4) According to the set optimization target and the data including wind temperature, wind speed and heading angle, calculate the edge weight of each level of each route side.

The route optimization objectives include four types: the shortest distance, the most time-saving, the most fuel-efficient and the most cost-effective. For different optimization objectives, the edge weights of each level of each route are calculated.

If the optimization objective is the shortest distance, the distance to the ground of the airway side is used as the weight of the edge.

If the optimization goal is to save the most time, the time when the aircraft passes the airway edge is used as the edge weight. The time for the aircraft to pass the wayside is obtained by the following process:

查找所述最短路径字典MINDict_A得到所有节点到终点的最短距离

则飞机经过每个节点的估计重量

其中fc为单位距离油耗，

为该点到目标机场的最短距离，W_ZFW为飞机无油重；Estimate the weight of the plane when it passes through each node, and look up the shortest path dictionary MINDict _D to get the shortest distance between the starting point and all nodes

Find the shortest path dictionary MINDict _A to get the shortest distance from all nodes to the end point

then the estimated weight of the aircraft passing through each node

where fc is the fuel consumption per unit distance,

is the shortest distance from this point to the target airport, W _ZFW is the weight of the aircraft without oil;

其中t为单位距离耗时，

为该点距离起点的距离，T_dep为起飞时间；Estimate the time when the plane passes each point:

where t is the unit distance time,

is the distance from the point to the starting point, and T _dep is the take-off time;

According to the airspeed, wind speed, heading angle composite ground speed:

其中v_a为飞机速度，v_w为风速，θ为风与航线的夹角；

where v _a is the aircraft speed, v _w is the wind speed, and θ is the angle between the wind and the route;

其中L_e为该航路边的长度。the time for the aircraft to pass the airway

where _Le is the length of the airway side.

If the optimization objective is the most fuel-efficient, the fuel consumption of the aircraft passing the route is used as the edge weight. The fuel consumption on the route side is: _{Fe =T e *} FF _e , where FF _e is the fuel flow corresponding to the route side, and T _e is the time for the aircraft to pass the route side.

If the optimization objective is the most cost-saving, the cost of the aircraft passing the airway side is used as the edge weight.

其中

为燃油相关成本；

为时间相关成本，主要是时间相关的飞机维修成本、时间相关的员工成本；

为航路相关成本，主要为航路费。Said wayside costs are:

in

for fuel-related costs;

Time-related costs, mainly time-related aircraft maintenance costs and time-related staff costs;

It is the cost related to the route, mainly the route fee.

5) Select the average of the edge weights of all levels on each route side as the estimated weight of the route side;

6) Using the A ^* algorithm to determine a horizontal route that satisfies the route constraints;

In order to achieve the purpose of controlling airway congestion and other purposes, the air traffic control agency will issue some restrictions on the direction and flow of the airway. Some restrictions need to be combined with the waypoints/routes/airspace passed in the previous sequence to determine whether the conditions are met. Such restrictions cannot be preprocessed in advance. When filtering, it must be checked while planning. It is conservatively estimated that there are currently about 100,000 global air route restrictions. By sorting out these restrictions, they can generally be divided into three types:

(1) Not available - not available: when condition X is true, Y must be false;

(2) Compulsory-must go through: when condition X is false, Y must be true;

(3) Only available-only available: only when condition X is true, Y can be true; where condition X and condition Y may pass through a certain waypoint, a combination of waypoints, a certain route, A part of a route or a certain airspace, the type (3) can be converted into when the condition X is false, Y must be false, so the route restriction rules can be classified as: (1) Not available - not available, (2) )Compulsory - must go through;

The A*(A-Star) algorithm is the most effective direct search method for solving the shortest path in the static road network, and it is also an effective algorithm for solving many search problems. The closer the distance estimate in the algorithm is to the actual value, the faster the final search will be. The present invention adopts the improved A ^* algorithm, and its evaluation function is:

f(n)=g(n)+h(n); where f(n) is the cost estimate for each possible node, which consists of two parts, where g(n) is the actual cost from the starting point to the current node, h(n) is the cost estimate from the current node to the destination, the shortest distance from each route node to the destination airport pre-calculated in MINDict _A without restrictions is used as h(n), and each node retains multiple extensions path, and adjust h(n) to be the shortest path through all necessary nodes when there are route-related restrictions.

The process of determining the horizontal route that satisfies the route limitation is as follows:

(1) Establish an open list and a close list, all of which are initialized to empty, and initialize the state of all nodes to open;

(2) Initialize two rule sets R _na and R _cmp , where R _na is the (1) Notavailable type rule involved in the optimization scope, and R _cmp is the (2) Compulsory type rule involved in the optimization scope;

(3) Add the starting point S to the open list, and use a five-dimensional label to represent the node {pre-node, cost, weight, time, C _n }, which respectively represent the pre-order node, the cost estimate, and the weight of the aircraft after passing the point. , time and the set of nodes that must be passed through, where pre-node and C _n are initialized to be empty, cost is initialized to the corresponding shortest distance without restriction in MINDict _A , weight is initialized to the take-off weight of the aircraft, and time is initialized to the flight take-off time. If the list is empty, or K shortest paths from the start point to the end point have been found, the program terminates, where K can be valued according to experience;

(4) If the open list is not empty, find the node n with the smallest cost from the open list, that is, the node n with the smallest value of f(n) for path expansion;

(5) Delete node n from the open list. If the state of node n in the close list is close, skip the node and select the next node. Otherwise, check the rules of the corresponding path. If it does not violate the rules, it will The path of the node is added to the close list. If the number of nodes in the close list reaches K after the node n is placed, the state of the node is changed to close. If the node n is the end point, a path from the start point to the end point is found;

(6) Traverse node m with outgoing edges from node n. If m is not close, calculate its cost f(m). Since the weight of the aircraft arriving at the starting point of each edge has a great influence on the fuel consumption, cost and time of the edge, the expansion When an edge is reached, the weight of the edge to be extended is recalculated from the starting point based on the actual weight of the aircraft when it reaches the edge, and the MINDict _D is updated and the weight of the aircraft after passing through the edge is recorded. For the current expansion node, check whether the conditions in R _cmp are triggered, If it is, check whether there is a mandatory node specified by the restriction in the must-pass node set, if so, ignore it, otherwise the update must go through the set C _m , if the must-pass set C _m is empty, h(m)=current node to The unrestricted shortest path distance of the target point, otherwise h(m) is the shortest path from the current point to the end point through the must-pass point, that is, the unrestricted shortest path distance from the current node to the starting point in the must-travel set + the must-travel set The unrestricted shortest path distance between the midpoint and the point + the unrestricted shortest path distance between the set end point and the target point, update the cost f(m) of the current expansion node and add it to the open list;

The weight of each route edge is jointly determined by the estimated weight of the shortest path without restriction in the reverse direction and the shortest path with restrictions from the start point to the point in the forward direction, so it is called the bidirectional dynamic estimation weight;

(7) Repeat steps (4) to (6) until the shortest path to the target point is obtained or the open list is empty.

7) Determine the vertical route according to the obtained horizontal route;

To determine the flight height of the aircraft in the air, the best altitude can be directly used as the flight altitude of the aircraft during the vertical optimization of the shortest distance algorithm. The vertical optimization algorithm that saves the most time and fuel uses the greedy algorithm. Select the most time-saving, fuel-saving, and cost-saving level among the altitude levels as the flight level of the aircraft for calculation.

In the process of vertical optimization, when the cruise calculation is performed for each edge, it is necessary to estimate the cruise end point in advance, that is, the TOD point. The following judgments need to be made: 1) Judging from the starting point of the edge, whether it can reach the BOD point, that is, the bottom point of the descent; 2) Whether it can reach the BOD point when descending from the end point; 3) If the former can reach the BOD but the latter If not, start descending from this side, calculate the TOD point information, and end the cruise.

As shown in Figure 3, A is the departure airport, G is the target airport, and the known horizontal road from A to G is ABCDEFG;

The gray line indicates whether it can reach the BOD point when descending from this point. When the TOC, C, D, and E points are judged, the BOD point can be reached, but when the F point is judged, the remaining horizontal distance is not enough to make the aircraft. It descends to the ground, so it should start from the EF side to do the descending process, calculate the TOD point, and end the cruise.

The optimization of the vertical route adopts a greedy algorithm, and selects the altitude with the least cost as the flight height of the aircraft for iterative calculation. When the difference between the calculated landing weight of the aircraft and the input standard landing weight is within 10KG, the iteration ends.

The planning method of the present invention adds a constraint that the height difference between adjacent airways does not exceed a threshold value in the cruise phase, so as to avoid jumps in the altitude during the cruise phase.

8) Output optimization results;

The following are the comparison test data of the route planning method of the present invention and the route planning software LIDO commonly used by airlines:

The effect of the route planning of the present invention is verified by taking the Guangzhou-Amsterdam route as the test route. The data in Table 1 is the comparison between the optimization results calculated according to different optimization objectives and the commonly used route planning software LIDO. When comparing, all restrictions of the route taken are considered according to the actual situation. It can be seen that the difference between the calculation prediction result of the present invention and the LIDO prediction result is not more than 1%. The shortest distance result is better than LIDO. It shows that the method of the present invention achieves the optimization goal, and the result can be used to plan a route with restrictions.

Table 1.

The above-mentioned embodiments are only preferred embodiments of the present invention, but are not intended to limit the invention. Any modifications and improvements made on the basis of the concept of the present invention should fall within the protection scope of the present invention. The specific protection scope is as follows: The claims record shall prevail.

Claims (10)

1. A method for planning an international airline route with a traffic limit is characterized by comprising the following steps:

1) Loading the whole network route data to generate a route network diagram;

2) Cutting the air line network graph according to a set takeoff airport and a set landing airport, and compressing the air line network graph to obtain a directed graph G = { V, E } for optimization, wherein V is a set of all nodes in the directed graph G, and E is a set of all navigation sides in the directed graph G;

3) Using Dijkstra algorithm to calculate the shortest distance from the starting point to all nodes without limit and establish a shortest path dictionary MINDCit _D Calculating the shortest distance from all nodes to the end point without limitation and establishing a shortest path dictionary MINDICT _A The method is used for estimating the weight of the navigation side and estimating the estimated distance from the current point to the terminal point by the subsequent A-star algorithm;

4) Calculating the edge weight of each altitude layer at each navigation side according to a set optimization target and data comprising wind temperature, wind speed and course angle;

5) Selecting the average value of the edge weights of all height layers at each navigation side as the estimated weight of the navigation side;

6) Determining a horizontal route meeting route limit by using the A-x algorithm;

7) Determining a vertical airway according to the obtained horizontal airway;

8) Outputting an optimization result;

the route restriction rules are classified as: (1) Not available-Not-passable; (2) The Compulsory-must pass through,

a is described ^* The evaluation function of the algorithm is:

f (n) = g (n) + h (n); where f (n) is the cost estimate for each possible node, and is composed of two parts, where g (n) is the actual cost from the start point to the current node, and h (n) is the cost estimate from the current node to the end point, in MINDICT _A The pre-calculated shortest distance from each route node to the destination airport without the restriction is used as h (n), each node reserves a plurality of extension paths, and adjusts h (n) to be the shortest path passing through all necessary nodes when the relevant restriction of the route exists.

2. The method of restricted international airline route planning according to claim 1, characterized by: in the step 6), the determination process of the horizontal route meeting the route limit is as follows:

(1) Establishing an open list and a close list, initializing the open list and the close list to be empty, and initializing the states of all nodes to be open;

(2) Initializing two rule sets R _na And R _cmp ，R _na To optimize the Not available type rules of class (1), R, involved in the scope _cmp The rule is the rule of the category (2) Comulsory type involved in the optimization scope;

(3) Adding the starting point S into the openlist, and representing the node { pre-node, cost, weight, time, C by using a five-dimensional label _n Represents the preorder node, cost estimate, weight after the plane passes the point, time and must pass the node set, wherein pre-node, C _n Initialization to null, cost initialization to MINDICT _A If the open list is empty or the shortest path from the K starting points to the end point is found, the program is terminated;

(4) If the openlist is not empty, finding the node n with the minimum cost, namely the minimum f (n) value from the openlist to carry out path expansion;

(5) Deleting the node n from the open list, skipping the node if the state of the node n in the close list is close, selecting the next node, otherwise, carrying out rule check on the corresponding path, adding the path of the node into close if the rule is not violated, modifying the state of the node into close if the number of the nodes in close reaches K after the nodes are placed in the node n, and finding a path from the starting point to the end point if the node n is the end point;

(6) Traversing the node m of the node n with the outgoing edge, if m is not close, calculating the cost f (m), because the weight of the airplane reaching the starting point of each edge has great influence on the oil consumption, the cost and the time of the edge, when the edge is expanded, the weight of the edge to be expanded is calculated from the starting point in the forward direction again according to the actual weight of the airplane when the edge is reached, and updating MINDICT _D And recording the weight of the aircraft after passing the edge, and checking whether R is triggered or not for the current expansion node _cmp If yes, checking whether the requisite node specified by the limitation exists in the requisite node set, if yes, ignoring, otherwise updating the requisite set C _m If necessary set C _m Null, h (m) = current node toIf not, h (m) is the shortest path from the current point to the end point through the must-pass point, namely the shortest path from the current node to the start point in the must-pass set without limitation + the shortest path between the middle point and the point in the must-pass set without limitation + the shortest path from the end point of the must-pass set to the target point without limitation, and the cost f (m) of the current extended node is updated and added into openlist;

the weight of each navigation side is determined by the estimation weight of the shortest path without limit from the reverse direction to the end point and the estimation weight of the shortest path with limit from the starting point to the forward direction, so the weight is called as the bidirectional dynamic estimation weight;

(7) And (5) repeating the steps (4) to (6) until the shortest path of the target point is obtained or the openlist is empty.

3. The method for planning an international airline route with traffic restriction according to claim 2, wherein the compression manner of the airline network map in the step 2) is: and for the node with the access degree of 1, if the node is not the node in any path-related condition and any path-related restricted object, deleting the node, connecting a predecessor node and a successor node of the node to generate a virtual edge, wherein the weight of the virtual edge is the sum of the weights of the node and the predecessor node as well as the two navigation sides of the node and the successor node.

4. The method of restricted international airline route planning according to claim 3, wherein the following filtering process is performed for the nodes and route edges in the directed graph G:

a) If the node is not any condition in the path-related constraint and the node in the constrained object and meets NM > C (N + M) (wherein N is the degree of entry of the node, M is the degree of exit of the node, and C is a given parameter), deleting the node, and connecting a predecessor node and a successor node of the node to generate a virtual edge;

b) If another path which is shorter than the virtual edge exists between two nodes connected by any virtual edge, deleting the virtual edge with the longer path;

c) The rules which are irrelevant to the passing waypoints, the routes and the airspaces or the time for arriving at a certain waypoint, the route and the airspace and can be directly filtered through the taking-off time and the landing time of flights are called static rules, the static rules are preprocessed according to the known information including set model, set airport and set arriving airport, the corresponding waypoints, the routes and the airspaces are filtered, and the corresponding nodes and route edges are not generated in the directed graph G.

5. The method for planning a restricted international airline route according to claim 1, characterized in that in steps 4) and 5):

if the optimization target is the shortest distance, taking the ground distance of the navigation side as the side weight;

if the optimization target is the most time-saving, the time of the aircraft passing through the navigation side is taken as the side weight;

if the optimization target is the most fuel-saving, taking the oil consumption of the aircraft passing through the side of the navigation road as the side weight;

and if the optimization target is the most cost-saving, taking the cost of the aircraft passing through the side of the navigation as the side weight.

6. The method of restricted international airline route planning according to claim 5, wherein the time for the aircraft to pass by the route side is obtained by:

estimating the weight of the airplane passing through each node, and searching the shortest path dictionary MINDICt _D Obtaining the shortest distance between the starting point and all the nodes

Looking up the shortest path dictionary MINDict _A Obtaining the shortest distance from all nodes to the terminal

The estimated weight of the aircraft passing each node

Wherein fc is the unit distance oil consumption,

the shortest distance, W, from the point to the target airport _ZFW The airplane has no oil weight;

estimating the time when the aircraft passes each point:

where t is the elapsed time per unit distance,

is the distance of the point from the starting point, T _dep Is the takeoff time;

synthesizing the ground speed according to the vacuum speed, the wind speed and the course angle:

wherein v is _a As aircraft speed, v _w The wind speed is theta, and theta is an included angle between wind and a flight line;

the time when the plane passes by the navigation side

Wherein L is _e Is the length of the edge of the airway.

7. The method of claim 5, wherein the fuel consumption at the roadside is: f _e ＝T _e *FF _e Wherein FF _e Fuel flow, T, for the fairway side _e The time when the aircraft passes by the navigation side.

8. The method of restricted international airline route planning of claim 5, wherein the cost of the route side is:

wherein

The relative cost of fuel oil,

For time-related costs,

For the cost associated with the airway.

9. The method for planning a restricted international airline route according to claim 1, characterized in that in step 7): and optimizing the vertical air route by adopting a greedy algorithm, selecting the height layer with the minimum cost from the plurality of height layers as the flight height of the airplane to carry out iterative computation, and finishing the iteration when the difference between the computed airplane landing weight and the input standard landing weight is less than 10 KG.

10. The method of restricted international airline route planning according to claim 9, wherein a constraint is added during the cruise phase that the difference in altitude between adjacent airlines does not exceed a threshold value, to avoid a jump in the altitude layer during the cruise phase.

Images