数学建模飞机的登机顺序安排问题

1、飞机的登机顺序安排问题摘要美国航空机场服务规划副总裁马克.都彭的话来说:“登机就好比是跟在一辆慢吞吞的卡车后行驶,又不能超车。”长期以来,航空公司为了使飞机按时出发费尽了心思。有的公司安排从后排开始登机,有的公司从靠窗座位开始,还有些公司设计出两者的组合方案。但实际情况却没有如航空公司所愿。近年来随着民用航空业飞速发展,无论是航空公司还是旅客都希望缩短登机时间,这样航空公司可以赢得更多时间用于飞行获得丰厚利润,旅客也可以缩短旅途时间。然而随着乘坐飞机的旅客越来越多以及飞机的容量不断增加,使得登机时间却在不断加长。如何缩短登机时间这一问题亟待解决。针对客机登机顺序问题,文章将登机过程类比于总线型

2、局域网的数据传输过程,建立了总线状态模型,在此基础上建立了蒙特卡洛随机模拟模型。总线状态模型的主要思想是:利用总线型局域网拓扑结构的原理,将客机登机所需时间转化为拓扑结构中总线从空载状态到负载状态再到空载状态所经过的时间。通过查阅相关资料文献,我们筛选出六种比较具有代表性的登机方案-Back to Front、Rotating Zone、Random、Reverse Pyramid、Outside in、block。对选择的不同机型进行模型求解,对模拟结果进行分析,得出不同飞机设计登机方案的原则。在此原则的基础上,提出新的方案,并对新方案进行模拟求解,最后从已有方案的六种方案和新提出的方案中提

