飞机排队模型-数学建模

MCM-89题机场安排最优排队调度问题机场通常是用“先到先服务”的原则来分配飞机跑道，即当飞机准备好离开登机口时，驾驶员电告地面控制中心，加入等候跑道的队伍。假设控制塔可以快速在线数据库中得到每架飞机的如下信息：1、预定离开登机口的时间；2、实际离开登机口的时间；3、机上乘客人数；4、预定在下一站转机的人数和转机时间；5、到达下一站的预定时间。又设共有七种飞机，载客从100人起以50人递增，载客最多的一种是400人。试开发和分析一种能使乘客和各航空公司双方都满意的数学模型。（注：七种飞机可能分属于不同的航空公司）在目前的各国机场，一般都使用“先到先服务”的排队系统，这一系统虽一直延用，但效率不高，且不能调节意外情况的发生。在这里将要给出一个利用数据库系统快速排队的模型，以使机场高效的服务，并使航空公司在尽量小的花费情况下，达到顾客满意的目的。模型的基本假设1.机场上所有要起飞的飞机，都必须使相同一条跑道，并且任何一架飞机在起飞的时候都需要完全地占有整条跑道，每架飞机占用的时间是一样长的。这一假设可把整个时间分割成离散的等长的小时间段（也称为起飞窗口宽度），在每个小时间段上可容纳一架飞机完成起飞操作。2.第i架飞机由第j个时间段上起飞时，其所需费用仅与该飞机和时间位置有关，而与它前面是哪架飞机无关。即费用不是前面飞机的函数，因此这一假设可把对应于不同排序的总费用都统一描述为一个线性函数。3.任何飞机从离开自己的通道口到达跑道入口处所需要的时间假定都一样。同时为了避免有一大堆飞机挤在跑道入口处等待飞机（一般机场也不太可能这样），这时如有另一架飞机需要紧急起飞，这就须将所有排在前面的飞机挤到一边来腾地方，因此假设每架飞机都有立即进入跑道口的通道。这样在须要调整次序时，只须在数据库中的次序上进行调整，而不必对飞机实地重排。并且飞机须在为其指定的小时间段上才准许离开自己的通道口。4.设是一架飞机要按时到达目的地所必须起飞的最晚时限，并假设如果一架飞机在时限以后才起飞，则它必须以最大安全速度飞完全程。（而在以内起飞者可着情加速）。5.如果一架飞机在时限以后起飞，则该机上所有需转机的乘客都将误下次班机，并设给每个乘客用于赔偿重新安排旅行计划的补偿费用是一样的。模型设计与可行性分析如果在t0时刻仅有一架飞机或没有要求起飞的飞机，则机场就直接安排其起飞或闲置。因此设在t0有n架飞机同时要求起飞。由假设1，可将n架飞机起飞所需要的总时间分成n个等长的小时间段（如∆长）。下面如何安排哪架飞机在哪个时段上起飞要依赖于实际航班的花费和顾客的满意程度来确定。设为Cij第i架飞机从第j个小时间段上起飞时所需一切费用之和，于是所有可能的排序带来的费用计算有如下的费用距阵表示：111212122212.....................nnnnnncccccccccc（1）并设Xij=0或1，当第i架飞机在第j个时段上起飞时Xij=1，否则Xij=0于是相应地安排方案距阵为：111212122212.....................nnnnnnxxxxxxxxxx（2）由于ijx只取0，1值，故如下的一个距阵（2）即对应一个排序方案：飞机窗口123…n1010…02100…0……………n000…1即第一架飞机排第2个窗口起飞，第2架排第一个窗口起飞…，最后一架排最后起飞。并由上表的安排结构，知道（2）中的距阵满足每行中仅有一个元素为1，即每个窗口上仅有一架飞机占用；该阵每列中也有一个元素为1，即每架飞机占用n个窗口中的一个。即变量Xij须满足约束：1nijjx=11,2,...,in(3)1nijix=11,2,...,jn由于ijx为取0，1值的变量，因此不同的分派安排对应的仅仅是ijx取1的位置不同而已。于是设1c为安排第一架飞机的费用11111121211...nnccxcxcx由此全部飞机安排的总费用为：11nnijijijzcx即构成目标函数。（由于假设2，ijc独立于ijx的取值，故此目标函数是一线性函数）。为求得使c达最小的ijx，构造了如下的线性规划模型：mincx11,1,2,...nijjxin11,1,2,...,nijixjn01ijx或此模型是一个运输问题的特例----指派模型，其中c=111212122212(,,...,,,,...,...,,,...,)nnnnnnccccccccc为一行向量。111212122212x=(,,...,,,,...,...,,,...,)nnnnnnxxxxxxxxx为一列向量，为转置符号。对于分派问题，已有专门为此种特殊结构而设计的有效的解题算法，它被称为Graver—Thrallprimal算法。对于1个随机产生的具有16个变量的分派问题，最多只须2.9秒即可完成求解，而使用现代的计算机，对任意适当个变量的指派问题，只须不到一秒钟即可求得解。同时，由于模型中费用系数阵（1）须要经过量化，而他们可由下一段四中的公式求得。并由数据库中的数据进行计算，这一量化模型的过程须要另一个不到一秒钟。因此整个模型的建立与求解所用时间是以秒为数量级的，故当机场控制塔在面临一串连珠炮一样的起飞请求时都可几乎立即对排序作出响应。而飞机的起飞间隔远不是以秒为数量级的。一般至少几分钟，因此模型是可行的。更重要的是。在设有意外发生的情况下，还可利用机场的原有时间表，由数据库事先安排好起飞顺序，并让飞机安排起飞顺序起飞，而唯一需要重新安排的情况仅仅发生在有飞机晚点或紧急的情况，而这时的运算也会在一秒钟左右解决问题。而且由假设（3），也不会因改变而产生临时的拥挤情况。四、模型中费用系数阵的量化由于（1）中的Cij是第i架飞机从第j个时间段上起飞的费用，它与一架航班的型号及运行费用和其上载客情况和他们的满意程度有关，为简化运算，把基本运行费设置为费用零点，而只考虑由于飞机延迟起飞而引起的费用。这一费用包括由于晚点而不再以最经济的速度而是以较快或最快速度飞行带来的燃料损失；及乘客因耽误下站转机而重新安排旅途的损失；以及顾客因各种延迟带来的不愉快而转化的损失。将这三者分别归入费用计算并简记为：费用:1.燃料附加费2.乘客误机费3.乘客不满意的损失下面分别建立几个费用的计算公式1.燃料附加费由于晚点，飞机必须以尽可能快的速度飞行，故燃料随晚点的时间长短而变化，然而既使晚点，只要为达到最大时限，就可以以低于最大安全速度飞行。并在起飞后就可近似地保持常速，因此燃料消耗在时间内应恒定，由于不知道燃料消耗如何随飞行速度变化，选用了近似的线性函数，即单位时间增加油耗的费用函数为：0kttτ0()Ft（＄/单位时间）0kt其中扣除了飞行的一般油耗，只计入增加的油耗，并且式中：t：为飞机晚点的时间；（t=0即为飞机预定起飞的时间）；实际上t作为压缩因子。0k：为晚点单位时间由加速引起的增加油耗的价格，同时0k与不同引擎的飞机有关。又由于飞机蚝油总数还与飞行距离有关，因此总费用应为max0)(vdtF，其中d为飞行距离，它可由d=max()AvT计算，AT为飞机预定到达时间，maxv为最大安全飞行速度，是常数。因此将常数maxv并入0k中，记为0k于是有一架飞机因晚点增加的总费用为：由此公式看出，飞机晚点越久，则耗油越多，直至它在离开时即以最大速度起飞（假设4）。下面为了建模讨论的方便，将上述公式中及以后要用到的一些参数给出一个总表：()AktTt()Ft（5）()AktTt模型参数总表0t：第一个窗口（小时间段）的起始时间；t：飞机晚点时间，或从0t计起，飞机真正起飞时间；:dt为一架飞机预定起飞的时间（d为departure）;AT：为一架飞机预定到达的时间（A为Arrive）;：为等长的时间间隔时间段的长度，也称为起飞窗口；j：为第j个窗口的标号；k：用来决定某飞机单位时间增加燃料费用的常系数，它一般与飞机型号有关；maxv：一种飞机的最大安全飞行速度；avv：一种飞机按时起飞的平均速度，它也与飞机型号有关；（av,acerage）r:用来计算耽误了转机的乘客重新安排旅程的费用；：机上须转乘的人数；:p机上登机的总人数；a：将由晚点而引起的乘客的不满意程度转换成美元的转换系数；b：将由晚点而耽误转机的乘客的愤怒转换成美元的转换系数；a：反映乘客对晚点不满意上升的快慢程度的因子；ijc：第i架飞机在第j个窗口起飞的总费用；于是，0(1)dtttj，这里要求0dtt，因为如果飞机未准备好而令其起飞，则该窗口将不能很好的利用。只有当它的预定时间到时，才可考虑它在第j个（1j）窗口起飞的问题，并计算式（5）中maxAdTv()AdavdTTv2.乘客误机费设为乘客耽误了转机而必须补偿的费用，这里取为常数（假设5）。如果对各人的补偿费确实不同，则取为各人费用的数学期望----平均值，且重新安排旅程只发生在飞机晚点时间超过了时限时才发生，故费用如下计算()()Rtrut（6）：为须转乘的人数；():ut为单位阶跃函数，即00()10tutt由假设5，如果飞机晚点，则所有须转机的个乘客都将将误了转机，若放宽此条件，则()Rt将是一些阶跃函数之和（当相应顾客晚点时，其对应的函数变为1）。3.乘客不满意的损失由于飞机晚点越多，则乘客会越不满意，如果仅晚点一两分钟，则顾客不会太不愿意；但如果晚点到误了转乘班机，则该乘客会顿时变得焦躁不安并且非常愤怒，这一情况可以适当地摘述为一个指数增长函数附加一个阶跃函数，则总的费用函数为：()(1)()atDteaPbut（7）其中,,ab都是常数，且:p为乘客数；：为要转乘的乘客数；：为反映乘客等待时不满意上升快慢的因子；1ate：中（-1）是为了使0t（即飞机准时起飞）时最小的不满意置零的项；,ab：为将相应的不满意转化为美元的系数；():ut为单位阶跃函数，它表达了因误机而顿时产生的不满意。常数,ab一般不相等，这是由于误了转机的乘客一般要只是晚了一会的乘客不满意程度要大得多些。综上所述。则费用系数ijc为由于第i架飞机从第j个窗口起飞时增加燃料、重新安排旅程、和不满意程度而引起的三项费用的总和。在假设3中规定每架飞机从离开自己的通道口到达跑道入口所需要的时间是一样的，这一假定可使得我们置预定时间为0t，并加入计算（5）、（6）、（7）式。如果这条假设放宽，则可令t等于对应飞机所需时间为起点，而取代原式中的0t，即如（5）式中：()AKtT0tt()Ft()AKtTt其中0t为起飞时间，当0tt时，才附加油耗。模型还可以在某种条件下处理降落的请求，但不能同时对起飞和降落都达到最优排序。如果要做到此项，则费用系数ijc将依赖于前面的飞机的排序情况，因此目标函数将不在是线性的了。但是只要将要到达的飞机一准备好降落，就可以准许其降落的话，这模型仍适用，这只要将't；设为飞机将要达到的时间；'：设为一架飞机着陆并最终不再占用跑道所需的时间。由原假设是起飞所需的窗口，则着陆的飞机将于第'0()/jtt个窗口降落，而损失函数ijc对'jj仍不变，只对那些'jj的，须在计算时，在t上附加'、后再计算费用即可。为了防止那些还未准备好的飞机，在就绪之前就对其发出起飞的命令，置一架飞机在它预定起飞时间以前的某窗口起飞的损失为无穷大，并假如考虑1，2，3中的费用，得到计算费用的通式：ttdijc=()(1)atAKTteap0tt()(1)atAKTreapbt这里0(1)dtttjamax()AdvATTvTv1,2,...,,1,2,...,injn由于有上述的统一公式，则原设在0t时刻有n架飞机可扩展到一天有n架飞机要求起飞的情形。模型中的参数,,,dAtTp都可由数据库提供，而事先