Logistics. Part 1. Optimization of air traffic in directions and schedule formation

Surely everyone had to fly in a half-empty plane or meet with a flight transfer, perhaps you thought about the cost-effectiveness and efficiency of such a flight. How much potential profit does the airline lose? Indeed, flights are unprofitable, and sometimes even unprofitable. Can such decisions be explained in terms of the optimal behavior of the air carrier? For example, in the current situation with flight cancellation due to COVID-19: how is the fleet distributed in other directions, which provides a local rate of return? Let's try to build a dynamic model that will respond to external changes and strive to come to a state of equilibrium. In this article, we take only a small set of parameters, try to forecast demand, send planes of lower capacity,reduce the frequency of flights when it is unprofitable.



At first glance, the task is very similar to the “backpack problem”. In fact, there is$$$n$ airports $$$a_{1}, a_{2}, .., a_{i}, .., a_{n}$, each of the airports can accommodate $$$b_{1}, b_{2}, .., b_{i}, .., b_{n}$airplanes. The aircraft themselves are of different types$$$f_{1}, f_{2}, .., f_{j} .., f_{m}$. Aircraft maintenance costs$$$j$type in $$$i$airport cost in $$$z_{ij}$, and profit $$$p_{j}$. Find such$$$x_{ij}$ ($$$x_{ij} \geqslant 0, x_{ij} \in \mathbb{Z}$) at which the total profit is maximized $$$P$:

$$

$$max(P) = \sum_{j = 1}^{m} p_{j}x_{j}\; ; \;\;\; x_{j} = \sum_{i = 1}^{n} x_{ij}$$

and total costs $$$Z$ for the maintenance of aircraft at airports are minimized:

$$

$$min(Z) = \sum_{i = 1}^{n} \sum_{j = 1}^{m}z_{ij}x_{ij}$$

With capacity restrictions for each airport:

$$

$$\sum_{j = 1}^{m} x_{ij} \leqslant b_{i}$$

Now take into account that the airports are interconnected by airlines $$$r_{1}, r_{2}, .., r_{k}, .., r_{l}$. Then, the arrangement of aircraft at airports will have to be carried out not only taking into account their type, but also the direction in which they will fly, i.e. initially sought$$$x_{ij}$ now become $$$x_{ijk}$. Moreover, the directions themselves can be combined into arbitrary routes along which the movement of aircraft occurs.

Model description

Obviously, the value of the total profit and loss depends on some rather complex airline strategy: the selected types of aircraft, the routes drawn up and the schedules for each of them. But to talk about strategies in more detail, you need to make a lot of clarifications.

Demand for air travel

One of the most important parameters for the formation of an optimal strategy is the demand for air travel between individual cities, but the data collected does not allow a reliable idea of ​​it. Nevertheless, even in such conditions of uncertainty, as new information arrives, some actions should be taken aimed at increasing profits and reducing losses.

Some indirect conclusions about the demand for a particular destination can be made on the basis of data on the number of passengers transported through it. For example, if an airplane made 5 flights in a certain direction and was on average more than 90% full, then we can conclude that the demand in this direction is quite large and decide to increase the number of traffic in this direction. On the other hand, if after these five flights on the sixth there was a sharp decrease in the number of passengers, then this factor affects the “average” occupancy in the long run and may be a good reason for adjustments.

The easiest way to make decisions based on such random data is to use moving averages. However, the problem is that the airline cannot afford to experimentally test its hypotheses about demand, that is, if after a flight there has been a sharp decrease in passenger load on the aircraft, then this is already considered a signal for action. For example, in this case, you can reduce the frequency of flights in this direction and increase it in another with a consistently high occupancy rate. On the other hand, knowledge of the average occupancy rate of the previous 10 flights just allows us to more or less accurately judge how stable the occupancy rate of the aircraft in this direction. If the value of the average occupancy rate starts to decrease steadily, then this can serve as a signal for taking more serious measures, for example,replacing an aircraft with an aircraft with a lower capacity, a more dramatic change in the route of the aircraft, or replacing the aircraft and changing its route at the same time.

