Centralized Scheduling of Service Vehicles for Aircraft Turnaround Based on Partheno-Genetic Algorithm
-
摘要: 针对飞机过站保障车辆集中式调度问题，提出递阶式编码结构单亲遗传算法.该算法采用保障作业编号构成控制基因染色体、车辆编号构成参数基因染色体，分别体现过站保障作业时序约束和车辆指派规则约束，使算法对问题具有良好的适用性；设计控制基因染色体片段段内换位变异和参数基因染色体片段段间换位变异相结合的遗传算子，并引入车辆可调度能力空间概念提出解码算法，实现对解空间搜索能力优化；以过站保障造成的航班延误惩罚费用和车辆行驶费用之和最小为优化目标，建立算法适应度函数，可衡量过站保障和车辆使用综合效率.采集某机场过站航班数据验证所给算法有效性并对比分析车辆就近指派和使用率均衡两种调度策略，结果表明，算法收敛性良好，且就近指派策略相对于使用率均衡策略，在过站保障延误方面改进较小，但在车辆行驶时间方面改进达40%.Abstract: In order to solve the centralized scheduling problem of service vehicles for aircraft turnaround, a partheno-genetic algorithm with hierarchical encoding structure was proposed. The service activity number and vehicle number were employed to encode the control and parametric genes chromosome, respectively, which characterized the temporal and vehicle scheduling rules in turnaround service, ensuring the applicability of algorithm. The crossover and mutation operators were designed, which acted on each control genes chromosome segment and between different parametric genes chromosome segments. The schedulable capacity concept for service vehicle was introduced in chromosome decoding process to optimize search ability of algorithm. The fitness function was established to minimize the penalty of flight delay due to turnaround service and driving distance cost of vehicle, which measured the overall efficiency of turnaround service and vehicle scheduling. The data of aircraft turnaround was used to validate the proposed algorithm, and also the nearest vehicle scheduling strategy and workload balance scheduling strategy were compared. The results indicate that, the convergence of the proposed algorithm is acceptable, and flight delays in these two scheduling strategies are close, while the vehicle driving time is 40% shorter in the nearest vehicle scheduling strategy.
-
Key words:
- aircraft turnaround /
- centralized scheduling /
- partheno-genetic algorithm
-
图 1 飞机过站保障车辆调度过程
Figure 1. Scheduling process of service vehicle for aircraft turnaround
图 2 保障车辆调度的两级递阶式染色体编码结构及示例
Figure 2. Two-level hierarchical chromosome coding structure for service vehicle scheduling and the coding example
图 4 两种策略下的过站保障车辆作业时段甘特图
Figure 4. Gantt chart for service vehicles operation based on two vehicle dispatching strategies
表 1 某机场飞机过站保障作业任务编号、时序约束、耗时及所需车辆类型
Table 1. Task code, temporal constraint, time consumption, and service vehicle for aircraft turnaround in one airport
作业任务编号 任务名称 紧前作业编号 作业耗时/min 作业所需车辆 1 飞机入位 — 0.5 — 2 放轮挡 1 1.0 — 3 机务维护 2 18.0 — 4 廊桥对接 2 2.0 客梯车* 5 开客舱门 4 0.5 — 6 下客 5 6.0 摆渡车*、客梯车* 7 开货舱门 4 2.0 — 8 行李卸载 7 12.0 传送带车 9 污水操作 4 3.0 污水车 10 货邮装载 7 20.0 平台车 11 清水操作 4 3.5 清水车 12 客舱清洁 — 22.0 — 13 餐食配供 1 10.0 餐车 14 航油加注 2 15.0 加油车 15 上客 2 7.0 摆渡车*、客梯车* 16 关货舱门 4 1.5 — 17 关客舱门 5 0.5 — 18 撤廊桥 4 0.5 — 19 撤前轮挡 7 0.5 — 20 牵引车对接 4 1.0 牵引车 21 撤主轮挡 7 1.0 — 22 推出 4 3.0 牵引车 注：“—”表示不需要车辆；“*”表示相应车辆仅在飞机停靠远机位时需要. 
下载: 导出CSV
表 2 某机场飞机过站保障车辆配备规则及车辆总量参照表
Table 2. Scheduling rules and total number of vehicle for aircraft turnaround service in one airport
机型 客梯车 摆渡车 传送带车 污水车 平台车 清水车 餐车 加油车 牵引车 C 1 1 2 1 1 1 1 1 1 D 1 2 1 1 1 1 2 1 1 E 1 3 1 1 2 1 2 1 1 F 1 4 1 1 2 1 4 2 1 某机场各类保障车辆总量 1 1 6 2 6 2 4 5 5
下载: 导出CSV
表 3 飞机过站信息
Table 3. Aircraft turnaround information
航班号 预计入位时间 预计出位时间 飞机类型 停靠机位 机位类型 CA1102/CA1839 08:25 09:15 C 301 近机位 SC4651/SC4652 08:30 09:35 C 310 近机位 SC4851/SC4852 08:35 09:37 C 302 近机位 CA1108/CA9601 08:38 09:38 C 313 近机位 SC1155/SC1158 08:40 09:40 C 304 近机位 CA1606/CA1605 08:42 09:45 C 314 近机位 CA1104/CA1847 08:45 09:50 C 306 近机位 CA1701/CA1702 08:47 09:47 C 316 近机位 CA1662/CA1557 08:49 09:49 C 308 近机位 CA931/CA932 08:51 09:51 C 303 近机位 CA1142/CA1859 08:54 09:45 C 311 近机位 CA1802/CA1649 08:56 09:55 C 305 近机位 CA1951/CA1704 08:59 09:50 C 312 近机位 CA1206/CA1545 09:04 10:00 C 315 近机位 CA1286/CA1591 09:06 10:10 C 307 近机位 CA133/CA1657 09:17 10:30 C 317 近机位 CA1350/CA1623 09:25 10:35 C 301 近机位 CA1640/CA1851 09:40 10:20 C 310 近机位 CA1703/CA1813 09:45 10:26 C 302 近机位 CA1957/CA1712 09:50 10:50 C 313 近机位
下载: 导出CSV
表 4 不同调度策略下的过站保障车辆优化调度结果
Table 4. Optimized scheduling results based on different service vehicle scheduling strategies
飞机架次 过站保障延误/min 车辆行驶时间/min 平均遗传代数/代 平均计算耗时/s MIN_T AVE_L CUR MIN_T AVE_L CUR MIN_T AVE_L MIN_T AVE_L 20 312 331 302 296 495 363 5.0 5.0 11.3 14.2 40 351 377 360 583 988 711 5.3 5.0 15.4 17.3 60 422 451 432 811 1433 1038 5.3 5.3 18.2 22.3 80 483 501 488 1158 1981 1325 5.4 5.6 22.1 29.2 100 521 542 530 1496 2411 1535 5.4 5.7 30.4 34.1 150 610 633 615 2149 3519 2331 5.5 6.2 33.2 38.4 200 699 718 703 2845 4882 2850 5.8 6.4 41.3 45.5
下载: 导出CSV
表 5 不同过站飞机架次下的车辆调度TGA和PGA结果比较
Table 5. Scheduling results comparison between TGA and PGA for different numbers of turnaround aircraft min
算法 各架次过站保障延误 20 40 60 80 100 150 200 TGA 319 362 430 512 552 646 742 PGA 312 351 422 483 521 610 699
下载: 导出CSV
-
丁建立, 赵键涛, 曹卫东.基于贝叶斯网的航班过站时间动态估计[J].南京航空航天大学学报, 2015, 47(4):517-524. http://d.old.wanfangdata.com.cn/Periodical/njhkht201504007DING Jianli, ZHAO Jiantao, CAO Weidong. Dynamic estimtion about turnaround time of flight based on Bayesian network[J]. Journal of Nanjing University of Aeronautics and Astronautics, 2015, 47(4):517-524. http://d.old.wanfangdata.com.cn/Periodical/njhkht201504007 VIDOSAVLJEVIC A, TOSIC V. Modeling of turnaround process using Petri Nets[C]//Proc. of the 14th ATRS World Conference. Porto: EUROCONTROL, 2010: 1-13. https://www.researchgate.net/publication/257866337_Modeling_of_Turnaround_Process_using_Petri_Nets MIQUEL A, ALEXEY N, CESAR T. A simulation model to improve air cargo operations in passenger aircraft[C]//Proc. of the 2010 Summer Computer Simulation Conference. San Diego: IEEE Press, 2010: 446-451. https://www.researchgate.net/publication/221112987_A_simulation_model_to_improve_air_cargo_operations_in_passenger_aircraft FRANCISCO F, MIQUEL E, JENARO N. Use of colored petri nets to model aircraft turnaround at an airport[C]//Proc. of the 6th International Conference on Scientific Computing to Computational Engineering. Athens: [s.n.], 2014: 1-8. 孙瑞山, 张子仝.基于CPM停机坪航班保障工作方法研究[J].中国民航大学学报, 2011, 29(5):23-29. doi: 10.3969/j.issn.1001-5590.2011.05.006SUN Ruishan, ZHANG Zitong. Study on apron flight service work method based on CPM[J]. Journal of Civil Aviation University of China, 2011, 29(5):23-29. doi: 10.3969/j.issn.1001-5590.2011.05.006 NORIN A, GRANBERG A G, YUAN D, et al. Airport logistics-a case study of the turn-around process[J]. Journal of Air Transport Management, 2012, 20(3):31-34. DU J Y, BRUNNER J O, KOLISCH R. Planning towing processes at airport more efficiently[J]. Transportation Research Part E, 2014, 70(1):293-304. http://www.sciencedirect.com/science/article/pii/S136655451400129X CHEUNG A, LP W H, LU D. An aircraft service scheduling model using genetic algorithms[J]. Journal of Manufacturing Technology Management, 2005, 16(1):109-119. doi: 10.1108/17410380510574112 YUQUAN D, QIAN Z. ACO-IH: An improved ant colony optimization algorithm for airport ground service scheduling[C]//Proc. of IEEE International Conference on Industrial Technology. Chengdu: [s.n.], 2008: 1-6. https://www.researchgate.net/publication/224327842_ACO-IH_An_improved_ant_colony_optimization_algorithm_for_Airport_Ground_Service_Scheduling 姚韵, 朱金福, 柏明国.航班过站地面服务的优化调度算法[J].信息与控制, 2007, 36(4):486-492. doi: 10.3969/j.issn.1002-0411.2007.04.016YAO Yun, ZHU Jinfu, BAI Mingguo. An optimization scheduling algorithm for flight turnaround ground service[J]. Information and Control, 2007, 36(4):486-492. doi: 10.3969/j.issn.1002-0411.2007.04.016 苟晶晶.机场规划所需地勤保障车辆最低数量预测[J].中国民航飞行学院学报, 2015, 27(2):50-53. doi: 10.3969/j.issn.1009-4288.2015.02.012GOU Jingjing. Prediction of the minimum requirement of ground vehicles for airport planning[J]. Journal of Civil Aviation Flight University of China, 2015, 27(2):50-53. doi: 10.3969/j.issn.1009-4288.2015.02.012 王芹, 樊玮.飞机地面作业提前/拖期调度研究[J].计算机工程与应用, 2008, 44(10):214-216. doi: 10.3778/j.issn.1002-8331.2008.10.064WANG Qin, FAN Wei. Research on earliness/tardiness scheduling about airplane ground job operation[J]. Computer Engineering and Applications, 2008, 44(10):214-216. doi: 10.3778/j.issn.1002-8331.2008.10.064 樊琳琳.大型机场地勤服务中的车辆调度问题的初步研究[D].沈阳: 东北大学, 2009. http://www.wanfangdata.com.cn/details/detail.do?_type=degree&id=J0066844 VAN LEEUWEN P, LEN OEI L, BUZING P. Adaptive temporal planning at airports[R]. Amsterdam: National Aerospace Laboratory NLR, 2007. https://www.researchgate.net/publication/228962896_Adaptive_temporal_planning_at_airports VAN LEEUWEN P, WITTEVEEN C. Temproal decoupling and determining resource needs of autonomous agents in the airport turnaround process[R]. Amsterdam: National Aerospace Laboratory NLR, 2009. https://www.researchgate.net/publication/221155953_Temporal_Decoupling_and_Determining_Resource_Needs_of_Autonomous_Agents_in_the_Airport_Turnaround_Process -
下载:
点击查看大图
图(6) / 表(5)
计量
- 文章访问数: 392
- HTML全文浏览量: 172
- PDF下载量: 175
- 被引次数: 0