ABSTRACT

In recent years, the punctuality rate of airport flights has received much attention. The on-site dispatch of special vehicles in the airport will directly affect the punctuality rate of the flight. This paper reviews the impact of airport special vehicle optimized scheduling on flight punctuality rate, researches the progress of special vehicle optimized scheduling methods in airports, focuses on fuel trucks, studies the nature of special vehicle optimized scheduling problems and current commonly used optimized algorithms, and realizes the system and technical support of vehicle on-site dispatching, provides reference for further research on optimizing the scheduling problem of special vehicles in the airport, and prospects for the development of special vehicle optimized scheduling problems.

Keywords:Special Vehicle, Optimized Scheduling, Fuel Truck, Optimized Algorithm

机场特种车辆优化调度问题研究现状及展望

张朝倩，崔艳雨

中国民航大学机场学院，天津

收稿日期：2019年5月11日；录用日期：2019年5月23日；发布日期：2019年5月30日

摘 要

近年来，机场航班正点率倍受关注，特种车辆在机场中的场内调度直接对航班的正点率产生影响。本文综述了机场中地面保障服务，车辆调度问题和特种车辆优化调度方法的研究进展，以加油车重点，研究特种车辆优化调度问题的本质和目前常用的优化算法，以及实现特种车辆场内调度的系统和技术支持，为进一步研究优化特种车辆在机场场内调度问题提供参考，并对特种车辆优化调度问题的发展进行了展望。

关键词 :特种车辆，优化调度，加油车，优化算法

Copyright © 2019 by author(s) and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY).

http://creativecommons.org/licenses/by/4.0/

1. 引言

随着民航业的快速发展，越来越多的机场规模逐渐扩大，机场的日吞吐量也日益增加 [1] ，这对机场地面作业和提供的服务提出了更高的要求。提高机场的地面作业和服务效率可以有效地降低航班延误率。机场中进行地面保障服务的特种车辆主要由行李运输车进行旅客行李的运输；加油车进行飞机燃油加注；清洁车进行加水；配餐车进行餐食供应；污水处理车进行污水处理作业等 [2] 。民航飞机在机坪中需要进行的地面保障服务如图1所示。

图1. 民航飞机地面保障服务示意图

目前的机场的地面保障服务作业仍旧存在人工调度 [3] [4] [5] ，即：若有一个任务到达，人工地派遣一辆有空闲时间的车辆临时出发，对飞机进行保障任务，完成此任务后回到指定的停车地点等待下一次指派命令的到达。这种低效率的调度方式，使得一个特种车辆每次只能对一个航班进行服务，会导致车辆任务分配不均衡、路线规划不合理，特种车辆的任务容易出现差错，航班地面保障服务时间的增加，进一步致使航班延误率增高。因此，本文对机场特种车辆调度的研究状况进行归类和总结，在现有的研究成果中提出尚存在的问题和对今后研究方向的展望。

2. 车辆调度问题

2.1. 车辆路径问题

车辆路径问题(Vehicle Routing Problem, VRP)：现有不同物资需求量的顾客若干，顾客数量一定，派遣车辆从车场出发为每个顾客配送物资，管理者在满足一定的约束条件下合理地组织车辆的行程，使车辆行驶路径的总里程和成本达到最低。车辆路径问题早在1956年被Ramser和Dantzig两位学者首次提出。车辆路径问题示意图，如图2所示。车辆路径问题是传统的旅行商问题(Traveling Salesman Problem, TSP)的特例。车辆调度问题又分为两大类，第一类是VRP (Vehicle Routing Problem)问题，第二类是VSP (Vehicle Scheduling Problem)问题。两者混合的问题组成了带时间窗约束的车辆调度问题，统称为VRPTW (Vehicle Scheduling Problem with Time Windows)问题 [6] 。

图2. 车辆路径示意图

2.2. 机场特种车辆的调度问题

机场特种车辆的调度问题的本质是车辆路径问题 [7] 。航班到港和离港是动态的、具有时间约束限制的，并且各种特种车辆之间的工作协调配合也有一定的时间限制，因此特种车辆调度问题又是一种动态的带时间窗的车辆路径问题(dynamic vehicle routing problem with time window, DVRPTW)。

机场特种车辆调度问题可以描述为：飞机在某机场过站期间，为保证飞行安全，会接受一系列的地面服务，进行地面服务的车辆主要有行路运输车、加油车、配餐车、摆渡车等等。机场内同一时间会有不同的航班停靠在不同的机位等待地面服务的特种车辆进行相应的工作。如何使各种特种车辆在一定的服务时间内，对相应的航班准确高效地完成各自的服务，并降低航班因地面服务的拖延造成航班的延误。

