Benders’ decomposition algorithm to solve bi-level bi-objective scheduling of aircrafts and gate assignment under uncertainty

Document Type: Research Paper


School of Industrial Engineering, College of Engineering, University of Tehran, Tehran, Iran


Management and scheduling of flights and assignment of gates to aircraft play a significant role to improve the performance of the airport, due to the growing number of flights and decreasing the flight times. This research addresses the assignement and scheduling problem of runways and gates simultaneously. Moreover, this research is the first study that considers the constraint of unavailability of runway’s and the uncertain parameters relating to both areas of runway and gate assignment. One of the distinguishing contributions of the proposed model is that the problem is formulated as a bi-level bi-objective one. The leader objective function minimizes the total waiting time for runways and gates for all aircrafts based on their importance coefficient. Meanwhile, the total distance traveled by all passengers in the airport terminal is minimized by a follower objective function. To solve the proposed model, Benders’ decomposition method is applied. Empirical data are used to show the validation and application of the proposed model.  A comparison shows the effectiveness of the model and its significant impact on decreasing the costs.


Main Subjects

Airport Council Intrnational.(2010).ACI Global traffic forecast 2010-2025 executive summery.

Airport Council International.(2012). April,ACI releases word airport traffic report 2005-2011.

Atkin, J.A., Burke, E.K., Greenwood, J.S. & Reeson, D.(2007). Hybrid metaheuristics to aid runway scheduling at London Heathrow airport. Transportation Science, 41(1), 90-106.

Balakrishnan, H. & Chandran, B.(2006). August. Scheduling aircraft landings under constrained position shifting. In AIAA Guidance, Navigation, and Control Conference and Exhibit, Keystone, CO.

Bard, J.F.(1983). An efficient point algorithm for a linear two-stage optimization problem. Operations Research, 31(4), 670-684.

Bard, J.F. & Purnomo, H.W.(2007). Cyclic preference scheduling of nurses using a Lagrangian-based heuristic. Journal of Scheduling, 10(1), 5-23.

Beasley, J.E., Krishnamoorthy, M., Sharaiha, Y.M. & Abramson, D.(2000). Scheduling aircraft landings—the static case. Transportation science, 34(2), 180-197.

Beasley, J.E., Sonander, J. & Havelock, P.(2001). Scheduling aircraft landings at London Heathrow using a population heuristic. Journal of the operational Research Society, 483-493.

Bencheikh, G., Boukachour, J., Alaoui, A.E.H. & Khoukhi, F.E.(2009). Hybrid method for aircraft landing scheduling based on a job shop formulation. International Journal of Computer Science and Network Security, 9(8), 78-88.

Bennell, J.A., Mesgarpour, M. & Potts, C.N.(2011). Airport runway scheduling. 4OR, 9(2), 115-138.

Bialas, W. and Karwan, M., 1978. Multilevel linear programming. State University of New York at Buffalo.

Bianco, L., Dell’Olmo, P. & Giordani, S.(2006). Scheduling models for air traffic control in terminal areas. Journal of Scheduling, 9(3), 223-253.

Bianco, L., Dell'Olmo, P. & Giordani, S.(1999). Minimizing total completion time subject to release dates and sequence‐dependentprocessing times. Annals of Operations Research, 86, 393-415.

Bihr, R.A.(1990). A conceptual solution to the aircraft gate assignment problem using 0, 1 linear programming. Computers & Industrial Engineering, 19(1), 280-284.

Bojanowski, L., Harikiopoulo, D. & Neogi, N.(2011), June. Multi-runway aircraft sequencing at congested airports. In Proceedings of American Control Conference (ACC), 2011, 2752-2758.

Bolat, A.(2001). Models and a genetic algorithm for static aircraft-gate assignment problem. Journal of the Operational Research Society, 52(10), 1107-1120.

Caprı̀, S. & Ignaccolo, M.(2004). Genetic algorithms for solving the aircraft-sequencing problem: the introduction of departures into the dynamic model. Journal of Air Transport Management, 10(5), 345-351.

Chen, Y. & Florian, M.(1992). On the geometric structure of linear bilevel programs: a dual approach. Centre De Recherche Sur Les Transports Publication, 867.

Cheng, C.H., Ho, S.C. & Kwan, C.L.(2012). The use of meta-heuristics for airport gate assignment. Expert systems with applications, 39(16), 12430-12437.

