Application of Greedy Random Adaptive Search Algorithm (GRASP) in Flight Recovery Problem

Publications

Share / Export Citation / Email / Print / Text size:

International Journal of Advanced Network, Monitoring and Controls

Xi'an Technological University

Subject: Computer Science , Software Engineering

GET ALERTS

eISSN: 2470-8038

DESCRIPTION

14
Reader(s)
42
Visit(s)
0
Comment(s)
0
Share(s)

SEARCH WITHIN CONTENT

FIND ARTICLE

Volume / Issue / page

Related articles

VOLUME 3 , ISSUE 1 (May 2018) > List of articles

Application of Greedy Random Adaptive Search Algorithm (GRASP) in Flight Recovery Problem

Wang Shaochang * / Xu Fei * / Yang Weixia * / Ma Zhe *

Keywords : Light Recovery, NP Problem, LRS Algorithm, GRASP Algorithm, Modeling

Citation Information : International Journal of Advanced Network, Monitoring and Controls. Volume 3, Issue 1, Pages 39-44, DOI: https://doi.org/10.21307/ijanmc-2018-008

License : (CC-BY-NC-ND-4.0)

Published Online: 07-May-2018

ARTICLE

ABSTRACT

With the rapid growth of air transportation, capital is becoming increasingly scarce, and the abnormal situation of flight is becoming more and more serious. Irregular flights have become popular in society, and it is also a great difficulty for airlines. Flight recovery is a classic NP problem. It is of great theoretical significance and practical value to study flight restoration problem. The punctuality of the airline’s schedule is a key factor in retaining current customers and attracting new passengers. However, because the civil aviation transportation system is very complex, many reasons will cause the flight plan can not be carried out normally. Weather, air traffic flow control, airport security check, passenger’s own reasons and temporary shortage of crew cause the flight can’t be executed normally, that is, abnormal flight or flight interruption. Flight interruption will affect the normal operation of airlines. Some flights have to be cancelled or delayed, which will cause huge economic losses to airlines. Besides, the delay or cancellation of flights will cause great inconvenience to passengers and affect the reputation of airlines. The operation control and management level of abnormal flights has attracted more and more attention from domestic airlines. Optimization control and algorithm design have also become a hot topic in the research of abnormal flights in China. Based on the further understanding of the NP problem, this paper verifies the feasibility of the greedy random adaptive search algorithm GRASP algorithm in the NP problem solving process under the flight recovery problem model. According to the analysis, the resource allocation model is established to verify the shortcomings of Lagrange relaxation algorithm (LRS) in flight recovery problem. Meanwhile, the greedy random adaptive search algorithm (GRASP) is used to solve the model, and the new flight schedule is obtained. Through the experimental results, the feasibility of the algorithm is proved in the error range.

Graphical ABSTRACT

I. THE PROBLEM BACKGROUND

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.

II. MATHEMATICAL MODEL

A. Problems to be solved

  • 1) 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.

  • 2) 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.

  • 3) The minimum interval is 45 minutes.

  • 4) The earliest flight delay cannot be delayed earlier than the original planned departure time.

  • 5) Flight time for each flight is equal to the arrival time in flight data minus departure time in flight data.

  • 6) 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.

  • 7) 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.

  • 8) The arrival time of the last flight of all aircraft cannot be later than the latest available time of the aircraft.

  • 9) 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.

  • 10) 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.

  • 11) 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.

  • 12) 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?

B. Question assumptions

  • 1) Assume that each flight is not renamed;

  • 2) Assume that only the minimum cost of the recovery system is considered and all flights are treated equally;

  • 3) Assume that the crew is not equipped;

  • 4) Assume that there is no fault plane flying normally, it will take off and land normally;

  • 5) Assume that the aircraft can be accelerated in the air and should fly at normal speed;

  • 6) Assume that the aircraft will not take the channel during maintenance of the airport, other aircraft can enter the airport normally.

  • 7) 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;

  • 8) 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;

  • 9) Assume that a passenger cannot board an aircraft equal to the passenger’s delay of 2 hours;

  • 10) Regardless of the capacity of the airport, all airports can theoretically work 24 hours a day.