3、出适合各型飞机最优的登机方案。关键词:客机、登机、总线状态模型、蒙特卡洛随机模拟模型一.问题重述航空公司可以自由的安排等待登机的旅客的登机顺序,首先安排有特殊需要的乘客登机就座已经成为惯例. 按照常规有特殊需要的轮椅旅客首先登机,紧跟着是头等舱的乘客(他们坐在飞机的前部. 然后是安排经济舱和商务舱的乘客按行排队登机,从飞机后排的乘客依次往前安排登机。从航空公司的角度来看,除了考虑到乘客的等待时间外,时间就是金钱,所以登机时间最好应该减小到最少. 只有飞机载客飞行,航空公司才能赚钱,而过长的登机时间将会限制飞机在一天内的飞行次数.发展大型飞机,诸如空客A380-800客机(载客800人 这样的最

4、小化登机(离机时间的问题就更显得重要了。(1针对不同的小型(85-210座、中型(210-330座和大型(450-800座客机,设计制订并比较不同乘客人数的登机或离机程序.(2编写一份不超过两页纸的实施概要,你要阐明你们的研究结论。阅读对象包括航空公司的业务主管、登机口的执法人员、空(地勤有关人员.二.问题分析本文要求设计合理优化的登机、下机步骤,使乘客登机、下机的时间最小,以此来增加飞机在每个周期的飞行次数,缩短周转时间从而为航空公司增加收益。要研究不同登机方案的登机时间,首要的问题是要明确登机时间是由哪些部分构成,通过对文献的研读以及对登机过程的研究,我们发现周转时间的影响因素关键在于登机

5、乘客造成的干扰时间,问题的重点在于尽可能的缩短干扰时间,在假设条件下转换成尽量减少干扰次数的问题上,包括减少座位干扰次数和过道干扰次数。登机时间主要由乘客步行时间、放行李的时间、不同排座位乘客之间的干扰时间以及同一排的乘客之间的干扰时间构成,在此基础上就是建立相应的模型计算总的登机时间。通过对飞机座位布局和乘客登机过程的研究,我们发现飞机座位布局跟局域网的总线型拓扑结构极为相似,而乘客的登机过程跟局域网上的信息传递过程极为相似,于是可以通过将飞机登机问题转化为总线型局域网上的信息传递问题来进行研究。飞机的走道就相当于总线型局域网的总线,乘客相当于总线中传递的信息包,在局域网中总线状态可以描述局

6、域网的状态,同样,飞机走道的状态(走道上各位置乘客的状态也可以反映飞机的登机状态。于是,可以通过飞机走道状态的研究来找到总登机时间的算法。找到计算登机时间的算法后,可以进一步结合计算机模拟的算法对现有的登机策略进行模拟研究,通过对结果的对比分析并结合实际情况,可以判断不同登机方案的优劣并提出相对最优的方案。三.模型假设(1所有乘客所带上机的行李的大小重量相同;(2乘客的身体情况和行动能力相同;(3乘客一个紧接一个以相同间距进入飞机,且进入飞机过道上的乘客之间的间距也保持相同;(4过道上一次只能通行1人;(5 乘客为同一排的乘客让出空间使其到达自己位置时,必须先让到过道上,此时在过道上的让与被让

7、者占有的过道空间还是一个人所占有的空间;(6乘客不会走错到不属于自己的位置上;(7乘客首先在走道上放好自己的行李,各乘客放行李的时间相同,且一次放好不会再进行调整;(8所有乘客按登机牌上的座位号对好入座,不会调换座位;(9飞机所有位置坐满;(10乘客不会出现迟到等其他一些突发情况。(11某乘客登机行为只可能影响到在他之后登机的一个人,对其他人没有后续影响.(12登机门为飞机的前舱门。(13乘客均按登机牌号码入座。如果乘客不对号入座,那么就有可能造成配载的计算重心与飞机的实际重心发生偏差,非满客时此规定尤为重要。四.符号说明错误!未找到引用源。b t 乘客从一排座位到相邻座位间的步行时间f t

8、乘客放行李的时间1t 需要一个乘客让位的时间2t 需要两个乘客让位的时间t 基本时间间隔,b t t =i t 表示i t 时刻i Z i t 时刻的总线状态ik z i t 时刻的总线上k 节点的状态五.模型准备5.1登机时间登机时间是指发登机牌到旅客安检、托运行李、候机楼候机、排队登机等时间;从旅客进入飞机到在座位上坐好的时间为入座时间。乘客登机时间是这两部分时间之和。经波音公司调查,乘客登机时间主要来自于乘客入座时间(特别是大飞机,如 A380。乘客入座时间来自于乘客入座的干扰,主要是座位干扰和通道干扰。登机方式及步骤(1从后往前:把乘客分为适当的几组,按一定的次序从机舱的尾部就做一直到

9、机舱前面结束就做。(2从外向内:首先靠着窗户的就座,然后中间的就座,最后靠走道的就座。(3反向金字塔系统:首先是后窗与中间就坐,然后是前窗与中间,再接着是后面的的走廊过道,最后是前面的走廊过道。5.2总线型局域网的拓扑结构总线型局域网的拓扑结构是指用一根称为总线的同轴电缆将服务器和工作站以线性方式连接在一起。总线的两端都有一个终端器,它可给连接在总线之间的电路加载。所有网络上的计算机通过合适的接口连接在总线上,即网络上的所有节点共享这条总线,总线上的节点通过广播信息的地址与各节点通信。支线上的每个节点都有唯一的一个地址。当节点的地址与信息的地址相同时,就把总线上的信息复制下来。网络结构示意图如

10、下(图1。图1总线型局域网拓扑结构在总线型局域网中,可以只有一台服务器,只有这台服务器能向网络中其他各节点发送数据包,其他网络节点通过共同的总线接受服务器发送给自己的数据包。5.3乘客登机就座过程与总线型拓扑结构信息传输的类比通过研究飞机的登机过程,我们发现飞机的登机过程与上面介绍的总线型局域网信息传输过程非常相似。从结构上来说,客机的舱门好比总线型局域网拓扑结构的服务器,过道好比总线,客机的各个座位好比拓扑结构中支线上的各个节点,乘客好比要传输的数据包。从过程上来说,乘客经过舱门,通过过道,到达自己座位的过程就好比网络结构中的服务器发出一个个的数据包到总线再到各个节点的过程;而当乘客到达总线

11、上的目的地址进入支线时,由于要放行李或有其他乘客干扰使其占用过道时间较长,这相当于总线的传输速度要比支线的传输速度快得多,因此支线在接受数据时会占用较多的总线时间。从上面的分析不难看出,飞机的登机过程在一定程度上可以近似看作一总线型局域网传输数据的过程,因此我们完全可以借鉴研究局域网的一些思想和方法来研究飞机登机的过程。在局域网中,可以用总线状态即总线上各节点的状态来描述和研究某时刻局域网的运行状态,因此我们可以通过研究登机过程中某时刻飞机走道的状态来描述登机的过程。只要找到走道相邻各状态之间的联系,就可以求得登机的时间。从这个角度出发可以建立求解飞机登机时间的模型。5.4基本问题的确定要研究

12、登机过程的总时间,首要的问题是确定登机时间由那些部分构成。在登记过程中,乘客从飞机入口走到相应位置要花费步行时间;一般乘客都带有一些随身行李,到达座位旁的走道时要先将行李放在座位上方的行李架上,这就是放行李的时间;当乘客需要已入座好的同排乘客让出空间使自己入座时,需要一定的让座时间。于是,整个登机过程所需时间主要就与乘客的步行时间、放行李时间、让座时间三部分有关,下面分别对这三种时间进行研究。(1步行时间根据资料,在登记过程中,乘客从某一排行走到相邻排的平均时间是0.95秒,根总线节点支线节点终端器终端器 支线 总线服务器据假设(3和假设(4,为研究问题方便,可以将整个走道沿行进方向分成若干段

13、,每一段的长度就是相邻两排座位之间的距离,如下图所示(图2: 图2 客机座位平面简化图图中标注为0的格子表示过道的一段,标注为负的格子表示左边的座位,标注为正的格子表示右边的座位,1(-1、2(-2、3(-3分别代表靠走道的座位、中间的座位、靠窗的座位。因此可以认为,在走道不堵塞的情况下,一个乘客经过0.95b t =秒从走道的一个格子行走到相邻的下一个格子。(2放行李的时间根据资料,乘客平均放行李的时间是7.1f t s =,根据假设(1和假设(7,每个乘客到达自己座位旁的走道时,都要先站在走道上放好行李,且放行李的时间都是7.1秒。(3让座位的时间座位干扰:靠在窗户的乘客入座时,外面的座位

14、上已经有乘客就坐,这时外边的这位的乘客需要起身给刚来的这位乘客让开位置使他能够顺利入座。根据资料,平均让座的时间是9.7秒,设A 、B 、C 分别代表同排的三个位置的入座顺序(A 代表最先入座、C 代表最后入座,如C-B-A 代表靠窗的座位最先入座、靠过道的座位最后入座,其考虑的情况为以下几种:1B-C-A 这种情况需要的时间为3个单位,如设一个单位的时间为0t ,则这种情况需要03t 的让位时间;2 C-A-B 这种情况需要03t 的让位时间;3 A-C-B 这种情况需要05t 的让位时间;4 B-A-C 这种情况需要06t 的让位时间; 5 A-B-C 这种情况需要08t 的让位时间;于是

15、由平均让位时间9.7秒可以计算出0 1.94t s =。据此,对于某一个乘客来说,如果需要别的乘客让位,其可能的情况为: 1 只需要靠走道的一个乘客让位,所需时间为03 5.82t s =; 1 只需要坐中间的一个乘客让位,所需时间为03 5.82t s =;3需要靠走道和坐中间的两个乘客让位,所需时间0611.64t s =。 综上,某个乘客若需要让位,其可能的情况是: 1 只需一个乘客让位,所需时间为1 5.82t s =;1 需要两个乘客让位,所需时间为211.64t s =。 需要说明的是,以上放行李的时间和让位的时间都是指从动作发生开始至让出走道为止之间的时间。同时,为了研究问题的方

16、便,以乘客步行时间0.95b t =为基准,将放行李时间7.1f t s =调整为7.6f t s =,将让位时间1 5.82t s =调整为1 5.7t s =,将211.64t s =调整为211.4t s =。这样调整后8f b t t =,16b t t =,212b t t =,这样就可以0.95b t =为一个时间间隔研究总线状态的改变,可以方便问题的研究。同时,做出这样调整还有另外一个意义。由于还有很多突发因素没有考虑,有可能计算出的登机时间比实际的小,这样就会导致出现航班延误的情况,对时间做出上述调整后,必然会增加计算所得的登机时间,从而可以在一定程度上减少航班延误的情况发生。

17、六.模型的建立与求解6.1总线状态模型的建立由前面的分析,将登机过程看成总线型局域网的信息传输过程以后,总的登机时间就相当于总线开始由空载状态进入负载状态起,最后回复到空载状态瞬间所经历的时间,而这段时间的确定依赖于中间任一时刻总线状态的确定。总线状态的描述若总线上有n 个节点,那么i t 时刻的总线状态i Z 可以描述为:(01i ik Z z = i1i2ik in i(k-1i(k+1(z ,z ,z ,z ,z ,z 或其中0ik z =表示i t 时刻k 节点上没有到达信息包,1ik z =表示i t 时刻k 节点上有到达信息包。这样,总线状态通过其上各个节点的状态来描述,总线状态的

18、改变取决于各节点状态的改变。设(1i t -时刻k 节点的状态为(1i k z -,i t 时刻k 节点状态的为ik z ,那么从(1i t -时刻到i t 时刻k 节点状态的改变可以分为以下四种情况: (1 (100i k ik z z -=出现这种情况的可能条件是:1 (1(10i k z -=,即(1i t -时刻1k -节点上没有数据包到达;2 (1(11i k z -=,即(1i t -时刻1k -节点上有数据包到达,且其目的地址就是1k -节点,但还在等待进入下一级目的地址;(2 (101i k ik z z -=出现这种情况的条件是:(1(11i k z -=,即(1i t -时

19、刻1k -节点上有数据包到达; (3 (110i k ik z z -=出现这种情况的条件可能是:1 (11i k z -=且(1(10i k z -=同时(1(10i k z -+=,即(1i t -时刻k 节点上有信息包到达,且其目的地址是比k 节点大的节点,而(1k -节点上没有数据包到达,同时(1k +节点上没有到达数据包;2 (11i k z -=且(1(11i k z -=同时(1(10i k z -+=,即(1i t -时刻k 节点上有信息包到达,且其目的地址是比k 节点大的节点,而(1k -节点上有数据包到达其目的地址就是(1k -节点,同时(1k +节点上没有到达数据包;3

20、(11i k z -=且(1(11i k z -=,即(1i t -时刻k 节点上有信息包到达,且其目的地址是k 节点,从(1i t -时刻到i t 时刻的基本时间间隔t 内刚好完成放行李或放行李和被让位的过程后离开过道(即让出总线;(4 (111i k ik z z -=出现这种情况的条件可能是:1 (11i k z -=,即(1i t -时刻k 节点上有数据包到达,且其目的地址是k 节点,但从(1i t -时刻到i t 时刻的基本时间间隔t 内还没结束放行李或放行李和被让位的过程而离开过道(即让出总线;2 (11i k z -=且(1(11i k z -+=,即(1i t -时刻k 节点上

21、有数据包到达,1k +节点上也有数据包到达,k 节点上有数据包的目的地址是比k 节点大的节点,从(1i t -时刻到i t 时刻的基本时间间隔t 内1k +节点上的数据包还没有让出总线;3 (11i k z -=且(1(11i k z -+=同时(1(11i k z -=,即(1i t -时刻k 节点上有数据包到达,1k +节点上也有数据包到达,k 节点上有数据包的目的地址是比k 节点大的节点,从(1i t -时刻到i t 时刻的基本时间间隔t 内1k +节点上的数据包刚好让出总线,k 节点上的数据包传送到1k +节点的同时1k -节点的数据包传送到k 节点。根据上述的节点状态改变情况,就可以

22、由上一时刻的所有节点状态确定下一时刻的所有节点状态,即某一时刻的总线状态可以由初始状态和各节点状态的时间递归确定,当总线状态又回复到空载状态时,就是登机完成的时刻。需要说明的是,总线回复到空载状态是以最后一个信息包离开总线,即走道上的最后一个乘客离开走道瞬间为标志,事实上登记结束应该以最后一个乘客入座为标志,但从走道到入座的时间相比总的登机时间来讲可以忽略,因此以总线回复到空载瞬间为登机结束的标志是合理的。6.2随机模拟模型的建立由于在实际情况中,不可能严格要求乘客按照某一顺序排队登机,所以无论以怎样的登机策略登机,登机的过程总存在着一定的随机性,这种随机性一方面来自于乘客进入飞机舱的顺序具有

23、一定的随机性,另一方面人的行动也总是具有一定的随机性和不确定性。根据前面的假设,不考虑这种人的行为不确定性对登机过程的影响,即每个人以既定的相同的行为、时间和节奏进行登机,这样在模拟登机过程的时候所要模拟的随机事件就只剩下乘客进入飞机的顺序。设一定数量的乘客进入飞机的顺序是任意的一个随机顺序,利用蒙特卡洛随机模拟的方法,在计算机上可以先产生一个随机的乘客进入飞机的顺序,然后通过前面的总线状态模型,从总线状态的角度模拟飞机登机的全过程,进而求出登机时间。对同一种登机策略在同一种飞机上进行多次模拟,可以得到该种登机方案运用到该种飞机上的登机时间的期望。下图所示为蒙特卡洛随机模拟的流程图(图3:座位

24、编号产生随机登机顺序初始化总线状态下一间隔时间总线状态否是否空载是退出图3 蒙特卡洛流程图6.3模型的求解根据题目要求,我们选择了大、中、小三种机型的座位布置情况来进行模拟计算,三种机型分别是“B737-300”、“B757-200”和“B777-300”。中、小型飞机都是单走道的,大型飞机是双走道的,其作为布置图见附件1(附图1至附图3。根据前面模型准备的讨论,可以将飞机的座位布置图作如下简化,以小型飞机“B737-300”为例,其简化后的座位布置图如下(图4: 图4 小型机B737-300座位布置图其他两种飞机的座位布置简化图见附件2(附图4和附图5。图3中没有画出头等舱的座位情况,因为头等舱座位较少空间较大,对于总登机时间的影响较小,因此在模拟计算时可以不予考虑,只模拟商务舱和经济舱的登机情况。根据资料,现有的并且较常用的登机方案有六种:Back to Front、Rotating Zone、Random、Reverse Pyramid、Outside In、Block。其登机方法如下图(图5所示: 图5 六种登机方案示意图其中颜色浅的表示先登记,颜色越深表