Cheng, Y.(1997). A knowledge-based airport gate assignment system integrated with mathematical programming. Computers & Industrial Engineering, 32(4), 837-852.

Coello, C.C., Lamont, G.B. & Van Veldhuizen, D.A.(2007). Evolutionary algorithms for solving multi-objective problems. Springer Science & Business Media.

Dorndorf, U., Drexl, A., Nikulin, Y. & Pesch, E.(2007). Flight gate scheduling: State-of-the-art and recent developments. Omega, 35(3), 326-334.

Ernst, A.T., Krishnamoorthy, M. & Storer, R.H.(1999). Heuristic and exact algorithms for scheduling aircraft landings. Networks, 34(3), 229-241.

Fahle, T., Feldmann, R., Götz, S., Grothklags, S. & Monien, B.(2003). The aircraft sequencing problem. In Computer science in perspective,152-166.

Gamst, M., & Jensen, T. S. (2012). “A branch-and-price algorithm for the long-term home care scheduling problem”. In Proceedings of Operations Research, 483-488.

Genç, H.M., Erol, O.K., Eksin, İ., Berber, M.F. & Güleryüz, B.O.(2012). A stochastic neighborhood search approach for airport gate assignment problem. Expert Systems with Applications, 39(1), 316-327.

Haghani, A. & Chen, M.C.(1998). Optimizing gate assignments at airport terminals. Transportation Research Part A: Policy and Practice, 32(6), 437-454.

Hamzawi, S.G.(1986). Management and planning of airport gate capacity: a microcomputer‐based gate assignment simulation model. Transportation Planning and Technology, 11(3), 189-202.

Hansen, J.V.(2004). Genetic search methods in air traffic control. Computers & Operations Research, 31(3), 445-459.

Hansen, P., Jaumard, B. & Savard, G.(1992). New branch-and-bound rules for linear bilevel programming. SIAM Journal on scientific and Statistical Computing, 13(5), 1194-1217.

Harikiopoulo, D. & Neogi, N.(2011). Polynomial-time feasibility condition for multiclass aircraft sequencing on a single-runway airport. Intelligent Transportation Systems, IEEE Transactions on, 12(1), p2-14.

Jiménez, M., Arenas, M., Bilbao, A. & Rodrı, M.V.(2007). Linear programming with fuzzy parameters: an interactive method resolution. European Journal of Operational Research, 177(3), 1599-1609.

Jung, G. & Laguna, M.(2003). Time segmenting heuristic for an aircraft landing problem. Unpublished work, previously available from leeds-faculty. colorado.

Li, H. & Womer, K.(2009). Scheduling projects with multi-skilled personnel by a hybrid MILP/CP benders decomposition algorithm. Journal of Scheduling, 12(3), 281-298.

Lim, A., Rodrigues, B. & Zhu, Y.(2005). Airport gate scheduling with time windows. Artificial Intelligence Review, 24(1), 5-31.

Ding, H., Lim, A., Rodrigues, B. & Zhu, Y.(2004). New heuristics for over-constrained flight to gate assignments. Journal of the Operational Research Society, 760-768.

Liu, Y.H.(2011). A genetic local search algorithm with a threshold accepting mechanism for solving the runway dependent aircraft landing problem. Optimization Letters, 5(2), 229-245.

Maenhout, B. & Vanhoucke, M.(2010). Branching strategies in a branch-and-price approach for a multiple objective nurse scheduling problem. Journal of Scheduling, 13(1), 77-93.

Maharjan, B. & Matis, T.I.(2011). An optimization model for gate reassignment in response to flight delays. Journal of Air Transport Management, 17(4), 256-261.

Moore, J.T. & Bard, J.F.(1990). The mixed integer linear bilevel programming problem. Operations research, 38(5), 911-921.

Papadakos, N.(2009). Integrated airline scheduling. Computers & Operations Research, 36(1), 176-195.

Parra, M.A., Terol, A.B., Gladish, B.P. & Urıa, M.R.(2005). Solving a multiobjective possibilistic problem through compromise programming. European Journal of Operational Research, 164(3), 748-759.

Psaraftis, H.N.(1978). A dynamic programming approach to the aircraft sequencing problem. Cambridge, Mass.: Massachusetts Institute of Technology, Flight Transportation Laboratory.

