数学建模(飞机登记).doc

飞机就座问题的研究摘 要针对客机登机顺序问题，文章将登机过程类比于总线型局域网的数据传输过程，建立了总线状态模型，在此基础上建立了蒙特卡洛随机模拟模型。总线状态模型的主要思想是：利用总线型局域网拓扑结构的原理，将客机登机所需时间转化为拓扑结构中总线从空载状态到负载状态再到空载状态所经过的时间。通过查阅相关资料文献，我们筛选出六种比较具有代表性的登机方案-Back to Front、Rotating Zone、Random、Reverse Pyramid、Outside in、block。对选择的不同机型进行模型求解，对模拟结果进行分析，得出不同飞机设计登机方案的原则。在此原则的基础上，提出新的方案，并对新方案进行模拟求解，最后从已有方案的六种方案和新提出的方案中提出适合各型飞机最优的登机方案。关键词：客机、登机、总线状态模型、蒙特卡洛随机模拟模型1.问题重述航空公司允许引领候机乘客以任何次序就座。按照惯例，有特殊需要的旅客首先就座，紧跟着是头等舱的旅客(他们坐在飞机的前部)，然后是经济舱和商务舱的旅客从飞机后排开始向前排按照排结组就座。除了考虑到乘客的等待时间,从航空公司的角度来看,时间就是金钱,登机时间应该最小化。只有载客飞行，飞机才能为航空公司赚钱。过长的登机时间将会限制飞机在一天内的飞行次数。大型飞机，如A380-800客机(载客800人) 就更要缩短登机（以及下机）的时间。现在的问题是：要就乘客人数不同的小型机(85-210)、中型机(210-330)、大型机(450-800)，设计并比较登机和下机时间的步骤。同时准备一份不超过两页纸的实施概要，以便向相关人员阐明结论。2.问题分析本问题是研究不同登机方案对不同大小飞机登机时间的影响，从中找到使不同大小飞机登机时间最短的登机方案，从而增加飞机每天的飞行次数。要研究不同登机方案的登机时间，首要的问题是要明确登机时间是由哪些部分构成，通过对文献的研读以及对登机过程的研究，我们发现登机时间主要由乘客步行时间、放行李的时间、不同排座位乘客之间的干扰时间以及同一排的乘客之间的干扰时间构成，在此基础上就是建立相应的模型计算总的登机时间。通过对飞机座位布局和乘客登机过程的研究，我们发现飞机座位布局跟局域网的总线型拓扑结构极为相似，而乘客的登机过程跟局域网上的信息传递过程极为相似，于是可以通过将飞机登机问题转化为总线型局域网上的信息传递问题来进行研究。飞机的走道就相当于总线型局域网的总线，乘客相当于总线中传递的信息包，在局域网中总线状态可以描述局域网的状态，同样，飞机走道的状态（走道上各位置乘客的状态）也可以反映飞机的登机状态。于是，可以通过飞机走道状态的研究来找到总登机时间的算法。找到计算登机时间的算法后，可以进一步结合计算机模拟的算法对现有的登机策略进行模拟研究，通过对结果的对比分析并结合实际情况，可以判断不同登机方案的优劣并提出相对最优的方案。3.模型假设与符号说明3.1模型假设(1)所有乘客所带上机的行李的大小重量相同；(2)乘客的身体情况和行动能力相同；(3)乘客一个紧接一个以相同间距进入飞机，且进入飞机过道上的乘客之间的间距也保持相同；(4)过道上一次只能通行1人；(5) 乘客为同一排的乘客让出空间使其到达自己位置时，必须先让到过道上，此时在过道上的让与被让者占有的过道空间还是一个人所占有的空间；(6)乘客不会走错到不属于自己的位置上；(7)乘客首先在走道上放好自己的行李，各乘客放行李的时间相同，且一次放好不会再进行调整；(8)所有乘客按登机牌上的座位号对好入座，不会调换座位；(9)飞机所有位置坐满；(10)乘客不会出现迟到等其他一些突发情况。3.2符号说明 乘客从一排座位到相邻座位间的步行时间 乘客放行李的时间 需要一个乘客让位的时间 需要两个乘客让位的时间 基本时间间隔， 表示时刻 时刻的总线状态 时刻的总线上节点的状态4.模型准备4.1总线型局域网的拓扑结构总线型局域网的拓扑结构是指用一根称为总线的同轴电缆将服务器和工作站以线性方式连接在一起。总线的两端都有一个终端器，它可给连接在总线之间的电路加载。所有网络上的计算机通过合适的接口连接在总线上，即网络上的所有节点共享这条总线，总线上的节点通过广播信息的地址与各节点通信。支线上的每个节点都有唯一的一个地址。当节点的地址与信息的地址相同时，就把总线上的信息复制下来。网络结构示意图如下(图1)。总线节点支线节点终端器终端器支线总线服务器图1总线型局域网拓扑结构在总线型局域网中，可以只有一台服务器，只有这台服务器能向网络中其他各节点发送数据包，其他网络节点通过共同的总线接受服务器发送给自己的数据包。4.2乘客登机就座过程与总线型拓扑结构信息传输的类比分析通过研究飞机的登机过程，我们发现飞机的登机过程与上面介绍的总线型局域网信息传输过程非常相似。从结构上来说，客机的舱门好比总线型局域网拓扑结构的服务器，过道好比总线，客机的各个座位好比拓扑结构中支线上的各个节点，乘客好比要传输的数据包。从过程上来说，乘客经过舱门，通过过道，到达自己座位的过程就好比网络结构中的服务器发出一个个的数据包到总线再到各个节点的过程；而当乘客到达总线上的目的地址进入支线时，由于要放行李或有其他乘客干扰使其占用过道时间较长，这相当于总线的传输速度要比支线的传输速度快得多，因此支线在接受数据时会占用较多的总线时间。从上面的分析不难看出，飞机的登机过程在一定程度上可以近似看作一总线型局域网传输数据的过程，因此我们完全可以借鉴研究局域网的一些思想和方法来研究飞机登机的过程。在局域网中，可以用总线状态即总线上各节点的状态来描述和研究某时刻局域网的运行状态，因此我们可以通过研究登机过程中某时刻飞机走道的状态来描述登机的过程。只要找到走道相邻各状态之间的联系，就可以求得登机的时间。从这个角度出发可以建立求解飞机登机时间的模型。4.3基本问题的确定要研究登机过程的总时间，首要的问题是确定登机时间由那些部分构成。在登记过程中，乘客从飞机入口走到相应位置要花费步行时间；一般乘客都带有一些随身行李，到达座位旁的走道时要先将行李放在座位上方的行李架上，这就是放行李的时间；当乘客需要已入座好的同排乘客让出空间使自己入座时，需要一定的让座时间。于是，整个登机过程所需时间主要就与乘客的步行时间、放行李时间、让座时间三部分有关，下面分别对这三种时间进行研究。(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) 需要两个乘客让位，所需时间为。需要说明的是，以上放行李的时间和让位的时间都是指从动作发生开始至让出走道为止之间的时间。同时，为了研究问题的方便，以乘客步行时间为基准，将放行李时间调整为，将让位时间调整为，将调整为。这样调整后，这样就可以为一个时间间隔研究总线状态的改变，可以方便问题的研究。同时，做出这样调整还有另外一个意义。由于还有很多突发因素没有考虑，有可能计算出的登机时间比实际的小，这样就会导致出现航班延误的情况，对时间做出上述调整后，必然会增加计算所得的登机时间，从而可以在一定程度上减少航班延误的情况发生。 5.模型的建立与求解5.1总线状态模型的建立由前面的分析，将登机过程看成总线型局域网的信息传输过程以后，总的登机时间就相当于总线开始由空载状态进入负载状态起，最后回复到空载状态瞬间所经历的时间，而这段时间的确定依赖于中间任一时刻总线状态的确定。5.1.1总线状态的描述若总线上有个节点，那么时刻的总线状态可以描述为：其中表示时刻节点上没有到达信息包，表示时刻节点上有到达信息包。这样，总线状态通过其上各个节点的状态来描述，总线状态的改变取决于各节点状态的改变。5.1.2节点状态的确定设时刻节点的状态为，时刻节点状态的为，那么从时刻到时刻节点状态的改变可以分为以下四种情况：(1) 出现这种情况的可能条件是：1) ，即时刻节点上没有数据包到达；2) ，即时刻节点上有数据包到达，且其目的地址就是节点，但还在等待进入下一级目的地址；(2) 出现这种情况的条件是：，即时刻节点上有数据包到达；(3) 出现这种情况的条件可能是：1) 且同时，即时刻节点上有信息包到达，且其目的地址是比节点大的节点，而节点上没有数据包到达，同时节点上没有到达数据包；2) 且同时，即时刻节点上有信息包到达，且其目的地址是比节点大的节点，而节点上有数据包到达其目的地址就是节点，同时节点上没有到达数据包；3) 且，即时刻节点上有信息包到达，且其目的地址是节点，从时刻到时刻的基本时间间隔内刚好完成放行李或放行李和被让位的过程后离开过道（即让出总线）；(4) 出现这种情况的条件可能是：1) ，即时刻节点上有数据包到达，且其目的地址是节点，但从时刻到时刻的基本时间间隔内还没结束放行李或放行李和被让位的过程而离开过道（即让出总线）；2) 且，即时刻节点上有数据包到达，节点上也有数据包到达，节点上有数据包的目的地址是比节点大的节点，从时刻到时刻的基本时间间隔内节点上的数据包还没有让出总线；3) 且同时，即时刻节点上有数据包到达，节点上也有数据包到达，节点上有数据包的目的地址是比节点大的节点，从时刻到时刻的基本时间间隔内节点上的数据包刚好让出总线，节点上的数据包传送到节点的同时节点的数据包传送到节点。根据上述的节点状态改变情况，就可以由上一时刻的所有节点状态确定下一时刻的所有节点状态，即某一时刻的总线状态可以由初始状态和各节点状态的时间递归确定，当总线状态又回复到空载状态时，就是登机完成的时刻。需要说明的是，总线回复到空载状态是以最后一个信息包离开总线，即走道上的最后一个乘客离开走道瞬间为标志，事实上登记结束应该以最后一个乘客入座为标志，但从走道到入座的时间相比总的登机时间来讲可以忽略，因此以总线回复到空载瞬间为登机结束的标志是合理的。5.2随机模拟模型的建立由于在实际情况中，不可能严格要求乘客按照某一顺序排队登机，所以无论以怎样的登机策略登机，登机的过程总存在着一定的随机性，这种随机性一方面来自于乘客进入飞机舱的顺序具有一定的随机性，另一方面人的行动也总是具有一定的随机性和不确定性。根据前面的假设，不考虑这种人的行为不确定性对登机过程的影响，即每个人以既定的相同的行为、时间和节奏进行登机，这样在模拟登机过程的时候所要模拟的随机事件就只剩下乘客进入飞机的顺序。设一定数量的乘客进入飞机的顺序是任意的一个随机顺序，利用蒙特卡洛随机模拟的方法，在计算机上可以先产生一个随机的乘客进入飞机的顺序，然后通过前面的总线状态模型，从总线状态的角度模拟飞机登机的全过程，进而求出登机时间。对同一种登机策略在同一种飞机上进行多次模拟，可以得到该种登机方案运用到该种飞机上的登机时间的期望。下图所示为蒙特卡洛随机模拟的流程图(图3)：是座位编号产生随机登机顺序初始化总线状态下一间隔时间总线状态是否空载退出否图3 蒙特卡洛流程图5.3 模型的求解5.3.1飞机机型的确定根据题目要求，我们选择了大、中、小三种机型的座位布置情况来进行模拟计算，三种机型分别是“B737-300”、“B757-200”和“B777-300”。中、小型飞机都是单走道的，大型飞机是双走道的，其作为布置图见附件1（附图1至附图3）。根据前面模型准备的讨论，可以将飞机的座位布置图作如下简化，以小型飞机“B737-300”为例，其简化后的座位布置图如下(图4)： 图4 小型机B737-300座位布置图其他两种飞机的座位布置简化图见附件2(附图4和附图5)。图3中没有画出头等舱的座位情况，因为头等舱座位较少空间较大，对于总登机时间的影响较小，因此在模拟计算时可以不予考虑，只模拟商务舱和经济舱的登机情况。5.3.1现有登机方案根据资料，现有的并且较常用的登机方案有六种：Back to Front、Rotating Zone、Random、Reverse Pyramid、Outside In、Block。其登机方法如下图(图5)所示：图5 六种登机方案示意图其中颜色浅的表示先登记，颜色越深表示登机次序越后。5.3.1模拟结果及分析对选择的三种机型，分别利用上面建立的模拟模型对六种登机方案进行计算机模拟，计算登机时间，模拟结果如下：(1) 小型飞机(2) 中型飞机(3) 大型飞机从以上模拟结果可以看出，对于中小型飞机，主要按座位的列来组织分批登机的方案Reverse Pyramid、Outside In、Block总体上都明显由于其他三种方案，主要按座位的行来组织登记的方案Back to Front、Rotatin