基于物联网的多目标机场加油车调度模型和算法

Multi-Objective Airport Refueling Vehicle Scheduling Model and Algorithm Based on Internet of Things

摘要: 基于物联网动态跟踪加油车、航空器和停机位的状态，据此构建一类多目标机场加油车调度的数学模型，考虑航空器的加油时间窗等现实因素，将航空器的加油任务分配给不同机场加油车，追求加油车行驶成本、航班延误成本最小化。根据问题特征，设计求解该问题的NSGA-II，找到其Pareto解。最后，以某机场加油车调度为例，生成最佳调度方案，分析模型的灵敏度，从而证明莫和算法的优越性。

Abstract: By using the internet of things to dynamically track the status of refueling vehicles, aircrafts and gates, a multi-objective linear programming model for airport refueling vehicle scheduling problems is constructed. By considering realistic factors such as the refueling time window of the aircraft, the model aims to assign the refueling tasks of the aircraft to different airport refueling trucks, so as to minimize the driving cost and flight delay cost of the refueling trucks. According to the characteristics of the problem, NSGA-II is designed to solve the problem, and its Pareto solution is found. Finally, taking an airport refueling truck scheduling as an example, the optimal scheduling scheme is generated, the sensitivity of the model is analyzed, and the performance difference of the improved algorithm before and after solving the problem is compared, thus proving the superiority of the model and algorithm.

1. 引言

机场加油车调度问题是机场场面运行核心保障任务之一，若加油车调度方案不合理，可能引起大面积航班延误。利用物联网设备，如传感器和GPS定位系统，实现对航空器、加油车和机位的实时状态监控，基于收集到的数据进行加油车的优化调度，不仅能够提高机场运营效率，还能增强地面服务的可靠性和安全性，最终提升整体的航空服务水平。因此，开展基于物联网的机场加油车智能调度是发展趋势之一。

诸多学者对机场加油车智能调度理论和方法进行深入研究，主要涉及解决方案[1]-[3]和调度模型算法[4]-[15]两方面。在解决方案方面，王可聪[1]从车辆的智能调度管理出发，对调度关键技术、平台框架进行分析与拓展；焦星云等[2]将特种车辆与航班信息有机融合，为机场特征车辆的指挥调度提供了一种有效的解决方案；潘一桐[3]论述机场加油车调度的整体系统框架。在调度模型算法方面，张晓楠等[4]建立以总旅行时间最小为目标的机场加油车调度优化模型，并设计蚁群算法求解该问题；杨珏[5]和冯明端等[6]利用基于不同启发式算法的遗传算法对加油车调度模型进行求解；张宇驰等[7]对机场车辆和航班资源与机坪平面布局进行数学建模，提升了目标机场运行效率；唐非等[8]提出了解决加油车调度模型一个高效启发式算法；张凤等[9]考虑航班服务水平函数，利用C-W节约算法求解路径最短与服务最优的加油车调度问题；衡红军等[10] [11]和丁建立等[12]探讨了考虑需求变化的静态和动态问题，考虑航空器过站地面保障服务的时间约束、空间约束等；姜雨等[13]探讨了机位指派、滑行路径和机坪特种车辆调度协同问题；Yuquan Du等[14]和Jia Yandu等[15]构建以车辆任务均衡为目标的数学规划模型。

由上可知，现有研究主要不足有二：1) 现有研究尚未系统研究基于物联网的机场加油车调度框架；2) 机场加油车调度忽略了车辆调度成本和航班延误之间耦合关系对调度方案的影响。综上所述，本文基于物联网动态跟踪加油车、航空器和停机位的状态，据此构建一类多目标机场加油车调度的数学模型，考虑航空器的加油时间窗等现实因素，将航空器的加油任务分配给不同机场加油车，追求加油车行驶成本、航班延误成本最小化。根据问题特征，设计求解该问题的NSGA-Ⅱ，找到其Pareto解。最后，以某机场加油车调度为例，生成最佳调度方案，分析模型的灵敏度，从而验证模型和算法的有效性。

2. 基于物联网的多目标机场加油车调度模型

2.1. 机场加油车调度物联网构架

为了提升机场加油车的调度效率、安全和绿色水平，基于物联网动态跟踪加油车、航空器和停机位的状态，其物联网构架如图1所示，主要包括：

感知层：利用GPS和传感器，收集加油车、航空器和停机位的各种信息，包括位置、速度、油量等。