3. 国内外研究现状

目前针对机场特种车辆调度优化的研究主要集中在两方面。一方面是基于特种车辆服务特点的优化算法的研究，主要有遗传算法、最邻近算法、蚁群算法、粒子群算法、动态搜索算法、Epsilon约束算法、启发式算法、整数规划和基于时间窗的算法等。另一方面，是对机场特种车辆的调度问题进行仿真研究 [8] 和优化系统的设计。在设计派工系统时多采用计算机软件技术、嵌入式控制系统技术、自动化技术、无线数字通讯技术 [9] 、地理信息系统和GPS定位技术等，实现系统的自动派工 [10] [11] [12] [13] 。

3.1. 机场特种车辆调度的优化算法总结

在国内，主要运用遗传算法的研究有：王俊义(2018) [14] 主要针对机场除冰车的调度问题，采用特种车辆综合调度和先到先服务调度两种策略进行研究，分析了特种车辆综合调度以及先到先服务调度两种调度模型。丁建立等(2016) [15] 引入了时间窗，对没有服从时间窗约束的航班进行一定的惩罚，利用局部优化策略进行再次优化建立模型。郑洁，高剑明(2008) [16] 对提高机场的飞行器保障服务设施的使用效率，利用妥协算法和遗传算法，建立多目标规划模型，缩短保障设备流转时间。冯霞等(2016) [17] 基于多目标规划的遗传算法，将最少需要派遣的服务车辆数和服务开始最早时间为目标，构建远机位上客和加油服务的协同调度模型。姚韵等(2007) [18] 提出了基于生产作业排序特点，结合不同生产设备的工作能力的特点，设计了设备能力差分算法，将多目标优化问题转化为作业排序优化问题。

运用最邻近算法的研究有：殷龙、衡红军(2016) [19] 构建带时间窗的特种车辆调度模型，利用最邻近算法求解，得出燃油加注的任务分配结果，以降低服务成本。晏晓东(2017) [20] 针对特种车辆的调度问题，先进行静态调度：选择了适合该问题的节约值算法和改进型最邻近算法进行路径优化，解决了任务分配不均的问题，设计了基于时序衔接的任务分配算法。在静态调度的基础上进行动态调度，设计了基于规划时间窗的动态调度方法。衡红军(2017) [21] 针对行李运输车辆调度问题，用最邻近算法构建进出港航班组成的车辆行驶路程最短的子路径集合，然后根据时间衔接关系对其进行优化，实现所派车辆数最少和车辆任务均衡的目标。

运用蚁群算法的研究有：王一飞(2014) [22] 对加油车的车辆调度问题数学模型进行了描述，基于蚁群算法对给出的模型进行了改进，对算法容易出现的搜索停滞现象进行了改进，使算法能够收敛于最优解。吴建波(2015) [23] 在研究飞机过站地面服务的时间约束、空间约束和相应的需求后，基于多Agent调度技术对地面服务特种车辆调度的算法进行研究。

运用粒子群算法的研究有：王世宏等(2013) [24] 在考虑设备设施能力约束的情况下，建立了引入量子行为的以最小化加油车辆最大完工时间为目标的算法，弥补之前算法容易陷入局部最优和早熟收敛的不足。高原等人(2008) [25] 基于改进的粒子群算法，针对机场行李车、配餐车和加油车的调度，提出了多航班多服务的调度模型。

运用动态搜索算法的研究有：王博涛(2006) [26] 在对机坪中特种车辆调度问题约束条件构成要素进行分析，并利用分解策略和多目标权衡策略，将机坪中调度问题分为机位指派和机坪特种车辆调度问题。以开始服务时间为主要变量，以飞机接受服务时间最短为目标，在满足服务顺序、服务时间和服务设施的能力三个约束条件下，设计了动态搜索算法和保障动态的服务排序的启发式算法。衡红军等(2017) [27] 对加油车的调度构建具体时刻的调度模型，设计了基于规划时间窗的特种车辆动态调度算法，将动态问题转化为静态问题，减少车辆的总行驶路程和所需服务车辆数，使每辆车任务量均衡。

还有许多研究运用其他启发式算法、Epsilon约束算法。樊琳琳(2009) [28] 考虑地勤服务车辆具有时间窗约束和资源装载和卸载需求量，设计了带时间窗的车辆路径问题的两阶段启发式算法。何丹妮(2018) [29] 运用启发式算法，根据摆渡车的服务流程、资源配置和航班过站的时间窗约束，建立使派遣车辆最少、车辆行驶总路程最短以及车辆任务分配均衡为目标的优化模型。王璐等(2018) [30] 针对机场罐式加油车在飞机过站时的调度问题进行了研究，以罐式加油车最小化完成服务时间和航班最少等待加油时间为双目标，建立起双目标规划模型，并求解问题的Pareto前沿，开发Epsilon约束算法。

