Application of Greedy Random Adaptive Search Algorithm (GRASP) in Flight Recovery Problem
Publicado en línea: 07 may 2018
Páginas: 39 - 44
DOI: https://doi.org/10.21307/ijanmc-2018-008
Palabras clave
© Wang Shaochang 2018 et al., published by Sciendo
This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
As is known to all, there are many interesting problems in computer field, such as salesman problem, packaging problem, partner problem, etc., and they are all belong to NP problem. The flight scheduling problem is also one of the classic NP problems. In the case of simple flight recovery, it’s essentially a part of the operational recovery problem. In a broad sense, flight recovery is operation recovery. It includes narrow flight recovery, crew recovery and rescheduling of passenger trips, which are bound together to form an overall super-sized operational optimization problem. The difficulty of flight recovery is mainly due to the immediacy of the recovery programme, except for the complexities involved. After the flight disturbance, the decision and implementation of the recovery plan is the sooner the better. In the case of manual adjustment, operator can only think of some basic factors affecting the flight safety, it is difficult to take into account the global network optimization, not to mention the passenger trip plan or according to the value of passenger flight information to determine the priority of the recovery.
In the literature [1], Danzig-Wolfe algorithm was used to solve the multi-commodity flow model of abnormal flight passenger trips. The correctness and validity of the algorithm is verified by a classical example. According to the literature [2], a deep priority algorithm is proposed to construct all feasible trips. By simplex method, the model algorithm can quickly and efficiently restore the passenger flow, and can reduce the loss greatly. In the literature [3], a heuristic method is used to solve the problem and the feasibility is proved. In the literature [4], the timetable recovery model and algorithm of the airline are proposed. Literature [5] proposed a mathematical model for the simultaneous recovery of airline flights and passengers. In the literature [6], Lagrangian relaxation method is used to relax the task constraint and equipment constraint in the model. However, the LRS algorithm has some shortcomings in solving the problem, which will be explained in detail in the following sections.
The maximum delay time of the flight is 5 hours, which means that the flight will be cancelled after more than 5 hours. With a decision unit at 10 minutes interval, then there are 30 delay decisions for one flight.
Aircraft replacement is to arrange flights to other planes for execution, which are different from the original plan. Aircraft replacement does not need to be carried out between identical planes, and is generally arranged for any aircraft belonging to the same family or the same aircraft.
The minimum interval is 45 minutes.
The earliest flight delay cannot be delayed earlier than the original planned departure time.
Flight time for each flight is equal to the arrival time in flight data minus departure time in flight data.
To make sure that every single plane is connected to the end of the plane, which means that the first flight to the airport has to be the same as the next flight, and that the time between the arrival and the flight of the first flight is 45 minutes.
The first flight of all aircraft has to meet the following two conditions: the plane’s departure airport is the same as the departure airport of the flight, and the flight time is no longer than the earliest available time of flight.
The arrival time of the last flight of all aircraft cannot be later than the latest available time of the aircraft.
The decision time interval for flight delay is 10 minutes, regardless of the capacity of the airport. Fellow travelers are passengers who book together and travel in exactly the same way. They share the same passenger number and consider it as a whole, which means they can’t take different flights.
All flights, including the airport’s OVS during the closing time, their delays require consideration. To the greatest possible protection flight, try not to cancel the flight.
Due to the impact of the snowstorm, the management decided to close the airport OVS between 18:00 and 21:00 on April 22, 2016. The airport can’t take off or land on any flight at the time of the hour, and every flight before that time is in a normal state, and the airport is immediately back to normal after that time period. All flights scheduled to take off between 18:00 and 21:00 (not including 18:00 and 21:00) on that day need to be rescheduled, and their rearrangement may result in rescheduling of other flights after closure.
The runway at OVS airport is limited to five aircraft in five minutes, and five planes to land at the same time.
Considering the passenger capacity of the aircraft, it is assumed that the cost of adjusting the flight between different types of machines is not only delayed by half an hour but also the cost of the passengers (We still don’t think about the passenger’s journey, assuming that the passenger’s schedule is all right, and assuming that all flights are 100% full). For example, aircraft DIBPV has a capacity of 140 people, and COBPV has 170 passengers. If the aircraft COBPV is distributed to DIBPV, 30 passengers will be unable to board because there are no seats available. However this is not the case if the original planned flight of DIBPV is assigned to the COBPV. Suppose a passenger is unable to board a plane that costs about two hours’ delay, how do you reschedule the flight to ensure the shortest amount of delays?
Assume that each flight is not renamed;
Assume that only the minimum cost of the recovery system is considered and all flights are treated equally;
Assume that the crew is not equipped;
Assume that there is no fault plane flying normally, it will take off and land normally;
Assume that the aircraft can be accelerated in the air and should fly at normal speed;
Assume that the aircraft will not take the channel during maintenance of the airport, other aircraft can enter the airport normally.
Assume that all aircraft of the same model have the same capacity, while there is no cost to adjust the flight, but there are costs to adjust between different models;
Assume that the added cost of a flight adjustment on a different aircraft is equivalent to a half-hour delay, and if the displacement and delay might occur at the same time, the cost added;
Assume that a passenger cannot board an aircraft equal to the passenger’s delay of 2 hours;
Regardless of the capacity of the airport, all airports can theoretically work 24 hours a day.
TABLE 1.
NOTATION TABLE
Problems mainly consider the plane carrying, the cost of adjusting the flight between different models is not only half an hour’s delay, but also the cost of not being able to board passengers. It involves the number of flight displacements, which means resource assignment problem mainly considers three factors in model construction:
If a plane carrying a large number of passengers is replaced by a small passenger plane some passengers will overflow, and some passengers will not be able to register because of the number of passengers.
When flight replacement is carried out by different models, it is necessary to find a flight with a higher passenger volume matching degree;
A passenger could not board the plane at about the same cost as the passenger’s delay of 120 minutes.
First of all, analyze the number of planes affected by the flight replacement, statistical analysis of the passenger capacity of these aircraft, to provide data for the model of problem one. Secondly, we should analyze the optimal matching degree of different flight replacement and try to get all passengers to board. Finally, the flight plan is to be made, while the passenger has the shortest amount of delay, and the optimal solution to the problem.
The final result of the problem requires that passengers have the shortest delay time. At the same time, the matching degree of flight replacement is the best, and the cost of adjusting the flight between different models is not only half an hour’s delay, but also the cost of not being able to board passengers. There are two situations in which the objective function is easy to obtain:
Z means the total time of flight delay;
Tp represents the delay time affected by the number of landing slots;
N means the number of non-boarding that is generated by a small airline Pa replacing large flight Pb;
Tm means passenger delay time;
TL means a delay time for a passenger who can’t board the plane;
Due to the limitation of runway at OVS airport, the airport can only take off five planes at a maximum of five minutes every five minutes;
The airport OVS closing time will close the airport between 18:00 and 21:00 on April 22, 2016, so the normal take-off and landing of some flights will be subject to time constraints;
To make sure that every single plane is connected to the end of the plane, which means that the first flight to the airport has to be the same as the next flight, and that the time between the arrival and the flight of the first flight is 45 minutes.
When two flights are replaced, the replacement of the flight with high passenger capacity is preferred. the constraint conditions of satisfaction are as follows:
tn means the actual departure time of the flight;
tib means the departure time of the flight;
ib means the current flight; ib∈flight set F;
According to the above analysis, the resource assignment model of flight recovery is established as follows:
According to the characteristics of the abnormal flight, the model is a multi-model flight recovery problem for the target function. The objective function in the model can be divided into two parts to solve and optimize. LRS algorithm usually can only give the solution of one model, and the algorithm is not very controllable. Model for the problem, complex, and there are two time cost in the objective function, so we will use a heuristic algorithm, greedy randomized adaptive search algorithm (GRASP), the algorithm can use a variety of computing resources to solve practical problems, helps to reduce the model solving time, improve efficiency.
Greedy randomized adaptive search algorithm is an iterative process is divided into two phases, the first stage is the initial solution is constructed by adaptive stochastic process, the second stage is to use a local search procedure for the improvement of the initial solution. Greedy randomized adaptive search algorithm is used to construct the initial solution of the corresponding is the flight time, local search process to generate the initial solution of the corresponding improvements are a result of the carrying of the delay time, the problem of the desires of passengers overall shortest delay time is the flight time and capacity to produce the sum of the delay time.
In the initial solution construction phase, the qualified Candidate List (RCL) is released into the Restricted Candidate List. By searching RCL, the optimal solution is obtained at the optimal stage of searching. At the end of each iteration, the optimal solution is updated. If the current solution is better than the previous one, then the current optimal solution is updated, otherwise the next iteration process will be carried out. When the algorithm stops, the output is the optimal solution. Through the above analysis, we can see that the solution time of the model can be adjusted flexibly as needed. The flow chart of the non-normal flight scheduling algorithm in GRASP is shown in figure 1.
Figure 1.
Flow chart of irregular flight scheduling algorithm based on GRASP
The LRS algorithm is used to obtain the results shown in table 2.
TABLE 2.
TYPE 9 FLIGHT REARRANGEMENT SCHEDULE FOR ALL RESTRICTED CONDITIONS
OVS closing time constraints according to the airport, the airport runway OVS several constraints, and the same aircraft flight arrival time before and after the flight departure time, the minimum time interval constraint and analysis of model 9 all flights, regardless of the plane displacement, 0-1 integer programming model is set up, after using subgradient Lagrangian relaxation algorithm (LRS), get affected flights of 9 new take-off and landing time as shown in figure 2.
Figure 2.
Model 9 all delayed flight visualizations
Figure 2, the horizontal type 9 all delay flights, flight time ordinate said, black vertical lines represent the current flight not delay flight time, red vertical bar said that the current flight delay time, the number of vertical lines above said the flight delay.
The specific steps for solving the simulation model are as follows:
Step1: in the initial deconstruction phase will conform to the conditional release of the restricted list of candidates (Restricted Candidate List, RCL). The RCL is searched and the optimal solution is found in the optimal search stage.
Step2: then updates the optimal solution at the end of each iteration. If the current solution is better than the previous one, it updates the current optimal solution, otherwise, it will continue the next iteration process.
The main problem is that the total delay time of all flights is the shortest among different types of aircraft. That is to say, the replacement of flights is the best. The replacement of flights is the operation of flight swaps. The departure airport and the airport at the same time are the same. When we solve the problem, we match the flight carrying capacity on the result of the problem and match the best flight displacement table to replace the flight. The total number of flights is 13. The result is shown in Table 3.
TABLE 3.
THE BEST FLIGHT REPLACEMENT TABLE FOR PASSENGERS
The overall delay of the problem flight was 1142 minutes. Through the experimental results, the feasibility of the algorithm is also proved in the error range.
The role of air transportation in world politics, business transactions and other social activities is essential, and the air transportation system is a very complex system. Various factors can lead to the failure of the whole system. Flight interruption management is a complex and challenging task. In this paper, the problem of flight recovery is analyzed and studied carefully, and the related problem model is established and the algorithm is designed. Aiming at the problem of the complexity of the model and the objective function in two time cost, the design uses a set of heuristic algorithms: greedy random adaptive search algorithm (GRASP), the algorithm can use a variety of computing resources to solve practical problems, help to reduce the calculation time of the model to improve the efficiency.