航班调度问题

第1页共5页《数学模型》课程设计报告书数理科学与工程学院2015年6月30日姓名***专业***班级***学号****指导教师****第2页共5页1.问题重述航班着陆调度（具有时间窗口的调度问题）在大型机场中，飞机的降落要受到很多安全约束条件的限制。本节中将研究如何对单条跑道上的飞机降落进行调度。已经有人研究了更一般的问题，但这些问题相当复杂（动态案例，例如航班晚点，同时有多条跑道，等等），因此我们只讨论一个简单的情形。有十个航班需要降落。每个航班都有一个最早到达时间（飞机以最高速度到达降落区域的时间）和最晚到达时间（可能受其他因素如燃油量等的影响）。在这个时间窗口内，航空公司需要选择一个目标时间，并将它作为航班到达时间公布出去。如果比此目标时间迟到或早到，则可能会引起机场秩序混乱并带来额外的费用支出。为将这些费用计入考虑，并方便进行比对，每个航班都定义了早到每分钟的惩罚和晚到每分钟的惩罚。下表列出了每个航班的时间窗口（以从当天零时起分钟数计）和惩罚值。表格11.4：航班时间窗口等信息飞机12345678910最早到达1291958996110120124126135160目标时间15525898106123135138140150180最晚到达559744510521555576577573591657早到惩罚10103030303030303030晚到惩罚10103030303030303030由于尾流影响以及飞机停留在跑道上的时间影响，在两次降落之间需要间隔一段安全时间。在表11.5中第p行第q列即表示在航班p和q降落之间需要等待的最短时间（分钟），即便这两个航班实际上不是连续降落的。应采取何种降落调度方案才能够在使总惩罚最小，同时航班又都在指定的时间窗口中降落，并且满足两个航班降落之间的时间间隔？表格11.5：相邻降落之间的间隔时间矩阵123456789101-3151515151515151523-151515151515151531515-8888888415158-8888885151588-8888861515888-8888715158888-8888151588888-8891515888888-81015158888888-2.问题分析为了防止空中交通拥挤，修改航班的降落时间，延长或减少航班进场飞行时间，使降落航班更快速有序进入机场着陆。实际操作中，由于缺乏有效的辅助决策工具，通常以先来先服务为基本原则进行排序。这个问题只考虑单跑道的飞机降落调度。飞机以最高速度到达降落的时间和受到影响而迟些到达的时间分别可为最第3页共5页早和最晚到达时间，航空公司必须在时间窗口内选择一个目标时间公布出去，由于航班早到和晚到都会带来额外支出费用，所以该问题可以简化为怎样使得额外支出最小并且各航班都按时到达的问题。3.符号说明early(i)第i个航班的最早到达时间late(i)第i个航班的最晚到达时间on(i)第i个航班的目标到达时间fine(i)第i个航班的早到或晚到惩罚因子d(i,j)航班i和j降落之间需要等待的最短时间x(i)设第i个航班的降落时间为X(i)4.模型假设a.假设飞机最早和最晚到达时间的准确性较高；b.假设此实验的数据是科学合理的；c.假设飞机在空中不会出现问题且随时与航空公司保持联络；d.假设只考虑飞机实际到达时间和目标时间的差值带来的额外支出费用。5.模型建立由问题中所给数据可得出目标函数表达式为：101))()((*)(iionixabsifineM目标函数表示航空公司支付最少费用。问题的目标是所有航班都在指定的时间窗口中降落，并且满足两个航班降落之间的时间间隔的情况下，采取最优的降落调度方案，使总惩罚最小。由于早到和晚到的惩罚因子相同，因此不用区分早到和晚到的情况，可将每个航班的到达时间和目标时间的时间差用绝对值表示。所以总惩罚就是将10个航班的惩罚加起来，而每个航班的惩罚为的该航班的惩罚因子乘以其时间差。目标函数即由此得出。从表中数据可得出满足表达式的约束条件：1）每个航班具有最早到达时间和最晚到达时间，因此可以确定该问题的决策变量为每个航班的降落时间，由模型假设可知第i个航班的降落时间X(i)应满足early(i)≤x(i)≤late(i),即航班降落时间在最早和最晚到达时间之内。2）航班1与航班2时间的安全降落时间间隔：|x(1)-x(2)|=3；3)航班1与航班i的安全降落时间间隔：|x(1)-x(i)|=15,(i=3,4...10)；4)航班2与航班i的安全降落时间间隔：|x(2)-x(i)|=15,(i=3,4...10)；5)航班i与航班j的安全降落时间间隔|x(i)-x(j)|=8,(i!=j,i=3,4...10,j=3,4...10)；6)要限制飞机的降落时间为整数；6.模型求解模型的求解使用lingo软件使用lingo的全局求解，结果为第4页共5页航班123456789、10航班降落时间16525898106118126134142150180165,258,98,106,118,126,134,所以在满足的条件内10个航班的最佳降落时间分别为142,150,180，最少的总罚款为M=700，为全局最优！7.结论解析与分析从结果可以看出总惩罚值M还是比较小的，航班1的降落时间与目标时间相差10分钟，是为了让航班9和10在目标时间降落，因为9和10的惩罚值比较大。航班3、4，航班5、6、7、8、9、之间的降落时间刚好都相差8，并且每个降落时间与目标时间相近，有的相同。这样也是减少与目标时间的差值来减少惩罚值。8.模型的优缺点模型的优点：时间利用率高，航班调整力度小，排序结果符合实际管制情况，可操作性强。运用线性规划和线性拟合的方法解决了总罚款最少的问题模型的缺点：考虑的方面有很大的局限性，可能与实际情况出入比较大。模型忽略了很多的影响航班降落的偶然因素，建立的条件比较理想，意义有限。9.模型的推广与应用在交通运输业中，除了航班降落调度，还有列车等的运输调度。类似于航班，列车也会受到很多偶然因素的影响。可以根据具体修改参数以及约束条件可以根据此模型进行最优的安排。得到结果后，可以拿来作为班次出发以及达到的时间的参考。如果班次出发到达的时间不理想可以根据实际来修改约束条件，以及其他数据，来进一步优化交通运输的班次问题。10.参考文献《数学模型》第四版，姜启源，谢金星，叶俊，编。附录：model:sets:plane/1..10/:x,early,on,late,fine;link(plane,plane):d;endsetsdata:early=1291958996110120124126135160;!最早到达时间;on=155,258,98,106,123,135,138,140,150,180;!目标时间;late=559,744,510,521,555,576,577,573,591,657;!最晚到达时间;fine=10,10,30,30,30,30,30,30,30,30;!迟到或早到每分钟罚金;!相邻降落飞机之间的最短时间矩阵;d=031515151515151515301515151515151515151508888888第5页共5页151580888888151588088888151588808888151588880888151588888088151588888808151588888880;enddatamin=@sum(plane:fine*@abs(x-on));!目标函数;@for(plane(i):x(i)=late(i));!降落时间不能大于最迟降落时间;@for(plane(i):x(i)=early(i));!降落时间不能小于最早降落时间;@for(link(i,j)|i#ne#j:@abs(x(i)-x(j))=d(i,j));!保证两个飞机的降落间隔不小于最小间隔时间;@for(plane:@gin(x));!限制飞机降落时间为整数;end