Introduction to Aviation Logistics. From Simple to Complex
Everybody loves to dream, especially when talking about exploring new places or returning to those which have already became favorite. The anticipation of the future journey inspires until it is overshadowed by the presence of organizational needs such as choice and purchase of tickets. For some reason, we always postpone this issue until it is too late or delegate it to someone who can deal with it on their own: tour operators, metasearch engines or other aggregators. Most of us, for sure, have encountered situations when you get a message:
Sorry, currently we don’t have any results to show. Please change search parameters.
As can often happen, we do not get the desired result in response to our initial request for a route search. This makes us jumping from one website to another in order to get a satisfying result for our search. The main reason of these issues to be occurring are the lack of direct connection to desired destination or pre-provided connection routes. Moreover, offered routes with connections often can include layover for more than 5–6 hours, or even a whole day.
How can this be when having such a variety of airlines, we still get results that do not always satisfy us? Since we have already started the discussion, how are the search mechanisms for route options built in terms of algorithm? In order to answer these questions, we will refer to applied mathematics with the use of algorithms and evaluation criteria.
When faced the task of creating a search system that would search for optimal routes, I already had a long-time experience of different types solving logistic issues. This idea seemed to be very cut and dried to me, as I was sure that it could be solved by simple methods and in a relatively short time. As you are reading the article right now, you can already guess that it actually was not like initially expected.
The starting point of the project was the decision to build a transportation network in the form of a graph. The transportation network initially included data on airports, airlines, their schedules with flights and connection time figures.
It was taken as a basis that airports are considered as the vertex of the graph and the edges are flights between them. As a result, we got something like a backbone (as a skeleton has) on the basis of which we added a schedule. The schedule had its own characteristics: departure and arrival times. At the same time, the movement along the edges was always possible only at a certain time, which was characterized by particular problem solutions:
- minimum travel time;
- minimum number of stops;
- layover between flights when choosing connection routes.
However, we still have the difficulty that the query always contains interrelated search criteria that include one or two or more refinements. The following means that the application of criteria approach imposes certain conditions on the calculation of the searched route variants. In addition to the conditions listed above, service classes, total cost, number of passengers and their categories, as well as the presence of a number of additional services affecting the result are put into the calculation. Taking all of the above into account, it was finally able to fit into my concept of solving the problem by multi-objective optimization: searching for the shortest path according to several criteria (MOSP, or multi-objective shortest path).
One more way of the problem solution we considered the application of nonlinear programming. We decided to look into this one too, as the approach is:
In order to test one hypothesis, it is necessary to provide a number of other hypotheses.
Due to the arcs of the graph being weighted as vectors, the solution of the problem could be reduced to nonlinear programming. The solution could be perfect, if not for the fact that vectors only had two characteristics: length and projection on coordinate axes, which means the presence in the target function of variables with degree no greater than two. However, in my case, the components of vectors are conflicting with each other, which means that the case is completely opposite to nonlinear programming. In order to understand it better, let us have an example: a conflict can occur in any situation because each flight has a certain aircraft capacity and it is impossible to sell more seats for it than presented.
When the analysis part of the project was done, I proceeded with decomposition into the following parts:
- schedule-based search for all the shortest routes to destination;
- search among the shortest routes for the most optimal one on the basis of criteria approach.
After decomposition, the logically followed question appeared:
Which approach to use when building a transportation route network?
Which of the available graphs is more acceptable for solving this problem?
Time-extended model
A time-extended graph is a directed graph. The arcs of such a graph are weighted as the directions of departure and arrival points of flights, and the vertices are the slots of available flights (take-off and landing times). The purpose of the time-extended model is to extend the original graph with airports by vertices and arcs, reflecting route connections by connecting airports to each other according to flight schedules:
Arcs are labeled as: e(BC,3). For example, an arc is connecting airport B to airport С and is directed from B to C, while the index 3 indicated by a comma means that this is not the only flight but the third one. Each arc can easily be weighted, for example: the weight of the arc e(BC,3) can be calculated as
w(BC,3) = t(C,9) − t(B,6). The vertices within a single airport are easily organized according to the time value of each flight. Similarly, based on the connection time within the airport, flights are connected by arcs that correspond to the available transfer time from one flight to another.
The advantage of the time-extended graph is that the fastest route can be found in minimum time, e.g., using Dijkstra’s algorithm. The disadvantage of using this approach is the multiple increase of vertices and edges, which, however, does not affect the sparsity of the graph, because the increase in the number of edges is proportional to the increase in the number of vertices.
Time-dependent model
A time-dependent graph is a directed graph without additional transformations being made over the original graph. Each arc corresponds to a route with links between airports, while the arc has a special data set including parameters for departure and arrival times of flights along the route. The value extracted from this dataset depends on the exact moment at which the arc is accessed, that is why the name of the model is time-dependent.
The advantage of the time-dependent graph is an ability to find the path with the fewest number of connections. As for the disadvantage, the excessive data load of each arc can be mentioned.
Multigraph
A multigraph is a directed graph with a set of features inherent in the time-extended and time-dependent models.
The number of arcs between airports here is the same as in the time-extended model, but these arcs are weighted by departure and arrival times. In this case, the connection time in each airport will have to be constantly and repeatedly calculated. On the other hand, the multigraph representation has exactly the same amount of flight information as the time-dependent model, but all this information is assigned to multiple arcs. Searching for the route with the least number of stops will be as simple as in the time-dependent model. However, passing along one arc does not take into account the information of other arcs, which means that even after the route with the least number of stops is found, the algorithm will have to be run again in order to calculate the data about other flights (arcs).
Representing the transportation route network as a multigraph is kind of a draft state for the time-extended and time-dependent models. The search for the fastest route will be performed by the same transformations, typical for the time-extended model. The search for the route with the least number of stops will be performed by the time-dependent model. The problem in this case appears with the search for the shortest route by two criteria, that has already been a part of the class of NP-hardness problems. At the same time, Dijkstra’s algorithm’s modification performs complex manipulations with vertex partitioning.
The representation of computational complexity of the problem with a multigraph model of a set of routes with airports and flights can be considered through the simplest modification method: Dijkstra’s algorithm, which searches only for Pareto-efficient routes. The total sum of criteria of an individual Pareto-efficient route cannot be worse or better than other Pareto- efficient routes in all criteria at the same time. For example, the set of paths with the following sum of two criteria {(30, 10), (20, 20), (10, 30)} would be Pareto-efficient.
To better understand a concept, consider the operation of the algorithm on a small graph whose arcs are weighted by two-dimensional vectors:
The operation of the modified Dijkstra’s algorithm on such a graph will consist of iterations with consecutive crossing out of vertices, taking in consideration that each vertex may have more than one Pareto-efficient value. We will also need to store data about the origin of each computed sum value.
As the problem takes into consideration routes with airport links by flights, it is reasonable to assume that there can a lot of arcs between two vertices, and each of them can be defined by at least a three-component vector. However, as the components of the vectors increase, the Pareto-efficient routes may also increase. In this case, almost all of the arcs between two vertices may be Pareto-efficient. The sum of routes will contain even more Pareto-efficient routes which can be seen in a small multigraph weighted by two-dimensional vectors:
It is acceptable to use a modified Dijkstra’s algorithm since it can work on multigraphs as well, however, the performance of the algorithm depends on both the number of vertices n and the number of arcs m. For sparse simple graphs and the usual algorithm, the complexity is calculated by
0(n × log(n) + m × log(n)). However, it is hard to define whether the resulting multigraph is sparse one, since in general the edge density of multigraphs can be much larger than that of a complete graph. If we take into account that the number of edges of a complete graph is weighted through the number of its vertices by the formula: E = (V(V − 1))/2. And the edge density is weighted as: D = 2E/(V(V − 1)). For complete graphs max(D) = 1, but for multigraphs the value of edge density is not limited.
Therefore, I decided to stick to the following strategy: Dijkstra’s algorithm will be used to find the main shortest route, and Yen’s algorithm will be used to find all other shortest routes. At this stage we operate with unweighted arcs and can immediately discard paths with, let’s say, four connections, which means that finding a single shortest route will be guaranteed to take less than 0(n²).
Let us know proceed to the direct solution of the first sub-task (multi-criteria optimization) by the conditional optimization method I have chosen before. The method can be defined as, despite the contradictory criteria, there is always the highest priority one, and all the others have acceptable values. As a result, the optimization of the whole problem is reduced to optimization by the highest priority one.
The peculiarity of the problem is that not only direct flights are included into calculation, but also connecting flights. Therefore, the model of time-dependent graph is very suitable for the current solution of the problem, as often the number of connections is not generated more than 3–4 segments in the route. The time-dependent graph, first of all, contains the data set of available routes as flights with connections between airports. Then, an estimate of departure and arrival times for connections is computed with respect to the regular unweighted graph. All the following actions need to be done at this stage in order to find all valid routes between airports A and B with a previously fixed number of connections, e.g., three.
Considering that the graph is unweighted at this stage, the shortest route can be found using the conventional breadth-first search (BFS), while all other shortest routes can be found by usage of Yen’s algorithm. Since the BFS is performed in linear time, we can say that the time to find all routes, with the same 3 connections, will be linear.
Get Andrey Kotlov’s stories in your inbox
Join Medium for free to get updates from this writer.
However, we still got the question: which short paths of routes with connections and transfers are actually the shortest? Otherwise, we will be stuck at the point when we have an array of data that will not allow us to make a decision. The set of criteria often includes the most efficient in this case, for example:
- minimum travel time;
- minimum number of transfers.
Both criteria can have configurable intervals or time values, so the only thing left to do is to combine the routes and perform real-time check for compliance with the allowed values:
As the maximum number of connections can be 3 to 4, some combinations of flights will be immediately excluded. This will move us to solve the next sub-task with identifying among the routes the most efficient ones according to the criteria.
The criteria system can be mentioned as the main issue when generating routes, as the concept of efficiency will depend on the preferences of a particular passenger. Also, a user can often manage the received routes by setting a different set of filters only when results have already been presented for initial search. Even in the case where we provide them with ranked routes in accordance with the shortest paths, the results will be an array of data that will not allow the passenger to make up his mind and will lead to an endless search of options. Therefore, the generation of route variants array is an extremely important parameter affecting the whole task.
What then needs to be taken into account?
Creation of ranking filters is lots of work, as the set of filters, their number and the degree of influence on each other can significantly change the result of search for optimal routes. We all know the key parameters of a flight: airlines, dates with departure/arrival times, departure/arrival airports, time zone shifts, connection and transfer times. However, we often forget about a very important thing such as necessary and sufficient time to arrive at the airport or travel time between airports to make a connection when the subsequent departure is from another location. We should also not forget about the category of our passenger, as well as their number for the subsequent proposal of not only the optimal route in terms of time, but also in terms of price, depending on the fare policy.
The array of offers should provide possible customer with a certain degree of confidence. This confidence should be based on mathematical principles, providing a minimum set of offers with options that take into account preferences and reduce the risk of force majeure. In this case, force majeure is not only defined by the probability of flight delays or changes in the time and airport of departure/arrival, but also indicators such as natural, technological and epidemiological situations that entail full or partial flight cancellations.
The ability to manage data in our realities entails many questions:
Is everything taken into account?
What can be added?
And here we meet with a paradox that the algorithm must be both optimal and simple at the same time. After all, you often have to sacrifice something, therefore the idea of minimizing the initial criteria to the minimum number of criteria seemed to me the most acceptable.
When following the way of criteria selection and omitting secondary criteria, it is possible to distinguish such options which take into account not only time of the whole trip, cost, comfort class, number of connections and their duration of connections, but also information on airport busy times and connection ways between airports (if there is a change from one to another).
The decision-making system of choosing efficient routes in situations where we have a set of criterion sets influencing preferences is now becoming that one issue, which was not recognized at the initial stage. Even when implementing a systematization, there are quite a lot of differences in these criteria, so let’s review them separately.
Comfort class
Everyone can interpret the comfort conditions differently, but airlines have developed the following levels:
- first class;
- business class;
- economy class.
In my approach, I assumed that the parameter comfort class can be measured in the values from 1 to 10. The following condition was taken as the basis: the lower this parameter for a particular flight, the less comfortable it will be in the ranking system. At the same time, a new problem arises due to the non-additivity of such a value. This means that the sum of comfort indices of two flights will not reflect their overall comfort. For example, there are two combinations of routes:
- the first route with two segments: the first has comfort value of 10 and the second one is only 1;
- the second route with two segments: the first has comfort value of 6, and the second one is almost the same, having a value of 5.
As a result, the sum and arithmetic mean of the parameter defining the comfort level of each route will be the same. However, this does not mean that they will reflect the true state of things. Taking into account the necessity to consider exactly the aggregate comfort level of two routes, the most appropriate solution in this situation can be to use their average values together with the standard deviation, which would allow us to assess the spread of comfort levels. This means that in the initial state we focus on the average comfortability, and only then we consider how much these comfortabilities differ from each other, using the value of the standard deviation.
This way, the criteria break down into two very close ones. On the other hand, it is clear that assuming such measurability of the comfort level is very far from reality, at least because we already have previously known class levels. Secondly, it is just as obvious that the comfort level of the whole trip is in some functional dependence on other criteria, e.g.: the duration of the flight, the number of connections and their duration, the rating of the airline and its air fleet.
To sum up, we will use the representation of comfort level in the terms of two indicators: the arithmetic mean of flight comfort indicators and their standard deviation.
Duration of connections
There are two types of route matching:
- pre-arranged connections between airlines;
- connections between any airlines, arranged by the system.
For us, the most important are those connections that will be the result of the combination of two or more airlines on the same route with agreed time periods, based on a minimum connection time required, but not always sufficient to transfer from one flight to another. Therefore, in order to combine flights, sufficient connecting time must be calculated in such a route.
Here we have a conflict to be appearing, as often such flights are excluded from the options for the offer. However, due to the presence of such a criterion, there are situations when a connection with a waiting time of more than a day is optimal, or efficient, for our passenger. Therefore, it makes sense not to discard routes with too long connection times, as they may still be in demand.
Airport busy time
Airport busy time can be assessed by calculating the efficient routes with an assessment of the degree of their occupancy based on the sale of tickets for flights, taking into account the participation of one or another airport in the route. Obviously, the minimum connection time will have some functional dependence on airport busy time.
Number of connections
The number of connections is a controversial value in itself, as it is often the way to reduce the cost of the entire route. Still there is a category of passengers for whom the presence of even one connection can cause a number of issues and is not acceptable. We should also not forget the situation when the route with a transfer is the most efficient. For example, that there are expensive business class tickets left for the desired route or there are tickets with a fare with no exchange/refund, which entails the probability of rejection of the proposed option.
The number of connections includes another sub-criterion of the probability of transferring from one airport to another. Therefore, the generation of connections is often a difficult task, as in the calculation of the route it is necessary to include the time for travel between airports, which mean that a customer needs to order tickets for transportation within the city.
The criteria of travel time and cost are additive quantities, and they rely on direct indicators with a ranking system. It is also important to mention the need to include total travel time with the calculation of the time to arrive at or depart from the airport to the destination, as well as for connections to account for the need for additional travel costs between airports.
Structure of the global goal
Let’s assume that the definition of efficiency should be understood as the best choice for everyone at all times. Not only for passengers, but also for airlines, airports and maybe other travel service providers.
In this case, breaking down a single, very complex goal into sub-goals is the only way out:
In order to satisfy all interest sides, less global but somewhat conflicting goals will have to be achieved.
How to achieve this?
Looking ahead, we can say that breaking down a complex goal into simpler sub-goals is also related to optimization and graph theory, namely the search for optimal hierarchical structures. Decision-making system is quite closely related to such methods as: Laplace, Wald, Savage and Hurwitz criteria.
One of the most universal approaches in solving multi-objective optimization problems is to find Pareto and Slater efficient solutions. If we evaluate an array of shortest routes according to the Slater criterion, then the path that is the best by all criteria simultaneously will be considered efficient. A path is considered Pareto efficient if all other ones are better than it by one parameter but worse by another. This means that it is impossible to improve a path by at least one criterion without worsening it by the others.
Pareto and Slater efficiency solutions can be demonstrated graphically for a minimization problem with two criteria:
The set of points with parameters of the Pareto-efficient criteria are labeled in green, while the Slater-efficient ones are labeled in yellow. The set of Slater-efficient points also contains the set of Pareto-efficient points. All these points will represent the ends of vectors starting at the origin of coordinates of the seven-dimensional space.
