Integration of colonial competition algorithm and quick selection of preparation time in solving the aircraft sequence planning problem

Master's Thesis

Abstract

Air traffic management is one of the sensitive and stressful jobs that face various problems and obstacles every day, and the Aircraft Sequencing Problem is one of the most important issues that are addressed in the field of Air Traffic Control.

The aircraft sequencing problem is an NP-hard problem. they lose in high dimensions and cannot achieve the optimal solution in an acceptable time; As a result, nowadays, heuristic and meta-heuristic algorithms are used to solve such problems.

In this thesis, by combining the ERT (Earliest Ready Time) algorithm to select the best ready-to-operate aircraft with the modified colonial algorithm that uses the random nearest neighbor method for the absorption function along with the triangle improving method for the revolution function, a new method is presented in solving the aircraft sequence problem. The results of the implementation of this algorithm show that it is highly efficient compared to other algorithms. Keywords: airplane landing sequence, corrective colonial competition algorithm, air traffic management, quick preparation time selection algorithm. With the arrival of different planes in the airport's radar range, the flight attendants in the control tower must determine the order of landing of the planes that are flying in the airport's sky at that moment. In order to allocate such a landing order, various limitations are taken into consideration, among which the limitation of separation of two planes can be mentioned. This restriction is very important from the point of view of aerodynamic issues, and if it is not observed, there is a possibility of an accident for successive planes.

The most important result of planning the landing of planes is to minimize the delays, which prevents additional fuel costs for the planes, as well as the dissatisfaction of the passengers. Since the costs related to the fuel of the flight fleet include a significant percentage of the costs of the airlines, the planning of the landing of the planes has been taken into consideration by the airlines as well as the airport companies. This has caused most airports that perform better in terms of flight traffic management to attract the attention of more airlines. On the other hand, in case of achieving a suitable performance in flight traffic management, airport companies will have the possibility to receive more planes in a fixed time period.

Airport companies get part of their income from the parking fee[1]. The cost of parking spaces varies depending on its facilities. Facilities such as ground electricity [2] or passenger entrances [3] have an effect on the price of the parking space. There are two types of parking spaces in all airports in the world. Parking space with passenger entrance and parking space away from the hall [4]. A parking space with a passenger entrance, or another name for a parking space with a connecting hose, is a parking space where the passengers of an airplane enter or leave the plane without the need to enter the airport area directly using a corridor (connecting hose). But the planes located in the second parking lot of the hall need a bus service [5] to pick up or drop off their passengers. Among these two types of parking spaces, the parking space with passenger entrance has a higher price. The price of these seats is calculated in such a way that a fixed amount is received from the relevant airline for every passenger who uses a plane from the passenger entrance, compared to which the price of the bus service is insignificant. Despite the higher price of the parking space with passenger entrance, airlines prefer to assign their planes to the parking space with passenger entrance in order to get more satisfaction from their passengers. The parking lot with the passenger entrance also has a safety advantage, by using the passenger entrance, there are no more risks caused by the presence of passengers in the airport area and various incidents are prevented.

Given that when the airline contracts with the airports, the airlines cannot declare conditions regarding the type of parking space and the type of parking space of an aircraft is the responsibility of the airport controller at the moment of landing of the plane; Therefore, in the case of proper planning, more planes can be allocated to the parking lots with passenger entrances and in this way help to increase the airport's income.

According to the above, the management of airports in order to attract airlines and also increase their income should be able to create a balance between the two issues of traffic control of incoming airplanes (the landing sequence of airplanes) and the allocation of airplanes to passenger entrances so that in addition to increasing their income, they can satisfy their customers (airline companies). keep But the only problem in this field is the high dependence of these two issues on each other. This means that the planes must be assigned a parking space as soon as they land at the airport, and that parking space must be empty and ready for service at the moment of landing. Or in other words, sometimes the landing of a plane with a delay of a few minutes will cause a parking space with passenger entrance to be empty, and by assigning this plane to the same space, the airport's income will increase; But airports should always keep in mind that the amount of this delay has a direct impact on the satisfaction of airlines. In this chapter, we have an overview of the literature on these two topics. 1-2- Outline of the topic In the United States, it is estimated that the cost of domestic flight delays is about 3.5 billion dollars per year, which will result in a large financial burden with the increase in commercial competition between different airlines. As a result, the planning and sequencing of flights has become one of the most important work issues in the field of flight maintenance. To face this problem and in the situation where the airport has several runways, different algorithms are used. The planning of incoming flights for several runways is a function of the allocation of incoming flights to different runways in an airport, so that the sequence of incoming flights and their landing time reduces flight delays by maintaining the standard separation between flights and the available capacity at the airport.

To solve the ASP problem in airports with multiple runways, a simple solution called first-in-first-served [6] (FCFS) is used, which is based on the landing time. Scheduled [7] (PLTs) at that airport. Figure 1-1 shows a simple example of solving the problem using the FCFS method

(images are available in the main file)

Figure 1-1- Solving the ASP problem using the FCFS method

However, in determining the order of arrival of flights and choosing the appropriate landing strip to reduce the flight delay, they consider the landing time interval [8] (LTI), which shows the minimum acceptable separation time for two flights entering a runway in a row gives Basically, LTI is a variable quantity because:

To maintain the safety of flights, it is necessary that two flights of the same height have a minimum horizontal separation based on the type of aircraft and their actual position.

The speed of each aircraft during landing is different.

The facilities and equipment of each runway are effective in determining the LTI time.

Table 1-1 is an example of the minimum LTI time related to different types. It shows passenger planes. As you can see, this table is asymmetric, so that the LTI time of the B727 behind the B747 is 200 seconds, while only 70 seconds are needed in the situation where the order of the two planes is moved. Although the FCFS solution respects justice based on PLT, but due to the asymmetry of LTI time, by moving the position of the aircraft in the entry queue of each runway or by moving them between the rows of different runways, flight delays can be reduced and the flight capacity of the airport can be increased. Check at the desired airport. Since safety is guaranteed with LTI, then the objective function for this problem needs to be obtained on the efficiency of airport operations and accuracy in servicing flights.