In order to create a model, suppose that the value of true demand in each direction is a random variable $$$q_{ijt} = \xi(t)$ and can take values ​​from the interval $$$[0, q_{ij, max}]$with the same probability. Now suppose that a plane with maximum capacity runs in this direction$$$d_{j,max}$obviously that if $$$q_{ijt}$ much more than $$$d_{j,max}$, then most likely the plane will be almost full. In order for the modeling process to be possible, suppose that the value$$$q_{ij, max}$in each direction can be roughly estimated, for example, by the size of the cities that are connected by this direction. We also assume that to study the behavior of the model, this value can be changed, but cannot be predicted.

Profit and loss calculation for each individual aircraft

The maintenance costs of each aircraft can be determined by the ratio:

$$

$$z_{ij}(t) = c_{ij}\Delta t + c_{0ij}$$

This ratio shows that the cost of maintaining an aircraft type $$$f_{j}$ at the airport $$$a_{i}$depend on the time of his stay at this airport. There is some fixed charge$$$c_{0ij}$which may be charged for take-off and landing. In the future, this fixed fee increases in proportion to the coefficient$$$c_{ij}$. This ratio does not allow "freezing" of individual planes at some airports, i.e. reflects a very important feature of reality: " aircraft inaction = losses ".

Since we are talking about individual planes, in order to uniquely identify each of them, we introduce another index$$$x = \overline{0, g}$ Where $$$g = \sum x_{ijk}$. Then the profit for each individual aircraft can be calculated by the formula:

$$

$$p_{ijkx} = d_{ijkx}s_{jk} - \beta_{j} \Delta t_{jk}$$

Value $$$d_{ijkx}$ determines how full the plane with index $ x $ is under natural restriction $$$d_{ijkx} \leqslant d_{j,max}$, which shows that the fullness of the aircraft cannot exceed its maximum capacity. The cost of one ticket in the direction$$$r_{k}$ by plane $$$f_{j}$ is set by $$$s_{jk}$. In addition, this formula takes into account that the cost of a flight also depends on the type of aircraft and the time it takes to complete the flight:$$$\beta_{j}$ Is a coefficient that determines the cost per unit time of an aircraft type flight $$$f_{j}$, and $$$\Delta t_{jk}$ - this is the time that this type of aircraft needs to overcome the direction $$$r_{k}$.

If you designate the route of the aircraft as$$$R_{x} = (r_{1},r_{2},..r_{k})$, then the total profit and costs of all flights included in it are recorded as

$$

$$P_{R_{x}} = \sum_{k}(d_{ijkx}s_{jk}-\beta_{j} \Delta t_{jk}) \; ; \;\;\;\;\;\;\; Z_{R_{x}} = \sum_{k}(c_{ij} \Delta t_{ijkx} + c_{0ij})$$

Where $$$k$ runs through the indices of all directions included in the route, and $$$\Delta t_{ijkx}$- this is the delay time of the aircraft at each airport route. Then, the total profit and costs of all aircraft can be calculated by the formulas:

$$

$$P = \sum_{x}\sum_{k}(d_{ijkx}s_{jk}-\beta_{j} \Delta t_{jk}) \; ; \;\;\;\;\;\;\; Z = \sum_{x}\sum_{k}(c_{ij} \Delta t_{ijkx} + c_{0ij})$$

On the other hand, if all the information on the routes of all aircraft is available, the total profit and costs can be calculated by the formulas:

$$

$$P = \sum_{i = 1}^{m} \sum_{j = 1}^{n} \sum_{k = 1}^{l} \sum_{x=1}^{x_{ijk}} (d_{ijkx}s_{jk}-\beta_{j} \Delta t_{jk})\; ; \;\;\;\;\;Z = \sum_{i = 1}^{m} \sum_{j = 1}^{n} \sum_{k = 1}^{l} \sum_{x=1}^{x_{ijk}} (w_{ij} \Delta t_{ijkx} + w_{0ij})$$

Management Cost

The expressions for calculating profits and costs may already be suitable for modeling, but they do not take into account the important fact that after some control action the functioning of the entire system changes, and the restructuring of the entire system cannot be instantaneous. In addition, it should be understood that the control action itself cannot be “magical” in nature, that is, we cannot teleport planes, make them fly for days on end, etc. To synchronize the schedule of one aircraft with the schedules of others, you can either delay or delay its departure. If the moment the control action was applied the aircraft was caught in the air, then we still have to wait for it to land.



