Optimization of multi-type airport ferry vehicles schedules with double service time windows characteristic
-
摘要:
为提升摆渡车运行的灵活性、增强车辆调度方案的能效和实践可操作性，综合考虑多车型和机场摆渡车运输服务的双时间窗特性，从任务点视角构建机场摆渡车调度问题的混合整数线性规划模型。该模型可视为一个考虑多车型和双时间窗且需求可拆分的车辆路径问题，是一个复杂的NP-hard问题，为此，提出一种改进的自适应大邻域搜索(ALNS)算法。以北京首都国际机场东飞行区为背景的案例仿真结果表明：所提算法具有良好的稳定性和优化效果，200次迭代下10轮次计算实验结果的标准差与平均值之比仅为5.6%，优化前后对应的最优目标函数值下降达54%；多车型调度方案显著优于人工和单一车型调度方案，在车辆容量利用能效上较人工、大车型和小车型方案分别提升了98.3%、31.3%和22.2%，在运行总成本上较人工、大车型和小车型方案则分别下降了48.3%、23.4%和23.5%。
Abstract:A mixed-integer linear programming model is developed for the airport ferry vehicle scheduling problem from the perspective of task units, taking into account both the double time windows characteristics of the airdrome ferry vehicle transport service and multi-type vehicles in order to increase the flexibility of airport ferry vehicle operation and the efficiency and practicality of the vehicle scheduling schemes. The resultant model can be viewed as a split-delivery vehicle routing problem with multi-type vehicles and double service time windows, which is a complex NP-hard problem. To solve such a challenging problem, a tailored adaptive large neighborhood search (ALNS) algorithm is proposed. Computational experiments are conducted on the eastern airfield of the Beijing Capital International Airport. The experimental results demonstrate that the proposed algorithm shows excellent stability and effectiveness. The ratio of the standard deviation to the average value of the calculation results for 10 iterations under 200 iterations is only 5.6%, and the optimal objective function value decreases by 54% before and after optimization. In addition, the multi-type vehicle schedule performs much better than both the man-made and the single-type schedules, which produces 98.3%, 31.3% and 22.2% of vehicle capacity efficiency increase and creates 48.3%, 23.4% and 23.5% of total operation cost saving in comparison to the man-made, single-big-type, and single-small-type schedules, respectively.
-
图 1 本文摆渡车调度问题示例
Figure 1. An illustrative example for the ferry vehicle scheduling problem
图 3 首都机场东区远机位分布与摆渡路线
Figure 3. Layout and running routes of far stands in eastern airfield of BCIA
图 4 不同终止迭代次数下的实验结果统计（左列）与最优目标函数值下降过程（右列）
Figure 4. Experimental result statistics (left column) and evolution of optimal objective function values (right column) under different iterative tolerances
图 5 不同调度方案的满载率热力图
Figure 5. Thermodynamic chart of vehicle full-load ratios for different scheduling strategies
表 1 不同调度方案的计算结果
Table 1. Results between different scheduling schemes
调度方案 用车数量/辆 用车成本/
元行驶费用/
元总成本/
元大车 小车 人工调度 9 13500 656 14156 单一大车型调度 6 9000 546 9546 单一小车型调度 11 8800 750 9550 多车型联合调度 3 3 6900 410 7310 
下载: 导出CSV
表 2 多车型调度方案与其他3种方案的结果对比
Table 2. Results comparison between multi-type vehicle scheduling schemes and other three schemes
对比调度策略 改进幅度/% 用车成本 行驶费用 总成本 人工调度 48.9 37.5 48.3 单一大车型调度 23.3 24.9 23.4 单一小车型调度 21.6 45.3 23.5
下载: 导出CSV
表 3 不同调度方案的车辆利用能效对比
Table 3. Vehicle utilization efficiency comparison between different scheduling schemes
调度方式 车辆总体平均
满载率/%车辆平均容量服务率/
（人·单位容量−1）大车 小车 总体 人工调度 82.05 7.17 7.17 单一大车型调度 82.05 10.83 10.83 单一小车型调度 90.78 11.64 11.64 多车型联合调度 90.78 18.33 10.33 14.22
下载: 导出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] 杨文东, 陶婧婧, 贾玉平. 机坪摆渡车实时调度系统仿真[J]. 南京麻豆精品秘 国产传媒学报, 2013, 45(6): 854-858.YANG W D, TAO J J, JIA Y P. Simulation of real-time scheduling of airport ferry bus[J]. Journal of Nanjing University of Aeronautics & Astronautics, 2013, 45(6): 854-858(in Chinese). [3] 冯霞, 任子云. 基于遗传算法的加油车和摆渡车协同调度研究[J]. 交通运输系统工程与信息, 2016, 16(2): 155-163.FENG X, REN Z Y. Collaborative scheduling of fuelling vehicle and ferry vehicle based on genetic algorithm[J]. Journal of Transportation Systems Engineering and Information Technology, 2016, 16(2): 155-163(in Chinese). [4] 何丹妮. 大型机场航班过站地面服务车辆调度问题研究: 以摆渡车为例[D]. 北京: 北京交通大学, 2018.HE D N. Research on the scheduling problem of ground service vehicles for large airport flights: taking car ferry as an example[D]. Beijing: Beijing Jiaotong University, 2018(in Chinese). [5] HAN X, ZHAO P X, MENG Q C, et al. Optimal scheduling of airport ferry vehicles based on capacity network[J]. Annals of Operations Research, 2020, 295(1): 163-182. doi: 10.1007/s10479-020-03743-0 [6] 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 [7] HAN X, ZHAO P X, KONG D X. A bi-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. [8] LIU Y H, WU J 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 [9] 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. [10] 冯明端, 肖雪, 周航. 机场地面保障多车型车辆联合调度模型研究[J]. 武汉理工大学学报(交通科学与工程版), 2023, 47(1): 67-72.FENG M D, XIAO X, ZHOU H. Research on the multi-type joint scheduling model of airport ground support vehicles[J]. Journal of Wuhan University of Technology (Transportation Science & Engineering), 2023, 47(1): 67-72(in Chinese). [11] 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 [12] BAO D W, ZHOU J Y, ZHANG Z Q, et al. Mixed fleet scheduling method for airport ground service vehicles under the trend of electrification[J]. Journal of Air Transport Management, 2023, 108: 102379. doi: 10.1016/j.jairtraman.2023.102379 [13] BRÄYSY O, GENDREAU M. Vehicle routing problem with time windows, part I: route construction and local search algorithms[J]. Transportation Science, 2005, 39(1): 104-118. doi: 10.1287/trsc.1030.0056 [14] 中国民用航空局. 航班安全运行保障标准: 民航发〔2020〕4号[S]. 北京: 中国民用航空局, 2020.Civil Aviation Administration of China. Flight safety operation guarantee standards: CAAC〔2020〕No. 4[S]. Beijing: Civil Aviation Administration of China, 2020(in Chinese). [15] ROPKE S, PISINGER D. An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows[J]. Transportation Science, 2006, 40(4): 455-472. doi: 10.1287/trsc.1050.0135 [16] WINDRAS MARA S T, NORCAHYO R, JODIAWAN P, et al. A survey of adaptive large neighborhood search algorithms and applications[J]. Computers & Operations Research, 2022, 146: 105903. -
下载:
点击查看大图
计量
- 文章访问数: 599
- HTML全文浏览量: 132
- PDF下载量: 6
- 被引次数: 0
