Dual-phase scheduling of apron support vehicles considering multi-vehicle coordination
-
摘要:
大型机场机坪保障车辆一直面临较大运行压力，而多种机坪保障服务的配合约束和动态航班信息对车辆调度提出更高挑战。考虑连续工作、容量限制的连续工作和往返工作3种不同模式车辆运行约束差异，以车辆数量最少和行驶总距离最小为目标，建立多车型协同的机坪保障车辆调度模型。根据机场实际运行情况，对该模型进行双阶段求解，在静态阶段设计一种融合局部搜索的非支配排序遗传算法Ⅱ(LS-NSGA Ⅱ)，在动态阶段设计一种类邻域搜索算法求解多车型协同调度问题。数据仿真结果表明：所建模型静态调度阶段结果相对于先到先服务(FCFS)，车辆数量和行驶总距离分别降低了18.9%和8.9%；动态调度阶段结果能保持原调度计划车辆数量，行驶距离调整量相较于大规模邻域搜索算法降低了25.8%。研究结果可以为大型机场机坪保障车辆调度管理和决策提供一定的指导。
Abstract:The coordination restrictions of several apron support services and dynamic flight information have resulted in increased operational demand on large airport apron support vehicles and more difficulties with vehicle scheduling. Considering the difference of vehicle operation constraints in three different modes of continuous operation, capacity-limited continuous operation and round-trip operation, a multi-vehicle cooperative apron support vehicle scheduling model is established with the goal of minimizing the number of vehicles and the total driving distance. The model is solved in two stages according to the actual operation of the airport. In the static stage, a local search non-dominated corting genetic algorithms Ⅱ (LS-NSGA II) algorithm integrating local search is designed. In the dynamic stage, a similar neighborhood search algorithm is designed. The static results show that the number of vehicles and the total driving distance are reduced by 18.9% and 8.9% respectively compared with the first-come-first-served. In comparison to the big neighborhood search technique, the dynamic results can keep the number of cars in the static scheduling plan while reducing the adjusted driving distance by 25.8%. The research results can provide a certain guiding significance for the scheduling management and decision-making of large airport apron support vehicles.
-
图 2 多车型协同的机坪保障车辆双阶段调度算法流程
Figure 2. Two-stage scheduling algorithm process of multi-vehicle cooperative apron support vehicle
图 4 LS-NSGA Ⅱ、NSGA Ⅱ和FCFS求解结果散点图
Figure 4. LS-NSGA Ⅱ，NSGA Ⅱ and FCFS solution result scatter plot
表 1 行李牵引车转场距离
Table 1. Luggage tractor transfer distance
前序航班$i$性质 后序航班$j$性质 车辆转场方向 转场距离$ s_{ij}^\alpha $ 进港 进港 行李中心→停机位 $ {d_{bj}} $ 进港 离港 行李中心→行李中心 $ 0 $ 离港 进港 停机位→停机位 $ {d_{ij}} $ 离港 离港 停机位→行李中心 $ {d_{ib}} $ 
下载: 导出CSV
表 2 航班计划表（示例）
Table 2. Flight schedule (example)
航班编号 机型 机位 计划进/离港时刻 航班性质 过站时长/min 1 A32B 268 10：00 进港 65 2 ERJ190 434 10：00 离港 65
下载: 导出CSV
表 3 车辆所需数量和服务时长
Table 3. Number of vehicles required and minutes of service
机型 车辆所需数量/台 服务时长/min 行李牵引车 传送带车 清水车 行李牵引车 传送带车 清水车 进港 离港 进港 离港 C 1 1 1 15 25 15 25 5 D 2 1 1 15 25 15 25 7 E 2 1 1 15 25 15 25 7 F 3 2 1 20 30 20 30 9
下载: 导出CSV
表 4 LS-NSGA Ⅱ参数设置
Table 4. LS-NSGA Ⅱ parameters settings
参数 数值 LS-ANSGA Ⅱ迭代次数 300 LS-ANSGA Ⅱ种群大小 150 交叉概率 0.7 变异概率 0.05 目标函数权重 0.5
下载: 导出CSV
表 5 动态变化的航班数量
Table 5. Number of dynamic change flights
航班性质 航班数量 时间变更 停机位变更 航班取消 进港 33 2 1 离港 14 2 1
下载: 导出CSV
表 6 LS-NSGA Ⅱ、NSGA Ⅱ和FCFS结果对比
Table 6. LS-NSGA II，NSGA II and FCFS results comparison
车辆类型 $ Z_1^i $/台 $ Z_2^i $/m 行李牵引车 传送带车 清水车 行李牵引车 传送带车 清水车 LS-NSGA Ⅱ 14 10 3 128456 48467 22336 15 11 4 121648 45679 22194 16 12 5 120358 44974 22074 17 13 119365 44075 18 14 118453 43754 NSGA Ⅱ 14 10 3 129375 49447 23257 15 11 4 123956 46346 23071 16 12 5 121365 45355 22887 17 13 120745 44698 18 14 118753 44256 FCFS 18 14 5 131965 50486 25476
下载: 导出CSV
表 7 最优解对比
Table 7. Comparison of optimal solutions
算法 $ {Z_1} $/台 $ {Z_2} $/m LS-NSGA Ⅱ 30 189521 NSGA Ⅱ 30 193373 FCFS 37 207927
下载: 导出CSV
表 8 顺序调度与协同调度结果对比
Table 8. Comparison of sequential scheduling and collaborative scheduling
调度模式 $ {Z_1} $/台 $ {Z_2} $/m $Z_1^i $/台 $Z_2^i $/m 行李牵引车 传送带车 清水车 行李牵引车 传送带车 清水车 顺序调度 32 191873 16 12 4 122515 47033 22325 协同调度 30 189521 15 11 4 121648 45679 22194
下载: 导出CSV
表 9 SNS和ALNS算法结果对比
Table 9. SNS and ALNS algorithms results comparison
动态调度算法 $ {Z_1} $/台 与静态调度差值/台 $ {Z_2} $/m 与静态调度差值/m 计算时间/s SNS 32 +2 217111 + 27590 6.53 ALNS[20] 32 +2 228146 + 38625 142.72
下载: 导出CSV
表 10 动态调度与静态调度结果对比
Table 10. Comparison of dynamic scheduling and static scheduling
调度模式 $ {Z_1} $/台 $ {Z_2} $/m $Z_1^i $/台 $Z_2^i $/m 行李牵引车 传送带车 清水车 行李牵引车 传送带车 清水车 动态调度 32 217111 16 12 4 136614 56816 23681 静态调度 30 189521 15 11 4 121648 45679 22194
下载: 导出CSV
表 11 动态调度中不同情景下的航班数量
Table 11. Number of flights under different scenarios in dynamic scheduling
机坪保障车辆
类型航班信息改变 航班信息未改变 保障车辆改变 保障车辆未改变 保障车辆改变 保障车辆未改变 行李牵引车 37 16 24 68 传送带车 28 25 15 77 清水车 3 14 0 61
下载: 导出CSV
表 12 行李牵引车双阶段调度结果对比
Table 12. Comparison of two-stage scheduling results of luggage tractor
车辆序号 航站楼分区 1 2 3 4 5 6 7 1 √ √ ○ ○ 2 √ √ ○ ○ ○ 3 √ ○ ○ ○ 4 √ √ √ ○ 5 √ √ √ ○ ○ ○ 6 √ √ √ ○ ○ ○ ○ ○ ○ ○ 7 √ √ √ √ √ √ √ ○ ○ ○ ○ ○ ○ ○ 8 √ √ ○ ○ 9 √ √ ○ ○ ○ 10 √ √ √ √ √ √ √ ○ ○ ○ 11 √ ○ ○ 12 √ √ √ ○ ○ ○ 13 √ √ ○ ○ 14 √ √ ○ 15 √ √ ○ ○ 16 ○ ○ ○ 注：√表示静态调度，○表示动态调度。
下载: 导出CSV
-
[1] KUHN K, LOTH S. Airport service vehicle scheduling[J]. Air Traffic Control Quarterly, 2010, 18(1): 63-83. doi: 10.2514/atcq.18.1.63 [2] NORIN A, GRANBERG T A, YUAN D, et al. Airport logistics–a case study of the turn——around process[J]. Journal of Air Transport Management, 2012, 20: 31-34. [3] NORIN A, YUAN D, GRANBERG T A, et al. Scheduling de-icing vehicles within airport logistics: a heuristic algorithm and performance evaluation[J]. Journal of the Operational Research Society, 2012, 63(8): 1116-1125. doi: 10.1057/jors.2011.100 [4] 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 [5] 王博, 王剑辉, 彭笑非, 等. 基于机场协同决策系统的机坪牵引车调度方法[J]. 科学技术与工程, 2021, 21(4): 1667-1673. doi: 10.3969/j.issn.1671-1815.2021.04.061WANG B, WANG J H, PENG X F, et al. The method for scheduling towing tractors based on A-CDM system[J]. Science Technology and Engineering, 2021, 21(4): 1667-1673(in Chinese). doi: 10.3969/j.issn.1671-1815.2021.04.061 [6] GAMAYANTI N, SAHAL M, WIBISONO A. Optimization of vehicle routing problem with tight time windows, short travel time and re-used vehicles (vrptsr) for aircraft refueling in airport using ant colony optimization algorithm[J]. Journal on Advanced Research in Electrical Engineering, 2018, 2(1): 43-46. [7] 衡红军, 戚馨桐. 考虑任务均衡的加油车动态调度问题[J]. 计算机工程与科学, 2020, 42(5): 923-930.HENG H J, QI X T. Dynamic refueling vehicle scheduling considering task balance[J]. Computer Engineering & Science, 2020, 42(5): 923-930(in Chinese). [8] ZHAO P X, 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 [9] HAN X, ZHAO P X, KONG D X. Two-stage optimization of airport ferry service delay considering flight uncertainty[J]. European Journal of Operational Research, 2023, 307(3): 1103-1116. doi: 10.1016/j.ejor.2022.09.023 [10] GUO W A, XU P, ZHAO Z, et al. Scheduling for airport baggage transport vehicles based on diversity enhancement genetic algorithm[J]. Natural Computing, 2020, 19(4): 663-672. doi: 10.1007/s11047-018-9703-0 [11] 袁成斌. 基于启发式算法的机场除冰资源调度策略研究[D]. 武汉: 华中科技大学, 2020: 51-63.YUAN C B. Research on airport deicing resource scheduling strategy based on heuristic algorithm[D]. Wuhan: Huazhong University of Science and Technology, 2020: 51-63(in Chinese). [12] ZHAO P X, GAO W Q, HAN X, et al. Bi-objective collaborative scheduling optimization of airport ferry vehicle and tractor[J]. International Journal of Simulation Modelling, 2019, 18(2): 355-365. doi: 10.2507/IJSIMM18(2)CO9 [13] ZHU S R, SUN H J, GUO X. Cooperative scheduling optimization for ground-handling vehicles by considering flights’ uncertainty[J]. Computers & Industrial Engineering, 2022, 169: 108092. [14] GUIMARANS D, PADRÓN S. A stochastic approach for planning airport ground support resources[J]. International Transactions in Operational Research, 2022, 29(6): 3316-3345. doi: 10.1111/itor.13104 [15] 吴枕. 大型机场地面保障车辆协同与动态调度研究[D]. 北京: 北京交通大学, 2021: 27-38.WU Z. Research on coordination and dynamic scheduling of ground support vehicles in large airports[D]. Beijing: Beijing Jiaotong University, 2021: 27-38(in Chinese) . [16] 蔡畅. 枢纽机场摆渡车动态调度方法研究[D]. 哈尔滨: 哈尔滨工业大学, 2021: 31-44.CAI C. Research on dynamic dispatching method of hub airport car ferry[D]. Harbin: Harbin Institute of Technology, 2021: 31-44(in Chinese) . [17] XUE G Q, WANG Y, GUAN X Y, et al. A combined GA-TS algorithm for two-echelon dynamic vehicle routing with proactive satellite stations[J]. Computers & Industrial Engineering, 2022, 164: 107899. [18] 王庞伟, 邓辉, 于洪斌, 等. 车路协同系统下区域路径实时决策方法[J]. 北京航空航天大学学报, 2019, 45(7): 1349-1360.WANG P W, DENG H, YU H B, et al. Real-time regional path decision method in cooperative vehicle infrastructure system[J]. Journal of Beijing University of Aeronautics and Astronautics, 2019, 45(7): 1349-1360(in Chinese). [19] 范厚明, 张跃光, 田攀俊, 等. 时变路网下异型车辆动态配置与路径优化[J]. 系统工程理论与实践, 2022, 42(2): 455-470. doi: 10.12011/SETP2020-0017FAN H M, ZHANG Y G, TIAN P J, et al. Dynamic vehicle routing problem of heterogeneous fleets with time-dependent networks[J]. Systems Engineering-Theory & Practice, 2022, 42(2): 455-470(in Chinese). doi: 10.12011/SETP2020-0017 [20] CHEN S F, CHEN R, WANG G G, et al. An adaptive large neighborhood search heuristic for dynamic vehicle routing problems[J]. Computers & Electrical Engineering, 2018, 67: 596-607. -
下载:
点击查看大图
计量
- 文章访问数: 279
- HTML全文浏览量: 68
- PDF下载量: 10
- 被引次数: 0
