A new linear programming approach and genetic algorithm for solving airline boarding problem. (English) Zbl 1252.90101

Soolaki, Majid; Mahdavi, Iraj; Mahdavi-Amiri, Nezam; Hassanzadeh, Reza; Aghajani, Aydin

Appl. Math. Modelling 36, No. 9, 4060-4072 (2012).

Summary: The airline industry is under intense competition to simultaneously increase efficiency and satisfaction for passengers and profitability and internal system benefit for itself. The boarding process is one way to achieve these objectives as it tends itself to adaptive changes. In order to increase the flying time of a plane, commercial airlines try to minimize the boarding time, which is one of the most lengthy parts of a plane’s turn time. To reduce boarding time, it is thus necessary to minimize the number of interferences between passengers by controlling the order in which they get onto the plane through a boarding policy. Here, we determine the passenger boarding problem and examine the different kinds of passenger boarding strategies and boarding interferences in a single aisle aircraft. We offer a new integer linear programming approach to reduce the passenger boarding time. A genetic algorithm is used to solve this problem. Numerical results show effectiveness of the proposed algorithm.

MSC:

90C90	Applications of mathematical programming
90B06	Transportation, logistics and supply chain management
90C11	Mixed integer programming
90C59	Approximation methods and heuristics in mathematical programming

Keywords:

OR in airlines; mixed integer linear programming; transportation; boarding strategy; genetic algorithm

Software:

minlpBB

References:

[2]	Van Landeghem, H.; Beuselinck, A., Reducing passenger boarding times in airplanes: a simulation based approach, Eur. J. Oper. Res., 142, 294-308 (2002) · Zbl 1082.90542
[3]	Lewis, C. S.N.; Lieber, R., Testing the latest boarding procedures, Wall Street J. (2005)
[4]	Bazargan, M.; Vasigh, S., Size versus efficiency – a case study on US commercial airports, J. Air Transport Manage., 9, 187-193 (2003)
[5]	Marelli, S.; Mattocks, G.; Merry, R., The role of computer simulation in reducing airplane turn time, AERO Mag. (1998)
[6]	Ferrari, P.; Nagel, K., Robustness of efficient boarding in airplanes, Transport. Res. Rec., 1915, 44-54 (2005)
[8]	Van den Briel, M. H.L.; Villalobos, J. R.; Hogg, G. L.; Lindemann, T.; Mule´, A. V., America west airlines develops efficient boarding strategies, Interfaces, 35, 191-201 (2005)
[9]	Bazargan, M., A linear programming approach for aircraft boarding strategy, Eur. J. Oper. Res., 183, 1, 394-411 (2007) · Zbl 1127.90006
[10]	Holland, J. H., Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence (1975), University of Michigan Press: University of Michigan Press Ann Arbor, MI · Zbl 0317.68006
[11]	Goldberg, D., Genetic Algorithms in Search Optimization, and Machine Learning (1989), Addison-Wesley: Addison-Wesley New York, NY · Zbl 0721.68056
[12]	Gen, M.; Cheng, R., Genetic Algorithms and Engineering Design (1996), Wiley: Wiley New York, NY