论文题目：Scheduling optimisation of multi-type special vehicles in an airport（机场中多类型特殊车辆的调度优化）

论文作者：Liu Yonghong;Wu Jianjun; Tang Jie; Wang Weiping; Wang Xiaofei

论文期刊：TRANSPORTMETRICA B: TRANSPORT DYNAMICS

论文网址：https://doi.org/10.1080/21680566.2021.1983484 

摘要：地面保障车辆数量不足和调度不当会对机场服务质量造成重大影响，而机场特殊车辆的合理调度可以大大提高机场服务效率。本文提出了以所需特殊车辆数最少和额外总时间成本最小为目标的双目标混合整数规划模型。此外,还考虑了各种车辆的服务约束关系和车辆的可重用性,以充分利用现有的特殊车辆资源。为便于模型求解,将综合调度问题简化为多个具有并行服务和时序约束的子问题，并开发了具有多个染色体的非支配排序遗传算法和精英策略分别求解。最后,利用国内某机场的实际航班数据,验证了模型的有效性,并提供了有益的管理启示。

关键词：特殊车辆; 混合整数规划; 多染色体遗传算法; 双目标优化

1、研究背景

近年来，随着全球民航业的快速发展，机场地面服务受到越来越多的关注。2019年，中国民航业完成了近6.6亿人次的客运量，同比增长7.9%（《2019年民航业发展统计公报》）。空中交通的显著增加导致了日益拥挤的机场和严重的航班延误（《2019年全球机场和航空公司准时报告》）。每天有数百架飞机飞往许多国际机场，这对地面处理服务来说是一个重大挑战。机场地勤服务的资源分配和调度，如机场跑道分配问题、机组人员调度问题、登机口分配问题以及地面支持车辆调度问题，特殊车辆调度作为机场运营管理的重要组成部分，直接影响航班的安全和正常运行。高效的调度计划可以有效提高机场的地面保障能力和航班准点率。因此，合理调度特殊车辆具有重要的研究意义。本文讨论了作为周转过程一部分的特殊车辆运行调度问题。

2、问题描述与模型建立

根据机场的实际运营要求，机场专用车辆调度模型的目标如下：

1. 尽量减少专用车辆的总数。

2. 尽量减少特殊车辆的总额外时间成本（包括等待、驾驶和补充资源时间）。

本研究中服务的航班为过境航班。模型假设如下：

1. 不同飞机类型所需的特殊车辆类型和服务时间不同。本研究只考虑了一种类型的飞机。

2. 所有车辆的起点都是同一个仓库（0）。

3. 不同服务要求对应的每一次飞行都由一辆专用车辆一次性完成，同一类型的专用车辆规格相同。

4. 服务启动后，在完成之前不会中断。

5. 当特殊车辆资源不足时，他们会返回仓库补充资源。

约束条件：

变量解释：

表1：变量解释

3、算法求解

在这项研究中，设计了一种基于混合编码的NSGA-II算法来解决该模型，使用自然数编码直接用实数表示基因。最终服务路线如下图所示：

图1：车辆分配计划和相应的染色体代码。

本研究中用于求解模型的算法的具体步骤如下：

步骤1：随机生成初始种群P₀，种群大小为N，并根据染色体子串计算所有个体的车辆数量和总额外时间成本。

步骤2：确定每个个体的初始适应度，并根据目标函数值为P_n中的所有个体分配适应度值。根据目标函数值按升序对个体进行排序，并通过比赛选择从人群P_n中选择个体。后代群体Q_n是通过交叉和突变算子产生的，并计算了Q_n中个体的两个目标值。

步骤3：组合P_n和Q_n以形成种群R_n=P_nQ_n，对R_n进行非支配分层，并获得所有不同级别个体的非支配集合F_i，i=1，2。

步骤4：计算临界层与临界层之前的个体之间的拥挤距离。使用选择运算符，从最大值到最小值选择9个个体，并将其保留在下一代P_n+1中。

步骤5：对人群P_n+1进行交叉和突变操作，并根据拥挤距离选择新一代人群Q_n+1。

