Multi-Stage Optimization Method for Dispatch of Ground-Service Vehicles at the Airports During Peak Flight Period
-
摘要: 在航班运行高峰时段内，地面服务需求更加集中，机场可调度的地勤车辆数量有限，可能引发航班延误，导致机场多方面损失。针对该问题，研究了地勤车辆多阶段优化调度方法，重点考虑摆渡车和加油车2种地勤保障车路由与时间窗口限制，以航班准点率及延误时间为评价指标进行优化调度。构建了具有4类节点和5类弧的容量-费用网络G1，通过设置合适弧容量及费用参数，确定最小费用流规划模型；采用拉格朗日松弛启发式算法对模型求解，通过不断寻优，设置对偶间隙初值、容许误差，最大迭代次数，输出预测结果；深入分析高峰时段的航班运行状态，构建基于时空网络的整数线性规划模型，优化第一阶段未服务航班的总延误时间；结合最小化最大值定理，构建单航班服务延误模型，将单个航班延误造成的损失降到最低。最后，基于实际航班数据，结合机坪平面布局开展仿真实验和验证，结果表明：利用优化调度得到加油车和摆渡车准时服务的最大航班数分别为30，131架?次，待服务航班的最小总延误时间分别为223，542 min，航班总延误下降21.56%，显著缩短航班延误时间，提升了机场场面的整体运行效率。Abstract: During the peak hours of flights, the demand for ground service is more concentrated. Plus, the limited number of available handing vehicles for dispatching at the airport, flights delay occurs, which have caused losses to the airport in many aspects. Aiming at this issue, a multi-stage optimization method for dispatch of ground-services vehicles is proposed, with a focus on considering the routing and time window constraints of shuttle buses and refueling vehicles. The flight punctuality rate and delay time are used as evaluation indexes to dispatch-optimization. A capacity-cost network G1 with four types of nodes and five types of arcs is developed. By setting appropriate arc capacity and cost parameters, the planning model of the minimum cost flow is determined, and Lagrangian relaxation heuristic algorithm is used to solve the problem. Through continuous optimization, the initial value of the dual gap, the allowable error, and the maximum number of iterations are set, and the prediction results are output. The flight operation status during peak hour is deeply analyzed, and an integer linear programming model is proposed based on a time-space network, in which the total delay of unserved flights is optimized in the first stage. Combined with the minimum-maximum theorem, a delay model for a single flight is developed to minimize the loss. Finally, based on the real flight data, simulation experiments and the method validation are carried out combing with the apron layout. The results shown that: ① the maximum number of flights served on-time by refueling and shuttle vehicles are 30 and 131, respectively; ② the minimum total delay of flights to be served are 223 and 542 min, respectively; ③ the total flight delay decreased by 21.56%, significantly shortening the flight delay and improving the overall operational efficiency at the airport.
-
图 6 模型Ⅰ求解加油车、摆渡车调度迭代过程
Figure 6. Model Ⅰ solves the iterative process of fuel truck and ferry scheduling
图 7 多种优化算法求解最小费用流模型的效果对比
Figure 7. Comparison of the effectiveness of various optimizationalgorithms for solving minimum cost flow models
表 1 机场地面保障车辆功能及服务需求
Table 1. Airport ground support vehicle function and service requirements
名称 功能 服务需求 加油车 主要保障出港航班的燃油需求 小型机场采用罐式加油车，单车容量一般不低于20 000 L；大型机场配备管线及适量罐式，各机场最低配备数量应不少于2辆。 摆渡车 远机位进出港旅客的接送 B类及以下飞机配备1辆，C类飞机1~2辆，D类飞机2~3辆，E、F类飞机2~4辆。 
下载: 导出CSV
表 2 航班原始信息（部分）
Table 2. Original flight information (partial)
航班号 起飞时刻 落地时刻 停机位 机型 性质 B1 11：35 13：26 127 A321 离港 B2 10：09 11：12 158 B738 离港 B3 12：52 15：35 712 B738 到港 B4 07：55 10：34 714 A320 到港 B5 14：03 16：20 135 B738 离港 B6 13：00 14：04 139 B738 到港 B7 14：45 15：44 136 A333 离港 B8 20：25 21：15 161 B737 离港 B9 20：37 21：39 524R B738 离港 B10 21：43 00：07 723 B737 到港 B11 08：37 09：37 105 B737 离港 B12 19：33 21：04 724 A320 离港 B13 14：52 16：36 324 A320 到港 B14 18：12 20：23 533 B737 离港 B15 20：32 22：16 111 B737 离港
下载: 导出CSV
表 3 不同停机坪之间以及停机坪与车场之间的车辆行驶时间
Table 3. Vehicle travel distance between different aprons and between aprons and car parks
单位: min 地点 停机坪C3 停机坪C5 停机坪C7 停机坪E5 停机坪E3 车场P1 停机坪C3 0 8 2 4 4 2 停机坪C5 8 0 8 6 11 9 停机坪C7 2 8 0 2 4 2 停机坪E5 4 6 2 0 6 3 停机坪E3 4 11 4 6 0 5 车场P1 2 9 2 3 5 0
下载: 导出CSV
表 4 机场摆渡车调度方案
Table 4. Airport ferry scheduling program
车辆编号 优先服务航班序列 次服务航班序列 总服务时间/min 车辆编号 优先服务航班序列 次服务航班序列 总服务时间/min 1 1 → 14 → 27 → 33 → 56 74 210 16 7 → 21 → 35 → 48 62 → 71 234 2 1 → 14 → 27 → 33 → 56 75 201 17 7 → 20 → 36 → 48 63 → 74 242 3 2 → 14 → 27 → 34 → 57 None 174 18 8 → 20 → 36 → 49 63 211 4 2 → 16 → 30 → 34 → 57 None 184 19 8 → 22 → 39 → 49 64 206 5 2 → 16 → 30 → 43 → 55 72 209 20 9 → 22 → 39 → 50 64 228 6 3 → 18 → 28 → 43 → 55 72 202 21 9 → 25 → 37 → 50 65 217 7 3 → 18 → 28 → 44 → 58 None 174 22 10 → 25 → 37 → 51 65 → 75 259 8 4 → 15 → 29 → 44 → 58 None 174 23 10 → 26 → 38 → 51 66 196 9 4 → 15 → 29 → 45 → 59 None 181 24 11 → 26 → 38 → 52 67 212 10 5 → 17 → 29 → 45 → 59 None 174 25 11 → 23 → 42 → 52 68 204 11 5 → 17 → 31 → 46 → 70 60 223 26 11 → 23 → 42 → 52 68 204 12 5 → 19 → 31 → 46 → 70 60 224 27 12 → 24 → 41 → 53 66 210 13 6 → 19 → 32 → 46 → 71 61 216 28 12 → 24 → 41 → 53 67 204 14 6 → 21 → 32 → 47 61 → 73 246 29 13 → 17 → 54 69 150 15 7 → 21 → 35 → 47 62 → 73 247 30 13 → 17 → 54 69 150
下载: 导出CSV
表 5 机场加油车调度方案
Table 5. Airport fuel truck dispatching program
车辆编号 优先服务航班序列 次服务航班序列 总服务时间/min 车辆编号 优先服务航班序列 次服务航班序列 总服务时间/min 1 1→18 31 73 9 9→26 None 42 2 3→20 33 69 10 11→22 None 34 3 2→17 34 96 11 13→28 None 37 4 5→25 32 101 12 10→30 None 41 5 4→24 39 108 13 12→27 None 34 6 6→19 29 90 14 15 36 45 7 8→23 35 89 15 16→37 None 34
下载: 导出CSV
-
[1] 陈邦昌. 关于智慧机场建设的实践与再认识: 以南京禄口机场二期工程为例[J]. 现代交通与冶金材料, 2021, 1(4): 32-34. https://www.cnki.com.cn/Article/CJFDTOTAL-YAJI202104007.htmCHEN B C. On the practice and reflection of smart airport building: by the case of Nanjing Lukou international airport phase 2 construction project[J]. Modern Transportation and Metallurgical Materials, 2021, 1(4): 32-34. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-YAJI202104007.htm [2] 中国民用航空局. 民航行业发展统计公报[R]. 北京: 中国民用航空局发展计划司, 2021.Civil Aviation Administration of China. Civil aviation industry development statistical bulletin[R]. Beijing: Development Planning Division of Civil Aviation Administration of China, 2021. (in Chinese) [3] HAN X, ZHAO P X, KONG D X. Abi-objective optimization of airport ferry vehicle scheduling based on heuristic algorithm: a real data case study[J]. Advances in Production Engineering & Management, 2022, 17(2): 183-192. [4] 衡红军, 晏晓东. 实现多目标优化的机场特种车辆调度算法[J]. 计算机应用与软件, 2016, 33(10): 238-242. https://www.cnki.com.cn/Article/CJFDTOTAL-JYRJ201610053.htmHENG H J, YAN X D. Implementing airport special vehicles scheduling algorithm with multi-objective optimisation[J]. Computer Applications and Software, 2016, 33(10): 238-242. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-JYRJ201610053.htm [5] 张凤, 汤晓鹏, 刘兵飞. 机场飞行区无人驾驶清水车优化调度方法[J]. 交通信息与安全, 2022, 40(2): 82-90. doi: 10.3963/j.jssn.1674-4861.2022.02.010ZHANG F, TANG X P, LIU B F. An optimization method for scheduling autonomous potable water service vehicles at airfields[J]. Journal of Transport Information and Safety, 2022, 40(2): 82-90. (in Chinese) doi: 10.3963/j.jssn.1674-4861.2022.02.010 [6] DU J Y, BRUNNER J O, KOLISCH R. Planning towing processes at airports more efficiently[J]. Transportation Research Part E: Logistics and Transportation Review, 2014, 70: 293-304. doi: 10.1016/j.tre.2014.07.008 [7] WANG Y, SUN J, SUN B, et al. Research on application of airport tanker truck scheduling based on particle swarm optimization[C]. 6th International Conference on Control, Robotics and Cybernetics(CRC), Shanghai, China: IEEE, 2021. [8] YUAN Y, HAN Y, XUE J Y, et al. A dynamic dispatching method in the unmanned airport baggage transportation system[C]. 23th IEEE International Conference on Mobile Data Management(MDM), Paphos, Cyprus: IEEE, 2022. [9] BI J, DING C, XIE D, et al. Multiobjective optimization of airport ferry vehicle scheduling during peak hours based on NSGA-Ⅱ[J/OL]. (2022-07-30)[2023-05-06]. https://doi.org/10.1155/2022/7388406 .[10] 唐非, 张瑞友, 刘树安. 面向机场地面服务的多服务协调调度算法[J]. 控制工程, 2020, 27(10): 1686-1692. https://www.cnki.com.cn/Article/CJFDTOTAL-JZDF202010005.htmTANG F, ZHANG R Y, LIU S A. Airport ground service oriented multi-service coordination scheduling algorithm[J]. Control Engineering of China, 2020, 27(10): 1686-1692. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-JZDF202010005.htm [11] LIU Y, WU J, TANG J, et al. Scheduling optimisation of multi-type special vehicles in an airport[J]. Transportmetrica B: Transport Dynamics, 2022, 10(1): 954-970. doi: 10.1080/21680566.2021.1983484 [12] CHEN B, TANG K, YANG Y. Airport resource scheduling optimization based on planning time window[C]. 33th Chinese Control and Decision Conference(CCDC), Kunming, China: IEEE, 2021. [13] 高文倩. 基于数据挖掘的机场航班地面保障能力优化研究[D]. 济南: 山东大学, 2019.GAO W Q. Research on optimization of airport flights ground support ability based on date mining[D]. Jinan: Shandong University, 2019. (in Chinese) [14] ZHANG J, CHONG X, WEI Y, et al. Optimization of apron support vehicle operation scheduling based on multi-layer coding genetic algorithm[J]. Applied Sciences, 2022, 12(10): 5279. doi: 10.3390/app12105279 [15] 吴枕. 大型机场地面保障车辆协同与动态调度研究[D]. 北京: 北京交通大学, 2021.WU Z. Research on collaborative and dynamic scheduling of ground support vehicles for large airports[D]. Beijing: Beijing Jiaotong University, 2021. (in Chinese) [16] 贾丽琦. 应用于机场保障的资源调度算法研究[D]. 西安: 西安科技大学, 2020.JIA L Q. Research on resource scheduling algorithms applied to airport support[D]. Xi'an: Xi'an University of Science and Technology, 2020. (in Chinese) [17] 唐云霄. 枢纽机场航班保障服务时间估计[D]. 天津: 中国民航大学, 2017.TANG Y X. The estimation about flight support service time of hub airport[D]. Tianjin: Civil Aviation University of China, 2017. (in Chinese) [18] EVLER J, ASADI E, PREIS H, et al. Airline ground operations: schedule recovery optimization approach with constrained resources[J]. Transportation Research Part C: Emerging Technologies, 2021, 128: 103129. doi: 10.1016/j.trc.2021.103129 [19] 中国民用航空局. 民用航空运输地面保障服务规范: MH/T 1036—2011[S]. 北京: 航空器适航审定司, 2011.Civil Aviation Administration of China. Civil aviation ground support service standards: MH/T 1036—2011[S]. Beijing: Aircraft Airworthiness Certification Division, 2011. (in Chinese) [20] 王立文, 李彪, 邢志伟, 等. 过站航班地面保障过程动态预测[J]. 北京航空航天大学学报, 2021, 47(6): 1095-1104. https://www.cnki.com.cn/Article/CJFDTOTAL-BJHK202106002.htmWANG L W, LI B, XING Z W, et al. Dynamic prediction of ground support process for transit flight[J]. Journal of Beijing University of Aeronautics and Astronautics, 2021, 47 (6): 1095-1104. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-BJHK202106002.htm [21] 杨珏. 基于遗传算法的机场特种车辆调度应用研究[J]. 计算机技术与发展, 2019, 29(3): 164-168. https://www.cnki.com.cn/Article/CJFDTOTAL-WJFZ201903035.htmYANG Y. Research on airport special vehicle scheduling based on genetic algorithm[J]. Computer Technology and Development, 2019, 29(3): 164-168. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-WJFZ201903035.htm [22] PADRON S, GUIMARANS D, RAMOS J J, et al. A bi-objective approach for scheduling ground-handling vehicles in airports[J]. Computers & Operations Research, 2016, 71: 34-53. [23] MAHMOUDI M, ZHOU X. Finding optimal solutions for vehicle routing problem with pickup and delivery services with time windows: a dynamic programming approach based on state-space-time network representations[J]. Transportation Research Part B: Methodological, 2016, 89: 19-42. doi: 10.1016/j.trb.2016.03.009 [24] 程琳, 宁翊森, 宋茂灿. 拉格朗日松弛启发式算法求解时空网络下的弧路径问题[J]. 交通运输工程学报, 2022, 22 (4): 273-284. https://www.cnki.com.cn/Article/CJFDTOTAL-JYGC202204021.htmCHENG L, NING Y S, SONG M C. Lagrangian relaxtion heuristic algorithm of arc routing problem under time-space network[J]. Journal of Traffic and Transportation Engineering, 2022, 22(4): 273-284. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-JYGC202204021.htm [25] ZHAO P, HAN X, WAN D. Evaluation of the airport ferry vehicle scheduling based on network maximum flow model[J]. Omega, 2021, 99: 102178. doi: 10.1016/j.omega.2019.102178 -
点击查看大图
图(7) / 表(5)
计量
- 文章访问数: 334
- HTML全文浏览量: 205
- PDF下载量: 44
- 被引次数: 0