网络层：利用4G/5G，负责将感知层收集到的信息传输到处理层。

处理层：主要负责对接收到的信息进行处理和分析，为加油车调度模型提供输入数据。

应用层：负责构建加油车调度模型和算法库，根据调度目标和约束条件，将数据、知识、模型和算法组装，生成面向实际场景的模型，调用求解器，生成调度方案，并可视化评估其优劣。

用户层：主要负责与用户进行人机交互，以便于用户进行决策。

Figure 1. Construction of IOT framework for refueling vehicles

图1. 加油车物联网框架构建

2.2. 数学模型

在某段时间内，多个航空器停靠在不同机坪的机位需要加油，必须在推出时刻前完成加油。将航空器的加油任务分配给不同车辆，一辆加油车从油库加满油之后，依次访问多个航空器的位置，在进行加油前准备、检查等常规操作后，完成当前航空器的加油任务继续执行下一个航空器的加油任务。根据问题特征，建立加油车调度问题的多目标混合整数数学规划模型，兼顾车辆调度成本和航班延误之间利益均衡目标。不失一般性，本文研究的前提假设条件包括：1) 不考虑航空器的加油车任务由不同车辆完成；2) 忽略车辆加油过程中的不确定对其影响。

根据上述问题描述，其数学模型如下所示。

$\min Z_1={\displaystyle {\sum }_{\forall r\in R}{\displaystyle {\sum }_{\forall i\in F}{\displaystyle {\sum }_{\forall i\in F}{x}_i^r\left[l{t}_i^r-l{T}_i\right]}}}$ (1)

$\min Z_2={\displaystyle {\sum }_{\forall r\in R}{\displaystyle {\sum }_{\forall i,j\in F}{z}_{ij}^r{t}_{ij}}}$ (2)

约束条件

${\displaystyle {\sum }_{\forall r\in R}{x}_i^r}=1,\forall i\in F$ (3)

${\displaystyle {\sum }_{\forall j\in F\cup \left\{0\right\}}{z}_{ij}^r}={\displaystyle {\sum }_{\forall j\in F\cup \left\{0\right\}}{z}_{ji}^r}=x_i^r,\forall i\in F,\forall r\in R$ (4)

${\displaystyle {\sum }_{\forall i\in F}{x}_i^r\cdot q_i}\le Q_r,\forall i\in F,\forall r\in R$ (5)

$l{t}_i^r+t_{ij}+\left(1-z_{ij}^r\right)\cdot M=a{t}_j^r,\forall i,j\in F,\forall r\in R$ (6)

$a{t}_i^r+T_p=w{t}_i^r,\forall i\in F,\forall r\in R$ (7)

$w{t}_i^r+q_i/speed=l{t}_i^r,\forall i\in F,\forall r\in R$ (8)

$l{t}_i^r\le l{T}_i,\forall i\in F,\forall r\in R$ (9)

其中：$z_{ji}^r$ 表示车辆r是否执行航空器i和j的加油任务；$x_i^r$ 表示车辆r是否执行航空器的加油任务；$q_i$ 表示航空器i的加油量；$Q_r$ 表示车辆r的加油量；$a{t}_i^r$ 、$w{t}_i^r$ 和$l{t}_i^r$ 表示表示车辆r执行航空器i的到达、开始加油和离开时间；$l{T}_i$ 表示航空器i的推出时刻。

公式(1)和(2)是目标函数，其中：公式(1)表示全部航班延误时间最小化；公式(2)车辆行驶时间最小化。公式(3)和(9)是约束条件，其中：公式(3)表示将每个航空器的加油任务分配给一辆车；公式(4)表示将加油辆车的网络流约束条件；公式(5)表示将加油辆车的油量满足全部航空器的加油需求；公式(6)表示一辆车完成上一个航空器的加油任务后来到下一个航空器的加油任务；公式(7)和(8)表示加油车的加油准备和加油时间；公式(9)表示加油车在一个航空器的加油结束任务不早于其推出时间。

3. NSGA-Ⅱ算法设计

鉴于NSGA-Ⅱ是求解多目标优化问题的最流行算法之一，被广泛应用在交通调度、路径优化等领域。本文采用NSGA-II求解多目标机场加油车调度问题，根据问题特征，定义了染色体编码，并设计了产生初始种群的启发式算法，具体算法过程如下所示。

3.1. 染色体编码

