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