In cases where the moment the control action is applied, the plane catches at one of the airports, one more restriction appears - the inability to force the plane to take off immediately after landing. For each type of aircraft, there must be some minimum time spent at the airport$$$\Delta t_{ij,min}$required for mandatory maintenance of the aircraft (refueling, cleaning the cabin, etc.)

$$

$$\Delta t_{ijkx} \geqslant \Delta t_{ij,min}$$

This means that the moment of applying the control action will still have to be correlated with the moment of landing.



After applying the control action, the planes fly again according to a clear, periodic schedule, i.e. the time spent by the aircraft at the airport, with the help of which the schedule is adjusted, may differ from all subsequent equal time intervals. This means that the costs associated with the control action may also differ from all subsequent ones and require separate calculations. Since the control action always correlates with the moment of the aircraft landing, we can designate this time interval as$$$\Delta t_{0, ijkx}$ and determine the costs associated with it using the familiar formula

$$

$$z_{ij}(t) = c_{ij}\Delta t_{0, ijkx} + c_{0ij}$$

The formula for calculating the total cost for all aircraft, also does not undergo much change.

$$

$$Z = \sum_{i = 1}^{m} \sum_{j = 1}^{n} \sum_{k = 1}^{l} \sum_{x=1}^{x_{ijk}} (w_{ij} \Delta t_{0, ijkx} + w_{0ij})$$

Aircraft Routes

One very important requirement is put forward for aircraft routes - cyclicality. This requirement may seem unreasonable, as tight binding of aircraft to such routes may be disadvantageous. However, this requirement does not oblige airplanes to bypass the entire cycle. Also, this requirement does not change the fact that the state of the system is still divided into two stages - “before” and “after” the application of the control action. This means that if any changes have occurred in the system, for example, demand has changed in one of the directions, one of the planes has been delayed or completely broken (disappeared), then only one control action is performed, i.e. all planes begin to carry out their routes cyclically only after it is completed. In principle, if route changes occur very often, after each control action,then there will be no cyclicality in the routes of aircraft. But on the other hand, if after some optimizing, controlling action of route changes no longer follows, then this will mean that the system itself will maintain its optimal and stationary state.

The requirement that all routes be cyclical can also be justified by the fact that there is no information whatsoever about the need for changes in routes in the future, that is, it may turn out that the aircraft will fly an arbitrary amount of time along a certain route without a single adjustment. If this route is not a cycle, then at one iteration it will stop moving. This means that at each iteration it will be necessary to track such stops for each aircraft and make some decisions on their further movement.

In addition to all of the above, there is another important requirement for routes and schedules - the maximum simultaneous stay of aircraft at each airport should not exceed their capacity. Therefore, after drawing up the route, it is necessary to draw up a schedule that could guarantee that at no point in time at any airport there will be more aircraft than he can take. If the planes have very long routes that are not cycles, then you will have to calculate the number of planes at each airport of this route, and these calculations will be related to the routes and schedules of other planes. On the other hand, if airplanes circumvent cyclic routes with a known period, then knowing the frequency of visits to each airport, you can very easily make schedules,which will not lead to excess capacity limits.

Since there is a strict requirement that routes be cycles, it becomes obvious that all routes must consist of simple cycles of a directed graph that models the network. To demonstrate this, we will depict four airports that are interconnected as follows:



This graph consists of six simple cycles:$$$(a_{1},a_{2})$, $$$(a_{2},a_{3})$, $$$(a_{3},a_{4})$, $$$(a_{2},a_{4})$, $$$(a_{2},a_{3},a_{4})$, $$$(a_{2},a_{4},a_{3})$. Cycles obtained by cyclic displacement of their vertices are considered equivalent, for example, cycles will be equivalent:$$$(a_{2},a_{4},a_{3})$, $$$(a_{4},a_{3},a_{2})$ and $$$(a_{3},a_{2},a_{4})$.

However, if it is known that a certain plane is located at a specific airport, then the order of the peaks in its route becomes important. Routing for a specific aircraft located at a certain airport is done by combining elementary cycles, including some cycles in others, or, if the route already contains internal cycles, eliminating them.

