基于智能网联的机场摆渡车车辆路径优化模型和算法

Airport Shuttle Vehicle Routing Optimization Model and Algorithm Based on Internet of Things

摘要: 基于智能网联动态跟踪航班的旅客接运任务、摆渡车的状态，据此构建一类机场摆渡车车辆路径优化的数学模型，考虑不同航班的旅客接运任务时间窗等现实因素，将若干旅客接运任务分配给不同类型机场加油车，确定车辆执行这些旅客接运任务的顺序，追求机场摆渡车调度成本最小化。根据问题特征，设计求解该问题的遗传算法，定义编码方案、产生初始种群的启发式算法、适应度函数、交叉和变异操作。最后，以某机场摆渡车调度为例，生成最佳车辆路径方案，分析不同车辆数对结果的影响，从而证明模型和算法的优越性。

Abstract: By using the internet of things to dynamically track the status of the passenger pick-up task and the shuttle car, a multi-objective linear programming model for airport shuttle vehicles problems is constructed. By considering the practical factors such as the time window of passenger pick-up task of different flights, the model aims to assign several passenger pick-up tasks to different types of airport refueling vehicles and determine the order of the vehicles to perform these passenger pick-up tasks, and, so as to minimize the scheduling cost of airport shuttle vehicles. According to the characteristics of the problem, the genetic algorithm is designed to solve the problem, where the coding scheme is defined, the heuristic algorithm for generating the initial population, the fitness function, crossover and mutation operations are defined. Finally, taking an airport shuttle bus scheduling as an example, the optimal vehicle routing scheme is generated, and the influence of different vehicle numbers on the result is analyzed, so as to prove the superiority of model and algorithm.

1. 引言

机场摆渡车是机场场面运行的保障资源之一。目前，摆渡车调度仍以人工调度方式为主，难以在日渐复杂的民航机场运行场景中满足管理合理化、运行高效化、操作精细化等要求，严重影响了机场管理的运行效率。基于智能网联的机场摆渡车调度是智慧机场的未来发展趋势，利用先进的信息通信技术、物联网技术实现实时监控摆渡车的运行状况，为每辆摆渡车制定最优的行驶路线，减少空驶和拥堵现象，提高车辆的运行效率[1]-[3]。

目前，国内外大量学者研究机场摆渡车调度问题，主要成果归纳如下：梁程[1]从摆渡车的现状和特点出发，对它的未来发展进行分析与拓展；黄晓玲[2]用运筹学模型对机场人力资源进行了预测和探索；祁欣月等[3]研究了地勤车辆多阶段优化调度方法，来缩短航班延误时间，提升机场场面运行效率；高伟等[4]和冯霞等[5]采用带精英策略的非支配排序的遗传算法，并以航班运行数据进行仿真，以解决特种车辆调度问题；李乐等[6]对机场特种车辆的调度管理进行了总结；冯明端等[7]面向机场地面特种设备车辆，构建了带有容量限制和时间窗的联合调度模型；张宇驰等[8]对机场车辆和航班资源与机坪平面布局进行数学建模，提升了目标机场运行效率；唐军[9]探讨了机场特种车辆的发展现状并提出了相应的对策；张文义等[10]采用了自适应大领域搜索求解算法，用以解决多车型和双时间窗并需求可拆分的车辆路径问题；衡红军等[11]和丁建立等[12]据航空器过站地面保障服务的时间约束、空间约束和相应的需求变化，对静态和动态问题进行优化；杨文东等[13]对机坪摆渡车的调度系统进行了仿真并探讨了摆渡车的实时调度问题；DAN等[14]研究了以最小化用车规模为目标的机场燃油和电动特种车辆混合调度问题，并提出了一种改进的自适应大邻域搜索算法来求解；HAN等[15]提出了一种两阶段优化方法来提升航班不确定下的摆渡车调度准点率；ZHAO等[16]引入虚拟航班，经过简化将问题转化为可有效求解的网络最大流问题。

由上可知，现有研究主要不足有二：1) 现有研究尚未系统研究基于智能网联的机场摆渡车调度框架[1]-[6]；2) 机场摆渡车调度忽略了调度时间窗、交通网络布局对调度方案的影响[11]-[15]。综上所述，本文基于智能网联动态跟踪机场摆渡车、航班的旅客接运任务状态，据此构建一类机场摆渡车调度的数学模型，考虑不同航班的旅客接运任务时间窗等现实因素，将旅客接运任务分配给不同摆渡车，确定机场摆渡车车辆路径，追求摆渡车行驶成本最小化。根据问题特征，设计求解该问题的遗传算法，定义编码方案、适应度函数、遗传操作。最后，以某机场摆渡车调度为例，生成最佳车辆路径方案，分析不同车辆数对结果的影响，从而证明模型和算法的优越性。

2. 基于智能网联的机场摆渡车调度模型

2.1. 机场摆渡车调度物联网构架