C. Meaning of the symbols

TABLE 1.

NOTATION TABLE

10.21307_ijanmc-2018-008-tbl1.jpg

D. The establishment and solution of the model

1) Analysis of problems

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.

2) Problem model establishment

a) Establishment of objective function

(1)
minZ=ib[tn(Xib,tntntib)+tp]+ibxib,tntmTL

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;

  • tn(Xib,tntntib) means the delay time of the flight being closed by the airport OVS;

  • Tp represents the delay time affected by the number of landing slots;

  • ibXib,tntmTLN means the cost of passengers who cannot board the plane;

  • 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;

b) Establishment of constraint conditions

  • 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:

    (2)
    s.t.{tnXib,tntnF1tnXiw,tntnF2tnXib,tntn,tnXib,tntn=CtnXib,tn,Xib,tn=0or1tbtaTPaPb=N

  • Xib,tn, is the 0-1 variable, indicating that the ith flight is 1 at the time of taking off at tn, otherwise it is 0;

  • 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;

c) Model establishment

According to the above analysis, the resource assignment model of flight recovery is established as follows:

III. GRASP ALGORITHM

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

10.21307_ijanmc-2018-008-f001.jpg
10.21307_ijanmc-2018-008-f002.jpg

IV. SIMULATION EXPERIMENT

A. Simulation model test

The LRS algorithm is used to obtain the results shown in table 2.

TABLE 2.

TYPE 9 FLIGHT REARRANGEMENT SCHEDULE FOR ALL RESTRICTED CONDITIONS

10.21307_ijanmc-2018-008-tbl2.jpg

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

10.21307_ijanmc-2018-008-f003.jpg

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

10.21307_ijanmc-2018-008-tbl3.jpg

B. Analysis of problem results

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.

V. CONCLUSION

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.

References


  1. Wang Ying. Research on the Problems of Abnormal Flights and Passenger Travel Restoration [D]. Nanjing University of Aeronautics and Astronautics, 2013.
  2. Gao Qiang, Yan Jun, Lu Honglan. Remove Method of Passenger Flow in Abnormal Flights [J]. Science and Technology and Engineering, 2011, 11 (27): 6670–6673.
  3. Zhao Xiu-Li, Zhu Jin-Fu, Guo Mei. Models and Algorithms of Delayed Flights Dispatch [J]. Systems Engineering Theory and Practice, 2008, (04): 129–134.
  4. Flight operations recovery: New approaches considering passenger recovery[J]. Stephane Bratu, Cynthia Barnhart. Journal of Scheduling. 2006 (3)
  5. Simultaneous recovery model for aircraft and passengers[J]. Niloofar Jafari, Seyed Hessameddin Zegordi. Journal of the Franklin Institute. 2010
  6. Corning, Wu Xiaoyue, Zhang Guoting. Lagrange Heuristic Algorithm For Alarm Control And Ccontrol Control [J]. Actaalie and Command Control, 2012, 37 (08): 104–107.
  7. Luo Rong-Qin, Zhao Xiao-Mei, Bi Jun, Zhang Jun. An Integer Programming Model of Delayed Flights Rearrangement Based on Comprehensive Flight Factors [J]. Transportation Research, 2017, 3 (03): 36–42.
  8. Pacheco A V F, Ribeiro G M, Mauri G R. A Grasp with Path-Relinking for the Workover Rig Scheduling Problem[J]. International Journal of Natural Computing Research, 2017, 1(2):1–14.
    [CROSSREF]
  9. Wu Gang, Yan Jun. An Improved Column Generation Algorithm for Uneven Flight Recovery [J]. JOURNAL OF NANJING UNIVERSITY OF AERONAUTICS, 2014, 46 (02): 329–334.
  10. Zhao Xiaomei, Bi Jun, Wang Yongxing, Zhang Jun. Aircraft Plan Recovery Model for Unnormal Airlines Considering Multi-Factors [J]. Transportation Research, 2017, 3 (02): 52–60.
  11. Li Ning, Mou Deyi. Uncertain programming method for unit recovery [J]. Journal of Cangzhou Teachers College, 2017, 33 (02): 10–13 + 23.
  12. Sun Cheng-Hao, Wang Wan-Zhen, Zhou Run. Stochastic Programming Method for Aircraft Recovering Decision of Unregulated Flights [J]. Shandong Industry Technology, 2017, (12): 262–263.
