论文研究 Problems with Queuing Arrangement When Boarding.pdf

飞机的登机顺序安排问题，毕强，何涛，飞机的登机顺序安排问题是典型的最优化问题，亦即应用何种策略使得登机时间最短，乘客等候时间最少。本文我们考虑了阶层的分析方中国科技记文在线http://www.paper.edu.cnFactors influencing the deboarding time: the congestion caused by a passenger who packs up his/herbaggage in the aisle3 Problem analysisBoarding interference is defined as an instance of a passenger blocking another passenger's access tohis or her seat. We assume that there is a correspondence between minimizing the expected number ofpassenger interferences and minimizing the boarding time. a passenger blocked by another passengertakes longer to reach his or her seat than one who has free access. Therefore, as the number ofpassengers facing interference during the boarding process increases, the total boarding time increasesThus, by minimizing passenger interferences, we shorten individual passengers'seating times, whichwill ultimately shorten overall boarding timesWe defined two types of interferences: seat interferences and aisle interferences. Seat interferencesoccur when passengers seated close to the aisle block other passengers seated in theConsider, for example, an aircraft with rows progressively numbered from front to back and seatsabeled A to F from left to right. A passenger sitting in seat 7C(the aisle seat in row 7)could block thepassenger seeking seat 7A ( the window seat)and will have to stand in the aisle for the passenger in 7Ato be seated. The interference is even worse when passenger 7A arrives and passengers 7B and 7C areseatedAisle interferences occur when passengers stowing baggage in overhead bins block other passengersaccess to seats. For example, if passenger gA boards the airplane just before passenger 14C, passengergA will block passenger 14C"s progress down the aisle as he or she stores baggage4 Model construction and solution4.1 Mode I: Dynamic Optimal Model4.1.1 Boarding StrategiesIf all passengers'seats are in the same classI First, let's take a look at what happens on one side of the aisle (passengers choose seats just on oneside of the single aisle; suppose there are 3 columns of scats arranged in n rows)First, we take into consideration 3 seats arranged in the same row on one side of the aisle as a unitIf passengers take their seats from inside to outside, then the boarding time needed is 3T; if passengerstake their seats randomly, then the average boarding time is1(6*63T+(3T+132)+(3T+213)+(3T+t231)+(3T+312)+(3T+t321)=3T+16°(t132+t213+t231+t312+t321From the above expression, it can be seen that taking seats randomly will result in the increasingprobability of making room to let others to get to their seats, and then the blockage of the aisle occursTherefore, suggestions are made that passengers should take inside seats instead of outside ones2. On the premise of Case 1, let's consider the case when a column is considered as a unit. Supposethere are n rows of seats in the cabin if passengers take their seats randomly then the number of rowsthey choose can be developed into a sequence, in which, when the following-up number is bigger thanor equal to the front number, the congestion occurs; it can be easily obtained in terms of probability thatthe number of passenger is 3n, and the number of rows they choose is still n types, when the time ofcongestion caused by passengers' placing baggage in place is(n-1)/2*T; if the following-up number issmaller than or equal to the front number, congestion can occur in either case. Suppose the number ofrows passenger choose is developed into a sequence with the exclusion of the passenger in front of theline, the probability of congestion occurrence in Row 1 is(n+1)/(n+1)=l, and the probability ofcongestion occurrence in Row 2 is n/(n+1); based on this rule, the probability of congestionoccurrence in Row n is 2/(n+1), then the total time of congestion is中国科技记文在线http://www.paper.edu.cn(1+n/(n+1)+(n-1)(n+1)+…+2/(n+1)*T3-3(m+3)n/2(n+1)*TSo we know that passengers should take their seats from back to front in order to reduce the times ofpassengers proceeding forward to back rows or sitting in the same row with the preceding passenger.3. When passengers whose seats are in the last row of each column put their baggage in place, unlesshe/she is not the last one, congestion must occur; hence, whatever means is taken to adjust, at least 2congestions will occur in the whole boarding process. On the premises l and 2, the most rational wayto allow the front row occupied before the back row, thus only two times of congestion occur, which isthe best pattern to expect the minimum congestionTo sum up, with respect to the case on one side of the single aisle, we suggest that passengers shouldtake their seats in the inside column from back to front and then the nearby column and on the basis ofthis rule all other seats are taken upI With respect to both sides of the aisle (passengers may choose seats on either side of the aisleSuppose there are 3 columns and n rows of seats on either sideThe rule is similar to that in one-side case: passengers also need to choose inside seats in the same rowConsidering the width of the aisle and the layout of the bin (bins are installed above on both sides ofthe plane), two passengers can be seated at the same time on both sides of the row with the aisle inbetween, and can put their baggage in the bins at the same time. Theoretically, for 6 passengers in thelast row, there can occur at least 2 times of congestion. If one column of passengers as a group is to geton board, and there are altogether 6 groups, then 5 times of congestion occur. Based on this, we canarrange the boarding with two columns of passengers as a group from back to front on the conditionthat they take the symmetrical seats on both sides of the aisle. There are 3 groups of passengers, butonly two times of congestion occur, which conforms to the theoretical patternAs for the situation on both sides of the aisle, we suggest that boarding should be done with twocolumns of passengers as a group, and seats should be taken from back to front, and from inside tooutside in a symmetrical fashion. First, the two symmetrical inside columns are fully occupied, then thenearby two columns of seats are taken. And it is the same with all the other columnsIll. With respect to the situation with double aisles(suppose there are 4 columns in the middle of theplane with 3 columns on either side each and n rows in the middle and either side of the plane)The boarding takes place simultaneously in either aisle of the plane. What's more, passengers placingbaggage in one aisle doesnt exert any influence on passengers'boarding from the other aisle, thats tosay, as for the same row, there are at most 4 passengers who can place their baggage. So we can saythat if passengers whose seats on one aisle and passengers on the other get on board in an intercrossingway, it is time-saving. Suppose there are k number of passengers in each group(k can be divided by1On, and its quotient is even) and boarding is done in an intercrossing way, then the boarding intervalbetween the first group and follow-up group in the same aisle is kT2, in which, if kT2>=T, then thebaggage placing of the first group won't influence the latter, and thus the whole boarding process wontproduce any congestion, either, if kT=4nT2, Suggestion 3 is adopted; when T1<4nT2, Suggestion 4 is adopted.As for Airbus A380-800, according to conventions, first-class passengers have the privilege to get offboard first, so passengers can get off board from two doors at the same time. Economic-classpassengers can deboard immediately after first-class passengers; since the upper business-class seatsare in the front rows, and economic-class ones are in the back rows, economic-class passengers shouldfirst deboard before business-class passengersThe plane seat arrangement is illustrated as followsFig. I Plane Seat Arrangement中国科技记文在线http://www.paper.edu.cnThe Fig. 1 is the layout of the lower part with 22 first-class seats; the right is the layout of the upperpart with 96 business-class seat on the top and the rest being economic-class seatsSpecific deboarding arrangement1. In view of the small number of passengers and spacious room, deboarding can be random2. The basic layout of seats in the lower part is 3-4-3(2 rows are arranged in 2-4-2), the seats arenumbered A, B, C, D,E, F, GH, L, J from left to right; the scats in 2-4-2 rows are numbered B, C, D,E, F, G,H, Ifrom left to rightScheme 1: if passengers from both aisles deboard in an intersectional manner, G and H deboard beforeC and d, who are followed by f and l, and then b and e, then and finally a, there ismax(0,T167T2)“3+max(0,T1-33T2)Scheme 2: if passengers of C and H, and C and D, get off the plane at the same time, congestion in Fand l, and B and E, occurs. By analogy, similar congestion also occurs in A and J, then there is 2T1When t1>67T2, the total congestion time in Scheme l is 4T1-234T2From4T1-234T22T1-2T1-234T2>0. there is t1>117T2.When T1>117T2, in comparison with Scheme 2, Scheme 1 means a bigger waste of time, so Scheme 2should be adoptedWhen T1<=1l7T2, in comparison with Scheme 2, Scheme l is better, so Scheme 1 should be chosenWhen 67T2>=T1>33T2, the congestion time in case of Scheme l is 2T1-33T22T1-33T23T1 therefore Scheme 1 is more time-saving. which should be chosenWhen T1=33T2, the congestion time in case of Scheme I is Tl, TlTl, so Scheme should bechosen3. The seat arrangement of the business-class cabin is 2-2-2. The seats are numbered A, B, C, D, E, Ffrom left to rightScheme 1: if passengers from both two aisles get off the plane in an intersectional matter, D and e getoff first followed by B and C, then F, and then A, the congestion time is max(0, T1-32T2)+max(0T1-16T2)cheme 2: if D and E, and B and C get off at the same time followed by a and F getting offSimultaneously, the congestion time is TIwhen T1>32T2, the congestion time in case of Scheme 1 is 2T1-4812From 2T1-48T2-TlT1-48T2>0. there is ti>48T2When T1>48T2, Scheme 1 is more time-consuming than Scheme 2, so scheme 2 is supposed to bechosenWhen T1<=48T2, Schemc I is more timc-saving than Scheme 2, so Schemc I is supposed to bechosenWhen T1<=32T2 Scheme I needs less time than Scheme 2. so scheme I should be chosenThe basis scat arrangement of the upper cconomic-class is 2-4-2(one row is of 2-3-2). The scats arcnumbered A, B, C D, E, F, G,H from left to right, and the seats in 2-4-2 row are numbered A, B, C, D,E, GHScheme 1: if passengers from both two aisles deboard in an intersectional manner, F and C should getoff first followed by b and C, then e and H, and then a and D. So the congestion time is max(0T1-25T2)+max(0,T1-26T2)Scheme 2: if passengers of B and C, and f and g get off at the same time with A and D, and e and hfollowing up the congestion time is t1When t1-26T2 the congestion time is 3T1-5IT2From 2T1-51T2-t1T1-51T2 >0. there is T1:>51T2When T1>51T2, Scheme l is more time-consuming than Scheme 2, so Scheme 2 should be chosenWhen t1<=51T2. Scheme 1 is more time-saving than scheme 2. so scheme i should be chosenWhen T1<=26T2. Scheme 1 needs less time than Scheme 2. so scheme l should be chosen中国科技记文在线http://www.paper.edu.cnIn view of different numbers of passengers, the deboarding schemes discussed above are all applicable4.2 Mode ll: Simulation Model4.2.1 Other SolutionsWe found only a few published papers on optimizing the passenger boarding process of airplanes. Awide palette of boarding strategies has been simulated systematically by Van Landeghem andBeuselinck (VLB)[1] Their results will be discussed throughout the paper, in comparison with ourown resultsThe aircraft boarding problem has also been analyzed theoretically as a nonlinear assignment problemThe problem is modeled as a binary integer program where the objective function is the minimizationof the total number of interferences. The study showed that outside-in loading strategies perform betterthan back-to-front do disturbances have not been taken into accountAnd finally the whole turn time process was investigated using an enplane-deplane simulation forBoeing. Various interior configurations of a Boeing 757 have been tested on different boardingstrategies using a discrete event simulation. boeing also verified the results with real passengersrepresenting a typical traveling population4.2. 2 Our SolutionOur examination is based on the studies of VlB. Our work differs to their work in some importantpointsWhile their model uses random process times with triangular distribution for passengers movement,our model applies deterministic constant process times as described. In addition some details such asthe baggage loading delay are not fully described in their paper. It will turn out that the results arerobust under such simplifications and assumptions. the main result is, as in vlb, that cerandom boarding is faster than the standard"back to front"boarding used by many airlinesWe will also look at the robustness of the strategies under disturbances. By disturbances we mean thatpassengers do not enter together with their assigned boarding groups, but earlier or later. Since earlyboarding can be prevented by the staff, this is trcatcd separately from late boarding. We will then alsolook at strategies that are both simple to implement and robust under such disturbancesThe typical boarding strategy, "back to front,, becomes more cfficient under disturbances. That is, inthe interest of cfficient boarding passengers should be encouraged not to follow the rowannouncements. There are, however, strategics that are more efficient than random, and predictably,their performance degrades under disturbances4.2.3 DisturbancesIn our simulation we introduced different disturbancesEarly and/or late passengers: If passengers are divided into boarding groups, it will often occur thatsome arrive late or early. The number of these passengers will increase with the number of boardinggroups. At the ticket reader system, the boarding staff has the possibility to reject passengers that queuein a earlier boarding group. For travelers that are arriving late, access is always granted. We will seehow much the ratio of late and early arriving passengers will influence the quality of the boardingstrategiesAircraft dimensions: A boarding strategy should be robust under the use of different airplane layoutsOccupancy level of the airplane: Airplanes are not always full, and therefore boarding strategiesshould be efficient also with smaller occupancies. llowever, boarding with the same strategy butwith fewer passengers will in the average always be faster than when the plane is full. As long as thescheduled turn times(and therefore the flight schedule) are not adjusted to the expected demand, thereis little need to test boarding strategies for reduced occupancy. Nevertheless, for completeness we will中国科技记文在线http://www.paper.edu.cnadd such results4.2.4 Simulation resultsThe boarding procedure has been analyzed using simulation. We modeled all of the disturbances listedabove. The different call-off methods were modeled as a stream of passengers (identified by their seatlocation) listed in an Excel file. In our model passengers arrive at a constant rate In reality this rate isdetermined by the gating opcrations. We chose not to include this step in our study, in order not toobscure the pure effect of sequencing. All processing times are random(Table 1). Decision variablesare limited to the choice of Class size and the sequence of the Classes. Independent variables areoccupation level of the airplane(62.5% and 100%)(The first one being the average utilization of thereference period with the airline), and carry-on baggage level (Table 2). In this study the first objectiveis to reduce total boarding time. The second objective is to augment the quality perception of thepassengers. Therefore, we will evaluate different boarding systems also by average and maximumindividual boarding timeTablel Process time in seconds(triangular distributionProcess times (second)MinModusMaxnormalPassing one row 1.82.4SituationInstall in seat6930Exit from scat 33.64.2into aisleTable2 Hand baggage distribution under different load conditionsNumber of pieces of hand 1baggage per personDistribution among passengers 60under normal load (Distribution among passengers 206020under high load (%)From America West Airlines we get the basic original data, on which simulations are obtained (Allbasic dates are in the appendix)By bBy-rWγ ha f ro%CALL OFFFIGURE 2: Total boarding time under different call-off systems(90% confidence interval, five replications)中国科技记文在线http://www.paper.edu.cnind vi-h al7uiviuud tuardiriu irrig Jr der dilererl. ca l-ufm rrieLFwud (100% jL iFIGURE 3: Individual boarding time under ditferent call-off methods (100%o occupation)Tab 3 Abscissa's signification(1)I Random1 3by block 10 des25by halfblock 6 alt 237 by halfrow alt 12by block B-E1 4by block 10 alt 126by halfblock 6 alt 1 mix 38 by halfrow alt_23by block 2 des 15by block 10 alt 427 by halfblock 10 des39 bv halfrow alt 54by block 3 des1 6by halfblock 2 des28 by halfblock 10 alt 140 by halfrow alt 8Sby block 3 alt_1 17by halfblock2 des mix 29 by halfblock_ 10 alt 4 41 by_ letter_ wintocorr6 by block 4 des 18 by halfblock 3 des30 by row des42 by letter alt7by_block_4 alt_ 1 19 by halftblock_3_alt 1 31 by row alt_ 143by seat des row by letterBby block 4 alt 2 20 by halfblock 4 des32 by row alt 244 by scat des row alt lettergby block 6 des 2lbyhalfblock 4 alt 133 by row alt 445 by seat alt 1 row alt letter10by block 6 alt 1 22by halfblock 4 des mix 34 by row alt 546 by seat alt 5 row alt letterllby block 6 alt 2 23 by halfblock 6 des35 by row alt 847 by seat alt 8 row alt letter12by_block_6_alt_3 24 by_ _halfblock-6-alt_1 36 by_halfrow desEffect of reduced seat occupancy 0%o confidence interval on selected sequences.100%load日25%ladE品CALL OF SYSTEMFIGURE 4: Effect of reduced seat occupancy(90% confidence interval) on selected sequencesTab 4 Abscissas signification(2)Random5by hallock 2 des mix 9by block 6 des 13by block 10 des2 by_block B-E 6 by alfblock_4 alt 1 10by_block 6 alt 1 14by-block_10 alt 113 by block 2 des7 by halfblock 6 alt 111by _block 6_alt_2 15by_block_10_alt_ 44 by block 10 des 8 by row des12by_block-6alt316by_halfblock_2_des