采用整数编码方式，利用一维向量U表示问题的每一个解，元素$u_i$ 取值为1~R之间的自然数，表示航空器i的加油任务由车辆$u_i$ 完成，其顺序由任务时间决定。例如：染色体$U=\left(1,2,3,1,2,3,1,2,3\right)$ 表示3辆车完成7个加油任务，其中：任务1、4、7由车辆1完成，任务2、5、8由车辆2完成，车辆3、6、9由车辆3完成。

3.2. 产生初始种群的启发式算法

该问题及其复杂，随机生成的个体很难是可行解。因此设计启发式算法生成可行个体，组成初始种群，具体步骤如下：

步骤1：根据全部航空器$\forall i\in F$ 的加油任务时间$t_i^p$ 进行排序，令结果为$F^{‴}={\left\{{F^{″}}_1,{F^{″}}_2,\cdots ,{F^{″}}_{\left|F\right|}\right\}}^{\prime }$ 。

步骤2：初始化可以完成所有航空器$F^{″}$ 加油任务的车辆集合R，令$i=1$ 。

步骤3：查找可以完成${F^{″}}_i$ 的车辆集合$vR$ ，若$vR\ne \varnothing$ ，从中随机选择车辆$\forall r\in vR$ 完成${F^{″}}_i$ ，转至步骤4；否则，转至步骤2。

步骤3.1：初始化$vR=\varnothing$ 。

步骤3.2：查找匹配航空器加油任务的任意车辆$\forall r\in R$ ，当前最后一个航空器$lF\left(r\right)$ 。

步骤3.3：检查$\forall r\in R$ 是否能在完成$lF\left(r\right)$ 后继续执行航空器${F^{″}}_i$ 的运行，若满足以下条件之一：①$lF\left(r\right)=\varnothing$ ，② $t_{lF\left(r\right)}^a+t_{lF\left(r\right)}^h+\max \left(T_{lF\left(r\right){F^{″}}_i}^1,T_{lF\left(r\right){F^{″}}_i}^2\right)\le t_{{F^{″}}_i}^a$ ，则$vR=vR\cup \left\{r\right\}$ 。

步骤4：$i=i+1$ ，若$i\le \left|F\right|$ ，转至步骤3；否则，算法终止，输出结果。

3.3. 非劣排序和拥挤距离排序

3.3.1. 非劣排序

步骤1：设置任意解$\exists x\in P$ 所支配的个体集合$S_x=\varnothing$ 和数量$n_x=0$ 。若存在某解$\forall q\in P$ 并满足$q\succ x$ ，则$S_x=S_x\cup \left\{q\right\}$ ；否则，$n_x=n_x+1$ 。

步骤2：令$Q=\varnothing$ ，$x_{rank}=1$ 和$i=1$ ，$F_1=\left\{x|n_x=0,\forall x\in P\right\}$ 。

步骤3：对$\forall x\in F_i$ 的$\forall q\in S_x$ ，$n_q=n_q-1$ 。当$n_q=0$ ，设置$q_{rank}=i+1$ 且$Q=Q\cup \left\{q\right\}$ 。

步骤4：若$Q\ne \varnothing$ ，$i=i+1$ 且$F_i=Q$ ，转步骤3；否则，算法停止。

3.3.2. 拥挤距离

根据全部个体的目标值进行排序，计算相邻个体$x_{i-1}$ 和$x_i$ 的距离${\epsilon }_m\left(x_i\right)$ ，据此计算个体$x_i$ 的拥挤距离$Distance\left(x_i\right)={\displaystyle {\sum }_{m=1}^M{\epsilon }_m\left(x_i\right)}$ 。

3.3.3. 选择算子

计算任意两个个体的非支配排序和拥挤距离，根据下述规则选择最佳个体，即：① $i\succ {}_{n}j$ 当且仅当$i_{rank}<j_{rank}$ ，② $i_{rank}=j_{rank}$ 且$Distance\left(x_i\right)>Distance\left(x_j\right)$ 。

3.4. 算法流程

NSGA-II的具体算法步骤如下所示。

步骤1：设置染色体数N、最大迭代次数$N_{iter}$ 以及交叉和变异系数。

步骤2：令$t=0$ ，随机地生成一个初始种群$P_0$ 。

步骤3：对第t代的种群$R_t$ 进行选择、变异和交叉操作，产生子代种群$Q_t$ ，并对它们进行合并，即$R_t=P_t\cup Q_t$ 。

