یک روش برنامه ریزی خطی جدید و الگوریتم ژنتیک برای حل مشکل سوار شدن به هواپیما

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.

Airlines start generating revenues by utilizing and flying their aircrafts, and of course they do not generate any revenue while the aircrafts are sitting on the ground. As a result, a traditional metric used by commercial airlines to measure the efficiency of their operations is airplane turnaround time. Usually, turnaround time is measured by the time between an airplane’s arrival and its departure [1], [2] and [3]. Some factors influencing turnaround time include passenger deplaning, baggage unloading, fueling, cargo unloading, airplane maintenance, cargo loading, baggage loading, and passenger boarding. Therefore, airlines flying short-haul flights typically select airports (within the same region) with low air/ground congestions [4]. Airlines have little control over passenger-boarding time because they have limited control over passengers. Therefore, while airlines want to speed up the passengers boarding airplanes, they are cautious in making changes to increase operational efficiency. The boarding process of passenger aircraft has been an issue since the inception of the airline industry; however, it has been steadily increasing in importance since the late 1970s. The process of airplane boarding is experienced daily by millions of passengers worldwide. Airlines have adopted a variety of boarding strategies in the hope of reducing the gate turn-around time for airplanes. To exert control over the boarding process, airlines assign passengers to boarding groups or zones, calling each boarding group to board in order (see Table 1). The deficiencies with respect to this aspect of flying has annoyed many travelers and sparked a debate among industry professionals and travelers alike as to how to rectify the situation, each with his/her own interest in mind (customers want ease/efficiency and airlines want efficiency/profitability). Consequently, airlines are currently struggling with how to more effectively address the boarding-process problem. The airline industry recognizes that the boarding process is a significant cost, yet little published research exists in the literature to address the ways to improve the process. Table 1 presents a summary of the boarding processes used by major US airlines. Table 1. Summary of the boarding processes used by major US airlines. Major US airlines Boarding method Boarding strategy American airlines Traditional block method By groups, starting at the rear of the aircraft and moving forward, about 1/5 of the rows at a time Continental airlines Traditional by-row method By rows, starting at the rear of the aircraft and moving forward, about 1/4 of aircraft at a time Delta airlines Non-traditional method By zones, starting with the back few rows, followed by the middle and then front sections, then back to a rear section Northwest airlines Random boarding method Passengers line up and take their assigned seat in no particular order Southwest airlines Open seating method Passengers are assigned a group and boarding number based on check-in times. After group is called, passengers take a position next to the column representing their number and proceed onto the aircraft. Passengers choose their own seats once onboard United airlines Open seating method Passengers are assigned a group and boarding number based on check-in times. After group is called, passengers take a position next to the column representing their number and proceed onto the aircraft. Passengers choose their own seats once onboard America West Reversed pyramid Window seats first, followed by middle, then aisle and loading diagonally Table options Marelli et al. [5] described a simulation-based analysis performed for Boeing 757. They designed the passenger enplane/deplane simulation (PEDS) to test different boarding strategies and different interior configurations on a Boeing 757 airplane. PEDS showed that by boarding outside-in, that is, window seats first, middle seats second, and aisle seats last, airlines could reduce boarding times significantly. Van Landeghem and Beuselinck [2] conducted another simulation-based study on airplane boarding showing that the fastest way to get people on an airplane would be to board them individually by their row and seat number through calling each one of the passengers individually to board the aircraft. In their study, they analyzed many alternative boarding patterns. One pattern that seemed practical and efficient was boarding passengers by half-row, that is, by splitting each row into a starboard-side group and a port-side group and then boarding the half-rows one by one. Prior to executing their simulation model, they assumed the arrival rate of passengers to be continuous, recognizing that “in reality, the passenger arrival rate is determined by the gating operations”. Their model also took into account that 60% of all passengers carried on one bag, 30% carried on two bags, and only 10% carried on three bags. In a recent shift in airline security policy, airlines now place limits on the number, size, and weight of carry-on luggages. The standard allowance typically includes one baggage-type item and one personal item, e.g., purse or briefcase. However, US domestic airlines have been generally liberal in enforcing these limits. Ferrari and Nagel [6] expounded upon the “bin occupancy model” of Van Landeghem and Beuselinck [2], to determine the amount of time attributed to storing carry-on luggage. The model calculated the time associated with storing carry-on luggages by evaluating the number of bags already in the bin plus the number of bags being carried by each passenger. They determined that boarding outside-in or individually by seat were the two best methods, a finding concurrent with Van Landeghem and Beueslinck (2002). In their study, a sensitivity analysis was conducted to determine the robustness of the various boarding strategies under the effect of three recognizable disturbances: early and/or late passengers, aircraft dimensions, and the occupancy level of the plane. This sensitivity study is known as the “average worst case” boarding time model [6]. Calculations determined that those boarding strategies which yielded good performance figures also yielded well “average worst case” boarding times and vice versa. While traditional computer-based simulation studies are good tools for testing the performance of already identified alternatives, they do not provide efficient mechanisms for constructing the most promising alternatives. For this reason, here we offer to use analytical models to analyze the problem. Surprisingly, in the airline industry, having a rich background in applying operations research techniques, we found only simulation-based solutions for analyzing and improving passenger airplane boarding. One exception is a study by Bachmat et al. [7] that approaches the airplane boarding problem from a physicist’s point of view. They constructed a model based on spacetime geometry and random matrix theory that captures the asymptotic behavior of airplane boarding. They were able to interpret their findings to provide an explanation for why the different boarding strategies performed the way they did. An analytical approach to aircraft boarding strategy was given by Van den Briel et al. [8]. They modeled the aircraft boarding strategy using a non-linear assignment model with quadratic and cubic terms. The model attempts to minimize the total interferences among the passengers. The non-linear problem, being NP-hard, was solved and verified using simulation modeling. The final recommended “reverse pyramid” boarding strategy was implemented at America West Airline. A recent analytical approach to aircraft boarding strategy is due to Massoud Bazargan [9]. He models the aircraft boarding strategy using a mixed integer linear programming approach to generate efficient boarding strategies. Our focus here is to develop a mathematical model to capture some passenger behaviors in boarding the aircraft. Although the models make several simplifying assumptions, they provide a good analysis of the factors affecting the boarding process. All other effects, such as the time used by passengers standing up to retrieve an item, sittings in the wrong seats, or late arrivals, or passing by passengers already seated are initially treated as negligible. Our model does not include the effects of the clustering of passengers into companions or families and other effects of human nature. Some airlines (especially low fare ones) do not assign seats at all. This free seating is not regarded to be acceptable by traditional passengers, and is not included in our study. It is likely to increase boarding time, as this system is comparable to being random, but there will be additional delays, especially for the late passengers looking for available free seats. Here, we present a new mixed integer linear programming approach to generate new boarding strategies. The mathematical model attempts to minimize the total interferences among the passengers which are the major causes of boarding delays, subject to operational and side constraints. The model provides the flexibility to optimize the boarding times for various aircrafts with different seat capacities. We then propose a mathematical model for a single aisle Airbus-320 aircraft. This specific type of aircraft is selected because it is one of the most common types of aircrafts adopted by many airlines. Another reason is that it enables us to provide a comparison between the performance of our offered model and those reported by the non-linear model developed by Van den Briel et al. [8], and the linear model developed by Massoud Bazargan [9]. The rest of this paper is organized as follows. Section 2 defines interferences and how they are formulated in our model. Section 3 provides the problem description. Section 4 defines constrains of interferences and how they are formulated in our model. Section 5 proposes the mixed linear integer model. Then, in Section 6, a genetic algorithm is proposed for solving this problem. In Section 7, we examine the parameters and solutions generated by the mathematical model. Finally, the conclusions and directions for further research are provided in Section 8.

We have developed a mixed integer linear programming model to minimize the total number of passenger interferences in a boarding problem. The operational and side constraints for this mathematical model were examined. The model was then applied to an Airbus-320 aircraft, as is commonly used by many airlines. We examined and compared the performance of our mathematical model using the GA approach with other boarding strategies (efficient solutions and reverse pyramid strategies). Computational results showed that the effectiveness of our approach. To the best of our knowledge, the literature on boarding problem considering linear programming and the genetic algorithm (GA) approach is still in its early stages of development and our work here is the first in applying the GA approach to the boarding problem. Several possible future research directions can be defined in this area, such as simplifying and/or introduction of more realistic assumptions, and development of competitive algorithms.