-
摘要: 分析了飞机和机组运行计划的特点与异同, 以最小化恢复总成本为目标函数, 以飞机、航班、机组和机场的时空衔接、流平衡等为约束条件, 建立了飞机和机组一体化恢复的约束规划模型。针对一体化恢复问题的特点和模型结构, 利用混合集合规划方法设计搜索算法, 并进行了实例验证。计算结果表明: 对小规模问题, 约束规划模型与分阶段恢复方法得到的结果一致, 延误均为6 020 min; 对中大规模问题, 约束规划模型与分阶段恢复方法求得的延误分别为9 670 min和12 840 min, 约束规划模型比分阶段恢复方法减少约24.69%的延误; 分阶段恢复方法在约22.2%的情况下无法求得可行解。可见, 约束规划模型可行。Abstract: The features and differences of running schedules for aircraft and crew were analyzed. The mininum total recovery cost was taken as objective function, the spatial-temporal connection and flow balance of aircraft, flight, crew and airport were considered as constraint conditions, and the constraint programming model of integrated recovery for aircraft and crew was built. Aiming at the characteristics of integrated recovery problem and model structure, the searching algorithm was designed by using mixed set programming method, and example verification was carried out. Calculation result indicates that for small scale example, the results obtained by the proposed model and sequential recovery method are same, and the delay is 6 020 min. For medium and large scale examples, the delays obtained by the proposed model and sequential recovery method are 9 670, 12 840 min respectively, and the delay obtained by the proposed model reduces by 24.69% compared with the result of sequential recovery method. By using sequential recovery method, 22.2% examples can not obtain feasible solution. So the proposed model is feasible.
-
表 1 算例1的航班计划
Table 1. Flight schedules of example 1
航班编号 起飞机场 降落机场 起飞时间 降落时间 飞机编号 机组编号 101 上海虹桥 成都 08:20 11:40 1 1 102 成都 上海虹桥 12:30 15:10 1 1 103 上海虹桥 三亚 17:05 20:00 1 2 104 三亚 上海虹桥 21:05 23:50 1 2 105 上海虹桥 台北 09:20 11:00 2 3 106 台北 上海虹桥 12:00 13:30 2 3 107 上海虹桥 哈尔滨 14:25 17:05 2 3 108 哈尔滨 上海虹桥 18:00 20:40 2 3 109 上海虹桥 济南 21:30 22:25 2 3 
下载: 导出CSV
表 2 算例1计算结果
Table 2. Calculation results of example 1
航班编号 飞机编号 机组编号 起飞时间 降落时间 101 1 1 08:20 11:40 102 1 1 12:30 15:10 103 1 2 17:05 20:00 104 1 2 21:05 23:50 105 2 2 11:10 12:50 106 2 3 13:40 15:10 107 2 3 16:00 18:40 108 2 3 19:30 22:10 109 2 4 23:00 23:55
下载: 导出CSV
表 3 算例2的航班计划
Table 3. Flight schedules of example 2
航班编号 起飞机场 降落机场 起飞时间 降落时间 飞机编号 机组编号 201 南京 首尔 08:15 10:15 3 5 202 首尔 盐城 11:15 13:00 3 5 203 盐城 首尔 13:40 15:10 3 5 204 首尔 南京 16:10 17:50 3 5 205 南京 广州 19:00 20:50 3 6 206 广州 南京 21:55 23:55 3 6 207 南京 厦门 08:00 09:40 4 7 208 厦门 南京 10:30 12:10 4 7 209 南京 西安 13:00 14:55 4 6 210 西安 南京 15:55 17:35 4 6 211 南京 北京 19:55 21:25 4 8 212 北京 南京 22:15 23:45 4 8
下载: 导出CSV
表 4 算例2计算结果
Table 4. Calculation results of example 2
航班编号 飞机编号 机组编号 起飞时间 降落时间 201 3 5 15:00 17:00 202 3 5 17:40 19:25 203 3 5 20:05 21:35 204 3 8 22:15 23:55 205 取消 206 取消 207 4 7 15:00 16:40 208 4 7 17:20 19:00 209 4 6 19:40 21:35 210 4 6 22:15 23:55 211 取消 212 取消
下载: 导出CSV
表 5 九个算例比较
Table 5. Comparison of nine examples
算例编号 飞机数量 日航班数量 机组数量 飞机与机场故障数量 3 2 12 4 1 4 3 20 6 3 5 4 26 8 3 6 5 32 11 3 7 6 36 13 3 8 7 40 14 2 9 8 46 16 3 10 9 54 18 3 11 10 62 18 3
下载: 导出CSV
表 6 两种计算结果对比
Table 6. Comparison of two calculation results
算例编号 方法 取消航班数量 延误航班数量 加机组数量 延误/min 3 S 0 5 0 1 220 I 0 5 0 1 220 4 S 0 11 0 2 680 I 0 11 0 2 680 5 S 4 0 0 2 120 I 4 0 0 2 120 6 S 无可行解 I 2 7 0 2 235 7 S 2 8 2 3 665 I 0 9 0 2 075 8 S 0 12 0 2 525 I 0 7 0 1 350 9 S 0 19 0 3 415 I 2 14 0 3 025 10 S 0 19 0 3 235 I 2 16 0 3 220 11 S 无可行解 I 4 22 4 4 500
下载: 导出CSV
-
[1] ABDELGHANY K F, ABDELGHANY A F, EKOLLU G. An integrated decision support tool for airlines schedule recovery during irregular operations[J]. European Journal of Operational Research, 2008, 185(2): 825-848. doi: 10.1016/j.ejor.2006.12.045 [2] 白凤. 不正常航班的飞机和机组调度研究[D]. 南京: 南京航空航天大学, 2010.BAI Feng. Research on aircraft and crew rescheduling problems of irregular flight[D]. Nanjing: Nanjing University of Aeronautics and Astronautics, 2010. (in Chinese). [3] TEODOROVIC D, GUBERINIC S. Optimal dispatching strategy on an airline network after a schedule perturbation[J]. European Journal of Operational Research, 1984, 15(2): 178-182. doi: 10.1016/0377-2217(84)90207-8 [4] TEODOROVIC D, STOJKOVIC G. Model for operational daily airline scheduling[J]. Transportation Planning and Technology, 1990, 14(4): 273-285. doi: 10.1080/03081069008717431 [5] JARRAH A I Z, YU Gang, KRISHNAMURTHY N, et al. A decision support framework for airline flight cancellations and delays[J]. Transportation Science, 1993, 27(3): 266-280. doi: 10.1287/trsc.27.3.266 [6] YAN Shang-yao, YANG D H. A decision support framework for handling schedule perturbation[J]. Transportation Research Part B: Methodological, 1996, 30(6): 405-419. doi: 10.1016/0191-2615(96)00013-6 [7] ARGUELLO M F, BARD J F, YU Gang. A GRASP for aircraft routing in response to groundings and delays[J]. Journal of Combinatorial Optimization, 1997, 1(3): 211-228. doi: 10.1023/A:1009772208981 [8] 唐小卫, 高强, 朱金福. 不正常航班恢复模型的贪婪模拟退火算法研究[J]. 预测, 2010, 29(1): 66-70. https://www.cnki.com.cn/Article/CJFDTOTAL-YUCE201001010.htmTANG Xiao-wei, GAO Qiang, ZHU Jin-fu. Research on greedy simulated annealing algorithm of irregular flight schedule recovery model[J]. Forecasting, 2010, 29(1): 66-70. (in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-YUCE201001010.htm [9] WEI Guo, YU Gang, SONG M. Optimization model and algorithm for crew management during airline irregular operations[J]. Journal of Combinatorial Optimization, 1997, 1(3): 305-321. doi: 10.1023/A:1009780410798 [10] STOJKOVIC M, SOUMIS F, DESROSIERS J. The operational airline crew scheduling problem[J]. Transportation Science, 1998, 32(3): 232-245. doi: 10.1287/trsc.32.3.232 [11] LETTOVSKY L, JOHNSON E L, NEMHAUSER G L. Airline crew recovery[J]. Transportation Science, 2000, 34(4): 337-348. doi: 10.1287/trsc.34.4.337.12316 [12] TEODOROVIC D, STOJKOVIC G. Model to reduce airline schedule disturbances[J]. Journal of Transportation Engineering, 1995, 121(4): 324-331. doi: 10.1061/(ASCE)0733-947X(1995)121:4(324) [13] 刘德刚. 航空公司实时飞机和机组调配问题的研究[D]. 北京: 中国科学院, 2002.LIU De-gang. Aircraft rerouting and crew pairing repair during airline irregular operations[D]. Beijing: Chinese Academy of Sciences, 2002. (in Chinese). [14] 朱博, 朱金福. 飞机计划恢复的混合集合规划方法研究[J]. 小型微型计算机系统, 2012, 33(11): 2556-2560. https://www.cnki.com.cn/Article/CJFDTOTAL-XXWX201211051.htmZHU Bo, ZHU Jin-fu. Research on mixed set programming for aircraft schedule recovery[J]. Journal of Chinese Computer Systems, 2012, 33(11): 2556-2560. (in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-XXWX201211051.htm [15] VAN HENTENRYCK P, SIMONIS H, DINCBAS M. Constraint satisfaction using constraint logic programming[J]. Artificial Intelligence, 1992, 58(1/2/3): 113-159. [16] HOOKER J N. Logic, optimization and constraint programming[J]. INFORMS Journal on Computing Fall, 2002, 14(4): 295-321. doi: 10.1287/ijoc.14.4.295.2828 [17] 霍佳震, 王新华. 基于约束规划求解车辆调度问题[J]. 物流技术, 2005, 24(1): 110-112. https://www.cnki.com.cn/Article/CJFDTOTAL-WLJS200509037.htmHUO Jia-zhen, WANG Xin-hua. Solving vehicle scheduling problem based on constraint programming[J]. Logistics Technology, 2005, 24(1): 110-112. (in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-WLJS200509037.htm [18] ZHOU Jian-yang. A note on mixed set programming[C]//IEEE. The 7th International Symposium on Operations Research and Its Applications. Zhangjiajie: IEEE, 2008: 131-140. [19] ZHOU Jian-yang. Introduction to the constraint language NCL[J]. The Journal of Logic Programming, 2000, 45(1/2/3): 71-103. -
点击查看大图
图(1) / 表(6)
计量
- 文章访问数: 803
- HTML全文浏览量: 84
- PDF下载量: 1040
- 被引次数: 0