XML PDF Share

FIGURES & TABLES

Figure 1.

Flow chart of irregular flight scheduling algorithm based on GRASP

Full Size   |   Slide (.pptx)

Figure 2.

Model 9 all delayed flight visualizations

Full Size   |   Slide (.pptx)

TABLE 1.

NOTATION TABLE

Full Size   |   Slide (.pptx)

TABLE 2.

TYPE 9 FLIGHT REARRANGEMENT SCHEDULE FOR ALL RESTRICTED CONDITIONS

Full Size   |   Slide (.pptx)

TABLE 3.

THE BEST FLIGHT REPLACEMENT TABLE FOR PASSENGERS

Full Size   |   Slide (.pptx)

REFERENCES

  1. Wang Ying. Research on the Problems of Abnormal Flights and Passenger Travel Restoration [D]. Nanjing University of Aeronautics and Astronautics, 2013.
  2. Gao Qiang, Yan Jun, Lu Honglan. Remove Method of Passenger Flow in Abnormal Flights [J]. Science and Technology and Engineering, 2011, 11 (27): 6670–6673.
  3. Zhao Xiu-Li, Zhu Jin-Fu, Guo Mei. Models and Algorithms of Delayed Flights Dispatch [J]. Systems Engineering Theory and Practice, 2008, (04): 129–134.
  4. Flight operations recovery: New approaches considering passenger recovery[J]. Stephane Bratu, Cynthia Barnhart. Journal of Scheduling. 2006 (3)
  5. Simultaneous recovery model for aircraft and passengers[J]. Niloofar Jafari, Seyed Hessameddin Zegordi. Journal of the Franklin Institute. 2010
  6. Corning, Wu Xiaoyue, Zhang Guoting. Lagrange Heuristic Algorithm For Alarm Control And Ccontrol Control [J]. Actaalie and Command Control, 2012, 37 (08): 104–107.
  7. Luo Rong-Qin, Zhao Xiao-Mei, Bi Jun, Zhang Jun. An Integer Programming Model of Delayed Flights Rearrangement Based on Comprehensive Flight Factors [J]. Transportation Research, 2017, 3 (03): 36–42.
  8. Pacheco A V F, Ribeiro G M, Mauri G R. A Grasp with Path-Relinking for the Workover Rig Scheduling Problem[J]. International Journal of Natural Computing Research, 2017, 1(2):1–14.
    [CROSSREF]
  9. Wu Gang, Yan Jun. An Improved Column Generation Algorithm for Uneven Flight Recovery [J]. JOURNAL OF NANJING UNIVERSITY OF AERONAUTICS, 2014, 46 (02): 329–334.
  10. Zhao Xiaomei, Bi Jun, Wang Yongxing, Zhang Jun. Aircraft Plan Recovery Model for Unnormal Airlines Considering Multi-Factors [J]. Transportation Research, 2017, 3 (02): 52–60.
  11. Li Ning, Mou Deyi. Uncertain programming method for unit recovery [J]. Journal of Cangzhou Teachers College, 2017, 33 (02): 10–13 + 23.
  12. Sun Cheng-Hao, Wang Wan-Zhen, Zhou Run. Stochastic Programming Method for Aircraft Recovering Decision of Unregulated Flights [J]. Shandong Industry Technology, 2017, (12): 262–263.

EXTRA FILES

COMMENTS