飞机排队模型.docx
《飞机排队模型.docx》由会员分享，可在线阅读，更多相关《飞机排队模型.docx（13页珍藏版）》请在冰点文库上搜索。
飞机排队模型
飞机排队模型
一.问题的提出
机场通常都是用先到先服务的原则来分配飞机跑道,即当飞机准备好离开登机口时,驾驶员电告地面控制中心,加入等候跑道的队伍。
假设控制中塔可以从快速在线数据库中得到每架飞机的如下信息:
1.预定离开登机口的时间;
2实际离开登机口的时间;
3.机上乘客人数;
4.预定在下一站转机的人数和转机的时间;
5.到达下一站的预定时间;
又设共有七架飞机,载客量从100人起以50人递增,载客最多的一种是400人。
试开发和分析一种能使乘客和各航空公司双方满意的数学模型。
在目前的各国机场,一般都使用先到先服务的排对系统,这一系统虽一直延用,但效率不高,且不能调节意外情况的发生。
将要给出一个利用数据库系统快速排队的模型,以使机场高效的服务,并使航空公司在尽量小的花费情况下,达到顾客满意的目的。
二.模型的基本假设
1.机场上所有要起飞的飞机,都须使用同一条跑道,并且任何一架飞机在起飞的时候都需要完全地占有整条跑道,每架飞机占用的时间一样长的。
2.第i架飞机由第j个时间段上起飞时，其所需费用仅与该飞机i和时间位置j有关，而与它前面是哪架飞机无关。
3.任何飞机从离开自己的通道口到达跑道入口所需的时间假定都一样。
同时为了避免有一大堆飞机挤在跑道入口处等待起飞，这时如有另一架飞机需要紧急起飞，这就须将所有排在前面的飞机挤到一边来腾地方,因此我们假设每架飞机都有立即进入跑道口的通道。
4.设τ是一架飞机要按时到达目的地所必须起飞的最晚时限,并假设如果一架飞机在τ时限以后才起飞,则它必须以最大安全速度飞完全程。
5.如果一架飞机在时限τ以后起飞,则该机上所有需转机的乘客都将误了下次班机,并设给予每位乘客用于赔偿重新安排旅行计划的补偿费用是一样的。
三．模型设计与可行性分析
`如果在某时刻t0仅有一架飞机或没有要求起飞的飞机,则机场就直接安排其起飞或闲置即可。
因此设在t0有n架飞机同时要求起飞。
由假设1，我们可将n架飞机起飞所需的总时间分成n个等长的小时间段。
为此我们设Cij为第i架飞机从第j个小时间段上起飞时所需的一切费用之和，所有可能的排序带来的费用计算有如下的费用矩阵表示：
C11C12…C1n
C21C22…C2n
（1）
C=……………
Cn1Cn2…Cnn
并设Xij=1第架飞机被指定在第j个小时间段窗口起飞
0否则
相应有安排方案矩阵为
x11x12…x1n
x21x22…x2n
X==…………
（2）
xn1xn2…xnn
故矩阵
（2）对应如下排列方案：
窗口飞机
1
2
3
……
n
1
0
1
o
……
0
2
1
0
0
……
0
…
….
….
…..
……
….
n
0
0
0
……
1
即第i架飞机排第2个窗口起飞,第2架排第1个窗口起飞,….,最后一架排最后起飞。
并由上表的安排结构,我们知道
（2）中的矩阵须满足每行中仅有一个元素为1,即每个窗口上仅有飞机一架飞机占用;该阵该列中也仅有一个元素为1,即每架飞机占用n个窗口中的一个。
即变量须满足约束：
∑xij（行和为1）i=1,2,…,n（3）
∑xij（列和为1）j=1,2,…,n
由于xij为取0，1值的变量，因此不同的分派安排对应的仅是xij取1的位置不同而已。
于是设c1为安排第1架飞机的费用c1=c11x11+c12x12+…+c1nx1n
全部飞机安排的费用为z=ΣΣcijxij
即构成我们的目标函数。
为求得使c达最小的xij,构造如下线性规划模型：
mincxn
约束条件∑j=1xij,i=1,2,…,n
n（4）
∑i=1xij,j=1,2,…,n
xij=0或1
其中C’=（C12,C12,…,C1n,C21,C22,…,C2n,…,Cnn）为一行向量。
X=（x11,x12,…,x1n,x21,x22,…,x2n,…,xn1,xn2,…,xnn）’为一列向量，’为转置符号
四．模型中费用系数阵的量化
为简化计算，我们可以把基本运行费用置为费用零点，而只考虑由于飞机延迟起飞而引起的费用。
这一费用包括由于晚点而不在以最经济的速度而是以最快速度飞行带来的燃料损失；及乘客因耽误下站转机而重新安排旅途的损失；及顾客因耽误带来的不愉快而转化的损失。
下面分别建立几个费用的计算公式。
1．燃料附加费
由于晚点，飞机必须以尽可能的速度飞行，故燃料随晚点的时间长短而变化，然而既使晚点，只要未达到最大时限，就都可以以低于最大安全速度飞行。
并在起飞后就可近似地保持常速，因此燃料消耗在单位时间应恒定，由于不知道燃料消耗如何随飞行速度变化，故选用近似的线性函数，即单位时间增加油耗的费用函数
为：
F（t0）=K0tt<τ
K0τt>=τ
其中扣除飞行的一般油耗，只计入增加的油耗，式中：
t:
为飞机晚点的时间；k0为每晚点单位时间由加速引起的增加油耗的价格，同时与不同引擎的飞机有关。
又由于飞机耗油总数还与飞行距离有关，因此总费用为F0（t）.d/vmax,其中d为飞行距离，由d=Vmax（TA-τ）计算，TA为飞机预定到达时间，Vmax为最大安全飞行速度。
因此有一架飞机因晚点增加的费用为：
F（t）=kt（TA-τ）t<τ（5）
kτ（TA-τ）t≥τ
由公式知，飞机晚点越久，则耗油越多，直到它离开时即以最大速度起飞。
为了建模方便，将一些参数给出一个总表：
t0:
第一个窗口的起始时间；
t:
飞机晚点时间，或从计起，飞机真正起飞的时间；
td:
为一架飞机预定起飞的时间；（d为departure）
TA:
为一架飞机预定起飞的时间；（A为Arrival）
Δ:
为等长的起飞间隔时间段的长度，也称为起飞窗口；
j:
为第j个窗口的标号；
k:
用来决定某种飞机单位时间增加燃料费用的常系数，它一般与飞机型号有关；
Vmax:
一种飞机的最大安全飞行速度；
Vav:
一种飞机按时起飞的平均速度，它与飞机型号有关；（average）
r:
用来计算耽误了转机的乘客重新安排旅途的费用；
π:
机上须转乘的人数；
p:
机上登机的总人数；
a:
将由晚点而引起的乘客的不满意程度转换成美元的转换系数；
b:
将由晚点而耽误转机的乘客的愤怒转换成美元的转换系数；
α:
反映乘客对晚点不满意上升的快慢程度的因子；
Cij:
第i架飞机在第j个窗口起飞的确总费用；
于是,t=t0-td+（j-1）Δ,这里要求td只有当它的预定时间到时，才可考虑它在第j个（j≥1）窗口起飞的问题，并计算式（5）中
τ=TA-d/Vmaxd=（TA-Td）Vmax
2.乘客误机费
工为简单起见，设为乘客耽误了转机而须补偿的费用，这里取常数。
如果对各人的补偿费确实不同，则取为各人费用的数学期望——即平均值。
且重新安排旅途只发生在飞机晚点时间超过时限时才发生，故费用如下计算：
R（t）=rπu（t-τ）（6）
这里π为须转乘的人数；
u（t）为单位阶跃函数，即u（t）=1t≤0
1t>0
由假设5，如果飞机晚点，则所有须转机的π个乘客都将误了转机，若放宽此条件，则R（t）将是一些阶跃函数之和。
3.乘客不满意的损失
由于飞机晚点越多，则乘客越不满意，如果仅晚点一两分钟，则顾客不会太不满意；但如果晚点到误了转乘班机，则顾客会顿时变得焦躁不安且非常愤怒，这一情况可以适当地描述为一个指数增长函数附加一个阶跃函数，则总的费用函数为：
D（t）=（exp（αt）-1）aP+bπu（t-τ）（7）
其中α,a,b都是常数，且
P为乘客数；
π为要转乘的乘客数；
α为反映乘客等待时不满意上升快慢的因子；
exp（αt）-1中（-1）是为了使（即飞机准时起飞）时最小的不满意置零的项；
a,b为将相应的不满意转化为美元的系数；
u（t-τ）为单位阶跃函数，它表达了因误转机而顿时产生的不满意.
常数a,b一般不相等，这是由于误了转机的乘客一般要比只是晚了一会的乘客不满意程度要大得多些。
综上所述，则费用系数cij为由于第i架飞机从第j个窗口起飞时增加燃料，重安排旅程和不满意程度而引起的三项费用之和。
在假设3中规定每架飞机从离开自己的通道入口所须的时间是一样的，这一假定可使得我们置预定起飞时间为t=0，并加入计算（5），（6），（7）式。
如果这条假设放宽，则令t等于对应飞机所需时间为起点，而取代原式中的t=o,即（5）式中F（t）=Kt（TA-τ）t0≤t<τ
Kτ（TA-τ）t≥τ
其中为起飞时间，当t≥t0时，才附加油耗。
同时我们的模型还可以在某种条件下处理降落的请求，但不能同时对起飞和降落都达到最优排序。
如果要做到此项，则费用系数cij将依赖于前面飞机的排序情况，因此目标函数将不再是线性的了。
但是如果只要将要到达的飞机一准备好降落，就可以准许其降落，这时模型任适用，这只要将t’设为飞机将要到达的时间；
Δ’设为一架飞机着陆并最终不再占用跑道所需的时间。
由原假设Δ是起飞所须的窗口，则着陆的飞机将于第j=（t’-t0）/Δ个窗口降落，而损失函数cij对jj’的，须在计算时，在t上附加Δ’后再计算费用即可。
最后，为了防止那些还未准备好的飞机，在就绪之前就对其发出起飞的命令，我们置一架飞机在它预定起飞时间之前的某窗口起飞的损失为无穷大，并加入考虑不周，2，3中的费用，得到计算费用的通式：
cij=∞tK（TA-τ）t+（exp（αt）-1）apt0≤t<τ
K（TA-τ）t+（exp（αt）-1）ap+rπ+bπt≥τ（8）
这里t=t0-td+（j-1）Δτ=TA-（TA-Td）Vav/Vmax
I=1,2,…,nj=1,2,…,n
由于有统一公式，则原设在t0时刻有n架飞机可扩展到一天中有n架飞机要求起飞的情形。
模型中的参数td,TA,π和P都由数据库提供，而事先给定的参数为Δ,K,Vav,Vmax和r及变量t都容易得计算出来。
t0可由计算机系统时钟提供。
而三个参数α,a和b可由飞机以往记录和惯例估算出来。
4．排队模型小结
1）对每架飞机都有一个起点td，终点TA，t0为凌晨12:
01，则代入公式cij可求得它在第j个窗口起飞时的费用；
2）求解线性规划模型的最优解，则可确定哪架在什么时刻起飞；
3）当有特殊情况发生后，则重新置剩下的飞机为I=1,2,…,n，起点为当时的时刻，将剩余飞机重排后求最求解，然后按顺序起飞。
在正常运行情况下，上述小结中1），2）步骤仅须做一次即可按部就班地运行，只有当意外发生时才启用3）部分。
五．模型检验
下面先进行的是变动其中参数的检验，即在参数受到扰动的情况下模型是否稳定的检验，如果这个模型中一个或几个参数有轻微的偏离值，而模型结果不致有太大的偏离最优解，则可认为模型是稳定的。
另外，如果参数的微小变化会带来模型的剧烈变化，则希望确定哪个参数更敏感。
虽然利用分派模型对求解很有效，但在作敏感性分析时却不在适应。
因为在进行敏感性分析时，变量的限制xij=0,1将不利于分析扰动情况，为此须利用分派模型是运输模型的特例的事实，并将xij=0,1的限制换成取一组非负整数的限制，即约束条件化为己有xij≥0,并利用运输模型是一类线性规划模型的事实，即可用单纯形法取解。
下面将分派模型（4）表为运输模型：
min∑∑cijxij
约束条件:
∑xij=1j=1,ni=1,2,…,n（9）
∑xij=1i=1,nj=1,2,…,n
xij≥0I=1,2,…,nj=1,2,…,n
由运输模型的有关理论[4][5]知：
运输问题有可行解，并且对（9）这样的运输模型一定有一个最优解且此最优解的所有分量都取整数值。
又注意到约束条件（9）的限制，则可能的整数解一定非0即1，因此运输问题等价于原问题（4）。
将（9）式由目标函数的向量形式表出：
minC’X
约束AX=b（10）
X≥0
其中b的所有分量都为1,A的元素为０或１，对应于约束（９）中的等式，可利用线性规划模型的结果来检验参数的敏感性了。
显然A和b的元素只有０和１，对给定了飞机数目后是相对固定的，因此参数所产生的变化只影响向量C’，假设得到一个最优解x，并假定已解决了其对偶问题：
maxb’y
约束条件A’y≤c（11）
其中为y列向量，维数与A阵的行数相同，A,b,C阵都如（１０）式，由对偶定理［４］——［７］知：
若原问题（１０）或对偶问题存在有限最幼解，则另一个亦有有限最优解，且有minC’x=maxb’y，现在给C’一个增量ΔC，则记C1=C+ΔC，将代入（１０）和（１１）式，看其对原模型带来何影响，由（１０）式中的约束Ax=b,x>=0，知其未受C1的影响，故原最优解x仍是原问题的一个可行解，但它有可能不再是最优解了。
而保持x仍是最优解的充要条件，由对偶定理的证明过程及单纯形法的基本定理可知，为:
A’y<=C1，即-ΔC<=C-A’y,此式可作为判断原解在扰动下是否仍保持最优的判别条件，但当上述条件不满足时，x不再是最优解，此时目标函数的新值为Z=C’x=（C+ΔC）X=C’X+（ΔC）’X=minZ+（ΔC）’X
即Z的变化是关于ΔC的线性函数，因此只要C的分量变化很小，则分派问题的不确定性也将很小。
由于是C费用系数向量，由它的计算公式（５）——（８）即可看出它的不确定性来自两个方面。
一个方面是来自实际参数的准确程度，对于航空公司来说应该是一个确切的已知量；而另一方面来自与乘客不满意的费用有关的参数，如三参数a,b,α，而模型的主要误差将来源于此三者，并且解对α最敏感，因为α是在指数部分，下面来决定这三个心理参数是如何来影响变化的。
假设得到了相应的a,b,α的估计即相关联的不确定性（扰动方差）：
â±б,b±б,α±б,
其中â表示a的估计，可由统计方面的顾问来决定，他可经过飞行情况数据的研究即顾客的不满意在长期运营中实际为顾客赔偿的损失中估计，б表示估计与真值的误差方差，余者类似。
则将（８）式中的Cij分别对a,b,α求偏导得：
dCij/da=（exp（at）-1）P,dCij/db=π,dCij/dα=texp（αt）aP
则Cij由a,b,α引起的不稳定性变化，可由全增量公式近似表示：
Δcij=dCij/daΔa+dCij/dbΔb+dCij/dαΔα
并可进一步假设各参数的变动之间相互独立，因此由独立和的方差公式［８］有Cij的方差为：
σ2cij=σa2
同理，对有dz/dCij=xij
故的方差可由下式给出：
因此代入a,b,α及σ2等数据，则可算出σ2的值，为了达到要求的，还可进一步对各参数的精度加以要求，但通过求出σ2即可以对模型在随机扰动下的不稳定性的方差有所估计了。
六．计算机模拟模型
为了了解模型运行的良好性，以及本模型的特点，用下述几个计算模拟例子来进行演示。
其中用到了单纯形法求解算法［６］［７］及专门的软化包及子程序。
为了编程简单并说明问题，必须在原有的基本假定基础上，再添加如下具体假定：
１．在每一窗口至多有三架飞机已准备好可以起飞，当仅有两架飞机准备好的情况发生时，可加入一个虚设变量，以其对应的费用系数都为０即可．
２．凭直观给模型指定了参数值，在实际中，这些值应该通过实验或调查获得：
（１）每一个起飞窗口为一分钟长，即任何飞机起飞需要至多一分钟，而且其它飞机不准在这一分钟里占用跑道；
（２）设有飞机降落情况；
（3）误转机的陪偿费为每人$350;
（4）误了转机的乘客愤怒程度等价于被耽误了15分钟的乘客的愤怒的两倍。
例1．（具有使最多乘客的飞机先走的功能）
考虑在早晨6：
00，三架飞机同时要求起飞,设它们的型号相同，有距此机场相同距离的终点机场，（但可能飞往不同城市的机场）。
设三架飞机为。
并且它们都预定在场：
20到达终点，但飞机上有350名乘客；飞机上有100名；上有400名。
且每架飞机上都有100名乘客要求转机，计算结果见下表。
具有最多乘客的飞机先走的功能演示
飞机
乘客
费用矩阵C
最优解矩阵X
A
350
0.000.480.97
010
B
100
0.000.410.83
001
C
400
0.000.501.00
100
最低费用Zmin=1.31，最优解矩阵C表明，A,B是最优排列，这与常识相符。
由于其它条件设定一样，故最优的安排是让乘客多者先走。
例2（具有使晚点最久者先走的功能）
当飞机C准备离开之际，飞机D要求紧急起飞。
飞机D已经晚点18分钟，它若想按时在7：
06分到达终点，就必须在2分钟里起飞。
其上有200名乘客，150人要求转机，下表给出结果。
一飞机已晚点很久的结果（表中第二列为：
机上人数/转乘人数）
飞机
乘客
晚点
费用系数阵C
最优解
D
210/150
18min
0.820.921.00
100
B
100/100
1min
0.070.150.22
001
A
350/100
1min
0.090.170.26
010
最低费用为Zmin=1.22,最优起飞顺序为D,A,B,与直观吻合:
即晚点很久者应优先走,否则航空公司就须付误机费了。
标准化了的费用阵C表明飞机D的花费很大。
而另外两个却相对很小。
例3（具有按情况决定先后的功能）
假设又过了两分钟，这时D和A已走，剩下B已经晚点3分钟，而另一架飞机E在此刻要求起飞。
设E有如下条件：
（1）按时准备就绪；
（2）在可按时到达终点（7：
42）之前，还富余42分钟可以闲置；
（3）机上有122名乘客，89人要求转机；
（4）晚点增加的费用为每分钟$450。
必须如所设引入一个虚拟变量，飞机X，这一飞机的一切费用系数都为0，得到结果如下：
按情况决定排序
飞机
乘客
晚点时间
费用矩阵
最优解
B
100/100
3min
0.600.801.00
010
E
122/89
0min
0.000.280.56
100
X
0/0
0min
0.000.001.00
001
在直观上不明显谁先走，事实上，似乎应让B先走，但可能由于E在高速飞行时增加的费用太昂贵及机上乘客数的缘故，使模型选定让E先走。
七．总结
我们的模型有易实施的特点，可结合于数据库中使用。
它对数目很大的机场，任意可装载的乘客数及须转机的乘客数，都可实现快速最优排序，并可处理同时要求起飞的请求，照顾晚点很久的先走功能，及可对不同型号和不同油耗的飞机进行适当的考虑。
模型很稳定，因此对它的良好运行报有信心，因为既使某些参数偏离了真值，它们对总的费用造成的偏离也不过是参数偏离的线性函数（正比例函数）。
模型中的三个参数a,b,α虽不太容易精确度量真值，但是可以通过实验近似估计到。
模型虽不能对起和降落同时达到优化，但却可达到在起飞的间隙中安排降落。
同时可以确信此模型是既可达到使航空公司节省费用，又可达到使顾客满意的理想模型。
升级会员 