在国外，运用遗传算法的研究有：Angus Cheung等(2005) [31] 对水车、清洁车和牵引车等进行研究，以车辆总工作时间为目标，对不同种类的车辆设计单独调度的模型，并用遗传算法进行求解。Kenneth和Steffen (2009) [32] 在机坪调度作业问题上，为较少航班延误和油耗，利用混合整数规划，将启发式遗传算法加入现已有模型的分支定界法中进行模型的优化。

运用蚁群算法的研究有：Yuquan Du (2008) [33] 用蚁群算法求解带时间窗的、短时间车辆路径和车辆循环利用的机场地面保障服务问题，以车辆数最少和服务时间最短为目标进行模型设计。

运用其他启发式算法的研究有：Jia Yan Du等(2014) [34] 对拖车进行研究，以使运营成本最小化为优化目标，建立MIP模型，并使用列代启发式算法进行求解。Andreatta (2014) [35] 建立了快速启发式算法求解车辆调度和人员分配问题。

运用整数规划及其他算法的研究有：Kuhn (2009) [32] 研究了机场地面保障服务车辆进行，为减少航班延误和运行成本而提出简单的整数规划模型。Xing Z等(2012) [36] 在博弈论的基础上对机场除冰车进行了研究。Norin A等(2012) [37] 针对除冰车，以航班延误时间和车辆行驶距离最小为目标进行优化。Wu和Caves (2002) [38] 将飞机过站的工作分为行李工作和旅客工作两类，利用马尔科夫随机过程对二者进行优化。

3.2. 机场特种车辆调度的仿真研究及优化系统设计

在国内，对特种车辆的调度模型进行仿真的研究有：杨文东等(2013) [39] 提出了多目标规划摆渡车调度仿真模型，实现了信息无线传输、人机交互和IC卡控制。黄鹂诗(2013) [40] 提出基于SIMIO的，以合理分配设备任务量和减少航班延误为目标的车辆调度优化模型，对摆渡车和加油车进行仿真，以优化资源。陶婧婧(2011) [41] 运用离散时间仿真方法，对远机位的摆渡车调度问题进行研究，并以软件SIMIO为平台进行仿真，减少飞机地面保障服务调度不当产生的航班延误。汪新林(2006) [42] 通过单顾客流输入建立仿真模型，提出了事件调度法和活动扫描法两种仿真策略。王世宏等(2012) [43] 借助GPSSW仿真语言对单队列多机种、服务台可休假、多服务台的加油车运行模型进行研究，得到合理的服务台数量分配结果，以减少飞机的延误。顾毓等(2008) [44] 从排队论的角度，借助数字仿真，基于事件调度策略，建立多队列多服务台的模型。周蔷(2012) [45] 针对不同类型除冰坪对飞机型号的约束和除冰能力的限制，用MATLAB中的层次分析法仿真出不同天气下飞机延误时间图。施毅等(2006) [46] 将战斗机结合排队论进行研究，基于事件调度方法对战斗机加油过程建立了系统仿真模型。

对机场特种车辆进行优化调度系统设计的研究有：唐小卫(2014) [47] 以Monte Carlo仿真方法，通过仿真平台建立了设备在流动过程中的仿真系统。宋颖颖(2013) [48] 针对机服务秩序、时间窗、资源限制等特点，设计了两阶段启发式算法，以减少航班延误为目标，在Super Map Objects控件的结合下完成了Visual Studio.NET平台的事实监控与智能调度的系统开发。刘晓琳(2010) [49] 运用遗传算法，采用轮赌选择法对特种车辆的调度进行求解，基于GIS、GPS、GPRS技术设计机场地面服务特种车辆指挥调度系统，实现指挥中心和特种车辆之间的信息交互。宋芳等人(2004) [50] 在分析现有机场运行特种车辆调度模式的基础上，提出了基于Multi-Agent调度系统，分析了系统中相互独立的Agent之间的相互协作。潘一桐(2018) [51] 应用GPS、GIS、ZigBee、通讯和智能控制等技术，为机场基于GIS车辆实时监控系统服务，进行机场场内的综合调度。