为了提升机场摆渡车调度的服务水平，搭建基于智能网联的机场摆渡车调度框架，其智能网联构架如图1所示。基于智能网联动态跟踪机场摆渡车、进离场航空器的状态，涉及车辆类型和位置、任务时间窗和数量。利用4G/5G技术将它们传输至调度中心，结合机场GIS基础数据库，获取数据如下：首先，日常统计报表数据；其次，模型和算法的输入数据。调度中心构建加油车智能调度专家系统，根据调度目标和约束条件，将数据、知识、模型和算法组装，生成面向实际场景的模型，调用求解器，生成机场摆渡车调度方案。用户通过人机交互完成相关操作，获取相关结果，并通过物联网将调度指令下达给摆渡车和旅客接运任务。

Figure 1. Intelligent network framework of airport shuttle vehicles

图1. 机场摆渡车智能网联框架

2.2. 机场摆渡车调度的数学模型

某机场在一段时间内多个航班的旅客接运任务，即：在规定时间窗将乘客从登机口运输至停机位。将多个航班的旅客接运任务分配给不同摆渡车，确定摆渡车依次访问这些任务的起讫点，确保乘客正常进离港任务需求。根据问题特征，建立机场摆渡车调度问题的混合整数数学规划模型，追求车辆调度成本最小化。不失一般性，本文研究的前提假设条件包括：1) 不考虑每个航班的旅客接运任务由不同摆渡车完成；2) 忽略乘客摆渡过程中的各种不确定对其影响。

根据上述问题描述，建立该问题的混合整数数学模型如下所示。

$\min Z={\displaystyle {\sum }_{\forall k\in R}{\displaystyle {\sum }_{\forall i,j\in F}{x}_{ij}^k{t}_{ij}}}$ (1)

约束条件

${\displaystyle {\sum }_{\forall k\in R}{y}_i^k}=1,\forall i\in F$ (2)

${\displaystyle {\sum }_{\forall j\in F\cup \left\{0\right\}}{x}_{ij}^k}={\displaystyle {\sum }_{\forall j\in F\cup \left\{0\right\}}{x}_{ji}^k}=y_i^k,\forall i\in F,\forall k\in R$ (3)

$y_i^k\cdot q_i\le Q_k,\forall i\in F,\forall k\in R$ (4)

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

$a{t}_i^k+r{T}_i=l{t}_i^k,\forall i\in F,\forall k\in R$ (6)

$a{t}_i^k\le p{T}_i-\Delta T,\forall i\in F,\forall k\in R$ (7)

其中：$x_{ij}^k$ 表示摆渡车k是否执行航班的旅客接运任务i和j的加油任务；$y_i^k$ 表示摆渡车k是否执行航班的旅客接运任务i的运输任务；$q_i$ 表示航班的旅客接运任务i的客流量；$Q_k$ 表示摆渡车k的载客量；$a{t}_i^k$ 和$l{t}_i^k$ 表示表示摆渡车k执行旅客接运任务i的到达和离开时间；$p{T}_i$ 表示航班的旅客接运任务i的推出时刻；$r{T}_i$ 表示航班的旅客接运任务i的运行时间；$\Delta T$ 表示提前准备时间。

公式(1)是目标函数，表示全部车辆空驶时间最小化。公式(2)~(7)是约束条件，其中：公式(2)表示将每个航班的旅客接运任务分配给一辆摆渡车；公式(3)表示每辆摆渡车的网络流约束条件；公式(4)表示每个航班的旅客接运任务客流量满足全部摆渡车的载客能量；公式(5)表示一辆摆渡车完成上一个航班的旅客接运任务后来到下一个旅客接运任务；公式(6)表示航班的旅客接运任务开始和结束时间；公式(7)表示摆渡车达到上一航班的旅客接运任务时必须其推出时刻前的一段时间内。

3. 算法设计

遗传算法(Genetic Algorithm, GA)最早是由美国的John Holland于20世纪70年代提出，是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法[17]-[20]。根据问题特征，采用遗传算法求解该问题，设计染色体编码、适应度函数、遗传操作等，具体如下：

3.1. 染色体设计

采用混合整数编码，采用一维向量$U=\left(u_1,u_2,\cdots ,u_F\right)$ 表示问题的每一个解，元素$u_i$ 取值为1-R之间的整数，表示任务是否被摆渡车$u_i$ 访问。显然地，任意U均满足公式(2)和(3)，若其满足公式(4)和(7)，则它是一个个体。

3.2. 适应度函数的设计

任意U可能不满足公式(4)和(7)，利用惩罚函数，将它们加入目标函数中，让这些不可行解的目标值非常大，从而评估个体的适应度函数大小。

