飞机的登机顺序安排问题.doc

论文题目:飞机登机顺序安排问题学院:服装学院班级:服工*姓名:* 学号:* 飞机登机顺序安排问题摘 要由于航空旅行快捷便利的优势，现代社会中起着重要作用。每时每刻，千千万万的人享受着他们的航空旅行。由于大众乐意看到机票降价，那么航空公司应设法采取其他措施活得较多利益，所以航空公司希望减少登机时间类提高登记时间类提高飞机的效率。本文首先本文首先模拟、分析现有五种登机模式，寻找到每种模式的优缺点以及减少登机时间的本质是要减少登机过程中发生走道干扰和作为干扰的次数。在此基础上提出双栈缓冲并行模式, 将乘客分组模式改为组对,利用飞机通道作为临时缓冲区,一次安排一个乘客组对登机入座。仿真结果比当前最佳方案在登机时间上优化16%,对提高航空公司收益、改善服务质量和节约运营成本有着十分重要的应用价值。关键词：登记时间 干扰 模拟仿真 离散 一 问题的提出 问题的背景航空公司允许引领候机乘客以任何次序就座，但已经成为惯例的是首先引领有特殊需要的乘客就座，然后是头等舱的乘客就座他们坐在飞机的前部，最后引领持经济舱和商务舱机票的乘客从飞机后排开始向前按照排结组就座。从航空公司的角度来看，除了考虑乘客的等候时间外，时间就是金钱，所以登机时间最好要减到最少。飞机只有在飞行的时候才能为航空公司赚钱，而长的登机时间限制了一架飞机一天中可以飞行的次数。诸如空中客车,可以容纳名乘客的大型机的发展就更要强调缩短登机(以及下机)时间的问题了。 二.问题的假设1. 假设乘客均按登机牌号码入座。因为如果乘客不对号人座,那么就有可能造成配载的计算重心与飞机的实际重心发生偏差，非满客时此规定尤为重要。2. 假设乘客每隔秒登机一次。虽然乘客是连续登机的，但也需要一段时间才能完成登机，因此本文将时间均分到每个乘客。3. 假设在不超过秒的时间内每个乘客都能找到座位并就做完毕。因为这样某乘客登机行为只可能影响到在他之后登机的一个人, 对其他人没有后续影响。4. 所有乘客所带上机的行李的大小重量相同。5. 乘客的身体情况和行动能力相同。6. 乘客一个紧接一个以相同间距进入飞机，且乘客之间的距离也相等。7. 过道上一次只能通行1人。8. 乘客为同一排的乘客让出空间使其到达自己位置时，必须先到过道上，此时在过道上的让与被让者占有的过道空间还是一个人所占有的空间。9. 乘客不会走错到不属于自己的位置上。三符号说明和名词解释t：为走道干扰因子，即单个走道干扰所花费的时间； ：为座位干扰因子，即单个座位干扰所花费的时间；：每次登机过程中发生的走道干扰次数；：每次登机过程中发生座位干扰的次数。 乘客放行李的时间 需要一个乘客让位的时间1 需要两个乘客让位的时间 基本时间间隔， 表示时刻 时刻的总线状态 时刻的总线上节点的状态四问题分析本问题是研究不同登机方案对不同大小飞机登机时间的影响，从中找到使不同大小飞机登机时间最短的登机方案，从而增加飞机每天的飞行次数。要研究不同登机方案的登机时间，首要的问题是要明确登机时间是由哪些部分构成，通过对文献的研读以及对登机过程的研究，我们发现登机时间主要由乘客步行时间、放行李的时间、不同排座位乘客之间的干扰时间以及同一排的乘客之间的干扰时间构成，在此基础上就是建立相应的模型计算总的登机时间。通过对飞机座位布局和乘客登机过程的研究，我们发现飞机座位布局跟局域网的总线型拓扑结构极为相似，而乘客的登机过程跟局域网上的信息传递过程极为相似，于是可以通过将飞机登机问题转化为总线型局域网上的信息传递问题来进行研究。飞机的走道就相当于总线型局域网的总线，乘客相当于总线中传递的信息包，在局域网中总线状态可以描述局域网的状态，同样，飞机走道的状态（走道上各位置乘客的状态）也可以反映飞机的登机状态。于是，可以通过飞机走道状态的研究来找到总登机时间的算法。找到计算登机时间的算法后，可以进一步结合计算机模拟的算法对现有的登机策略进行模拟研究，通过对结果的对比分析并结合实际情况，可以判断不同登机方案的优劣并提出相对最优的方案。 五.模型准备5.1总线型局域网的拓扑结构总线型局域网的拓扑结构是指用一根称为总线的同轴电缆将服务器和工作站以线性方式连接在一起。总线的两端都有一个终端器，它可给连接在总线之间的电路加载。所有网络上的计算机通过合适的接口连接在总线上，即网络上的所有节点共享这条总线，总线上的节点通过广播信息的地址与各节点通信。支线上的每个节点都有唯一的一个地址。当节点的地址与信息的地址相同时，就把总线上的信息复制下来。网络结构示意图如下(图1)。图1总线型局域网拓扑结构5.2乘客登机就座过程与总线型拓扑结构信息传输的类比分析通过研究飞机的登机过程，我们发现飞机的登机过程与上面介绍的总线型局域网信息传输过程非常相似。从结构上来说，客机的舱门好比总线型局域网拓扑结构的服务器，过道好比总线，客机的各个座位好比拓扑结构中支线上的各个节点，乘客好比要传输的数据包。从过程上来说，乘客经过舱门，通过过道，到达自己座位的过程就好比网络结构中的服务器发出一个个的数据包到总线再到各个节点的过程；而当乘客到达总线上的目的地址进入支线时，由于要放行李或有其他乘客干扰使其占用过道时间较长，这相当于总线的传输速度要比支线的传输速度快得多，因此支线在接受数据时会占用较多的总线时间。从上面的分析不难看出，飞机的登机过程在一定程度上可以近似看作一总线型局域网传输数据的过程，因此我们完全可以借鉴研究局域网的一些思想和方法来研究飞机登机的过程。在局域网中，可以用总线状态即总线上各节点的状态来描述和研究某时刻局域网的运行状态，因此我们可以通过研究登机过程中某时刻飞机走道的状态来描述登机的过程。只要找到走道相邻各状态之间的联系，就可以求得登机的时间。从这个角度出发可以建立求解飞机登机时间的模型。5.3登机时间值机时间是指发登机牌到旅客安检、托运 行李、候机楼候机、排队登机等时间；从旅客进入飞机到在座位上坐好的时间为入座时间。乘客登机时间是这两部分时间之和。经波音公司调查，乘客登机时间主要来自于乘客入座时间(特别是大飞机,如 A380)。乘客入座时间来自于乘客入座的干扰,主要是座位干扰和通道干扰。5.4现有的五种登机方式及步骤（1）从后往前：把乘客分为适当的几组，按一定的次序从机舱的尾部就做一直到机舱前面结束就做。（2）区间轮换制度：把乘客分为适当的几组，第一组从机舱前开始就做，第二组从机舱尾部就做，第三组接着第一组向后继续就做，第四组接着第二组，依次类推一直到中间都做好了。（3）没有限制：由于人可以自主的寻找到最优的方式就做，因此不增加任何安排。（4）反向金字塔系统：首先是后窗与中间就坐，然后是前窗与中间，再接着是后面的的走廊过道，最后是前面的走廊过道。（5）从外向内：首先靠着窗户的就做，然后中间的就做，最后靠走道的就做。图 六种登机方案示意图其中颜色浅的表示先登记，颜色越深表示登机次序越后。六.模型建立与求解6.1模型建立6.1.1干扰描述l 座位干扰：靠在窗户的乘客入座时，外面的座位上已经有乘客就坐，这时外边的这位的乘客需要起身给刚来的这位乘客让开位置使他能够顺利入座。如图1中A要越过B、B要越过C都会产生走道干扰。l 走道干扰：在走道上前进的旅客遇到其他旅客阻挡,不能继续前进,需要等待；当前面没有旅客阻挡时,才可以前进。如图1中当E就座后D/F要越过E才能就座会产生座位干扰。 图16.1.2乘客进舱流程图 基于以上两种干扰，本文得到了乘客进舱的大致流程图（不包括特殊情况），如图所示。排队进入飞机舱门每位乘客经历走道干扰、座位干扰、找到座位顺利完成就座完成登机过程 图26.1.3干扰次数的计算n 走道干扰次数的计算根据假设（2）和假设（3），本文认为走道干扰只会发生在相邻两位乘客之间。如果后一位乘客的座位在前一位乘客座位的前面或者前一位乘客和后一位在同一排，在这两种情况下势必要发生一次走道干扰。因此，我们首先设置一个初值为零的变量代表走道干扰的次数，接着用随机数代表乘客模拟登机过程，登机过程中每当遇到走道干扰情况设置变量就累计加一，一直到登机过程结束。当然对于多次模拟时我们可以先设置一元素均为零的一维数组来记录每次模拟得到的登机时间。n 座位干扰次数的计算座位干扰只发生在同一小排中（即走道得一侧，走道两侧的同一排互不干扰）。每位乘客有种位置可选，分别为、，因此在同一小排的位乘客先后的到达顺序可能为：这种情况。因此，我们首先设置一个初值为零的变量代表座位干扰次数，接着用随机数代表乘客模拟登机过程。对于每一位乘客，首先判断在他之前的所有乘客中是否有和他在同一排的；接着根据他们之间的位置关系判断是否发生座位干扰，登机过程中如果发生座位干扰则设置变量累计加一，一直到登机过程结束。多次模拟时可以效仿记录走道干扰次数的方法。6.1.4登机时间的计算要研究登机过程的总时间，首要的问题是确定登机时间由那些部分构成。在登记过程中，乘客从飞机入口走到相应位置要花费步行时间；一般乘客都带有一些随身行李，到达座位旁的走道时要先将行李放在座位上方的行李架上，这就是放行李的时间；当乘客需要已入座好的同排乘客让出空间使自己入座时，需要一定的让座时间。于是，整个登机过程所需时间主要就与乘客的步行时间、放行李时间、让座时间三部分有关，下面分别对这三种时间进行研究。(1)步行时间根据资料，在登记过程中，乘客从某一排行走到相邻排的平均时间是0.95秒，根据假设(3)和假设(4)，为研究问题方便，可以将整个走道沿行进方向分成若干段，每一段的长度就是相邻两排座位之间的距离，如下图所示(图2)：图2 客机座位平面简化图图中标注为0的格子表示过道的一段，标注为负的格子表示左边的座位，标注为正的格子表示右边的座位，1(-1)、2(-2)、3(-3)分别代表靠走道的座位、中间的座位、靠窗的座位。因此可以认为，在走道不堵塞的情况下，一个乘客经过秒从走道的一个格子行走到相邻的下一个格子。(2)放行李的时间根据资料，乘客平均放行李的时间是，根据假设(1)和假设(7)，每个乘客到达自己座位旁的走道时，都要先站在走道上放好行李，且放行李的时间都是7.1秒。(3)让座位的时间当乘客的座位是非靠走道的座位时，有可能需要相邻的乘客让开位置，根据资料，平均让座的时间是9.7秒，设A、B、C分别代表同排的三个位置的入座顺序（A代表最先入座、C代表最后入座，如C-B-A代表靠窗的座位最先入座、靠过道的座位最后入座），其考虑的情况为以下几种：1)B-C-A 这种情况需要的时间为3个单位，如设一个单位的时间为，则这种情况需要的让位时间；2) C-A-B 这种情况需要的让位时间；3) A-C-B 这种情况需要的让位时间；4) B-A-C 这种情况需要的让位时间；5) A-B-C 这种情况需要的让位时间；于是由平均让位时间9.7秒可以计算出。据此，对于某一个乘客来说，如果需要别的乘客让位，其可能的情况为：1) 只需要靠走道的一个乘客让位，所需时间为；1) 只需要坐中间的一个乘客让位，所需时间为；3）需要靠走道和坐中间的两个乘客让位，所需时间。综上，某个乘客若需要让位，其可能的情况是：1) 只需一个乘客让位，所需时间为；1) 需要两个乘客让位，所需时间为。需要说明的是，以上放行李的时间和让位的时间都是指从动作发生开始至让出走道为止之间的时间。其中： 为走道干扰因子，即单个走道干扰所花费的时间； 为座位干扰因子，即单个座位干扰所花费的时间；、可以根据不同的机型和实际情况设置。同时，为了研究问题的方便，以乘客步行时间为基准，将放行李时间调整为，将让位时间调整为，将调整为。这样调整后，这样就可以为一个时间间隔研究总线状态的改变，可以方便问题的研究。同时，做出这样调整还有另外一个意义。由于还有很多突发因素没有考虑，有可能计算出的登机时间比实际的小，这样就会导致出现航班延误的情况，对时间做出上述调整后，必然会增加计算所得的登机时间，从而可以在一定程度上减少航班延误的情况发生。6.2模型的求解模型的求解主要依赖于计算模拟各种登机模式。利用6.1的模型计算出每种模式下多次登机时间，最后求和平均得到每种登机模式需要的大致时间。为了定量的比较每种模式的优劣，本文利用MATLAB7.0模拟出多种登机模式，得到各种模式的登机时间。知己知彼；百战不殆，我们首先模拟出现今经常采用的几种登机模式，得到每种登机模式的登记时间。6.2.1模拟现有登机模式如果我们事先对138个座位进行编码（如图3），然后我们利用随机数模拟乘客拿着登机牌入座，那么我们就可以得到对应登机实际情况的混乱程度，并且我们可以通过程序得到每位模拟乘客在登机过程中遇到的每种干扰次数，最终得到整个登机过程中每种干扰发生的总次数。373839424140313233363534252627302928192021242322131415181716789121110123654图三 座位编码在候车室的时候先把乘客大体上分成五组排队，按照表一中不同颜色对应区域进行分组，每组中乘客顺序不做要求：这五组依次序登机，但每一组中的乘客并没有一定得先后顺序，具体情况如表二所示（所示内容仅多次模拟中的一次）： 表一 从前到后模式的分组133134135138137136127128129132131130121122123126125124115116117120119118109110111114113112103104105108107106979899102101100919293969594858687908988798081848382737475787776676869727170616263666564555657605958495051545352434445484746373839424140313233363534252627302928192021242322131415181716789121110123654表二 模拟的乘客登机顺序248212515273026229221619107428311146122395201813171314255505139534957443648333546385460404352564732454137595834858887687269677578618370777480646679767190816563738984628286929991941111069795104112102105981031091071011109611410811393100124120118131138122133136121129115130116119132135137125128117123134126127注：表格中的数值代表计算机模拟出的拿有特定登机牌的人，从第一个人开始，横向依次进入机舱，寻找自己对应的座位就坐。从后到前模式中乘客先从机舱的尾部开始入座,直到所有旅客就坐完毕。这种方法的优点就是走道干扰次数少,不足之处是座位干扰次数增加。（2）区域轮换模式按登机牌上的号码先把乘客分成5组，如表三所示不同颜色代表不同组。这5组得按次序从小到大的依次登机，首先第一组从后面往前排，然后第二组从前往后排，然后依次奇数组从后往前，偶数组再从前往后排，直到都登机结束。表三 区间轮换模式的分组133134135138137136127128129132131130121122123126125124115116117120119118109110111114113112103104105108107106979899102101100919293969594858687908988798081848382737475787776676869727170616263666564555657605958495051545352434445484746373839424140313233363534252627302928192021242322131415181716789121110区域轮换模式基于从后向前模式减少了走道干扰，增加了座位干扰。（3）从外向内首先把乘客分为三组，如表四所示不同颜色代表不同组。这三组得按照有外到内的次序登机。 表四 从外向内模式的分组133134135138137136127128129132131130121122123126125124115116117120119118109110111114113112103104105108107106979899102101100919293969594858687908988798081848382737475787776676869727170616263666564555657605958495051545352434445484746373839424140313233363534252627302928192021242322131415181716789121110123654从外到内模式中靠近窗户的乘客先入座, 中间一排的乘客其次,靠近走道的乘客最后就坐。这种方法的优点是座位干扰次数减少，走道干扰次数增加。（4）反金字塔模式将乘客按照表五的颜色区域进行分组。 表五 反金字塔模式的分组133134135138137136127128129132131130121122123126125124115116117120119118109110111114113112103104105108107106979899102101100919293969594858687908988798081848382737475787776676869727170616263666564555657605958495051545352434445484746373839424140313233363534252627302928192021242322131415181716789121110123654反金字塔模式基于从外到内的模式，避免座位干扰，从而也只有走道干扰。6.2.2不同模式数据分析从后向前模式区间轮换制度模式从外向内模式反金字塔模式双栈缓冲模式座位干扰次数68690022过道干扰次数7981707320登机所需时间（min）1081093536.630对上文所述的五种模式的分析，我们发现要想减少登机时间，只有尽可能的减少座位干扰和过道干扰次数。在座位相同的情况下，我们发现既有座位干扰和过道干扰的“从后到前“的登机模式所需的时间比只有过道干扰的“从外到内”登机模式所需的时间多，由此我们得到完成一次过道干扰所需的时间小于完成一次干扰所需的时间，所以在我们设计的新模式时候，要尽可能的使过道干扰的次数大于座位干扰的次数。我们通过对“从后到前”模式和“区域轮换” 模式的分析，发现“从前到后“模式所需的登机时间小于“区间轮换” 模式所需的时间，所以所以在我们设计的新模式时候，把乘客进行分组，要尽可能的安排坐在飞机后面的乘客先上飞机。6.2.3设计的新模式双栈缓冲并行模式：基于上文的分析及具体要求，我们引入了一个新模式：双栈缓冲并行模式。首先，将旅客分成若干组, 旅客按分组序号的顺序进入飞机, 偶数组按“从外向内”模式进入机舱的尾 区, 奇数组按”从后到前”模式进入机舱的前区。具体情况如表六所示： 表六 双栈缓冲并行模式的分组133134135138137136127128129132131130121122123126125124115116117120119118109110111114113112103104105108107106979899102101100919293969594858687908988798081848382737475787776676869727170616263666564555657605958495051545352434445484746373839424140313233363534252627302928192021242322131415181716789121110123654现在面临的问题是如何利用飞机的客舱通道进行分组, 以减少旅客入座过程的干扰, 加快旅客入座的 时间。为此本文设计了一种有效的旅客登机模式, 即双 栈缓冲并行模式, 这种模式的优势在于：将旅客分成组对，在每个组对中，偶数组的旅客按“从外到内”模式入座，2i+1组的旅客按“从后到前”模式入座。注意到，由于飞机通道缓冲区的作用，每个组对的前一组旅客不会干扰到后一组旅客入座。即前一组旅客入座过程与后一组旅客入座过程是并发进行的，当把两组旅客入座时间设计为相等时，前一组旅客的干扰时间可以忽略不计。或者说，在一个组对中的两组旅客用同一个时间段完成登机的入座过程。基于这种并行模式得到机舱分组如下: 颜色代表分组顺序，奇数组按“从后向前”模式进入, 偶数组按“从外到内”模式进入。具体步骤如下：1、把所有乘客按照上面方法分为2N+1组。第一组为头等舱旅客，优先进入。2、根据飞机的座位布局、行数和列数，计算在每个组对中, 前组OI旅客入座的 干扰数和后组BF旅客入座的干扰数，使两组旅客入座干扰数相等。进而划分出两组分别的旅客数量。3、经济舱的旅客按分组序号的先后顺序依次进舱，以一个一个的组对形式，安排旅客的入座过程。从,，直至全部旅客都入座就绪为止。4、优缺点比较BF 模式：旅客先从机舱的两头入座，当两头的旅客坐满之后，中间的旅客再入座，直到所有旅客就座完毕。这种方法的优点就是走道干扰时间少，不足之处是座位干扰时间增加。OI 模式：靠近窗户的旅客先入座，中间一排的旅客其次，靠近走道的旅客最后就坐。这种方