Consider a simple example, let's say some plane is located at the airport$$$a_{3}$then it can fly in one of two simple cycles: $$$(a_{3},a_{2})$ and $$$(a_{3},a_{2},a_{4})$. Cycle$$$(a_{3},a_{2})$ can be combined with a cycle $$$(a_{1},a_{2})$, the result is a cycle $$$(a_{3},a_{2},a_{1},a_{2})$. Same cycle$$$(a_{1},a_{2})$ can be included in the cycle $$$(a_{3},a_{2},a_{4})$ resulting in $$$(a_{3},a_{2},a_{1},a_{2},a_{4})$.

Now suppose the plane is at the airport$$$a_{3}$will cycle through the route $$$R_{1}=(a_{3},a_{2},a_{1},a_{2},a_{4})$, but in this case the demand in the directions is not satisfied $$$(a_{4},a_{2})$, $$$(a_{3},a_{4})$ and $$$(a_{2},a_{3})$ this means that you can add another simple cycle to the route of your existing aircraft $$$(a_{3},a_{4},a_{2})$ and get $$$(a_{3},a_{2},a_{1},a_{2},a_{4},a_{3},a_{4},a_{2})$ or add another plane that will cycle through the route $$$R_{2} = (a_{3},a_{4},a_{2})$.

Here it is worth making some clarifications to the concepts of “change” and “replacement” of routes. Changing a route involves modifying it by increasing or decreasing the number of its internal elementary cycles. And replacing a route involves replacing the elementary cycles themselves.
Obviously, aircraft routes can overlap each other, and preferably in those parts of the network where there is particularly high demand.

All simple graph cycles can be found using the Johnson algorithm, whose complexity is equal to$$$O((n+e)(c+1))$where $$$n$ - number of vertices $$$e$ - the number of ribs, and $$$c$- the number of elementary chains. In the future, you should change the routes of the aircraft with the check that the union of the sets of edges. of which they consist$$$R_{x}$coincided with the set of edges of the entire graph $$$E$, i.e. if the total number of aircraft is$$$g$, then the equality should be satisfied:

$$

$$\bigcup_{x = 1}^{g} R_{x} = E$$

Compliance with Airport Capacity Limit

In addition to the fact that the compiled schedule affects the throughput in each of the directions, it also affects the number of aircraft that can be at the airport at the same time. For convenience, imagine that a certain airport can only accept two planes at a time, but this airport is included in the routes of three planes. Obviously, there must be some stringent conditions to comply with the limit.

First, we will try to determine a general approach that takes into account the fact that planes carry out their routes cyclically with a given period and that schedule adjustments are possible with only one control action associated with changing the departure time of the aircraft.



The red dashed line indicates the moment when the system comes to the optimal stationary state. Everything that is up to this line can be considered the time interval when the control action is performed. In this case, it is shown how to change the time intervals$$$t_{0,1}$ and $$$t_{0,2}$You can control the periods when two planes visit the same airport. The figure shows that the aircraft spend a different amount of time at the airport, but at the same time, these time intervals do not overlap. This is only possible if their periods are equal or if the least common multiple of these periods is equal to one of the periods.

For example, if the periods of visiting the airport with two airplanes are 200 and 600 hours, then their offset relative to each other so that they will never visit the airport at the same time can be chosen. But if their periods are 300 and 700 hours, then no matter how they are shifted relative to each other, sooner or later, they will arrive at the airport at the same time.

However, it is also obvious that the control action can be such that this condition is met, but the intervals can still intersect, which means that the following conditions are met (letter $$$a$ in the index means that the plane flew to the airport; $$$d$ - flew out of the airport):

$$