Şeker, M. & Noyan, N.(2012). Stochastic optimization models for the airport gate assignment problem. Transportation Research Part E: Logistics and Transportation Review, 48(2), 438-459.

Rabeh, R., Saïd, K. & Eric, M.(2011). Collaborative model for planning and scheduling caregivers’ activities in homecare. In 18th IFAC World Congress, 2877-2882.

Rasmussen, M.S., Justesen, T., Dohn, A. & Larsen, J.(2012). The home care crew scheduling problem: Preference-based visit clustering and temporal dependencies. European Journal of Operational Research, 219(3), 598-610.

Redjem, R., Kharraja, S., Xie, X. & Marcon, E. (2012). June. Routing and scheduling of caregivers in home health care with synchronized visits. In Proceedings of 9th International Conference of Modeling, Optimization and Simulation, Bordeaux–France, 06-08.

Saharidis, G.K. & Ierapetritou, M.G.(2009). Resolution method for mixed integer bi-level linear problems based on decomposition technique. Journal of Global Optimization, 44(1), 29-51.

Sarin, S.C., Wang, Y. & Varadarajan, A.(2010). A university-timetabling problem and its solution using Benders’ partitioning—a case study. Journal of Scheduling, 13(2), 131-141.

Sharma, N.(2009). Mixed integer 0-1 programming for time-based metering in air traffic management.

Shi, C., Lu, J. & Zhang, G.(2005). An extended Kuhn–Tucker approach for linear bilevel programming. Applied Mathematics and Computation, 162(1), 51-63.

Shi, C., Lu, J., Zhang, G. & Zhou, H.(2006). An extended branch and bound algorithm for linear bilevel programming. Applied Mathematics and Computation, 180(2), 529-537.

Soomer, M.J. & Franx, G.J.(2008). Scheduling aircraft landings using airlines’ preferences. European Journal of Operational Research, 190(1), 277-291.

Srihari, K. & Muthukrishnan, R.(1991). An expert system methodology for aircraft-gate assignment. Computers & Industrial Engineering, 21(1-4), 101-105.

Stojković, G., Soumis, F., Desrosiers, J. & Solomon, M.M.(2002). An optimization model for a real-time flight scheduling problem. Transportation Research Part A: Policy and Practice, 36(9), 779-788.

Tang, C.H., Yan, S. & Hou, Y.Z.(2010). A gate reassignment framework for real time flight delays. 4OR, 8(3), 299-318.

[57] Teodorović, D.(1999). Fuzzy logic systems for transportation engineering: the state of the art. Transportation Research Part A: Policy and Practice, 33(5), 337-364.

Trautsamwieser, A. & Hirsch, P.(2014). A Branch‐Price‐and‐Cut approach for solving the medium‐term home health care planning problem. Networks, 64(3), 143-159.

Tuy, H., Migdalas, A. & Värbrand, P.(1993). A global optimization approach for the linear two-level program. Journal of Global Optimization, 3(1), 1-23.

Vicente, L., Savard, G. & Judice, J.(1996). Discrete linear bilevel programming problem. Journal of optimization theory and applications, 89(3), 597-614.

Wang, R.C. & Liang, T.F.(2005). Applying possibilistic linear programming to aggregate production planning. International Journal of Production Economics, 98(3), 328-341.

Wei, D. & Liu, C.(2007). August. Optimizing gate assignment at airport based on genetic-tabu algorithm. In Automation and Logistics, 2007 IEEE International Conference on, 1135-1140.

Wen, M.(2005). Algorithms of scheduling aircraft landing problem. (Doctoral dissertation,Technical University of Denmark, DTU, DK-2800 Kgs. Lyngby, Denmark).

Xu, J. & Bailey, G.(2001). January. The airport gate assignment problem: mathematical model and a tabu search algorithm. In System Sciences, 2001.In Proceedings of the 34th Annual Hawaii International Conference on, 10.

Zalila, F., 2002. An empirical study of rollout algorithms, beam search and multi-start adaptive memory programming for the airline gate assignment problem.

Zhan, Z.H., Zhang, J. and Gong, Y.J., 2009, July. Ant colony system based on receding horizon control for aircraft arrival sequencing and scheduling. In Proceedings of the 11th Annual conference on Genetic and evolutionary computation, 1765-1766.

Zhang, J., 2003, July. A Network-Flow model for assigning flights to gates at airports.Submitted in partial fulfillment of the requirements for the degree of master of applied science at Dalhouse University.