Team 2056 Page 1l of 50 nd is seated Idle. If there is no passenger in the processor(and the queue is empty) the processor will do nothing The processors run sequentially in order from back to front.(If th processors ran from front to back, during one time cycle, a passenger could be processed in the first processor, move to the second, be rocessed there, and continue in a similar manner the entire distance to his seat. )They continue to run until every passenger has found his seat The implementation of our algorithm can be seen in figure 2 Assumptions made in Section 3.1 The initial configuration of the system is that all passengers are queued at the first row. In actuality, the situation is slightly dif- ferent. All passengers are initially queued at the ticket counter where their boarding passes are scanned and they walk a short distance to the plane. Hence, a more realistic alternative to our process is a poisson arrival process from the ticket counter to the queue for the first row. However, we feel that this addi- tional process is unnecessary. It is not needed because of the high speed at which the tickets are taken. This process closely approximates the speed of normal walking. Hence, the passen- gers will reach the queue at a much higher rate than they are moved forward through the plane. Hence, the queue at proces- or 1 will form instantly, at the point that the first passengers walk into the plane There is no idle time between the first passenger entering queue I and the last. This assumption is also involved in our decision to queue all passengers at the first processor. In some cases the airline could wait until there is no queue left before inviting dditional passengers to board. For example, if calling pa gers by zone, the airline could wait until all passengers in one zone are seated before the next zone is invited onto the aircraft However, this is never to the airline' s advantage. We assume that the airline desires maximum efficiency, and hence ensures that there is no dead-time between passengers
Team 2056 Page 11 of 50 and is seated. • Idle. If there is no passenger in the processor (and the queue is empty) the processor will do nothing. The processors run sequentially in order from back to front. (If the processors ran from front to back, during one time cycle, a passenger could be processed in the first processor, move to the second, be processed there, and continue in a similar manner the entire distance to his seat.) They continue to run until every passenger has found his seat. The implementation of our algorithm can be seen in figure 2. Assumptions made in Section 3.1 • The initial configuration of the system is that all passengers are queued at the first row. In actuality, the situation is slightly different. All passengers are initially queued at the ticket counter, where their boarding passes are scanned and they walk a short distance to the plane. Hence, a more realistic alternative to our process is a poisson arrival process from the ticket counter to the queue for the first row. However, we feel that this additional process is unnecessary. It is not needed because of the high speed at which the tickets are taken. This process closely approximates the speed of normal walking. Hence, the passengers will reach the queue at a much higher rate than they are moved forward through the plane. Hence, the queue at processor 1 will form instantly, at the point that the first passengers walk into the plane. • There is no idle time between the first passenger entering queue 1 and the last. This assumption is also involved in our decision to queue all passengers at the first processor. In some cases, the airline could wait until there is no queue left before inviting additional passengers to board. For example, if calling passengers by zone, the airline could wait until all passengers in one zone are seated before the next zone is invited onto the aircraft. However, this is never to the airline’s advantage. We assume that the airline desires maximum efficiency, and hence ensures that there is no dead-time between passengers
Team 2056 Page 12 of 50 star sto Initialize Have a For each time stO Increment time no< passengers sat down? For each processor processor Have we cached the first yes OCessor? Process conta ns a ye is tnis the Do we no fumble? Sit Down Fumble Figure 2: Basic processor model flowchart
Team 2056 Page 12 of 50 Figure 2: Basic processor model flowchart
Team 2056 Page 13 of 50 Special needs and business class passengers have already boarded We assume that the boarding of special needs and business class passengers is not subject to time and order optimization. Rather, airlines have an obligation to these customers for early boarding. We start our simulation clock after these special classes of passenger have already boarded. We deal only with the bulk passenger class Every passenger functions individually. We expect that effi ciency will be improved when passengers travel in groups since they are self organizing (they do not collide with each other) 3.2 Extended model ach of the following subsections detail the modeling of an extension to the basic model. The final form of our processor-based model (and, hence, the origin of our results) combines the techniques of all of these extensions (i. e, we are creating a holistic model,not modeling these features separately 3.2.1 Seat assignment The initial model assigned seats randomly and without uniqueness n the final model. this has been remedied so that there is a one- to-one correspondence between passengers and seats. The seat as- signment can be chosen in many ways. As discussed later in the paper, we investigated random, genetically evolved, back-to-front and reverse pyramid loading schemes, among others Assumptions made in Section 3.2.1 The plane is fully booked, and every seat is occupied. This tion allows us to optimize over the worst-case scenario Since airlines attempt to maximize profits, they attempt to fully book as many flights as possible. Hence, most fights will be fully or nearly fully booked. Likewise, an airline, when scheduling, will schedule assuming the fight is fully booked else risk delays). Hence, it is most important to understand the fully booked scenario
Team 2056 Page 13 of 50 • Special needs and business class passengers have already boarded. We assume that the boarding of special needs and business class passengers is not subject to time and order optimization. Rather, airlines have an obligation to these customers for early boarding. We start our simulation clock after these special classes of passenger have already boarded. We deal only with the bulk passenger class. • Every passenger functions individually. We expect that effi- ciency will be improved when passengers travel in groups since they are self organizing (they do not collide with each other). 3.2 Extended Model Each of the following subsections detail the modeling of an extension to the basic model. The final form of our processor-based model (and, hence, the origin of our results) combines the techniques of all of these extensions (i.e., we are creating a holistic model, not modeling these features separately). 3.2.1 Seat assignment The initial model assigned seats randomly and without uniqueness. In the final model, this has been remedied so that there is a oneto-one correspondence between passengers and seats. The seat assignment can be chosen in many ways. As discussed later in the paper, we investigated random, genetically evolved, back-to-front and reverse pyramid loading schemes, among others. Assumptions made in Section 3.2.1 • The plane is fully booked, and every seat is occupied. This assumption allows us to optimize over the worst-case scenario. Since airlines attempt to maximize profits, they attempt to fully book as many flights as possible. Hence, most flights will be fully or nearly fully booked. Likewise, an airline, when scheduling, will schedule assuming the flight is fully booked (or else risk delays). Hence, it is most important to understand the fully booked scenario
Team 2056 Page 14 of 50 Arriving Passe Seated Passengers Time cost Middle Middle Aisle and window 9 Middle Window Middle and aisle 13 Figure 3: Table of seat collision values, in normalized processor time -arrange All other combinations of arriving passenger and seated passengers result in no time 3.2.2 Seat collisions A common occurrence when loading a plane is the need for a passen- ger to cross a seated passenger to reach his seat. For example, the passenger assigned to the window seat 22A could be forced to move across the passenger sitting in the middle seat 22B in order to reach for seat collisions, we implemented a new processor function: ount his seat. We call this situation a seat collision. In order to ac Rearrange. This cycle is spent waiting for the aisle to clea after the seat collision. This operation reduces the seat collision counter by one Seat collisions have a certain time penalty(which is stored as the seat collision counter)associated with This penalty is dependent on what type of collision occurs. The possible collisions for a standard 6-wide airplane can be seen in figure 3 When a seat collision is detected, the processor for that row spends a number of cycles equal to the time cost sorting out the collision. During that time, no other passengers may enter the pro- cessor(though they can enter the processor queue The values for the seat collision time costs were determined by phys- ical experimentation involving multiple trials over a simulated plane Assumptions in section 3.2.2 All seat collisions of a given type have the same time cost Though we could expect some variation in collision time(due
Team 2056 Page 14 of 50 Arriving Passenger Seated Passengers Time cost Middle Aisle 9 Middle Aisle and Window 9 Window Aisle 9 Window Middle 9 Window Middle and Aisle 13 Figure 3: Table of seat collision values, in normalized processor time trearrange tpass . All other combinations of arriving passenger and seated passengers result in no time penalty. 3.2.2 Seat collisions A common occurrence when loading a plane is the need for a passenger to cross a seated passenger to reach his seat. For example, the passenger assigned to the window seat 22A could be forced to move across the passenger sitting in the middle seat 22B in order to reach his seat. We call this situation a seat collision. In order to account for seat collisions, we implemented a new processor function: • Rearrange. This cycle is spent waiting for the aisle to clear after the seat collision. This operation reduces the seat collision counter by one. Seat collisions have a certain time penalty (which is stored as the seat collision counter) associated with them. This penalty is dependent on what type of collision occurs. The possible collisions for a standard 6-wide airplane can be seen in figure 3. When a seat collision is detected, the processor for that row spends a number of cycles equal to the time cost sorting out the collision. During that time, no other passengers may enter the processor (though they can enter the processor queue). The values for the seat collision time costs were determined by physical experimentation involving multiple trials over a simulated plane row. Assumptions in section 3.2.2 • All seat collisions of a given type have the same time cost. Though we could expect some variation in collision time (due
Team 2056 Page 15 of 50 to variation in passenger age or size), we expect the variation to be small, except for an insignificant number of outlier cases A major factor in airplane boarding times involves passengers stor ing their luggage. For a given plane, the number of overhead bins is limited, and as they become increasingly full, the time it takes to stow a bag increases. Hence, we developed a statistical model of baggage handling. Baggage handling is performed by the processor at a given row using the following command Stow. This cycle is spent by a passenger storing his bag in the overhead bin. The baggage handling counter is decreased by 1 Baggage handling times are stored in the baggage handling counter o determine baggage handling times, we use a Weibull distribution because of its added flexibility in shape and scale over other distri- butions. The density function of our distribution is given by f(x,k,)=5()“-2-() where A is a scaling parameter, k is a shape parameter, and a is the number of people who have entered the plane from the boarding line (figure 4) Integrating over the number of people who have entered, we obtain the following cumulative distribution function ae(x)dy 1-e We use this cumulative distribution function as a measure of the additional time it takes to load baggage as the plane fills up. The expression for the waiting time of passenger is given by 「c*F(x,h,入)+N1 where c is a measure of the additional time we would expect some- one to take to store baggage when the plane is full, N is a gaussian noise parameter which accounts for the non-uniformity of the board ing process and is the ceiling function
Team 2056 Page 15 of 50 to variation in passenger age or size), we expect the variation to be small, except for an insignificant number of outlier cases. 3.2.3 Baggage A major factor in airplane boarding times involves passengers stowing their luggage. For a given plane, the number of overhead bins is limited, and as they become increasingly full, the time it takes to stow a bag increases. Hence, we developed a statistical model of baggage handling. Baggage handling is performed by the processor at a given row using the following command: • Stow. This cycle is spent by a passenger storing his bag in the overhead bin. The baggage handling counter is decreased by 1. Baggage handling times are stored in the baggage handling counter. To determine baggage handling times, we use a Weibull distribution because of its added flexibility in shape and scale over other distributions. The density function of our distribution is given by, f(x, κ, λ) = κ λ x λ κ−1 e −( x λ ) κ where λ is a scaling parameter, κ is a shape parameter, and x is the number of people who have entered the plane from the boarding line (figure 4). Integrating over the number of people who have entered, we obtain the following cumulative distribution function, F (x, κ, λ) = Z x 0 κ λ y λ κ−1 e −( y λ ) κ dy = 1 − e −( x λ ) κ We use this cumulative distribution function as a measure of the additional time it takes to load baggage as the plane fills up. The expression for the waiting time of passenger x is given by, dc ∗ F (x, κ, λ) + Ne where c is a measure of the additional time we would expect someone to take to store baggage when the plane is full, N is a gaussian noise parameter which accounts for the non-uniformity of the boarding process and de is the ceiling function