步骤6：一旦达到最大迭代次数n=N，保留后代群体Q_n，输出帕累托最优解集，并终止算法。否则，返回步骤2并继续迭代。

4、计算研究

4.1实验数据

本研究利用一个国内机场在一天高峰时段的飞行数据，对摆渡车、加油车、食品车、运水车、污水车、垃圾车、行李运输车和拖拉机的调度进行了试验。用于在机场调度特殊车辆的数据包括上午50架次航班的信息。为了验证模型和算法的有效性，选择了不同日期的同一时间进行比较。由于一些外部因素，共有38个航班进行了计算验证。

（1）部分机场停车位坐标：

图2：部分机场机位分布

（2）飞机到达和起飞时间：

表2：机场出发和到达数据

表3：航班服务时间窗口

（3）其他数据：

表4：特殊车辆数据

4.2实验结果分析

本研究使用NSGA-II算法获得了机场专用车辆调度模型在不同情况下的帕累托最优解。每个帕累托最优解对应于一个车辆调度计划，并将车辆较少的帕累托最佳解作为结果。两天的调度结果如图3和图4所示：

图3：特殊车辆调度结果

图4：特殊车辆调度结果

为了验证模型和所提出的求解算法的有效性，将其与MOAED算法、PSO算法（将目标函数加权为单目标优化问题）、先到先服务（FCFS）调度方法和NSGA II算法（飞机类型越大，服务优先级越高）进行了比较。使用了一个圆顶形机场在一天的高峰期的飞行数据。通过为其他算法设置相同的最大专用车辆数量和时间窗口，确保了比较结果的准确性。

以下是对每个算法的调度结果的详细分析。表5和表6分别列出了五种算法所需的车辆数量和总额外时间成本。轮渡车辆和行李运输车辆的结果是两个调度结果的总和。从以上结果来看，基于NSGA-II算法的调度方案在车辆数量和运行时间方面比其他算法要好得多，这证明了所提出算法在机场专用车辆调度问题中的可行性和有效性。

表5：目标函数1的结果

表6：目标函数2的结果

5、结论

本工作涉及机场专用车辆的调度。所提出的模型包含了机场专用车辆运行的所有相关运行限制和规范。以摆渡车、加油车、食品车、水车、污水车、垃圾车、行李运输车和拖拉机为研究对象，建立了双目标调度模型。采用问题约简方法对机场专用车辆调度问题进行约简，将每种车辆的调度问题视为一个子问题，根据并行服务类型和顺序服务类型之间的约束关系，解决了每个子问题，并将结果集成到原问题的求解中。然后设计了多染色体编码方案，以同时优化分配和序列编码。最后，采用带有精英策略的NSGA-II算法，通过Python编程解决了该问题。结果表明，对于国内某机场在高峰时段的实际进出港航班，提供更好的解决方案，并且可以合理地解决该机场的早车调度问题。在案例研究中，通过与其他算法的比较，进一步验证了模型和算法的有效性，为机场地面服务的调度决策提供了理论支持。未来的研究可以指向扩展模型以添加动态元素，分析动态调度的求解策略和动态加速，设计车辆动态调度算法。开展车辆动态调度研究对促进智能机场的发展，提高机场运营管理水平具有重要意义。

1. 参考文献

[1]Chandrasekar,S.,andI.Hwang.2015.“AlgorithmforOptimalArrivalandDepartureSequencingandRunwayAssignment.”Journal of Guidance, Control, and Dynamics38 (4): 601–613.

[2]Coello, C. A., and A. D. Christiansen.2000. “Multiobjective Optimization of Trusses Using Genetic Algorithms.”Computers& Structures75 (6): 647–660.

[3]Deb, K., and R. B. Agrawal.1995. “Simulated Binary Crossover for Continuous Search Space.”Complex Systems9 (2):115–148.

[4]Deb, K., and M. Goyal.1996. “A Combined Genetic Adaptive Search (GeneAS) for Engineering Design.”Computer Scienceand Informatics26: 30–45.

[5]Deb,K.,A.Pratap,S.Agarwal,andT.A.M.T.Meyarivan.2002. “A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II.”IEEE Transactions on Evolutionary Computation6 (2): 182–197.