在国外，大多数研究集中在对机场特种车辆调度系统的设计：Wu C L和Robert E C [52] 模拟了随机事件中的干扰因素，采用Monte Carlo法，研究随机事件对航班接受地面服务正点率造成的影响，运用马尔科夫模型进行仿真，结果显示飞机过站接受地面服务的可延误时间和机坪地面服务设施水平对航班正点率造成较大影响。Braaksma和Shortreed (1987) [53] 利用关键路线，为多伦多机场设计了繁忙时段机坪保障服务调度模型，能确定特种车辆的关键路线和服务结束时间。Robert E. Caves和Cheng Lung Wu (2004) [32] 考虑了航班过站时间的随机和服务过程的不确定因素，利用Markovian仿真模型模拟航班过站接受服务时的不确定因素，运用Monte Carlo仿真技术进行随机模拟，研究出飞机过站的正点率和航班接受地面服务时间的关系。Manivannan和Zeimer (1996) [54] 利用Automod II仿真软件建立了有关枢纽机场或有中转服务的离散模型。Sanya Adeleye和Christopher Chung (2006) [55] 利用计算机仿真技术模拟了单个飞机在航班过站过程中接受地面保障服务时的各种干扰。

从前人对机场地面保障服务车辆的调度仿真中，多采用SIMIO软件来进行仿真，是基于其可视化仿真特点，采用实时3D技术，使模型逻辑能和实时3D对象紧密联系，可运运用于大型交通枢纽的仿真工作。对机场特种车辆的系统设计中，多采用Monte Carlo仿真法来模拟航班过站的随机性，从而更大限度地契合航班过站的特点。

4. 当前存在的问题及建议

1) 目前大多学者都是对单一服务种类特种车辆的调度问题进行研究，例如对机场加油车的调度问题进行的研究，只考虑了加油车路径优化使其行驶的总路程数最少、任务分配均衡、使飞行器接受服务的时间减少，以达到降低航班延误率目的。很少有学者将多种机场内部的特种车辆进行综合考虑，建立综合调度模型，例如，将配餐车、清洁车、加油车、行李运输车等车辆进行综合考虑，建立一个多种类特种车辆综合调度模型。

2) 前人的研究中多对同一服务种类单车型的特种车辆调度进行研究，少有考虑同一服务种类多车型特种车辆的综合调度模型。这需要将相同服务种类不同车型的服务能力进行考虑，构建车辆调度优化模型。大多数文章考虑接受服务的飞机机型是相同的，少有考虑不同机型对服务需求的不同。但实际情况是不同的机型对特种车辆的服务能力有所差别。以机场加油车为例，不同的飞机每次在接受地面加油服务时所需的燃油量是不同的，需要考虑机型匹配和限制等因素。

3) 机场特种车辆的调度问题与典型的车辆路径问题不同之处在于，机场航班计划是动态变化，变数较大，存在一定的随机性，某些机场场内道路的通行需要经过机场塔台的批准，特种车辆作业时间有限，调度难度较大。

针对以上问题，为进一步解决的方法，可以以各个机场对特种车辆综合调度的需求为导向，对机场内部各种特种车辆的调度问题进行建模和求解，需要在建模时，将不同机型对不同地面保障服务车辆的服务能力要求纳入约束范围，并加入时间窗约束，以适应机场航班计划变动较大的特点。在一段时间内频繁出现航班延误，应该动态调整特种车辆调度方案，及时对模型进行修改，以更好地适应实际的运行情况。

5. 总结和展望

目前针对机场特种车辆的调度问题的研究，将特种车辆的调度问题转化为带有时间窗约束的动态调度问题，多以派遣特种车辆数最少、特种车辆行驶总路程最短以及完成服务所需时间最短为目标。研究中多利用启发式算法设计的多种调度优化模型并进行仿真，已经取得了诸多成果。并借助计算机软件技术、自动化、无线数字通讯技术、嵌入式控制系统技术、GPS定位技术和地理信息系统等，对机场特种车辆调度系统进行设计。此外，还需进一步对机场中不同种类服务车辆和不同机型航班服务条件之间的限制加以协调配合，进一步降低航班因接受地面服务时特种车辆之间、航班和特种车辆之间因协调配合不当而引起的延误。

致 谢

感谢崔艳雨老师在本文写作过程中的悉心指导，感谢王一飞校友在其论文中提供的飞机民航飞机地面保障示意图，有你们的帮助，本人才能顺利完成此篇论文的撰写。

文章引用

张朝倩,崔艳雨. 机场特种车辆优化调度问题研究现状及展望
Current Status and Prospects in Researches of Optimization of Special Vehicles in Air-ports[J]. 计算机科学与应用, 2019, 09(05): 1012-1019. https://doi.org/10.12677/CSA.2019.95114

参考文献