步骤4：计算$R_t$ 的2N个体的非支配序和拥挤距离，依据等级的高低逐一选取个体，直到个体数量达到N就形成了新的种群$P_{t+1}$ 。

步骤5：$t=t+1$ 。如果$t\ge N_{iter}$ ，输出结果，算法终止；否则，返回步骤3。

4. 算例分析

某机场在6:30~8:00有18个航空器需要加油任务，基于物联网技术可以动态获取这些航空器的加油时间窗、机位位置和加油量等信息，如表1所示。安排多辆加油车从油库出发，完成全部航空器的加油任务。

采用Matlab自带的NSGA-Ⅱ工具箱实现求解该模型的程序，算法参数为：迭代500，染色体数500，交叉率0.8，共享半径取0.05，变异率0.05。根据调度目标和约束，求解该问题的Pareto解寻优曲线如图2所示，总共四个Pareto解。以Pareto解(176和39)为例，计算的最优方案如表2所示，四辆加油车完成17个航空器的加油任务的目标函数1和2分别为176和39。以车辆1为航空器14加油为例，车辆达到其机位的时间为6:37，开始加油时间为6:45，离开时间为6:57，满足全部任务时间窗。此外，由图2可知，随着目标函数1的逐步增加，目标函数2将逐步地减少，这是因为：车辆不足导致行驶里程减少，从而引起航班大面积延误。

此外，分析不同加油车对调度方案的影响，结果如图3所示，从中可知：随着车辆数的增加，目标函数1和2均减少，这是因为更多的车辆数缓解了航空器加油任务的供需紧张关系，从而减少航班大面积延误。然而，车辆数的增加引起调度成本也被增加，需要平衡调度成本与航班延误之间最佳耦合关系以确定最佳加油车数量。

Table 1. Basic information of aircraft

表1. 航空器的基本信息

航空器编号	推出时刻	停机坪	机位	加油量
1	7:45	1	11	2
2	7:40	12	12	7
3	7:25	11	8	14
4	6:45	1	8	15
5	7:10	1	3	25
6	7:50	1	4	26
7	7:55	1	12	27
8	7:40	1	6	43
9	7:50	1	15	47
10	7:25	13	1	50
11	8:00	1	7	55
12	6:50	12	10	60
13	7:45	12	9	61
14	7:40	13	7	66
15	6:45	1	10	72
16	6:45	12	8	73
17	6:55	12	11	74
18	6:50	1	16	75

Figure 2. Change relationship between double objectives of Pareto solution

图2. Pareto解的双目标之间变化关系

Table 2. Optimal refueling truck scheduling scheme

表2. 最优加油车调度方案

加油车	任务序列	达到时间	开始工作时间	离开时间
1	10-14	6:17~6:37	6:25~6:45	6:37~6:57
2	4-18-17-2-13	5:37~5:57~6:34~6:54~7:14	5:45~6:05~6:42~7:02~7:22	5:57~6:17~6:54~7:14~7:32
3	16-12-3-1-6-11	5:37~5:57~6:21~6:59~7:19~7:39	5:45~6:05~6:29~7:07~7:27~7:47	5:57~6:17~6:41~7:19~6:39~6:59
4	15-5-8-9-7	5:37~5:57~6:42~7:02~7:22	5:45~6:30~6:50~7:10~7:30	5:57~6:42~7:02~7:22~7:24

Figure 3. Influence of different vehicle numbers on scheduling schemes

图3. 不同车辆数对调度方案的影响

5. 结论

本文研究一类基于物联网的多目标机场加油车调度框架，包括模型和算法，考虑航空器的加油时间窗等现实因素，将航空器的加油任务分配给不同机场加油车，寻求加油车行驶成本、航班延误成本之间最佳资源匹配关系。研究表明：

1) 随着目标函数1的逐步增加，目标函数2将逐步地减少，这是因为车辆不足导致行驶里程减少，从而引起航班大面积延误。

2) 随着车辆数的增加，航空器加油任务的供需紧张关系被慢慢缓解，故目标函数1和2也逐渐地被减少。

然而，本文模型没有考虑航空器的加油任务提前等待和加油准备等现实情况，也未涉及加油车在不同机坪机位的运行规则。此外，该模型没考虑加油任务完成的不确定因素对加油车调度的影响。因此，如何考虑实际机场交通网络布局和航空器的加油任务准备的不确定加油车调度问题是我们拟开展的研究工作。