[6]Dorndorf, U., F. Jaehn, and E. Pesch.2008. “Modelling Robust Flight-Gate Scheduling as a Clique Partitioning Problem.”Transportation Science42 (3): 292–301.

[7]Du, J. Y., J. O. Brunner, and R. Kolisch.2014. “Planning Towing Processes at Airports More Efficiently.”TransportationResearch Part E: Logistics and Transportation Review70: 293–304.970Y.LIUETAL.

[8]Global Airport & Airline Punctuality Report.2019.http://www.variflight.com/detail/741.html?AE71649A58c77=.

[9]Guo, W., P. Xu, Z. Zhao, L. Wang, L. Zhu, and Q. Wu.2020. “Scheduling for Airport Baggage Transport Vehicles Based onDiversity Enhancement Genetic Algorithm.”Natural Computing19 (4): 663–672.

[10]Han, X., P. Zhao, Q. Meng, S. Yin, and D. Wan.2020. “Optimal Scheduling of Airport Ferry Vehicles Based on CapacityNetwork.”Annals of Operations Research295 (1): 163–182.

[11]Ip, W. H., D. Wang, and V. Cho.2012. “Aircraft Ground Service Scheduling Problems and Their Genetic Algorithm withHybrid Assignment and Sequence Encoding Scheme.”IEEE Systems Journal7 (4): 649–657.

[12]Kasemsontitum, B., and T. Tembundit.2012. “Airport Service Vehicle Routing And Dispatching Policy: Case Of Suvarnab-humi Airport.” International Conference on Industrial Management, 622–628.

[13]Li, Q., J. Bi, and Z. Li.2017. “Research on Ferry Vehicle Scheduling Problem within Airport Operations.” Proceeding of the10th International Symposium on Computational Intelligence and Design, 248–251.

[14]Norin, A., D. Yuan, T. A. Granberg, and P. Värbrand.2012. “Scheduling de-Icing Vehicles Within Airport Logistics: a HeuristicAlgorithm and Performance Evaluation.”Journal of the Operational Research Society63 (8): 1116–1125.

[15]Öner, N., H. Gultekin, and Ç Koç.2020. “The Airport Shuttle Bus Scheduling Problem.”International Journal of ProductionResearch, 1–23.doi:10.1080/00207543.2020.1841317.

[16]Padrón, S., and D. Guimarans.2019. “An Improved Method for Scheduling Aircraft Ground Handling Operations from aGlobal Perspective.”Asia-Pacific Journal of Operational Research36 (04): 1950020.

[17]Padrón, S., D. Guimarans, J. J. Ramos, and S. Fitouri-Trabelsi.2016. “A bi-Objective Approach for Scheduling Ground-Handling Vehicles in Airports.”Computers & Operations Research71: 34–53.

[18]Schyns, M.2015. “An ant Colony System for Responsive Dynamic Vehicle Routing.”European Journal of OperationalResearch245 (3): 704–718.StatisticalBulletinontheDevelopmentofCivilAviationIndustry.2019.https://www.mot.gov.cn/tongjishuju/minhang/202006/P020200702602086869690.pdf.

[19]Weiszer, M., J. Chen, and G. Locatelli.2015. “An Integrated Optimisation Approach to Airport Ground Operations to FosterSustainability in the Aviation Sector.”Applied Energy157: 567–582.

[20]Wen,X.,H.L.Ma,S.H.Chung,andW.A.Khan.2020. “Robust Airline Crew Scheduling with Flight Flying Time Variability.”Transportation Research Part E: Logistics and Transportation Review144: 102132.

[21]Zhao, P. X., W. Q. Gao, X. Han, and W. H. Luo.2019. “Bi-objective Collaborative Scheduling Optimization of Airport FerryVehicle and Tractor.”International Journal of Simulation Modelling18 (2): 355–365.

[22]Zhao, P., X. Han, and D. Wan.2021. “Evaluation of the Airport Ferry Vehicle Scheduling Based on Network Maximum FlowModel.”Omega99: 102178.