$$\left\{\begin{matrix} t_{1,a} \leqslant t_{2,d} \\ t_{1,d} \geqslant t_{2,a} \end{matrix}\right.$$

If the airport has a capacity of 2 aircraft, but it is included in the route of three aircraft, then pairwise fulfillment of these conditions for all three aircraft at once means that the limit will be exceeded.

On the other hand, if two planes have periods that do not lead to their simultaneous stay at the airport, then the third plane may have an arbitrary period. But in this case, it is imperative that the requirement that his time at the airport be strictly less than the time interval when the two previous aircraft are absent at the airport is met.

This leads to two simple rules for observing the airport capacity limit:

1. If the airport capacity is $$$n$then the periods of stay of the aircraft should be divided into $$$n$ . .
2. $$$n$ .

Strict fulfillment of these conditions can be justified only in one case, when it is known for certain that no control actions are expected in the future. But since there are no such guarantees, these conditions may be somewhat weakened. Moreover, strict fulfillment of these conditions may require very large delays of the aircraft, which are necessary to shift periods, i.e. prove to be very expensive. Therefore, these conditions can be adapted so that the capacity limit is exceeded only after some acceptable period of time, after which the next schedule adjustment can be made. However, there is no guarantee that such a phased adjustment will always lead to a reduction in the cost of adjustments. All this suggests that these rules can serve as the basis for more complex rules,for example, you can adjust the schedules of airplanes whose route has changed, according to the schedules of airplanes whose routes have remained unchanged, or calculate the cost of combinations of various sequential adjustments and select the best one.

The modeling process and optimal decision making

Suppose that at the initial time, the planes are arranged in some random or predetermined order. Since at the initial moment of time, there is no information about the number of passengers carried, at the initial stage there is a “reconnaissance of the situation”. At this stage, before starting the simulation process, it is necessary for each aircraft to assign a certain route. Obviously, all of these routes should cover the entire network of airports and help ensure that all movements between airports are carried out optimally with respect to loading.

The optimization process for some aircraft can be started as soon as the load values ​​are known in all directions of its route. Only at this moment will it be possible to calculate the values ​​of profit and costs from this aircraft on this route, which can be used for the optimization process. If such a change in route and schedule is possible that will increase known profits and reduce costs, then they will replace the previous ones.

Aircraft routes cannot be replaced before all workload values ​​in each direction have been made known, because this will not allow us to judge the total profit and costs. Only after all the workload values ​​in each direction become known, you can start not only to change the routes and schedules of individual planes, but also to changes in the general planning of transportation.

We assign an array to each direction.$$$W_{ij}$ a certain length (for example 5) into which the occupancy values ​​of passengers of each aircraft are entered $$$w_{ijt}$who made a flight in this direction. This array will be a stack of such values. The last value in this array - the load on the previous flight, will allow us to draw conclusions about the need for small tactical actions, and the average value over the entire array will serve as an indicator of the need for serious strategic adjustments.

If the last value of the array$$$W_{ij}$ goes beyond a certain interval $$$w_{ij, min} \leqslant w_{ijt} \leqslant w_{ij, max}$, determining the appropriateness of changes, then appropriate actions are taken to reduce or increase the frequency of flights in this direction. At the same time, if after reducing or increasing the frequency of flights in this direction, the value$$$\overline{W}_{ij}$If it continues to decline or grow anyway, this may be a signal that more fundamental changes are needed, for example, the inclusion of a given direction in the routes of several aircraft or the exclusion of this direction from the routes of all aircraft.

For example, suppose a plane flies along a cyclic route$$$(a_{1},a_{2},a_{3},a_{2})$. Assume the next departure from the airport$$$a_{1}$the number of passengers on the plane fell sharply. In this case, upon arrival at the airport$$$a_{2}$ a decision may be made to change the route $$$(a_{1},a_{2},a_{3},a_{2})$ on the $$$(a_{1},a_{2},a_{3},a_{2},a_{3},a_{2})$. Such a replacement is useful in that if the drop in demand in the direction$$$(a_{1},a_{2})$is not an accident, but a steady trend, then at least there will be a decrease in the frequency of flights in this direction. If, on the next visit to this destination, the number of passengers carried turned out to be as low or even lower, then the route$$$(a_{1},a_{2},a_{3},a_{2},a_{3},a_{2})$ can be changed to route again $$$(a_{1},a_{2},a_{3},a_{2},a_{3},a_{2},a_{3},a_{2})$, which reduces the frequency of visiting directions $$$(a_{1},a_{2})$even stronger. If the direction$$$(a_{1},a_{2})$ continues to decline steadily, you can generally replace the route $$$(a_{1},a_{2},a_{3},a_{2},a_{3},a_{2},a_{3},a_{2})$ on the $$$(a_{3},a_{2})$ or any other route that does not contain directions $$$(a_{1},a_{2})$.

All this can be demonstrated using the following scheme, which shows how the frequency of visiting a destination changes, the profitability of which is greatly reduced:


An indicator to reduce the frequency of flights in a destination$$$(a_{1},a_{2})$ serves the meaning $$$w_{1,2}$, every time it becomes less than 50, a decision is made to visit this direction with less frequency. After the value$$$\overline{W}_{ij}$becomes below the minimum value of the allowable interval, this direction is generally excluded from the route of the aircraft.

Also, for each type of aircraft, you can determine your allowable interval for the average value of the array elements$$$W_{ij}$. If this value is included in the acceptable interval for a certain type of aircraft, but not for an aircraft that is already flying along it, then successive route changes are made that lead to the replacement of aircraft types with more suitable ones.

It may seem that over time, as soon as all the average values ​​of the number of passengers in each direction come to equilibrium, all planes will concentrate in only one, the most profitable route. This would indeed be true if the capacity of each airport was unlimited. But due to the fact that each airport has a capacity$$$b_{i}$some planes will have to fly on less profitable routes. Obviously, it makes sense to perform actions to optimize one or several aircraft only after changes$$$w_{ijt}$ or how some value $$$\overline{W}_{ij}$will move from one interval to another. All this can be depicted as the following diagram:



This diagram shows how routes are changed for five aircraft of four different types (with different capacities). Initially, some aircraft do not perform the most profitable flights, but as more information about the passengers carried appears, their routes change, so as to best match their capacities. Ultimately, an equilibrium state is achieved in which each plane brings the greatest profit, i.e. runs on its routes with the highest possible frequency. The capacity of airports is also taken into account, which does not allow routes to completely overlap.

A very important question arises - how to find optimizing system of actions? This question is directly related to global optimization, i.e. you need to choose such combinations of aircraft routes, their types and schedules, in which the total profit will be maximum and costs will be minimal. If we were only talking about airplanes and their routes, even then the search area for solutions would be extremely large, since the size of the region depends on the number of simple cycles in the airport network factorially, and exponentially on the number of aircraft. Given that the routes can be of different lengths and contain a different number of internal cycles, the most optimistic estimate of the size of the solution space will look like$$$(n!)^m$where $$$n$ Is the number of simple cycles, and $$$m$- the number of aircraft. With the addition of combinations of aircraft types and their schedules, the decision space is expanding factorially even more.

Naturally, the search for optimal actions is possible only with the help of metaheuristic algorithms, and this search will be performed after any strong change in the number of filled seats of an individual aircraft, which can happen quite often. Also, the optimization process is two-stage: first, the search for optimal routes for each type of aircraft is performed, then their schedules are optimized. At the same time, schedule optimization can be an absolutely deterministic process, and thanks to the knowledge of the number of passengers transported in separate simple cycles, changing or replacing routes with more optimal ones can be done much faster than simply sorting out. But you should also remember about the possible local maximums and minimums, for example, the route with the highest degree of load, i.e.the most profitable may require schedules with very long delays at airports, i.e. sharply increase the cost of its maintenance.

The following question arises: “What metaheuristics should I choose: ant, simulated annealing, or evolutionary?” The ant algorithm is good at searching for profitable routes, but at a certain stage of modeling, the need for this search disappears and another appears - changing and replacing routes, and not necessarily with the greatest load of passengers.
The evolutionary algorithm does not guarantee getting into the global maximum and at the same time is very complicated by the rules of the processes of mutation and crossing routes.
Some advantageous parts of the routes may be destroyed by a mutation at the next iteration or not be crossed with profitable parts of other members of the population. However, the dimension of the problem is not so large that it would be very difficult to actually predict this as a fact and to predict how this algorithm will behave.

The simplest and most promising method for searching for optimal actions is an annealing simulation algorithm, it is very simple to implement and configure parameters. This algorithm also allows you to apply various empirical policies for generating more optimal routes, for example, the most profitable simple route cycles can cool faster than less beneficial ones, i.e. undergo smaller changes, which will contribute to the fastest convergence.

Conclusion

Of course, the considered problem is only the tip of the iceberg, and the created model is nothing more than the basis for further research in the next parts of the series of articles. For example, you need to consider that there are many airlines in the civil air transport market, i.e. they have to compete with each other. In the model, demand is represented by an absolutely random variable, but in fact it should have some kind of dependence on the pricing policy of airlines. It is also necessary to take into account that the operation of airports is much more complicated, since the planes in them form something like queues. In addition, there are many different restrictions that are governed by various agreements and laws.

In the future, an accurate model can become an indispensable centralized tool to facilitate analysis and forecasting of the civilian air transportation market and will make the most optimal decisions possible.