$F=z+H\cdot {\displaystyle {\sum }_{\forall k\in R}{\displaystyle {\sum }_{\forall i\in F}\max \left(Q_k-y_i^k\cdot q_i,0\right)}}+H\cdot {\displaystyle {\sum }_{\forall k\in R}{\displaystyle {\sum }_{\forall i\in F}\max \left(\le p{T}_i-\Delta T-a{t}_i^k,0\right)}}$ (8)

本文直接利用上述目标函数作为染色体的适应度函数以评估它们的优劣。

3.3. 产生初始种群

随机生成一个个体，若其不是可行个体被舍弃，直至找到一定数量的可行个体组成初始种群。

3.4. 遗传操作

遗传算法涉及选择、交叉和变异三种遗传操作算子，其中：选择算子采用轮盘赌选择法和精英保留法从父代种群中筛选优秀个体组成子代种群；交叉算子交换和组合父代种群中部分个体的基因以形成新个体；变异算子随机扰动一些个体的部分基因以避免选择和交叉算子操作引起种群的同质性。

显然，该算法的交叉和变异算子不会破个体的可行解结构，从而保证种群的多样性。

3.5. 终止原则

当迭代至最大次数后，算法停止。

4. 算例分析

某机场在6:30~8:00有20个航班的旅客接运任务，基于物联网技术可以动态获取它们的推出时刻、起讫点等信息，如表1所示。安排多辆机场摆渡车从调度中心出发，完成全部航班的旅客接运任务。

Table 1. Basic information of aircraft

表1. 航空器的基本信息

航空器编号	推出时刻	出发地	目的地
1	6:00	1	6
2	6:10	2	7
3	6:23	1	8
4	6:29	2	8
5	6:10	3	9
6	6:15	4	10
7	6:21	5	6
8	6:37	3	6
9	6:15	4	7
10	6:47	5	8
11	6:10	6	1
12	6:25	6	3
13	6:25	7	4
14	6:35	8	5
15	6:31	9	2
16	6:25	10	3
17	6:40	10	6
18	6:43	7	8
19	6:21	8	4
20	6:52	9	1

采用Matlab2021B的遗传算法工具箱编程该模型的程序，算法参数为：迭代100，染色体数50，交叉率0.8，变异率0.0。如图2所示，需要不到1 s迭代22次找到最优机场摆渡车方案，算法的最优解和平均解逐步收敛在同一水平，从而证明了算法的有效性。最佳调度方案如表2所示，安排四辆加油车完成20个旅客接运任务，总共空驶38 min，分别计算出它们的路径、出发和到达时间。以摆渡车1为例，任务顺序分别为1-11-19，到达它们的时间为6:00-6:10-6:21，离开它们的时间为6:05-6:15-6:25，满足相关时间窗约束，从而调度方案是可行的。

Figure 2. Algorithm iteration curve of optimal solution

图2. 最佳解的算法迭代曲线

Table 2. Optimal ferry car scheduling scheme

表2. 最优摆渡车调度方案

摆渡车	任务序列	达到时间	离开时间
1	1-11-19	6:00-6:10-6:21	6:05-6:15-6:25
2	6-13-14-18-20	6:15-6:25-6:35-6:43-6:52	6:20-6:30-6:38-6:47-6:542
3	5-7-4-8-10-12	6:10-6:21-6:29-6:37-6:47-6:57	6:15-6:23-6:32-6:41-6:50-7:00
4	9-3-15-17	6:15-6:23-6:31-6:40	6:17-6:26-6:35-6:45
5	2-16	6:10-6:25	6:14-6:30

Figure 3. Influence of different vehicle numbers on scheduling schemes

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

此外，分析不同摆渡车数量对调度方案的影响，结果如图3所示，从中可知：随着车辆数的增加，车辆空驶时间逐步地被减少，这是因为更多的车辆数导致每辆车完成的任务数减少，从而车辆空驶时间也被减少。因此，需要平衡调度成本与航班延误之间关系，选择最合适的摆渡车辆数量，据此计算最佳调度方案。

5. 结论

本文提出一类基于智能网联的机场摆渡车调度框架，包括摆渡车路径优化模型及其求解智能算法，考虑摆渡车的容量约束、旅客接运任务时间窗等现实因素，将若干旅客接运任务与摆渡车型匹配，确定每辆摆渡车完成这些旅客接运任务的路径和时间窗，追求机场摆渡车调度成本最小化。研究表明：

1) 我们的模型算法在1秒内找到问题的最佳解，满足全部摆渡车和旅客接运任务之间时间窗约束，从而贴近实际应用。

2) 车辆空驶时间逐步地被减少，这是因为更多的车辆数导致每辆车完成的任务数减少引起的。

然而，本文模型假设每个旅客接运任务的客流量小于摆渡车载客能量，其仅被一辆车完成。在现实中，部分旅客接运任务的客流量大于摆渡车载客能量，需要被多辆车完成。因此，如何考虑旅客接运任务可拆分的机场摆渡车车辆路径优化问题是我们将来拟开展的研究内容。