问题一 航班降落调度研究.docx

问题一 航班降落调度 摘要随着社会的发展，现在的交通运输也日益发达，这对于人类的意义十分重大。但是中国由于人口众多，对于交通运输的要求非常高，就算是如今的技术也无法完美地解决。因此，为了缓解交通运输压力，我们必须提高交通运输的效率。交通运输的效率对很多行业都有很众多的影响，这是当前迫在眉睫需要解决的问题。本文研究的是目前交通运输业经常会遇到且影响颇大的问题：飞机运输问题。本文主要针对现在空中运输经常出现的航班延误问题，对航班降落调度进行研究。众所周知，飞机运输是目前最快的交通运输方式，但是相比其他交通运输方式而言，它容易受到很多外界因素的影响，如当时的天气等。要让飞机能够正常运行，航班的调度问题是必须要考虑的。本模型以10个航班为研究对象，利用线性规划和线性拟合得到航空公司最少的额外费用支出，建立解决了航班降落的最佳时间而使总惩罚最少。该模型以尽量接近实际管制方法为基础，在确保飞行安全间隔的前提下，充分利用空余时间，在尽量短的时间内，尽可能多安排航班按照合理次序安全降落。模型同时考虑了排序对整个航班序列降落所需时间(累积降落时间)和延误总时间的影响，从而使得时间的分配达到最优化和减少惩罚。 类似地，此模型可以用于长途汽车或列车进站调度，根据最早和最晚进站时间，对汽车和列车进行最优化的调度，从而使运输效率最大化。 1.问题的提出航班降落调度： 在大型机场中，飞机的降落要受到很多安全约束条件的限制，本问题研究如何对单跑道上的飞机降落进行调度。已经有人研究了更一般的问题，但这些问题相当复杂（动态案例，例如航班晚点，同时有多条跑道，等等），因此我们在此只讨论一个简单的情形。有十个航班需要降落。每个航班都有一个最早到达时间（飞机以最高速度到达降落区域的时间）和最晚达到时间（可能受其他因素如染油量等的影响）。在这个是窗口内，航空公司需要选择一个目标时间，并将它作为航班到达时间公布出去。如果比此目标时间迟到或早到，则可能会引起机场秩序混乱并带来额外的费用支出。为将这些费用计入考虑，并方便进行比对，每个航班都定义了早到每分钟的惩罚和晚到每分钟的惩罚。下表列出了每个航班的时间窗口（以从当天零时起分钟数计）和惩罚值。表格1.1 航班时间窗口等信息飞机12345678910最早到达1291958996110120124126135160目标时间15525898106123135138140150180最晚到达559744510521555576577573591657早到惩罚10103030303030303030晚到惩罚10103030303030303030表格1.2 相邻降落之间的间隔时间矩阵123456789101-315151515151515152-151515151515151531515-8888888415158-8888885151588-8888861515888-888715158888-8888151588888-891515888888-81015158888888-由于尾流影响以及飞机停留在跑道上的时间影响，在两次降落之间需要间隔一段安全时间。在表4.2中第p行第q列即表示在航班p和q降落之间需要等待的最短时间（分钟），即便这两个航班实际上不是连续降落的。应采取何种降落调度方案才能够在使总惩罚最小，同时航班又都在指点的时间窗口中降落，并且满足两个航班降落之间的时间间隔？2.问题分析及简化为了防止空中交通拥挤，修改航班的降落时间，延长或减少航班进场飞行时间，使降落航班更快速有序进入机场着陆。实际操作中，由于缺乏有效的辅助决策工具，通常以先来先服务为基本原则进行排序。这个问题只考虑单跑道的飞机降落调度。飞机以最高速度到达降落的时间和受到影响而迟些到达的时间分别可为最早和最晚到达时间，航空公司必须在时间窗口内选择一个目标时间公布出去，由于航班早到和晚到都会带来额外支出费用，所以该问题可以简化为怎样使得额外支出最小并且各航班都按时到达的问题。3模型假设1） 假设飞机最早和最晚到达时间的准确性较高；2） 假设此实验的数据是科学合理的；3） 假设飞机在空中不会出现问题且随时与航空公司保持联络；4） 假设只考虑飞机实际到达时间和目标时间的差值带来的额外支出费用。符号说明：E(i) 第i个航班的最早到达时间L(i) 第i个航班的最晚到达时间T(i) 第i个航班的目标到达时间F(i) 第i个航班的早到或晚到惩罚因子W(i,j) 航班i和j降落之间需要等待的最短时间M 最优降落调度方案下的总惩罚(即最小惩罚)X(i) 设第i个航班的降落时间为X(i)4.模型的建立由问题中所给数据可得出目标函数表达式为： M=i=110Fi*Xi-T(i)目标函数表示航空公司支付最少费用。问题的目标是所有航班都在指定的时间窗口中降落，并且满足两个航班降落之间的时间间隔的情况下，采取最优的降落调度方案，使总惩罚最小。由于早到和晚到的惩罚因子相同，因此不用区分早到和晚到的情况，可将每个航班的到达时间和目标时间的时间差用绝对值表示。所以总惩罚就是将10个航班的惩罚加起来，而每个航班的惩罚为的该航班的惩罚因子乘以其时间差。目标函数即由此得出。从表中数据可得出满足表达式的约束条件：1） 每个航班具有最早到达时间和最晚到达时间，因此可以确定该问题的决策变量为每个航班的降落时间，由模型假设可知第i个航班的降落时间X(i)应满足E(i) X(i)L(i),即航班降落时间在最早和最晚到达时间之内。2） 航班1与航班2时间的安全降落时间间隔： X1-X23;3)航班1与航班i的安全降落时间间隔： X1-Xi15;4)航班2与航班i的安全降落时间间隔： X2-Xi15;5)航班i与航班i+1的安全降落时间间隔： Xi-X(i+1)8(i=310)5.模型的求解模型的求解使用lingo软件得出lingo的模型如下：sets:plane/1.10/:X,F,E,L,T;link(plane,plane):W,y;endsetsdata:E=129 195 89 96 110 120 124 126 135 160;!最早到达时间;L=559 744 510 521 555 576 577 573 591 657;!最晚到达时间;T=155 258 98 106 123 135 138 140 150 180;!目标时间;F=10 10 30 30 30 30 30 30 30 30;!罚金;!相邻降落之间的间隔时间矩阵;W= 031515151515151515!1;301515151515151515!2;151508888888!3;151580888888!4;151588088888!5;151588808888!6;151588880888!7;151588888088!8;151588888808!9;151588888880;!10;enddatamin=sum(plane:F*abs(X-T);!目标函数;for(plane(i):bnd(E(i),X(i),L(i);!最早降落时间和最迟降落时间限制;for(link(i,j)|i#ne#j:y(i,j)=if(x(i)#le# x(j),1,0);!飞机i比飞机j早降落，y（i,j）=1，否则为0;for(link(i,j)|i#ne#j:(y(i,j)+y(j,i)=1);!限制0-1变量y(i,j)+y(j,i)=1;for(link(i,j)|i#ne#j:abs(x(i)-x(j)=W(i,j);!保证相邻飞机降落的时间间隔;for(plane:gin(X);for(link:bin(y);使用lingo求解可得如下结果：Global optimal solution found at iteration:48818Objective value:700.0000VariableValueReduced CostX( 1)165.0000-19.20000X( 2)258.0000-9.844961X( 3)98.000000.000000X( 4)106.0000-57.64343X( 5)118.00000.000000X( 6)134.00000.000000X( 7)126.0000-60.00000X( 8)142.00000.000000X( 9)150.00000.000000X( 10)180.0000-29.33333Y( 1, 1)0.0000000.000000Y( 1, 2)1.0000000.000000Y( 1, 3)0.0000000.000000Y( 1, 4)0.0000000.000000Y( 1, 5)0.0000000.000000Y( 1, 6)0.0000000.000000Y( 1, 7)0.0000000.000000Y( 1, 8)0.0000000.000000Y( 1, 9)0.0000000.000000Y( 1, 10)1.0000000.000000Y( 2, 1)0.0000000.000000Y( 2, 2)0.0000000.000000Y( 2, 3)0.0000000.000000Y( 2, 4)0.0000000.000000Y( 2, 5)0.0000000.000000Y( 2, 6)0.0000000.000000Y( 2, 7)0.0000000.000000Y( 2, 8)0.0000000.000000Y( 2, 9)0.0000000.000000Y( 2, 10)0.0000000.000000Y( 3, 1)1.0000000.000000Y( 3, 2)1.0000000.000000Y( 3, 3)0.0000000.000000Y( 3, 4)1.0000000.000000Y( 3, 5)1.0000000.000000Y( 3, 6)1.0000000.000000Y( 3, 7)1.0000000.000000Y( 3, 8)1.0000000.000000Y( 3, 9)1.0000000.000000Y( 3, 10)1.0000000.000000Y( 4, 1)1.0000000.000000Y( 4, 2)1.0000000.000000Y( 4, 3)0.0000000.000000Y( 4, 4)0.0000000.000000Y( 4, 5)1.0000000.000000Y( 4, 6)1.0000000.000000Y( 4, 7)1.0000000.000000Y( 4, 8)1.0000000.000000Y( 4, 9)1.0000000.000000Y( 4, 10)1.0000000.000000Y( 5, 1)1.0000000.000000Y( 5, 2)1.0000000.000000Y( 5, 3)0.0000000.000000Y( 5, 4)0.0000000.000000Y( 5, 5)0.0000000.000000Y( 5, 6)1.0000000.000000Y( 5, 7)1.0000000.000000Y( 5, 8)1.0000000.000000Y( 5, 9)1.0000000.000000Y( 5, 10)1.0000000.000000Y( 6, 1)1.0000000.000000Y( 6, 2)1.0000000.000000Y( 6, 3)0.0000000.000000Y( 6, 4)0.0000000.000000Y( 6, 5)0.0000000.000000Y( 6, 6)0.0000000.000000Y( 6, 7)0.0000000.000000Y( 6, 8)1.0000000.000000Y( 6, 9)1.0000000.000000Y( 6, 10)1.0000000.000000Y( 7, 1)1.0000000.000000Y( 7, 2)1.0000000.000000Y( 7, 3)0.0000000.000000Y( 7, 4)0.0000000.000000Y( 7, 5)0.0000000.000000Y( 7, 6)1.0000000.000000Y( 7, 7)0.0000000.000000Y( 7, 8)1.0000000.000000Y( 7, 9)1.0000000.000000Y( 7, 10)1.0000000.000000Y( 8, 1)1.0000000.000000Y( 8, 2)1.0000000.000000Y( 8, 3)0.0000000.000000Y( 8, 4)0.0000000.000000Y( 8, 5)0.0000000.000000Y( 8, 6)0.0000000.000000Y( 8, 7)0.0000000.000000Y( 8, 8)0.0000000.000000Y( 8, 9)1.0000000.000000Y( 8, 10)1.0000000.000000Y( 9, 1)1.0000000.000000Y( 9, 2)1.0000000.000000Y( 9, 3)0.0000000.000000Y( 9, 4)0.0000000.000000Y( 9, 5)0.0000000.000000Y( 9, 6)0.0000000.000000Y( 9, 7)0.0000000.000000Y( 9, 8)0.0000000.000000Y( 9, 9)0.0000000.000000Y( 9, 10)1.0000000.000000Y( 10, 1)0.0000000.000000Y( 10, 2)1.0000000.000000Y( 10, 3)0.0000000.000000Y( 10, 4)0.0000000.000000Y( 10, 5)0.0000000.000000Y(